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 Answers 2

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$
1
  • $\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$ Commented Mar 31, 2014 at 19:36

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .