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

Question

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?

Answer 1

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

Answer 2

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$.