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


marked as duplicate by user17762, Qiaochu Yuan May 5 '12 at 20:01

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • 1
    $\begingroup$ This and this. $\endgroup$ – user2468 Feb 20 '12 at 19:30

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

  • $\begingroup$ can you be a little more specific? What is k in this case? and is that the formula to find the trailing zeroes or the exponent of 5? $\endgroup$ – user25329 Feb 20 '12 at 19:40
  • $\begingroup$ Dear Américo: You didn't explain what $k$ is. I'd replace it by $\infty$. (You can also replace it by $n$, or by many other expressions.) $\endgroup$ – Pierre-Yves Gaillard Feb 20 '12 at 19:40
  • 1
    $\begingroup$ Dear @user25329: Américo will probably answer, but in the meantime I'll tell you that Américo claims that the number of trailing zeroes equals the exponent of $5$, and that you can replace $k$ by $\infty$. (At least that's how I understand Américo's post.) $\endgroup$ – Pierre-Yves Gaillard Feb 20 '12 at 19:43
  • $\begingroup$ But don't we also need to take into account numbers like 25,125,625 that has multiple 5's in them? How can we take that into account and combine everything in one formula? In other words, what is the formula in terms of n that counts the number of zeros at the end of "n!"? $\endgroup$ – user25329 Feb 20 '12 at 19:54
  • $\begingroup$ @user25329: I fixed it. $\endgroup$ – Américo Tavares Feb 20 '12 at 20:00

(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).


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