A334173 Least i such that i-th term of Thue-Morse sequence (A010060) differs from (i + n)-th term.

0, 0, 2, 0, 1, 4, 0, 0, 1, 2, 0, 8, 0, 0, 2, 0, 1, 2, 0, 4, 0, 0, 1, 16, 0, 0, 2, 0, 1, 4, 0, 0, 1, 2, 0, 4, 0, 0, 1, 8, 0, 0, 2, 0, 1, 2, 0, 32, 0, 0, 2, 0, 1, 4, 0, 0, 1, 2, 0, 8, 0, 0, 2, 0, 1, 2, 0, 4, 0, 0, 1, 8, 0, 0, 2, 0, 1, 2, 0, 16, 0, 0, 2, 0, 1, 4

Offset: 1

Author

Jeffrey Shallit, Apr 17 2020

Keywords

• nonn
• easy

Comments

If the Thue-Morse sequence t(n) = A010060(n) = 1 then i=0 suffices since t(0)=0 != t(n). If t(n)=0 then any 1-bits of i in the low 0-bits of n are the same in i and i+n so still t(i) = t(i+n). The next smallest i is the lowest 1-bit of n (A006519). If the lowest run of 1-bits in n is an odd length then adding this i does not change 1's parity (for example binary n = 0111 becomes i+n = 1000) so that t(i+n) = t(n) = 0 != t(i) = 1. If the lowest run of 1-bits in n is an even length then the second lowest 1-bit of n is the next smallest i and similarly does not change 1's parity of i+n. - Kevin Ryde, Apr 27 2020

Examples

			The first few terms of the Thue-Morse sequence are: 0, 1, 1, 0, 1, 0, 0, 1, 1, 0, 0, 1, 0, 1, 1, 0, 1, 0, 0, 1, 0, 1, 1, 0, 0, 1, 1, 0, 1, 0... . Note that the Thue-Morse sequence has offset 0.
For n = 1, we see that the least i such that i and i + n index different terms is i = 0. Hence a(1) = 0.
For n = 2, the least i such that i and i + n index different terms is also i = 0. Hence a(2) = 0.
For n = 3, i = 0 won't work because Thue-Morse(0) and Thue-Morse(3) are both 0. Nor will i = 1 do because Thue-Morse(1) and Thue-Morse(4) are both 1. With i = 2, we see that Thue-Morse(2) = 1 and Thue-Morse(5) = 0. Hence a(3) = 0.
		

Links

• Michael De Vlieger, Table of n, a(n) for n = 1..10000

Crossrefs

Cf. A010060 (Thue-Morse), A006519 (lowest 1-bit), A089309 (length of lowest run of 1's).

Programs

Mathematica

Array[Block[{i = 0}, While[ThueMorse[i] == ThueMorse[i + #], i++]; i] &, 86] (* Michael De Vlieger, Jun 27 2020 *)

PARI

a(n)=if(n<3,return(0)); my(k); if(n%2==0, k=valuation(n,2); return(a(n>>k)<>2)); \\ Charles R Greathouse IV, Apr 18 2020

PARI

a(n) = if(hammingweight(n)%2,0, my(k=valuation(n,2)); 1 << (k + (valuation((n>>k)+1,2)%2==0))); \\ Kevin Ryde, Apr 27 2020

Formula

a(2*n) = 2*a(n).

a(8*n + 1) = a(4*n + 1) = A010060(n).

a(8*n + 5) = 1 - A010060(n).

a(8*n + 7) = a(2*n + 1).

a(16*n + 3) = a(8*n + 3) = 2 - 2*A010060(n).

a(16*n + 11) = 2*A010060(n).

This system lets you compute a(n) very quickly.

a(n)=0 if A010060(n)=1, otherwise a(n) = A006519(n) or 2*A006519(n) according as A089309(n) odd or even respectively; where A006519 takes the lowest 1-bit of n, and A089309 is the length of the lowest run of 1-bits of n. - Kevin Ryde, Apr 27 2020