OFFSET
1,3
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
LINKS
Michael De Vlieger, Table of n, a(n) for n = 1..10000
FORMULA
EXAMPLE
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.
MATHEMATICA
Array[Block[{i = 0}, While[ThueMorse[i] == ThueMorse[i + #], i++]; i] &, 86] (* Michael De Vlieger, Jun 27 2020 *)
PROG
(PARI) a(n)=if(n<3, return(0)); my(k); if(n%2==0, k=valuation(n, 2); return(a(n>>k)<<k)); k=n%4; if(k==1, return(1-hammingweight(n)%2)); k=n%8; if(k==3, 2-hammingweight(n)%2*2, a(n>>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
CROSSREFS
KEYWORD
nonn,easy
AUTHOR
Jeffrey Shallit, Apr 17 2020
STATUS
approved