# The first $n$ such that $n!$ has more than or equal $10000$ trailing zeros

I would like to find the first $$n!$$ such that $$(\text{The number of trailing zeros in }n!)\geq 10000$$.

By following the method in this post, If we represent $$n$$ in base $$5$$($$n=a_0 + 5a_1 +25a_2+\cdots)$$, we get:

$$[n/5]+[n/25]+[n/125]+\cdots = a_1 + 6a_2 + 31a_3 + 156a_4 + 781a_5 +3906a_6 + 19531a_7\cdots$$

where $$0 \leq a_k \leq 4$$, and this is equal to the number of trailing zeros in $$n!$$, according to the Legendre formula.

$$19531$$ is already excessive, so we can assume that $$a_k=0$$ for $$k\geq 7$$. Now we have to find the smallest $$n$$ such that

$$a_1 + 6a_2 + 31a_3 + 156a_4 + 781a_5 +3906a_6 \geq 10000$$.

But I am not sure how. Obviously, brute force is an option, but I would like a more "elegant" solution.

How can I continue?

• You have missed out a term - 1, 6, 31, 156, 781, 3906. Jun 23, 2021 at 11:34
• @JaapScherphuis Ah yes, just edied it. Jun 23, 2021 at 11:34

The highest power of $$2$$ dividing $$n!$$ is $$\lfloor \frac{n}{2} \rfloor+\lfloor \frac{n}{4} \rfloor+\lfloor \frac{n}{8} \rfloor+...$$

The highest power of $$5$$ dividing $$n!$$ is $$\lfloor \frac{n}{5} \rfloor+\lfloor \frac{n}{25} \rfloor+\lfloor \frac{n}{125} \rfloor+...$$

For $$n!$$ to have more than $$10000$$ trailing zeros, it is necessary and sufficient to have $$\lfloor \frac{n}{5} \rfloor+\lfloor \frac{n}{25} \rfloor+\lfloor \frac{n}{125} \rfloor+... \geq10000$$ (since this inequality is then automatically statisfied for $$2$$ instead of $$5$$)

This means $$n \leq 50000$$ (due to the first term), and using the fact that $$\lfloor \frac{n}{5} \rfloor+\lfloor \frac{n}{25} \rfloor+\lfloor \frac{n}{125} \rfloor+...$$ is increasing in $$n$$, it can be possible to isolate the solution through trial and error (bisection).

For instance, for $$n=40000$$, we get $$\lfloor \frac{n}{5} \rfloor+\lfloor \frac{n}{25} \rfloor+\lfloor \frac{n}{125} \rfloor+...=9998$$ so that would be $$9998$$ trailing zeros, so it must be close to this number. $$40005\leq n \leq 40009$$ yields $$9999$$ and $$40010$$ yields $$10000$$ so the answer is $$n=40010$$. This came from an educated guess but did not require too many calculations

You arrived at the inequality $$a_1+6a_2+31a_3+156a_4+781a_5+3906a_6\ge 10000$$ where the $$a_i$$ are base $$5$$ digits, so are in the range $$0$$ to $$4$$.

$$10000/3906 = 2.56...$$ so you can set $$a_6=2$$, as a value of $$3$$ would overshoot the goal too much. Substituting this into the inequality gives:

$$a_1+6a_2+31a_3+156a_4+781a_5\ge 2188$$

$$2188/781=2.80...$$ so we set $$a_5=2$$ and arrive at:

$$a_1+6a_2+31a_3+156a_4\ge 626$$

$$626/156=4.01...$$ so we set $$a_4=4$$ and arrive at:

$$a_1+6a_2+31a_3\ge 2$$

Now by setting $$a_3=a_2=0$$ and $$a_1=2$$ we will overshoot by the least possible amount because we get equality.

Therefore we have

$$n= a_65^6+a_55^5+a_45^4+a_35^3+a_25^2+a_15^1+a_05^0\\ = 2\cdot5^6+2\cdot5^5+4\cdot5^4+2\cdot5^1+a_0\\ = 31250+6250+2500+10+a_0\\ = 40010+a_0$$

Obviously setting $$a_0=0$$ gives the smallest answer $$40010$$.