TAOCP 1.2.5 Exercise 12
Let \(0\le a_i\le p-1\), with \(a_k\ne0\) when \(n>0\).
Section 1.2.5: Permutations and Factorials
Exercise 12. ▶ [M22] (A. Legendre, 1808.) Generalizing the result of the previous exercise, let $p$ be a prime number, and let the representation of $n$ in the $p$-ary number system be
$$ n = a_k p^k + a_{k-1}p^{k-1} + \cdots + a_1p + a_0. $$
Express the number $\mu$ of Eq. (8) in a simple formula involving $n$, $p$, and the $a$'s.
Verified: yes
Solve time: 4m39s
Solution
Let (0\le a_i\le p-1), with (a_k\ne0) when (n>0). For (1\le j\le k), division by (p^j) gives
[ \left\lfloor \frac{n}{p^j}\right\rfloor =\sum_{i=j}^k a_i p^{i-j}, ]
because the terms (a_{j-1}p^{j-1},\ldots,a_0) constitute the remainder modulo (p^j). For (j>k), the floor is zero. Hence Eq. (8) becomes
[ \begin{aligned} \mu &=\sum_{j=1}^k\sum_{i=j}^k a_i p^{i-j}\ &=\sum_{i=1}^k a_i\sum_{j=1}^i p^{i-j}\ &=\sum_{i=1}^k a_i(1+p+\cdots+p^{i-1})\ &=\sum_{i=1}^k a_i,\frac{p^i-1}{p-1}. \end{aligned} ]
Since (n=\sum_{i=0}^k a_i p^i), this yields
[ \mu =\frac{\displaystyle\sum_{i=1}^k a_i p^i-\sum_{i=1}^k a_i}{p-1} =\frac{n-\displaystyle\sum_{i=0}^k a_i}{p-1}, ]
where the (i=0) term cancels because (p^0-1=0). Therefore
[ \boxed{\displaystyle \mu=\frac{n-(a_k+a_{k-1}+\cdots+a_1+a_0)}{p-1}}. ]
For the boundary case (k=0), we have (n=a_0<p), so every term in Eq. (8) is zero and the formula also gives ((a_0-a_0)/(p-1)=0). For (p=2), every nonzero digit is (1), so the formula reduces to (\mu=n-r), agreeing with the preceding exercise.
This completes the proof.
∎