# Zeros at the end of a factorial

• Apr 26th 2006, 08:04 AM
zardoz
Zeros at the end of a factorial
What´s the best way to calculate how many 0s (zeros) there is at the end of a given factorial?
Sure you could just calculate the whole string of numbers and use your eyes but unfortunately
my calculator only gives x * 10^y answers after a certain point...

I tried to solve that question in the case of 32! and came up with a solution where I split 32! like this:

( (x)nPr(y) = x! / (x-y)!, I think there might be more correct way to write this... but that's how you see it in a calculator, so I guess you´ll understand)

32! = (32)nPr(2) * (30)nPr(5) * (25)nPr(5) * (20)nPr(5) * (15)nPr(5) * 10!

Then I'd calculate each term separately

(32)nPr(2) = 992

(30)nPr(5) / 10 = 1710072

(25)nPr(5) / 100 = 63756

(20)nPr(5) / 10 = 186048

(15)nPr(5) / 10 = 36036

10! / 100 = 36288

Now I can see that 10^7 is a factor in 32! and that the rest are 992, 1710072, 63756, 186048, 36036 and 36288.
So there´s atleast 7 zeros at the end, but then I run into another problem when I try to figure out how many
zeros there might be at the end of 32! / 10^7, which is about 2,631308369 * 10^28. I guess (but am not sure...)
that I can see how many zeros there are by multiplying the last number of each factor: 2*2*6*8*6*8 = 9216. So no
zeros at the end, which would mean that there´s a total of 7 zeros at the end of 32!.

Is there something wrong with my solution and can someone come up with a better one? Thanks in advance.

Btw, I hope I didn´t do too many mistakes in the terms since English is not my native language.
• Apr 26th 2006, 08:44 AM
To get a 0 at the end of the number, you need that number to be multiplied by a 10 or 100 or 1000

10 comes from 5x2
100 comes from 5x5x2x2 and so on

So basically all you have to do is find 5 or powers of 5 since you will easily find an even number to give you a 0

So let's try 5!
The only 5 or power of 5 that divides this number is 5^1 and 5/5 = 1 so there's only ONE 0 at the end of 5!

10! = 10/5 = 2 (we know this to be true)

25! = 25/5 + 25/5^2 = 5 + 1 = 6
So 6 Zeros at the end of 25! (Anybody want to confirm this :D )

And so on and so forth
• Apr 26th 2006, 11:12 AM
zardoz
Yep, thanks, I think I got it. Expect more questions, buahahaha :)
• Apr 26th 2006, 02:41 PM
ThePerfectHacker
There is another way to do this. It uses the greatest integer function and the following theorem:

Theorem: If $n$ is a positive integer and $p$ is a prime, then the exponent of the highest power of $p$ which divides $n!$ is:
$\sum^{\infty}_{k=1}\left[ \frac{n}{p^k} \right]$

Another way is called "Legendre's formula"
$n!=\prod_{p\leq n}p^{\sum \, ^{\infty}_{k=1}[n/p^k]}$
------------
To find the number of zeros terminating 32! you need to prime factorize and find the number of times 2 and 5 appear because the prime factorization of 10 (which gives zero's) is 2 times 5 and select the smaller number.

The the highest exponent for 2 in 32! which divides it is,
$[32/2]+[32/2^2]+[32/2^3]+[32/2^4]+[32/2^5]+...$
everything after the fifth degree vanishes to zero, thus we are left with,
$16+8+4+2+1=31$
The hihest exponent for 5 is,
$[32/5]+[32/5^2]+...$ everything after the second degree vanishes. Thus, you are left with
$6+1=7$
Thus, only 7 zero's follow after 32!

This is my 9:):) th post!!!
• Apr 26th 2006, 07:39 PM
Jameson
Here's something I just picked up on mathworld: The number of trailing zeros can be found by the following summation:

$\sum_{k=1}^{kmax}floor\left[\frac{n}{5^k}\right]$ where kmax is $\log_{5}n$. PerfectHacker: on the following line it shows the formula you listed and claims a strong relation.

http://mathworld.wolfram.com/Factorial.html
• Apr 26th 2006, 08:18 PM
ThePerfectHacker
Quote:

Originally Posted by Jameson
Here's something I just picked up on mathworld: The number of trailing zeros can be found by the following summation:

$\sum_{k=1}^{kmax}floor\left[\frac{n}{5^k}\right]$ where kmax is $\log_{5}n$. PerfectHacker: on the following line it shows the formula you listed and claims a strong relation.

http://mathworld.wolfram.com/Factorial.html

That is interesting, thank you Jameson.
• Apr 29th 2006, 11:59 PM
rgep
You can avoid the summation by a nice formula. The power of p that divides n! is $\frac{n-S(n)}{p-1}$ where $S_p(n)$ is the sum of the digits of n when written in base p.

Thus the power of 2 in 32! is $\frac{32 - 1}{2-1} = 31$ and the power of 5 is $\frac{32-4}{5-1} = 7$, since $32_{10} = 100000_2 = 112_5$.

It's fairly easy to see from this formula that the power of 5 is always less than or equal to the power of 2 in n!.