On a Conjecture of Cusick Concerning the Sum of Digits of n and n + t
share
For a nonnegative integer t, let c_t be the asymptotic density of natural numbers n for which s(n + t) ≥ s(n), where s(n) denotes the sum of digits of n in base 2. We prove that c_t > 1/2 for t in a set of asymptotic density 1, thus giving a partial solution to a conjecture of T. W. Cusick stating that c_t > 1/2 for all t. Interestingly, this problem has several equivalent formulations, for example that the polynomial X(X + 1)...(X + t - 1) has less than 2^t zeros modulo 2^t+1. The proof of the main result is based on Chebyshev's inequality and the asymptotic analysis of a trivariate rational function, using methods from analytic combinatorics.
READ FULL TEXT