cp's OEIS Frontend

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.

%I A064990 #47 Aug 19 2025 07:06:27
%S A064990 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,
%T A064990 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,
%U A064990 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
%N 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.
%C A064990 Called the Mephisto Waltz sequence (or the Mephisto Waltz infinite word).
%C A064990 May also be obtained by starting with 0 and iterating the morphism 0 -> 001, 1 -> 110.
%C A064990 The sequence is fourth-power free.
%C A064990 The sequence gives A_oo. For the concatenation A_0, A_1, A_2, ... see A134391.
%D A064990 J.-P. Allouche and J. Shallit, Automatic Sequences, Cambridge Univ. Press, 2003, p. 25.
%D A064990 Konrad Jacobs, Invitation to Mathematics, Princeton, 1992; pp. 105-106 and 215.
%H A064990 Joerg Arndt, <a href="http://www.jjj.de/fxt/#fxtbook">Matters Computational (The Fxtbook)</a>, section 38.1.2, pp. 729-730
%H A064990 J. Endrullis, D. Hendriks and J. W. Klop, <a href="http://joerg.endrullis.de/assets/papers/streams-degrees-2011.pdf">Degrees of streams</a>.
%H A064990 Joseph Meleshko, Pascal Ochem, Jeffrey Shallit, and Sonja Linghui Shan, <a href="https://arxiv.org/abs/2207.10171">Pseudoperiodic Words and a Question of Shevelev</a>, arXiv:2207.10171 [math.CO], 2022.
%H A064990 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/MephistoWaltzSequence.html">Mephisto Waltz Sequence</a>
%F A064990 a(3k-2)=a(k), a(3k-1)=a(k), a(3k)=1-a(k) for k>=1, a(0)=0.
%e A064990 Here are A_0 through A_4:
%e A064990   0
%e A064990   001
%e A064990   001001110
%e A064990   001001110001001110110110001
%e A064990   001001110001001110110110001001001110001001110110110001110110001110110001001001110
%p A064990 with(ListTools);
%p A064990 f2:=proc(S) map(x->x+1 mod 2, S); end;
%p A064990 f:=proc(S) global f2;
%p A064990 [op(S), op(S), op(f2(S))]; end;
%p A064990 S:=[0];
%p A064990 for n from 1 to 6 do S:=f(S): od:
%p A064990 S; # _N. J. A. Sloane_, Apr 30 2017
%t A064990 t = Nest[Flatten[# /. {0->{0,0,1}, 1->{1,1,0}}] &, {0}, 5] (*A064990*)
%t A064990 f[n_] := t[[n]]
%t A064990 Flatten[Position[t, 0]] (* A189658 *)
%t A064990 Flatten[Position[t, 1]] (* A189659 *)
%t A064990 s[n_] := Sum[f[i], {i, 1, n}]; s[0] = 0;
%t A064990 Table[s[n], {n, 1, 120}] (* A189660 *)
%t A064990 (* _Clark Kimberling_, Apr 25 2011 *)
%t A064990 Nest[ Flatten[# /. # -> {#, #, Abs[# - 1]}] &, {0}, 5]  (* _Robert G. Wilson v_, Sep 27 2011 *)
%t A064990 SubstitutionSystem[{0->{0,0,1},1->{1,1,0}},{0},{5}][[1]] (* _Harvey P. Dale_, Jan 25 2022 *)
%o A064990 (PARI) a(n) = vecsum(digits(n,3)>>1)%2; \\ _Kevin Ryde_, Jun 02 2020
%Y A064990 Cf. Thue-Morse sequence A010060, A001285. Number of 0's in A_k gives A007051, number of 1's is A003462. See also A064991.
%Y A064990 Cf. A134391, A189628.
%Y A064990 A285196 is a similar sequence.
%K A064990 nonn,easy,nice
%O A064990 0,1
%A A064990 Michael Gilleland (megilleland(AT)yahoo.com), Oct 31 2001
%E A064990 More terms from _Naohiro Nomoto_, Nov 29 2001
%E A064990 Corrected by _N. J. A. Sloane_, Jun 14 2010, at the suggestion of Chris Erickson