Thue-Morse at multiples of an integer

JOURNAL OF NUMBER THEORY

卷:131

Article

Morgenbesser, Johannes F.^1,2  Shallit, Jeffrey³  Stoll, Thomas¹ 

[1] Univ Aix Marseille 2, Inst Math Luminy, F-13288 Marseille 9, France

[2] Vienna Univ Technol, Inst Diskrete Math & Geometrie, A-1040 Vienna, Austria

[3] Univ Waterloo, Sch Comp Sci, Waterloo, ON N2L 3G1, Canada

关键词: Thue-Morse sequence;    Sum of digits;    Congruences;    Arithmetic progressions;   

DOI  :  10.1016/j.jnt.2011.02.006

来源: Elsevier

【 摘 要 】

Let t = (t(n))(n >= 0) 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 an 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. (C) 2011 Elsevier Inc. All rights reserved.

【 授权许可】

Free