zbMATH — the first resource for mathematics

On the number of binary digits in a multiple of three. (English) Zbl 0194.35004
L. Moser conjectured that considering the binary expansion of multiples of three \((11, 110, 1001, \dots)\) we can always find a preponderance of numbers containing an even number of digits 1 over those containing an odd number of digits 1. I. Barrodale and R. MacLeod verified this up to 500,000. This article contains a proof of the mentioned conjecture: Denote \(D(n)\) the number of digits 1 in the binary expansion of \(n\) and \[ S(N)=\sum_{0\leq j\leq N/3} (-1)^{D(N-3j)}. \] Theorem: For arbitrary \(n\) \[ 1/20<S(3n)/n^\alpha<5, \quad\text{where}\;\alpha=\log 3/\log 4. \] From the first inequality the Moser’s inequality follows. Further it is proved that \[ \lim_{n\to\infty} (S(3n)/n^\alpha) \] does not exist. The proof uses analytical methods but it is noted that S. Klein has found an elementary proof.
Reviewer: Št. Znám

11A63 Radix representation; digital problems
number theory
Full Text: DOI