# In how many ways can $1000000$ be expressed as a product of five distinct positive integers?

I'm trying to solve the following problem:

"In how many ways can the number $1000000$ be expressed as a product of five distinct positive integers?"

Here is my attempt:

Since $1000000 = 2^6 \cdot 5^6$, each of its divisors has the form $2^a \cdot 5^b$, and a decomposition of 1000000 into a product of five factors has the form $$1000000 = (2^{a_1} \cdot 5^{b_1})(2^{a_2} \cdot 5^{b_2})(2^{a_3} \cdot 5^{b_3})(2^{a_4} \cdot 5^{b_4})(2^{a_5} \cdot 5^{b_5})$$ where $a_i$ and $b_i$ are nonnegative integers which satisfy the conditions $$a_1 + a_2 + a_3 + a_4 + a_5 = 6, b_1 + b_2 + b_3 + b_4 + b_5 = 6$$ The total number of systems of $a_i$ which satisfy the first equation is $210$ and the same number is for $b_i$. Thus the total number of decompositions is $210 \cdot 210 = 44100$. However, in this enumeration, factorizations which differ only in the brder of the factors have been counted separately; that is, some factorizations are counted several times each.

To get the number of distinct unordered decompositions I must, at first, substract the number of ordered decompositions with at least two identical factors and, at second, divide resulting number by $5!$ to leave only unordered ones.

And I'm stuck at the step of counting the number of ordered decompositions with at least two identical factors. The number of decompositions with $k$ identical factors is $(\lfloor\dfrac{a}{k}\rfloor + 1)(\lfloor\dfrac{b}{k}\rfloor+1){5 \choose k}$, that is, the number of decompositions with two identical factors is $16 \cdot {5 \choose 2} = 160$, three identical factors - $9 \cdot {5 \choose 3} = 90$, four ones - $4 \cdot {5 \choose 4} = 20$ and five ones - $4 \cdot {5 \choose 5} = 4$. Thus the number of distinct decompositions must be equal $\dfrac{44100-160-90-20-4}{5!}$, but this number is not integral. I suppose that the numbers of decompositions with $k$ identical factors overlap and I misuse inclusion-exclusion principle. But I have no idea how I can count that overlapped decompositions.

• This is not the only error, but how many ways are there to express $1000000$ as a product of five identical factors, really? Commented Apr 25, 2015 at 15:21
• @Erick: must be equal 194 (counted by bruteforce using PARI/GP). This problem is a modification of the well-known problem "how many ways to write obe million as a product of three integers?". My teacher gave me this one as a training exercise for preparation to math olympiad. And he did not provide the answer) Commented Apr 25, 2015 at 19:54
• I was actually referring to the $4$ in your attempt ("five ones"). Note that there is at most one way to write any number as a product of five identical factors. This is a good indication that your formula $(\lfloor a/k \rfloor + 1) (\lfloor b/k\rfloor + 1) {5\choose k}$ is broken. Commented Apr 26, 2015 at 0:01
• @Erick: OK, all 5 factors are identical is a special case, it must be treated separately. But for other cases the formula is valid. Commented Apr 26, 2015 at 10:55
• Have you verified your formula for the case $k=2$? I suspect you need to think carefully about exactly how you are defining $k$. Which value (or values) of $k$ does the factorization $(8,8,25,25,25)$ fall into? Or $(1,10,10,100,100)$? Doesn't seem like your $5\choose k$ term can account for both of these, but there's more than one way to organize these partitions and I'm not sure which one you intend. Commented Apr 26, 2015 at 16:28

The number in question is the coefficient of $x^6 y^6 z^5$ in the product $$\prod_{0\le i,j\le 6}(1+x^i y^j z).$$ Here $z$ counts the number of factors (we want $5$); $x$ and $y$ tag the powers of $2$ and $5$ respectively; we want both of those to be $6$. Distinctness is ensured because, for each factor $2^i 5^j$, we either include it once (thereby multiplying by $x^i y^j z$) or we don't include it (and multiply by $1$).

Multiplying out the entire product is unwieldy, but you can compute it mod $(x^7,y^7)$, which eliminates a whole mess of terms you don't need. The coefficient of $x^6 y^6$ turns out to be $$5 z^7+64 z^6+194 z^5+235 z^4+123 z^3+24 z^2+z,$$ which enumerates the number of ways to write $1000000$ as a product of $k$ distinct factors, for all values of $k$. Taking $k=5$ we confirm Christian's answer of $194$.

• It might be worth explaining how this ensures distinctness; it's correct, but it took me a minute to see why. Still, this is definitely a straightforward way. Commented Apr 28, 2015 at 0:28
Commented Apr 28, 2015 at 1:41
• Is it possible to arrive at your displayed polynomial in $z$ without a computer? Commented Apr 29, 2015 at 19:28
• @ChristianBlatter Yes, but it's tedious. Make a $7\times7$ array to hold the coefficients of $x^i y^j$ (each is a polynomial in $z$), initialized with $1$ in the $(0,0)$ position and $0$'s elsewhere. For each binomial $(1+x^i y^j z)$, update each cell by looking backward $(i,j)$, multiplying the polynomial in that cell by $z$ and adding the result into the current cell. Repeat $49$ times (once for each binomial).
Commented Apr 30, 2015 at 1:33

