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.

This question already has an answer here:

I was just trying to work out the exponent for $7$ in the number $343!$. I think the right technique is $$\frac{343}{7}+\frac{343}{7^2}+\frac{343}{7^3}=57.$$ If this is right, can the technique be generalized to $p$ a prime number, $n$ any positive integer, then the exponent of $p$ in $n!$ will be $$\sum_{k=1}^\infty\left\lfloor\frac{n}{p^k}\right\rfloor\quad ?$$ Here, $\lfloor\cdot\rfloor$ denotes the integer less than or equal to $\cdot$ .

Obviously the sum is finite, but I didn't know if it was correct (since its veracity depends on my first solution anyway).

share|improve this question

marked as duplicate by Martin Sleziak, Eoin, 1999, egreg, darij grinberg Jun 30 at 19:36

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.

    
Yes. Now use this to find the number of trailing zeros :) –  M.B. Oct 14 '13 at 17:55
    
@M.B.: Would I use $p=2$ and $p=5$ in such an instance, then take whichever one is smaller? Also, should I delete the question now? Or should you just write "Yes." as an answer? –  anon271828 Oct 14 '13 at 17:56
    
Yup, I guess you mean the larger of the two? Clearly there are more twos than fives. You should probably give this question a closure, e.g. by replying to it yourself. –  M.B. Oct 14 '13 at 17:58
    
@M.B.: What do you mean by the larger of the two? To count the number of trailing zeros, I need to pair off a $2$ with a $5$. Since I believe your statement about there being more $2$'s than $5$'s is true regardless of the integer $n$, I really only need to count the exponent on $5$, right? This will give me the number of trailing zeros? Thanks. –  anon271828 Oct 14 '13 at 18:01
    
You're right that you count the $5$'s rather than the $2$'s. I guess that either M.B. was just wrong, or they meant that you should take the larger in the sense that $5>2$. A fun way to get an approximate answer is to forget the $\lfloor\rfloor$ signs and then sum the geometric series. So for instance $n!$ has about $n/4$ trailing zeros. –  Oscar Cunningham Oct 14 '13 at 18:09

2 Answers 2

Both the solution and its generalization are correct, as @M.B. points out in the comments to the original post. As a corollary, this provides an easy way to count the number of trailing zeros.

share|improve this answer

Why is it so ?

To form the value of $n$, all integers $1,2,\cdots n$ enter into play as factors, and some of them are multiples of $p$.

How many of them ? Well, $n'=\lfloor\dfrac np\rfloor$.

Then, if you discard the other factors and simplify the remaining product by $p^{n'}$, you end up with the expression of $n'!$. Then you repeat the process, until all factors are consumed.

For example, with $n=13,p=3$:

$$13!=1\cdot2\cdot\color{green}3\cdot4\cdot5\cdot\color{green}6\cdot7\cdot8\cdot\color{green}9\cdot10\cdot11\cdot\color{green}{12}\cdot13$$ has $4$ multiples of $3$ and remaining factors $$4!=1\cdot2\cdot\color{green}3\cdot4$$ that has $1$ other factor and remainder $$1!=1.$$

This reasoning establishes the recurrence

$$N_p(n!)=\lfloor\frac np\rfloor+N_p\left(\lfloor\frac np\rfloor!\right),$$

with solution

$$N_p(n!)=\sum_{k=1}^{p^k\le n}\lfloor\dfrac n{p^k}\rfloor.$$

share|improve this answer

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