14
$\begingroup$

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

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

2 Answers 2

11
$\begingroup$

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

$\endgroup$
11
  • $\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, 2012 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$ Feb 20, 2012 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$ Feb 20, 2012 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, 2012 at 19:54
  • $\begingroup$ @user25329: I fixed it. $\endgroup$ Feb 20, 2012 at 20:00
3
$\begingroup$

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

$\endgroup$

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