A071858 (Number of 1's in binary expansion of n) mod 3.

0, 1, 1, 2, 1, 2, 2, 0, 1, 2, 2, 0, 2, 0, 0, 1, 1, 2, 2, 0, 2, 0, 0, 1, 2, 0, 0, 1, 0, 1, 1, 2, 1, 2, 2, 0, 2, 0, 0, 1, 2, 0, 0, 1, 0, 1, 1, 2, 2, 0, 0, 1, 0, 1, 1, 2, 0, 1, 1, 2, 1, 2, 2, 0, 1, 2, 2, 0, 2, 0, 0, 1, 2, 0, 0, 1, 0, 1, 1, 2, 2, 0, 0, 1, 0, 1, 1, 2, 0, 1, 1, 2, 1, 2, 2, 0, 2, 0, 0, 1, 0, 1, 1, 2, 0

Offset: 0

Author

Benoit Cloitre, Jun 09 2002

Keywords

• nonn
• easy

Comments

This is the generalized Thue-Morse sequence t_3 (Allouche and Shallit, p. 335).

Ternary sequence which is a fixed point of the morphism 0 -> 01, 1 -> 12, 2 -> 20.

Sequence is T^(oo)(0) where T is the operator acting on any word on alphabet {0,1,2} by inserting 1 after 0, 2 after 1 and 0 after 2. For instance T(001)=010112, T(120)=122001. - Benoit Cloitre, Mar 02 2009

References

• J.-P. Allouche and J. Shallit, Automatic Sequences, Cambridge Univ. Press, 2003.

Links

• G. C. Greubel, Table of n, a(n) for n = 0..10000
• Jin Chen, Zhixiong Wen, Wen Wu, On the additive complexity of a Thue-Morse like sequence, arXiv:1802.03610 [math.CO], 2018.
• Index entries for sequences that are fixed points of mappings

Crossrefs

Cf. A000120, A010872.

Cf. A010060, A001285, A010059, A048707, A096271, A100619, A179868.

See A245555 for another version.

Programs

Mathematica

f[n_] := Mod[ Count[ IntegerDigits[n, 2], 1], 3]; Table[ f[n], {n, 0, 104}] (* Or *)
Nest[ Flatten[ # /. {0 -> {0, 1}, 1 -> {1, 2}, 2 -> {2, 0}}] &, {0}, 7] (* Robert G. Wilson v Mar 03 2005, modified May 17 2014 *)
Table[Mod[DigitCount[n,2,1],3],{n,0,110}] (* Harvey P. Dale, Jul 01 2015 *)

PARI

for(n=1,200,print1(sum(i=1,length(binary(n)), component(binary(n),i))%3,","))

PARI

map(d)=if(d==2,[2,0],if(d==1,[1,2],[0,1]))
{m=53;v=[];w=[0];while(v!=w,v=w;w=[];for(n=1,min(m,length(v)),w=concat(w,map(v[n]))));for(n=1,2*m,print1(v[n],","))} \\ Klaus Brockhaus, Jun 23 2004

Formula

a(n) = A010872(A000120(n)).

Recurrence: a(2*n) = a(n), a(2*n+1) = (a(n)+1) mod 3.

a(n) = A000695(n) mod 3. - John M. Campbell, Jul 16 2016

Extensions

Edited by Ralf Stephan, Dec 11 2004