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

Question

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?

Answer 1

yes:

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

Answer 2

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 $$

Answer 3

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.