Let $F(n)$ be the ways in which the number $10^n$ can be expressed as a product of five distinct positive integers. Using the same strategy as in this MSE link (the Polya Enumeration Theorem or PET), we get the following answer in terms of the cycle index $Z(P_5)$ of the set operator $\mathfrak{P}_{=5}:$

$$[A^n B^n] Z(P_5)\left(\frac{1}{1-A}\frac{1}{1-B}\right).$$

The cycle index is $$Z(P_5) = {\frac {{a_{{1}}}^{5}}{120}}-1/12\,a_{{2}}{a_{{1}}}^{3}+1/6\,a_{{3 }}{a_{{1}}}^{2}+1/8\,a_{{1}}{a_{{2}}}^{2} \\-1/4\,a_{{4}}a_{{1}}-1/6\,a_{{2}}a_{{3}}+1/5\,a_{{5}}.$$

The substituted cycle index then becomes $${\frac {1}{120\, \left( 1-A \right) ^{5} \left( 1-B \right) ^{5}}} \\-1/12\,{\frac {1}{ \left( -{A}^{2}+1 \right) \left( -{B}^{2}+1 \right) \left( 1-A \right) ^{3} \left( 1-B \right) ^{3}}}\\+1/6\,{ \frac {1}{ \left( -{A}^{3}+1 \right) \left( -{B}^{3}+1 \right) \left( 1-A \right) ^{2} \left( 1-B \right) ^{2}}}\\+1/8\,{\frac {1 }{ \left( 1-A \right) \left( 1-B \right) \left( -{A}^{2}+1 \right) ^{2} \left( -{B}^{2}+1 \right) ^{2}}}\\-1/4\,{\frac {1}{ \left( -{A}^{4}+1 \right) \left( -{B}^{4}+1 \right) \left( 1-A \right) \left( 1-B \right) }}\\-1/6\,{\frac {1}{ \left( -{A}^{2}+1 \right) \left( -{B}^{2}+1 \right) \left( -{A}^{3}+1 \right) \left( -{B}^{3}+1 \right) }}\\+1/5\,{\frac {1}{ \left( -{A}^{5}+1 \right) \left( -{B}^{5}+1 \right) }}.$$

Extracting coefficients from this we get the pieces $$A_1 = \frac{1}{120} {n+4\choose 4}^2,$$ $$A_2 = -\frac{1}{12} \left(\sum_{q=0}^{\lfloor n/2 \rfloor} {n-2q+2\choose 2} \right)^2,$$ $$A_3 = \frac{1}{6} \left(\sum_{q=0}^{\lfloor n/3 \rfloor} {n-3q+1\choose 1} \right)^2,$$ $$A_4 = \frac{1}{8} \left(\sum_{q=0}^{\lfloor n/2 \rfloor} {q+1\choose 1}\right)^2,$$ $$A_5 = -\frac{1}{4} (\lfloor n/4 \rfloor+1)^2,$$ $$A_6 = -\frac{1}{6} \left(\sum_{q=0}^{\lfloor n/3 \rfloor} [[n-3q\equiv 0\mod 2]]\right)^2,$$ and $$A_7 = \frac{1}{5} [[n\equiv 0\mod 5]].$$

This yields the closed formula $$\frac{1}{120} {n+4\choose 4}^2 - \frac{1}{48} \left(\sum_{q=0}^{\lfloor n/2 \rfloor} (n-2q+2)(n-2q+1)\right)^2 \\ + \frac{1}{6} \left(\sum_{q=0}^{\lfloor n/3 \rfloor} (n-3q+1)\right)^2 + \frac{1}{32} (\lfloor n/2 \rfloor + 1)^2(\lfloor n/2 \rfloor + 2)^2 -\frac{1}{4} (\lfloor n/4 \rfloor+1)^2 \\ -\frac{1}{6} \left(\sum_{q=0}^{\lfloor n/3 \rfloor} [[n-3q\equiv 0\mod 2]]\right)^2 + \frac{1}{5} [[n\equiv 0\mod 5]].$$

Additional simplification is possible here but does not appear to add to the understanding of the problem. The sequence that we obtain starting with $n=1$ is $$0, 0, 1, 12, 53, 194, 548, 1369, 3064, 6355, 12295, 22608, \\ 39658, 66992, 109357, 173435, 267890, 404494, 598065, 868065, \ldots$$ which is in agreement with the earlier answer.

We also obtain $$F(1000) = 14758828112205481602.$$

• Great! Nice application of the PET. Commented May 2, 2015 at 7:16

There are 5 types of possibilities for the unordered exponents $a_1,\cdots,a_5$ for 2:

$\textbf{1)}$ $6+0+0+0+0,\;\; 2+1+1+1+1$ $\;\;$(4 of a kind)

