Calculating the power of prime in factorial by changing base

Question

The greatest power $k$ of a prime $p$ in the prime factorization of $n!$ is equal to $\frac1{p-1}(n-s(n)_p)$, where $s(n)_p$ is the sum of digits of $n$ when represented in base $p$.

How to derive the above formula?

Answer 1

Let's try induction.

For $0\le n< p$ we have $k(n)=0$ and also $\frac1{p-1}(n-s(n)_p)=0$.

For $n\ge p$ we can write $n=mp+r$ with $m\in\mathbb N$ and $0\le r<p$ and may assume that $k(m)=\frac1{p-1}(m-s(m)_p)$. We note that $s(n)_p=s(m)_p+r$. The multiples of $p$ that are $\le n$ are of the form $pt$ with $1\le t\le m$ and the contribution of $pt$ to $k(n)$ is one more than the contribution of $t$ to $k(m)$, and of course the non-multiples contribute nothing to $k(n)$. We conclude that $$\begin{align}k(n)&=m+k(m)\\&=m+\frac1{p-1}(m-s(m)_p)\\&=\frac1{p-1}(mp-s(m)_p)\\&=\frac1{p-1}(n-r-s(m)_p)\\&=\frac1{p-1}(n-s(n)_p) \end{align}$$