A334173 - OEIS

%I #27 Jul 09 2020 07:59:43

%S 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,

%T 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,

%U 0,0,1,8,0,0,2,0,1,2,0,16,0,0,2,0,1,4

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

%C 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

%H Michael De Vlieger, <a href="/A334173/b334173.txt">Table of n, a(n) for n = 1..10000</a>

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

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

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

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

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

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

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

%F 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

%e 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.

%e 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.

%e For n = 2, the least i such that i and i + n index different terms is also i = 0. Hence a(2) = 0.

%e 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.

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

%o (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

%o (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

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

%K nonn,easy

%O 1,3

%A _Jeffrey Shallit_, Apr 17 2020