1
$\begingroup$

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?

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

2 Answers 2

7
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.