Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question

marked as duplicate by Marvis, Qiaochu Yuan May 5 '12 at 20:00

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.

Is there something that precludes you from simply computing the first few hundred factorials on a computer, then inspecting their digits? – Douglas S. Stones Jan 20 '11 at 8:13
Yes. This question belongs to a quantitative aptitude section of CAT(Common aptitude test) which must be answered in least possible time(varying from 1 to 3 mins) – user5918 Jan 20 '11 at 8:17
This recent question is related: – Hans Lundmark Jan 20 '11 at 9:16
So this is not really homework... btw, @user5918, you seem to posting a lot of questions without actually showing any of your working. It is considered to be in bad form to do that. Please put some thought/effort into your questions before asking them here. – Aryabhata Jan 20 '11 at 9:29

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.

share|cite|improve this answer
if the option changes to some other prime number greater than say 103 or 187 than this is sure that it will not work in time limit varying (1-5)min could you provide me the general solution to this problem so that the wrong answer could be straight away discarded – user5918 Jan 20 '11 at 8:37

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?

share|cite|improve this answer
no clue what so ever – user5918 Jan 20 '11 at 8:45
Not sure if I would recommend this method for an exam which has 2-3 minutes allotted to each question. – Aryabhata Jan 20 '11 at 9:34
@Moron: I strongly suspect that in 2-3 minutes, I could generate a list of the skipped numbers up to around 300 or so, but I haven't actually tried it yet. – Isaac Jan 20 '11 at 10:16
I certainly could generate such a list up to 156 by hand in 3 minutes and find time to double check it. Now if it took 3 minutes to decide that I wanted to generate such a list, that's a different issue... – Barry Smith Jan 20 '11 at 12:31
i have tried to solve the question considering the time factor(1-3)min:....According to Legender expression of calculating number of zeros in any factorial could be 5 raised to the power( 1,2,3,4,6) but surely not 5. HENCE APPLYING THIS OBSERVATION in this problem :IT CAN BE DERIVED THAT THE POWER OF 5 SHOULD BE EITHER(1,2,3,4,6)OR MULTIPLE OF (1,2,3,4,6) that is nothing but LCM of these numbers i.e(12) ,powers of multiple of 5 should be completely divisible by(1,2,3,4,6,12) if it is not divisible by all these numbers than that number cannot be the number of zeros in any (n)! – user5918 Jan 20 '11 at 14:04

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