Thue-Morse at multiples of an integer

DOI10.1016/J.JNT.2011.02.006MaRDI QIDQ538176zbMATH OpenOpenAlexWikidataFDO

Authors Johannes F. Morgenbesser, Thomas Stoll, Jeffrey Shallit

Publication date 23 May 2011

Published in Journal of Number Theory (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1009.5357

zbMATH Keywords

arithmetic progressionscongruencessum of digitsThue-Morse sequence

Mathematics Subject Classification ID

Radix representation; digital problems (11A63) Automata sequences (11B85) Distribution of integers with specified multiplicative constraints (11N25) Combinatorics on words (68R15)

Abstract: Let (t_n) be the classical Thue-Morse sequence defined by t_n = s_2(n) (mod 2), where s_2 is the sum of the bits in the binary representation of n. It is well known that for any integer k>=1 the frequency of the letter "1" in the subsequence t_0, t_k, t_{2k}, ... is asymptotically 1/2. Here we prove that for any k there is a n<=k+4 such that t_{kn}=1. Moreover, we show that n can be chosen to have Hamming weight <=3. This is best in a twofold sense. First, there are infinitely many k such that t_{kn}=1 implies that n has Hamming weight >=3. Second, we characterize all k where the minimal n equals k, k+1, k+2, k+3, or k+4. Finally, we present some results and conjectures for the generalized problem, where s_2 is replaced by s_b for an arbitrary base b>=2.

Recommendations

• Thue-Morse along two polynomial subsequences
• The subword complexity of polynomial subsequences of the Thue-Morse sequence
• scientific article; zbMATH DE number 6684207
• The level of distribution of the Thue–Morse sequence
• Generalized Thue-Morse sequences of squares

Cites work

• A summation formula related to the binary digits
• On digit sums of multiples of an integer
• On the Number of Binary Digits in a Multiple of Three
• Somme des chiffres et transcendance
• Stolarsky’s conjecture and the sum of digits of polynomial values
• Sur les nombres qui ont des propriétés additives et multiplicatives données
• The distribution of the sum of digits (\bmod𝑝)

Cited in

(13)

• On -nil ideals of bounded index of -nilpotence.
• Minimal automaton for multiplying and translating the Thue-Morse set
• Monochromatic arithmetic progressions in binary Thue-Morse-like words
• Thue-Morse along two polynomial subsequences
• scientific article; zbMATH DE number 5310321 (Why is no real title available?)
• Sums of the Thue-Morse sequence over arithmetic progressions
• Nondeterministic automatic complexity of overlap-free and almost square-free words
• The level of distribution of the Thue–Morse sequence
• Egyptian Fractions with Denominators from Sequences Closed Under Doubling
• Monochromatic arithmetic progressions in automatic sequences with group structure
• On monochromatic arithmetic progressions in binary words associated with pattern sequences
• The level of distribution of the sum-of-digits function in arithmetic progressions
• Monochromatic arithmetic progressions in the Fibonacci, Thue-Morse, and Rudin-Shapiro words

This page was built for publication: Thue-Morse at multiples of an integer

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q538176)