$\textbf{2)}$ $5+1+0+0+0,\;\; 3+0+1+1+1,\;\;4+2+0+0+0$ $\;\;$(3 of a kind)

$\textbf{3)}$ $4+1+1+0+0,\;\; 0+2+2+1+1$ $\;\;$(2 pairs)

$\textbf{4)}$ $3+3+0+0+0,\;\; 0+0+2+2+2$ $\;\;$(full house)

$\textbf{5)}$ $3+2+1+0+0$ $\;\;$ (1 pair)

Since we have the same 5 possibilities for the unordered exponents $b_1,\cdots,b_5$ for 5,

we can count the number of ways to pair up these types to get distinct divisors, using the fact that digits matched to repeated digits must be distinct, and their order doesn't matter:

$\textbf{1)}$ and 5) $\;$and$\;$ $\textbf{5)}$ and 1): $\;\;\;2(2\cdot1)(1)={\color{red}4}$ ways

$\textbf{2)}$ and 2): $\hspace{1.03 in}\;\;\;(3\cdot3)(1)={\color{red}9}$ ways

$\textbf{2)}$ and 3) $\;$and$\;$ $\textbf{3)}$ and 2): $\;\;\;2(3\cdot2)(2)=\color{red}{24}$ ways

$\textbf{2)}$ and 5) $\;$and$\;$ $\textbf{5)}$ and 2): $\;\;\;2(3\cdot1)(1+2\cdot3)=\color{red}{42}$ ways

$\textbf{3)}$ and 3): $\hspace{1.03 in}\;\;\;(2\cdot2)(1+2\cdot2)=\color{red}{20}$ ways

$\textbf{3)}$ and 4) $\;$and$\;$ $\textbf{4)}$ and 3): $\;\;\;2(2\cdot2)(1)=\color{red}{8}$ ways

$\textbf{3)}$ and 5) $\;$and$\;$ $\textbf{5)}$ and 3): $\;\;\;2(2\cdot1)(2\cdot3+3\cdot2)=\color{red}{48}$ ways

$\textbf{4)}$ and 5) $\;$and$\;$ $\textbf{5)}$ and 4): $\;\;\;2(2\cdot1)(3)=\color{red}{12}$ ways

$\textbf{5)}$ and 5): $\hspace{1.03 in}\;\;\;3\cdot3+3\cdot3\cdot2=\color{red}{27}$ ways

This gives a total of $\color{red}{194}$ ways of expressing $10^6$ as a product of 5 distinct positive integers.

There are 49 numbers of the form $2^\alpha 5^\beta$ with $0\leq\alpha\leq6$ and $0\leq\beta\leq 6$, and there are ${49\choose 5}=1\,906\,854$ sets of five different such numbers. Out of these five element sets exactly $194$ have product $10^6$. I found this using brute force. Handling the condition that the five factors should be different in an "automatic" way seems to transcend the usual inclusion-exclusion principle.

For $n{\ge}0$, $\;$ let $F(n)$ be the ways in which the number $10^n$ can be expressed as a product of five distinct positive integers.

Then $$F(n)=\left(\frac{1}{5!}\right)\left(24\left(\left\lfloor\frac{n}{5}\right\rfloor-\left\lfloor\frac{n-1}{5}\right\rfloor\right)^{2} +(-30)\left(\left\lfloor\frac{n}{4}\right\rfloor+1\right)^{2} +(-20)\left(\left\lfloor\frac{n+2}{2}\right\rfloor-\left\lfloor\frac{n+2}{3}\right\rfloor\right)^{2} +20\left(\left\lfloor\frac{(n+2)(n+3)}{6}\right\rfloor\right)^{2} +15\left(\frac{2n^{2}+10n+11+(2n+5)(-1)^n}{16}\right)^{2} +(-10)\left(\frac{4n^{3}+30n^{2}+68n+45+3(-1)^{n}}{48}\right)^{2} +\left(\frac{(n+1)(n+2)(n+3)(n+4)}{24}\right)^{2} \right)$$

The answer for this question is $F(6)=194$.

$$F(10)=6355,\quad F(100)=175519523577,\quad F(1000)=14758828112205481602.$$

• That's great! Can you please explain the derivation of coefficients of inclusion-exclusion in your formula? Commented Apr 28, 2015 at 13:02
• Let $G(p,q)$ be the number of connected simple graphs that have $p$ vertecies and $q$ edges. -20 (which is the coefficient of (floor((n+2)/2))-floor((n+2)/3))^2 ) equals $\binom{5}{3}((-1)^{2}G(3,2)+(-1)^{3}G(3,3))((-1)^{1}G(2,1))$. Commented Apr 28, 2015 at 13:39
• 24(which is the coefficient of (floor(n/5)-floor((n-1)/5))^2) equals $\binom{5}{5}((-1)^{4}G(5,4)+(-1)^{5}G(5,5)+(-1)^{6}G(5,6)+(-1)^{7}G(5,7)+(-1)^{8}G(5,8)+(-1)^{9}G(5,9)+(-1)^{10}G(5,10))$. Commented Apr 28, 2015 at 13:46