How do we calculate highest power of $p^a$ in $n!$?

Question

Calculate highest power of $p^a$ in $n!$ Eg. Highest power of $5^3$ in $150!$

Answer 1

I first describe how to find the highest power of $p$.

Let $N_m$ be the amount of numbers at most n which are a multiple of $p^m$. Then the number you are looking for is $\sum_{m} N_m$. Before we explain why, nite that this sum is not infinite. Indeed $N_m=0$ if $p^m>n$ so it only goes up to $m= \lfloor \log_p n \rfloor$.

Why is this the number we are looking for? Note that if $l$ is maximal such that $p^l$ divides k for some $k\le n$, the $k$ was counted in the sun exactly $l$ times: once for each of the summands $N_1, \ldots, N_l$. Hence, the sum is exactly the same as if we'd have just summed the highest power of $p$ which divides the numbers $1,\ldots,n$.

However, this sum is much easier to compute! Indeed, a moment reflection reveals that $N_m= \lfloor n/p^m \rfloor$, so the quantity you are looking for is ultimately $\sum_{k=1}^{\lfloor \log_p n \rfloor}\lfloor n/p^k \rfloor$.

For $p^\alpha$ you can use the sum $\sum_{k=1}^{\lfloor \log_{p^\alpha} n \rfloor}\lfloor n/p^{\alpha k} \rfloor$.