The binary digits of n+t

Abstract

The binary sum-of-digits function s counts the number of ones in the binary expansion of a nonnegative integer. For any nonnegative integer t, T. W. Cusick defined the asymptotic density ct of integers n ≥ 0 such that (Formula presented). In 2011, he conjectured that ct > 1=2 for all t – the binary sum of digits should, more often than not, weakly increase when a constant is added. In this paper, we prove that there exists an explicit constant M0 such that indeed ct > 1=2 if the binary expansion of t contains at least M0 maximal blocks of contiguous ones, leaving open only the “initial cases” – few maximal blocks of ones – of this conjecture. Moreover, we sharpen a result by Emme and Hubert (2019), proving that the difference (Formula presented) behaves according to a Gaussian distribution, up to an error tending to 0 as the number of maximal blocks of ones in the binary expansion of t grows.