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,1

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.

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

Table of n, a(n) for n=0..98.

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

Formula

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

Example

Here are A_0 through A_5:
0
001
001001110
001001110001001110110110001
001001110001001110110110001001001110001001110110110001110110001110110001001001110
001001110001001110110110001001001110001001110110110001110110001110110001001001110\
00100111000100111011011000100100111000100111011011000111011000111011000100100111\
0110110001110110001001001110110110001110110001001001110001001110001001110110110001

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*)
(* by 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 *)

Prog

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

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.

Sequence in context: A106138 A273129 A288936 * A284388 A289174 A059125

Adjacent sequences: A064987 A064988 A064989 * A064991 A064992 A064993

Keyword

nonn,easy,nice

Author

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

Extensions

More terms from Naohiro Nomoto, Nov 29 2001

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

Status

approved