Take the 2-minute tour ×
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.

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|improve this 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: math.stackexchange.com/q/17916/1242. –  Hans Lundmark Jan 20 '11 at 9:16
1  
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
add comment

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.

2 Answers

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|improve this answer
1  
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
add comment

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|improve this answer
    
no clue what so ever –  user5918 Jan 20 '11 at 8:45
1  
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
show 3 more comments

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