2
$\begingroup$

Pick an integer $b \ge 2$, and for $n \in \mathbf N$ let $s_b(n)$ denote the sum of the base-$b$ digits of $n$. It is a nice exercise to prove that $$s_b(n) = (b-1) \sum_{i=1}^\infty \left\{\frac{n}{b^i}\right\}.$$ In particular, this follows at once from $$s_b(n) = n - (b-1) \sum_{i=1}^\infty \left\lfloor \frac{n}{b^i}\right\rfloor,$$ and I seem to remember that the latter is due to Legendre, but I don't remember where I first read it and cannot find any reference, which is why I'm writing. So, thank you in advance for any help.

Edit. A 1967 note by Trollope on the AMM (click) mentions the second of the above identities; the author refers the reader to p. 12 in the 1955 edition of Legendre's Théorie des Nombres (which is consistent with the answer of Konstantinos Gaitanas, below). Unluckily, I have only a copy of a previous edition of the book (namely, the 1830 edition), where Legendre seems to consider only the case where $b$ is prime. Thus, I'm a little bit puzzled, since Trollope doesn't assume this condition in his note. Is there anybody with access to the 1955 edition?

$\endgroup$
2
$\begingroup$

Sorry for answering my own question, but it turns out that the second identity in the OP is explicitly stated and proved in: L. D. Yarbrough and S. Rabinowitz, Solution to Problem E1926, Amer. Math. Monthly 75 (Mar., 1968), No. 3, 296.

$\endgroup$
1
$\begingroup$

According to Dickson's History of the Theory of Numbers Vol. 1 page 263 at line 5:
"A. M. Legendre proved that if $p^μ$ is the highest power of the prime $p$ which divides $x!$ $\cdots$ then $$μ=\lfloor \frac{m}{p}\rfloor+\lfloor \frac{m}{p^2}\rfloor+\cdots=\frac{m-s}{p-1}$$
where $s=a_0+\cdots+a_n$ is the sum of the digits of $m$ to the base $p$"
We can see that rephrasing the above equation yields:
$$s=m-(p-1)\cdot \sum\limits_{i=1}^\infty \lfloor\frac{m}{p^i}\rfloor$$
Which looks like exactly what you wrote .
So i guess yes, Legendre first proved this in his famous (according to Dickson)
Théorie des nombres (1808)

$\endgroup$
  • $\begingroup$ While I agree that, for a prime base $b$, the 2nd identity in the OP can be viewed as a rephrasing of Legendre's theorem on the $b$-adic valuation of $n!$, which in turn is a straightforward consequence of De Polignac's formula (en.wikipedia.org/wiki/De_Polignac%27s_formula), I don't see how this can imply the identity in the general case, which is the one for which I'd like to get a reference. However, thanks for the effort! $\endgroup$ – Salvo Tringali Mar 31 '14 at 19:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.