A064990 If A_k denotes the first 3^k terms, then A_0 = 0, A_{k+1} = A_k A_k B_k, where B_k is obtained from A_k by interchanging 0's and 1's.

0, 0, 1, 0, 0, 1, 1, 1, 0, 0, 0, 1, 0, 0, 1, 1, 1, 0, 1, 1, 0, 1, 1, 0, 0, 0, 1, 0, 0, 1, 0, 0, 1, 1, 1, 0, 0, 0, 1, 0, 0, 1, 1, 1, 0, 1, 1, 0, 1, 1, 0, 0, 0, 1, 1, 1, 0, 1, 1, 0, 0, 0, 1, 1, 1, 0, 1, 1, 0, 0, 0, 1, 0, 0, 1, 0, 0, 1, 1, 1, 0, 0, 0, 1, 0, 0, 1, 1, 1, 0, 0, 0, 1, 0, 0, 1, 1, 1, 0

Offset: 0

Author

Michael Gilleland (megilleland(AT)yahoo.com), Oct 31 2001

Keywords

• nonn
• easy
• nice

Comments

Called the Mephisto Waltz sequence (or the Mephisto Waltz infinite word).

May also be obtained by starting with 0 and iterating the morphism 0 -> 001, 1 -> 110.

The sequence is fourth-power free.

The sequence gives A_oo. For the concatenation A_0, A_1, A_2, ... see A134391.

Examples

			Here are A_0 through A_4:
  0
  001
  001001110
  001001110001001110110110001
  001001110001001110110110001001001110001001110110110001110110001110110001001001110
		

References

• J.-P. Allouche and J. Shallit, Automatic Sequences, Cambridge Univ. Press, 2003, p. 25.
• Konrad Jacobs, Invitation to Mathematics, Princeton, 1992; pp. 105-106 and 215.

Links

• Joerg Arndt, Matters Computational (The Fxtbook), section 38.1.2, pp. 729-730
• J. Endrullis, D. Hendriks and J. W. Klop, Degrees of streams.
• Joseph Meleshko, Pascal Ochem, Jeffrey Shallit, and Sonja Linghui Shan, Pseudoperiodic Words and a Question of Shevelev, arXiv:2207.10171 [math.CO], 2022.
• Eric Weisstein's World of Mathematics, Mephisto Waltz Sequence

Crossrefs

Cf. Thue-Morse sequence A010060, A001285. Number of 0's in A_k gives A007051, number of 1's is A003462. See also A064991.

Cf. A134391, A189628.

A285196 is a similar sequence.

Programs

Maple

with(ListTools);
f2:=proc(S) map(x->x+1 mod 2, S); end;
f:=proc(S) global f2;
[op(S), op(S), op(f2(S))]; end;
S:=[0];
for n from 1 to 6 do S:=f(S): od:
S; # N. J. A. Sloane, Apr 30 2017

Mathematica

t = Nest[Flatten[# /. {0->{0,0,1}, 1->{1,1,0}}] &, {0}, 5] (*A064990*)
f[n_] := t[[n]]
Flatten[Position[t, 0]] (* A189658 *)
Flatten[Position[t, 1]] (* A189659 *)
s[n_] := Sum[f[i], {i, 1, n}]; s[0] = 0;
Table[s[n], {n, 1, 120}] (* A189660 *)
(* Clark Kimberling, Apr 25 2011 *)
Nest[ Flatten[# /. # -> {#, #, Abs[# - 1]}] &, {0}, 5]  (* Robert G. Wilson v, Sep 27 2011 *)
SubstitutionSystem[{0->{0,0,1},1->{1,1,0}},{0},{5}][[1]] (* Harvey P. Dale, Jan 25 2022 *)

PARI

a(n) = vecsum(digits(n,3)>>1)%2; \\ Kevin Ryde, Jun 02 2020

Formula

a(3k-2)=a(k), a(3k-1)=a(k), a(3k)=1-a(k) for k>=1, a(0)=0.

Extensions

More terms from Naohiro Nomoto, Nov 29 2001

Corrected by N. J. A. Sloane, Jun 14 2010, at the suggestion of Chris Erickson