Exponent of $p$ in the prime factorization of $n!$

Exponent of $p$ in the prime factorization of $n!$ is given by $\large \sum \limits_{i=1}^{\lfloor\log_p n \rfloor } \left\lfloor \dfrac{n}{p^i}\right\rfloor$. Can this sum be simplified further to some direct expression so that the number of calculations are reduced?

• This is an incredibly small calculation... – user98602 Aug 9 '14 at 17:18
• I am looking at @robjohn 's reply in below thread which shows that the sum simplifies to $\dfrac{n-\lfloor \log_p n\rfloor }{p-1}$ , but I don't really understand it and it is not giving correct answer for n=20 and p=2 math.stackexchange.com/questions/590885/… – ganeshie8 Aug 9 '14 at 17:19
• robjohn's answer says that the sum simplifies to $\dfrac{n-\sigma_p(n)}{p-1}$, where $\sigma_p(n)$ is the sum of the digits of $n$ in the base-$p$ representation, just like David Holden's answer here. Where did you get the $\lfloor \log_p n\rfloor$ from? – Daniel Fischer Aug 9 '14 at 17:31
• @DanielFischer, he seems to have figured out about the digit sum... if $i > \log_p n$ then $p^i > n$ and the floor of the fraction is zero. – Will Jagy Aug 9 '14 at 17:39
• @WillJagy I was referring to the formula in the comment, not the bound on the sum. (Didn't even notice that there appeared a $\lfloor \log_p n\rfloor$ too.) – Daniel Fischer Aug 9 '14 at 17:41

yes:

$$\frac{N-\sigma_p(N)}{p-1}$$ where $\sigma_p(N)$ is the sum of digits in the $p$-ary expression of $N$

• I think $\sigma_p (N)$ is same as $\lfloor \log_p N\rfloor$ ? i am trying to work below example : exponent of 2 in prime factorization of $20!$ is $18$ : wolframalpha.com/input/?i=prime+factorization+of+20%21 but your expression gives a different number : $\dfrac{20-\lfloor \log_2 20\rfloor }{2-1} = 16$ – ganeshie8 Aug 9 '14 at 17:33
• @GaneshTadi No. In binary, $20$ is $10100$, so the digit sum of $20$ in base-$2$ is $2$. $\frac{20-2}{2-1} = 18$, as it should be. $\lfloor \log_p n\rfloor$ is one less than the number of digits in base $p$. – Daniel Fischer Aug 9 '14 at 17:35
• if in binary $N=1101101$ then $\sigma_2(N) = 1+1+0+1+1+0+1=5$ – David Holden Aug 9 '14 at 17:35
• Gotcha :) I see my error in interpreting the formula, thanks a lot xD – ganeshie8 Aug 9 '14 at 17:37

note what Daniel says. $\lfloor \log_p N\rfloor$ is the exponent of $p$ in $N$ not in $N!$. let $P_N$ be the exponent of $p$ in $N!$ and consider $P_{N+1}$.

if $N+1$ is not divisible by $p$ then the least significant $p$-ary digit of $N$ increases by $1$ and so $$N+1 - \sigma_p(N+1) = N - \sigma_p(N)$$ and the exponent is unchanged.

suppose $N+1$ is divisible by $p^r$ for $r \gt 0$ but not by $p^{r+1}$ then each of the $r$ least significant binary digits must take the value $p-1$ but $1$ is added to the $r^{\text{th}}$ digit, which is not equal to $p-1$ hence: $$\sigma_p(N+1) = \sigma_p(N)+1 - r(p-1)$$ and $$N+1 - \sigma_p(N+1) = N - \sigma_p(n) + r(p-1)$$ hence $$P_{N+1} = \frac{N+1 - \sigma_p(N+1) }{p-1} \\ = P_N + r$$

The idea of this theorm is to reduce manual calculation , try to find exp of 2 for (23263662!) :P so i guess its fair to follow the theorm . Origion theorm was $\large \sum \limits_{i=1}^{\infty} \left\lfloor \dfrac{n}{p^i}\right\rfloor$ , the floor log n function come from condition that i<=n thus any i after n give term of zero.