The Legendre's formula gives $\alpha$ in
$$p^\alpha || n!$$
where $p$ is a prime number.
To calculate $\nu_p(n!)$ on paper, one should normally find the quotients $q_i$ in these equations by long division and then sum them up:
$$n=p^i q_i+r_i, \quad 0\le r_i \lt p^i$$
So we will divide $n$ by $p^i$'s multiple times.
The variation I stumbled upon is using the previous quotient and divide by $p$. This method of using recursive divisions is indeed relatively faster as the divisor remains small instead of growing exponentially (as it does in the first method). It is basically saying:
$$Q_0:=n$$ $$Q_i=pQ_{i+1}+R_{i+1}, \quad 0 \le R_i \lt p$$
Manipulating them a bit, we get:
$$n=p^i Q_i + \sum_{j=1}^i p^{j-1} R_j$$
As you see, the equations look similar to those of the first method. But I doubt if this variation will give the correct result because I couldn't prove $\forall i; q_i = Q_i$. This is my approach:
If I prove $0 \le \sum_{j=1}^i p^{j-1} R_j \lt p^i$, then $q_i = Q_i$ and the two methods are equivalent.
$$0\le R_i \lt p$$ $$0\le p^{i-1}R_i \lt p^i$$ $$0\le\sum_{i=1}^k p^{i-1} R_i \lt \sum_{i=1}^k p^i=p\frac{p^k-1}{p-1}$$
I should just check if $p\frac{p^k-1}{p-1} \le p^k$:
$$p(p^k-1) \le p^k (p-1)$$ $$-p \le -p^k$$ $$p \ge p^k$$
Which is wrong since prime numbers are greater than one.
Because of the essence of the proof I used, there might be another approach which works and can prove the two methods are the same.
Is the second method valid?
