A089215 Thue-Morse sequence on the integers.

1, 2, 3, 2, 4, 3, 2, 3, 5, 4, 3, 4, 2, 3, 4, 3, 6, 5, 4, 5, 3, 4, 5, 4, 2, 3, 4, 3, 5, 4, 3, 4, 7, 6, 5, 6, 4, 5, 6, 5, 3, 4, 5, 4, 6, 5, 4, 5, 2, 3, 4, 3, 5, 4, 3, 4, 6, 5, 4, 5, 3, 4, 5, 4, 8, 7, 6, 7, 5, 6, 7, 6, 4, 5, 6, 5, 7, 6, 5, 6, 3, 4, 5, 4, 6, 5, 4, 5, 7, 6, 5, 6, 4, 5, 6, 5, 2, 3, 4, 3, 5, 4, 3, 4, 6

Offset

1,2

Comments

Sequence is S(infinity) where S(1)={1,2} and S(n+1)=S(n)S'(n) where S'(n) is obtained from S(n) by substituting an element x of S(n) with M(n)-x where M(n)=2+Max{S(n)}.

For comparison, the Thue-Morse sequence on alphabet {1,2} is constructed as follows: S(1)={1,2} and S(n+1)=S(n)S'(n) where S'(n) is obtained from S(n) by substituting an element x of S(n) with 3-x.

Links

Table of n, a(n) for n=1..105.

Formula

Sum_{k=1..n} a(k) is asymptotic to C*n*log(n) with C=0.8....

a(n) = A209281(n) + 1. - Kevin Ryde, Jun 25 2022

Example

S(1)={1,2} then M(1)=4 and S'(1)={4-1,4-2}={3,2}. So S(2)={1,2,3,2}. M(2)=5 so S(3)={1,2,3,2}{5-1,5-2,5-3,5-2} and sequence begins 1,2,3,2,4,3,2,3,...

Prog

(PARI) a(n) = n--; my(s=1, h); while((h = n>>s), n=bitxor(n, h); s<<=1); hammingweight(n) + 1; \\ Kevin Ryde, Jun 25 2022

Crossrefs

Cf. A001285, A209281.

Sequence in context: A288535 A105117 A100876 * A238766 A375513 A325239

Adjacent sequences: A089212 A089213 A089214 * A089216 A089217 A089218

Keyword

nonn,easy

Author

Benoit Cloitre, Dec 10 2003

Status

approved