Thue-Morse at Multiples of an Integer

2010/09/27 by Morgenbesser, Johannes F., Shallit, Jeffrey, Stoll, Thomas
#11A63 #11N25 #68R15 #Combinatorics (math.CO) #FOS: Mathematics #Number Theory (math.NT)

paper · doi:10.48550/arxiv.1009.5357

Abstract

Let (t_n) be the classical Thue-Morse sequence defined by t_n = s₂(n) (mod 2), where s₂ 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₀, 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₂ is replaced by s_b for an arbitrary base b>=2.

Related

• Thue--Morse along the sequence of cubes
• Two analogs of Thue-Morse sequence
• Rarefied Thue-Morse Sums Via Automata Theory and Logic
• Gaps in the Thue--Morse word
• On the longest common subsequence of Thue-Morse words