Number of zeros not possible 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?

The number of zeros which are not possible at the end of the $n!$ is:

$a) 82 \quad\quad\quad b) 73 \quad\quad\quad c) 156 \quad\quad\quad d) \text{ none of these }$

I was trying to solve this problem. I know how to calculate the no of zeros in factorial but have no idea how to work out this problem quickly.

Answer 1

If you know how to calculate the number of zeros at the end of $n!$, then you know that there are some values of $n$ for which the number of zeros has just increased by 2 (or more), skipping over number(s). What numbers are skipped?

Further hint (hidden):

Find the number of zeros are at the end of (a) $24!$; (b) $25!$

edit more explicitly:

the factorials of 5-9 end in 1 zero, 10-14 end in 2 zeros, 15-19 end in 3 zeros, 20-24 end in 4 zeros, 25-29 end in 6 zeros, so 5 is the first number skipped. For what $n$ will the number of zeros at the end of $n!$ next skip over an integer and what is that number of zeros?

Answer 2

Assuming there is a single answer, the answer is $73$.

Consider $300!$, it has $300/5 + 60/5 + 10/5 = 74$ zeroes. $299!$ has $59 + 11 + 2 = 72$ zeroes.

Got this by trial and error and luck.

Note this is an application of Legendre's formula of the highest power of a prime $p$ dividing $n!$ being $$\displaystyle \sum_{k=1}^{\infty} \left \lfloor \frac{n}{p^k} \right \rfloor$$.

We only need to consider power of $5$ to get the number of zeroes.

---

Since you asked for a method:

For smallish numbers, you could try getting a multiple of $6 = 1+5$ close to your number, find the number of zeroes for $25/6$ times that and try to revise your estimate.

For example for $156 = 6*26$.

So try $26*5*5 = 650$. $650!$ has $26*5 + 26 + 5 + 1 = 162$ zeroes.

Since you overshot by $6$, try a smaller multiple of $6$.

So try $25*5*5$, which gives $25*5 + 25 + 5 + 1 = 156$. Bingo!

For $82$, try $78 = 13*6$.

So try $13*25$. Which gives $65 + 13 + 2 = 80$ zeroes.

So try increasing the estimate, say by adding 10 (since we were short by 2).

$13*25 + 10$ gives us $67 + 13 + 2 = 82$ zeroes.

For $187$ Try $186 = 6*31$.

So try $31*5*5$ this gives us $31*5 + 31 + 6 + 1 = 193$ zeroes.

since we overshot by $7$, try reducing it, say

$30*5*5$ gives us $30*5 + 30 + 6 + 1 = 187$

For larger numbers instead of multiple of 6, consider multiple of $1+5+25$, $1+5+25+125$ etc.

I am pretty sure there must be a better method, but I don't expect the CAT folks to expect candidates to know that!

Hope that helps.