A156595 Fixed point of the morphism 0->011, 1->010.

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

Offset: 0

Author

Alexis Monnerot-Dumaine, Feb 10 2009

Keywords

• easy
• nice
• nonn

Comments

Start with 0 and apply the morphism 0->011 and 1->010 repeatedly.

This sequence draws the Sierpinski gasket, when iterating the following odd-even drawing rule: If "1" then draw a segment forward, if "0" then draw a segment forward and turn 120 degrees right if in odd position or left if in even position.

From Dimitri Hendriks, Jun 29 2010: (Start)

This sequence is the first difference of the Mephisto Waltz A064990, i.e., a(n) = A064990(n) + A064990(n+1), where '+' is addition modulo 2.

This sequence can also be generated as a Toeplitz word: First consider the periodic word 0,1,$,0,1,$,0,1,$,... and then fill the gaps $ by the bitwise negation of the sequence itself: 0,1,1,0,1,0,0,1,0,.... See the Allouche/Bacher reference for a precise definition of Toeplitz sequences. (End)

From Joerg Arndt, Jan 21 2013: (Start)

Identical to the morphism 0-> 011010010, 1->011010011 given on p. 100 of the Fxtbook (see link), because 0 -> 011 -> 011010010 and 1 -> 010 -> 011010011.

This sequence gives the turns (by 120 degrees) of the R9-dragon curve (displayed on p. 101) which can be rendered as follows:

[Init] Set n=0 and direction=0.

[Draw] Draw a unit line (in the current direction). Turn left/right if a(n) is zero/nonzero respectively.

[Next] Set n=n+1 and goto (draw).

(End)

Examples

			0 -> 0,1,1 -> 0,1,1,0,1,0,0,1,0 -> ...
		

References

• M. Lothaire, Combinatorics on words.

Links

• J.-P. Allouche and R. Bacher, Toeplitz Sequences, Paperfolding, Towers of Hanoi, and Progression-Free Sequences of Integers, L'Enseignement Mathématique, volume 38, pages 315-327, 1992.
• Joerg Arndt, Matters Computational (The Fxtbook) (section 1.31.5 "Dragon curves based on radix-R counting", pp. 95-101, image on p. 101).
• Gabriele Fici and Jeffrey Shallit, Properties of a Class of Toeplitz Words, arXiv:2112.12125 [cs.FL], 2021.
• Kevin Ryde, Iterations of the Terdragon Curve, see index "AltTurnRpred" with AltTurnRpred(n) = a(n-1).
• Index entries for sequences that are fixed points of mappings

Crossrefs

Cf. A278996 (indices of 0's), A278997 (indices of 1's), A189717 (partial sums).

Cf. A189628 (morphisms guide).

Cf. A307672 (draws curves that align with the Sierpinski gasket).

Programs

Mathematica

Nest[ Flatten[ # /. {0 -> {0, 1, 1}, 1 -> {0, 1, 0}}] &, {0}, 10]
SubstitutionSystem[{0->{0,1,1},1->{0,1,0}},0,{5}][[1]] (* Harvey P. Dale, Jan 15 2022 *)

Python

from sympy import integer_log
def A156595(n): return sum(((m:=(n+1)//9**i)-2)//9+(m-3)//9+(m-5)//9+(m-8)//9+4 for i in range(integer_log(n+1,9)[0]+1))-sum(((m:=n//9**i)-2)//9+(m-3)//9+(m-5)//9+(m-8)//9+4 for i in range(integer_log(n,9)[0]+1)) if n else 0 # Chai Wah Wu, Feb 16 2025

Formula

a(3k-2)=0, a(3k-1)=1, a(3k)=1-a(k) for k>=1, a(0)=0. - Clark Kimberling, Apr 28 2011