|
| |
|
|
A334173
|
|
Least i such that i-th term of Thue-Morse sequence (A010060) differs from (i + n)-th term.
|
|
1
|
|
|
|
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
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
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
|
|
|
|
FORMULA
|
a(2*n) = 2*a(n).
a(8*n + 1) = a(4*n + 1) = A010060(n).
a(8*n + 7) = a(2*n + 1).
a(16*n + 3) = a(8*n + 3) = 2 - 2*A010060(n).
This system lets you compute a(n) very quickly.
|
|
|
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
|
|
|
|
STATUS
|
approved
|
| |
|
|
