For a positive integer \(n\), the product of the integers from \(1\) to \(n\) can be written in abbreviated form as \(n!\), which we read as “\(n\) factorial”. So, \[n! = n \times (n-1)\times(n-2)\times \cdots \times 3 \times 2\times 1\]
For example,
\(6! = 6 \times 5 \times 4\times 3\times
2\times 1 = 720\), and \(11! = 11\times
10 \times 9 \times \cdots \times 3 \times 2 \times 1 =
39\,916\,800\).
Note that \(6!\) ends in one zero and \(11!\) ends in two zeros.
Determine the smallest positive integer \(n\) such that \(n!\) ends in exactly \(1000\) zeros.
When finding a solution to this problem, it may be helpful to work with possible values for \(n\) to determine the number of zeros that \(n!\) ends in. One could use a calculator as part of this, but many standard calculators switch to scientific notation around \(14!\). A trial and error approach could work but it may be very time consuming. Our approach will be more systematic.
A zero is added to the end of a positive integer when we multiply by \(10\). Multiplying a number by \(10\) is the same as multiplying a number by \(2\) and then by \(5\), or by \(5\) and then by \(2\), since \(2\times 5 = 10\) and \(5\times 2=10\).
So we want \(n\) to be the smallest positive integer such that the prime factorization of \(n!\) contains \(1000\) \(5\)s and \(1000\) \(2\)s. Every even positive integer has a \(2\) in its prime factorization and every positive integer that is a multiple of \(5\) has a \(5\) in its prime factorization. There are more positive integers less than or equal to \(n\) that are multiples of \(2\) than multiples of \(5\). So once we find a positive integer \(n\) such that \(n!\) has \(1000\) \(5\)s in its prime factorization, we can stop, we know that there will be a sufficient number of \(2\)s in its prime factorization.
There are \(\left\lfloor\frac{n}{5}\right\rfloor\) positive integers less than or equal to \(n\) that are divisible by \(5\). Note, the notation \(\lfloor x \rfloor\) means the floor of \(x\) and is the largest integer less than or equal to \(x\). So \(\lfloor 4.2\rfloor = 4\), \(\lfloor 4.9\rfloor = 4\) and \(\lfloor 4\rfloor = 4\). Also, since \(5\times 1000 = 5000\), we know that \(n \leq 5000\).
Numbers that are divisible by \(25\)
will add an additional factor of \(5\),
since \(25 = 5\times 5\).
There are \(\left\lfloor\frac{n}{25}\right\rfloor\)
positive integers less than or equal to \(n\) that are divisible by \(25\).
Numbers that are divisible by \(125\) will add an additional factor of
\(5\), since \(125 = 5\times 5\times 5\) and two of the
factors have already been counted when we looked at \(5\) and \(25\).
There are \(\left\lfloor\frac{n}{125}\right\rfloor\)
positive integers less than or equal to \(n\) that are divisible by \(125\).
Numbers that are divisible by \(625\) will add an additional factor of
\(5\), since \(625 = 5\times 5\times 5\times 5\) and three
of the factors have already been counted when we looked at \(5\), \(25\), and \(125\).
There are \(\left\lfloor\frac{n}{625}\right\rfloor\)
positive integers less than or equal to \(n\) that are divisible by \(625\).
Numbers that are divisible by \(3125\) will add an additional factor of
\(5\), since \(3125 = 5^5\) and four of the factors have
already been counted when we looked at \(5\), \(25\), \(125\), and \(625\).
There are \(\left\lfloor\frac{n}{3125}\right\rfloor\)
positive integers less than or equal to \(n\) that are divisible by \(3125\).
The next power of \(5\) to consider is \(5^6 = 15\,625\). But since \(n\leq 5000\), we do not need to consider this power of \(5\) or any larger power.
Thus, we know that \(n\) must satisfy the equation \[\begin{aligned} \left\lfloor\frac{n}{5}\right\rfloor + \left\lfloor\frac{n}{25}\right\rfloor + \left\lfloor\frac{n}{125}\right\rfloor+ \left\lfloor\frac{n}{625}\right\rfloor+ \left\lfloor\frac{n}{3125}\right\rfloor = 1000 \end{aligned}\]
Let’s ignore the floor function. We know that \(n\) is going to be close to satisfying \[\begin{aligned} \frac{n}{5} + \frac{n}{25} + \frac{n}{125}+ \frac{n}{625}+ \frac{n}{3125} &= 1000\\ \frac{625n}{3125} + \frac{125n}{3125} + \frac{25n}{3125}+ \frac{5n}{3125}+ \frac{n}{3125} &= 1000\\ \frac{781}{3125}n &= 1000\\ n&=\frac{1000\times 3125}{781}\\ n &\approx 4001.2 \end{aligned}\]
The number of zeros at the end of \(4001!\) is equal to \[\begin{aligned} &\left\lfloor\frac{4001}{5}\right\rfloor + \left\lfloor\frac{4001}{25}\right\rfloor + \left\lfloor\frac{4001}{125}\right\rfloor+ \left\lfloor\frac{4001}{625}\right\rfloor+ \left\lfloor\frac{4001}{3125}\right\rfloor \\ &= \lfloor 800.2\rfloor + \lfloor 160.04\rfloor + \lfloor 32.008\rfloor + \lfloor 6.4016\rfloor + \lfloor 1.28032\rfloor\\ &=800 + 160 + 32 + 6 + 1\\ &= 999 \end{aligned}\]
Therefore, the number \(4001!\) ends in \(999\) zeros. We need one more factor of \(5\) in order to have \(1000\) zeros at the end. The first integer after \(4001\) that is divisible by \(5\) is \(4005\).
Therefore, \(4005\) is the smallest positive integer such that \(4005!\) ends in \(1000\) zeros.
Indeed, we can check. The number of zeros at the end of \(4004!\) is equal to the number of \(5\)s in its prime factorization, which is equal to \[\begin{aligned} &\left\lfloor\frac{4004}{5}\right\rfloor + \left\lfloor\frac{4004}{25}\right\rfloor + \left\lfloor\frac{4004}{125}\right\rfloor+ \left\lfloor\frac{4004}{625}\right\rfloor+ \left\lfloor\frac{4004}{3125}\right\rfloor\\ &= \lfloor 800.8\rfloor + \lfloor 160.16\rfloor + \lfloor 32.032\rfloor + \lfloor 6.4064\rfloor + \lfloor 1.28128\rfloor\\ &=800 + 160 + 32 + 6 + 1\\ &= 999 \end{aligned}\] The number of zeros at the end of \(4005!\) is equal to the number of \(5\)s in its prime factorization, which is equal to \[\begin{aligned} &\left\lfloor\frac{4005}{5}\right\rfloor + \left\lfloor\frac{4005}{25}\right\rfloor + \left\lfloor\frac{4005}{125}\right\rfloor+ \left\lfloor\frac{4005}{625}\right\rfloor+ \left\lfloor\frac{4005}{3125}\right\rfloor \\ &= \lfloor 801\rfloor + \lfloor 160.2\rfloor + \lfloor 32.04\rfloor + \lfloor 6.408\rfloor + \lfloor 1.2816\rfloor\\ &=801 + 160 + 32 + 6 + 1\\ &= 1000 \end{aligned}\]