The binary digits of n+t
Preprint
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 $c_t$ of integers $n\geq 0$ such that \[s(n+t)\geq s(n).\] In 2011, he conjectured that $c_t>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 $M_0$ such that indeed $c_t>1/2$ if the binary expansion of $t$ contains at least $M_0$ 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 $s(n+t)-s(n)$ 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.
Keywords
All Related Versions
This publication has 7 references indexed in Scilit:
- Sendov’s conjecture for sufficiently-high-degree polynomialsActa Mathematica, 2022
- Discrepancy Results for The Van Der Corput SequenceUniform distribution theory, 2018
- On a Conjecture of Cusick Concerning the Sum of Digits of $n$ and $n+t$SIAM Journal on Discrete Mathematics, 2016
- On a Combinatorial ConjectureIntegers, 2011
- A conjecture about binary strings and its applications on constructing Boolean functions with optimal algebraic immunityDesigns, Codes and Cryptography, 2010
- Precise distribution properties of the van der Corput sequence and related sequencesmanuscripta mathematica, 2005
- The ring of k-regular sequencesTheoretical Computer Science, 1992