Derive a formula to find the number of trailing zeroes in $n!$

Question

Possible Duplicate:
How come the number $N!$ can terminate in exactly $1,2,3,4,$ or $6$ zeroes but never $5$ zeroes?

I know that I have to find the number of factors of $5$'s, $25$'s, $125$'s etc. in order to do this. But how can you derive such a formula for any number $n$?

Answer 1

(HINT) Let's see:

For a number up to $4$, no fives divide $n!$. Between $5$ and $9$, exactly 1 5 divides $n!$. At $10$, we get another $5$. Thinking about it, we may suspect that at $15$, we would get our next 5, and so on.

So is the formula $\lfloor \frac{n}{5} \rfloor$? That seems to work up to 5, 10, 15, 20. But at $25$, we get not 1 but two additional factors of $5$! Thus we get that for $26$ and so on, too!

How can we modify our formula to account for that?

(and - so that you don't think it's done then, remember things like $125$ and $625$ too).

Answer 2

The number of trailing zeroes in $n!$ is the exponent of $5$ in the prime factorization of $n!$, which by the de Polignac's formula$^1$ is given by

$$e_5(n!)=\sum_{i= 1}^{\left\lfloor \log n/\log 5\right\rfloor} \left \lfloor \frac{n}{5^i} \right \rfloor.\tag{1}$$

Added. By the same de Polignac's formula the exponent of $2$ in the prime factorization of $n!$ is

$$e_2(n!)=\sum_{i= 1}^{\left\lfloor\log n/\log 2\right\rfloor} \left \lfloor \frac{n}{2^i} \right \rfloor.\tag{2}$$

Edited. For every $n$ there exists $m$ such that $n!=2^{e_2(n!)}\cdot 5^{e_5(n!)}m=(2^{e_2(n!)-e_5(n!)}m)10^{e_5(n!)}$, which proves that the number of trailing zeroes in $n!$ is the exponent of $5$ in the prime factorization of $n!$ .

Example: $n=50$. The exponent of $2$ in the prime factorization of $50!$ is

$$\begin{align} e_2(50!)=\sum_{i\geq 1}\left\lfloor \dfrac{50}{2^{i}}\right\rfloor &= \left\lfloor \dfrac{50}{2}\right\rfloor+\left\lfloor \dfrac{50}{2^{2}} \right\rfloor + \left\lfloor \dfrac{50}{2^{3}} \right\rfloor + \left\lfloor\dfrac{50}{2^{4}}\right\rfloor +\left\lfloor \dfrac{50}{2^{5}}\right\rfloor \\ &=25+12+6+3+1 \\ &=47, \end{align}$$

and the exponent of $5$ is $$e_5(50!)=\sum_{i\geq 1}\left\lfloor \dfrac{50}{5^{i}}\right\rfloor=\left\lfloor \dfrac{50}{5}\right\rfloor +\left\lfloor \dfrac{50}{5^{2}}\right\rfloor =10+2=12.$$ So, the number of trailing zeroes in $50!=2^{47}5^{12}m=(2^{35}m)10^{12}$ is $12$.

$^1$ For every integer $n$ the exponent of the prime $p$ in the prime factorization of $n!$ equals $$\displaystyle\sum_{i= 1}^{\left\lfloor \log n/\log p\right\rfloor}\left\lfloor \frac{n}{p^{i}} \right\rfloor .$$

This exponent is obtained by adding to the numbers between $1$ and $n$ which are divisible by $p$ the number of those divisible by $p^{2}$, then the number of those divisible by $p^{3}$, and so on. The process terminates at the greatest power $p^{i}\leq n$.