%I #131 Feb 02 2024 04:18:57

%S 0,1,0,2,0,1,0,0,1,0,2,0,1,0,1,0,2,0,1,0,0,1,0,2,0,1,0,2,0,1,0,0,1,0,

%T 2,0,1,0,1,0,2,0,1,0,0,1,0,2,0,1,0,0,1,0,2,0,1,0,1,0,2,0,1,0,0,1,0,2,

%U 0,1,0,2,0,1,0,0,1,0,2,0,1,0,1,0,2,0,1,0,0,1,0,2,0,1,0,1,0,2,0,1,0,0,1,0,2

%N Tribonacci word: limit S(infinity), where S(0) = 0, S(1) = 0,1, S(2) = 0,1,0,2 and for n >= 0, S(n+3) = S(n+2) S(n+1) S(n).

%C An Arnoux-Rauzy or episturmian word.

%C From _N. J. A. Sloane_, Jul 10 2018: (Start)

%C The initial terms in a form suitable for copying:

%C 0,1,0,2,0,1,0,0,1,0,2,0,1,0,1,0,2,0,1,0,0,1,0,2,0,1,0,2,0,1,0,0,1,0,2,0,1,

%C 0,1,0,2,0,1,0,0,1,0,2,0,1,0,0,1,0,2,0,1,0,1,0,2,0,1,0,0,1,0,2,0,1,0,2,0,1,

%C 0,0,1,0,2,0,1,0,1,0,2,0,1,0,0,1,0,2,0,1,0,1,0,2,0,1,0,0,1,0,2,0,1,0,2,0,1,

%C 0,0,1,0,2,0,1,0,1,0,2,0,1,0,0,1,0,2,0,1,0,0,1,0,2,0,1,0,1,0,2,0,1,0,0,1,0,

%C 2,0,1,0,2,0,1,0,0,1,0,2,0,1,0,1,0,2,0,1,0,0,1,0,2,0,1,0,2,0,1,0,0,1,0,2,0,

%C 1,0,1,0,2,0,1,0,0,1,0,2,0,1,0,0,1,0,2,0,1,0,1,0,2,0,1,0,0,1,0,2,0,1,0,2,0,

%C 1,0,0,1,0,2,0,1,0,1,0,2,0,1,0,0,1,0,2,0,1,0,1,0,2,0,1,0,0,1,0,2,0,1,0,2,0,

%C 1,0,0,1,0,2,0,1,0,1,0,2,0,1,0,0,1,0,2,0,1,0,0,1,0,2,0,1,0,1,0,2,0,1,0,0,1,

%C ...

%C Let TTW(a,b,c) denote this sequence written over the alphabet {a,b,c}. It begins:

%C a,b,a,c,a,b,a,a,b,a,c,a,b,a,b,a,c,a,b,a,a,b,a,c,a,b,a,c,a,b,a,a,b,a,c,a,b,

%C a,b,a,c,a,b,a,a,b,a,c,a,b,a,a,b,a,c,a,b,a,b,a,c,a,b,a,a,b,a,c,a,b,a,c,a,b,

%C a,a,b,a,c,a,b,a,b,a,c,a,b,a,a,b,a,c,a,b,a,b,a,c,a,b,a,a,b,a,c,a,b,a,c,a,b,

%C a,a,b,a,c,a,b,a,b,a,c,a,b,a,a,b,a,c,a,b,a,a,b,a,c,a,b,a,b,a,c,a,b,a,a,b,a,

%C c,a,b,a,c,a,b,a,a,b,a,c,a,b,a,b,a,c,a,b,a,a,b,a,c,a,b,a,c,a,b,a,a,b,a,c,a,

%C b,a,b,a,c,a,b,a,a,b,a,c,a,b,a,a,b,a,c,a,b,a,b,a,c,a,b,a,a,b,a,c,a,b,a,c,a,

%C b,a,a,b,a,c,a,b,a,b,a,c,a,b,a,a,b,a,c,a,b,a,b,a,c,a,b,a,a,b,a,c,a,b,a,c,a,

%C b,a,a,b,a,c,a,b,a,b,a,c,a,b,a,a,b,a,c,a,b,a,a,b,a,c,a,b,a,b,a,c,a,b,a,a,b,

%C ... (End)

%C From _Wolfdieter Lang_, Aug 14 2018: (Start)

%C The substitution sequence 0 -> 0, 1; 1-> 0, 2; 2 -> 0 read as an irregular triangle with rows l >= 1 and length T(l+2), with the tribonacci numbers T = A000073, leads to the tribonacci tree TriT with level TriT(l) for l >= 1 given by a(0), a(1), ..., a(T(l+2)-1).

%C E.g., l = 4: 0 1 0 2 0 1 0 with T(6) = 7 leaves (nodes). See the example below.

%C This tree can be used to find the tribonacci representation of nonnegative n given in A278038, call it ZTri(n) (Z for generalized Zeckendorf), by replacing every 2 by 1, and reading from bottom to top, omitting the final 0, except for n = 0 which is represented by 0. See the example below. (End)

%D The entry A092782 has a more complete list of references and links. - _N. J. A. Sloane_, Aug 17 2018

%D J.-P. Allouche and J. Shallit, Automatic Sequences, Cambridge Univ. Press, 2003, p. 246.

%H N. J. A. Sloane, <a href="/A080843/b080843.txt">Table of n, a(n) for n = 0..20000</a>

%H Jean Berstel and J. Karhumaki, <a href="http://www-igm.univ-mlv.fr/~berstel/Articles/2003TutorialCoWdec03.pdf">Combinatorics on words - a tutorial</a>, Bull. EATCS, #79 (2003), pp. 178-228.

%H Nataliya Chekhova, Pascal Hubert, and Ali Messaoudi, <a href="http://www.numdam.org/item?id=JTNB_2001__13_2_371_0">Propriétés combinatoires, ergodiques et arithmétiques de la substitution de Tribonacci</a>, Journal de théorie des nombres de Bordeaux, 13.2 (2001): 371-394.

%H D. Damanik and L. Q. Zamboni, <a href="https://arxiv.org/abs/math/0208137">Arnoux-Rauzy subshifts: linear recurrence, powers and palindromes</a>, arXiv:math/0208137 [math.CO], 2002.

%H F. Michel Dekking, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL19/Dekking/dekk4.html">Morphisms, Symbolic Sequences, and Their Standard Forms</a>, Journal of Integer Sequences, Vol. 19 (2016), Article 16.1.1.

%H F. Michel Dekking, Jeffrey Shallit, and N. J. A. Sloane, <a href="https://www.combinatorics.org/ojs/index.php/eljc/article/view/v27i1p52/8039">Queens in exile: non-attacking queens on infinite chess boards</a>, Electronic J. Combin., 27:1 (2020), #P1.52.

%H Eric Duchêne and Michel Rigo, <a href="http://dx.doi.org/10.1051/ita:2007039">A morphic approach to combinatorial games: the Tribonacci case</a>. RAIRO - Theoretical Informatics and Applications, 42, 2008, pp 375-393. doi:10.1051/ita:2007039. [Also available <a href="http://archive.numdam.org/item/ITA_2008__42_2_375_0">here</a>]

%H Robbert Fokkink and Dan Rust, <a href="https://doi.org/10.1007/s00182-022-00824-1">Queen reflections: a modification of Wythoff Nim</a>, Int'l J. Game Theory (2022).

%H Wolfdieter Lang, <a href="https://arxiv.org/abs/1810.09787">The Tribonacci and ABC Representations of Numbers are Equivalent</a>, arXiv:1810.09787v1 [math.NT], 2018.

%H 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 Aayush Rajasekaran, Narad Rampersad and Jeffrey Shallit, <a href="https://dx.doi.org/10.1007/978-3-319-66396-8_3">Overpals, Underlaps, and Underpals</a>, In: Brlek S., Dolce F., Reutenauer C., Vandomme É. (eds) Combinatorics on Words, WORDS 2017, Lecture Notes in Computer Science, vol 10432.

%H Gérard Rauzy, <a href="https://doi.org/10.24033/bsmf.1957">Nombres algébriques et substitutions</a>, Bull. Soc. Math. France 110.2 (1982): 147-178. See page 148.

%H Bo Tan and Zhi-Ying Wen, <a href="http://dx.doi.org/10.1016/j.ejc.2006.07.007">Some properties of the Tribonacci sequence</a>, European Journal of Combinatorics, 28 (2007) 1703-1719.

%H O. Turek, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL18/Turek/turek3.html">Abelian Complexity Function of the Tribonacci Word</a>, J. Int. Seq. 18 (2015) # 15.3.4

%H <a href="/index/Fi#FIXEDPOINTS">Index entries for sequences that are fixed points of mappings</a>

%F Fixed point of morphism 0 -> 0, 1; 1 -> 0, 2; 2 -> 0.

%F a(n) = A092782(n+1) - 1. - _Joerg Arndt_, Sep 14 2013

%e From _Joerg Arndt_, Mar 12 2013: (Start)

%e The first few steps of the substitution are

%e Start: 0

%e Rules:

%e 0 --> 01

%e 1 --> 02

%e 2 --> 0

%e -------------

%e 0: (#=1)

%e 0

%e 1: (#=2)

%e 01

%e 2: (#=4)

%e 0102

%e 3: (#=7)

%e 0102010

%e 4: (#=13)

%e 0102010010201

%e 5: (#=24)

%e 010201001020101020100102

%e 6: (#=44)

%e 01020100102010102010010201020100102010102010

%e 7: (#=81)

%e 010201001020101020100102010201001020101020100102010010201010201001020102010010201

%e (End)

%e From _Wolfdieter Lang_, Aug 14 2018: (Start)

%e The levels l of the tree TriT begin (the branches (edges) have been omitted):

%e Substitution rule: 0 -> 0 1; 1 -> 0 2; 2 -> 0.

%e l=1: 0

%e l=2: 0 1

%e l=3: 0 1 0 2

%e l=4: 0 1 0 2 0 1 0

%e l=5: 0 1 0 2 0 1 0 0 1 0 2 0 1

%e ...

%e ----------------------------------------------------------------------------------

%e n = 0 1 2 3 4 5 6 7 8 9 10 11 12

%e The tribonacci representation of n >= 0 (A278038; here at level 5 for n = 0.. 12) is obtained by reading from bottom to top (along the branches not shown) replacing 2 with 1, omitting the last 0 except for n = 0.

%e 0 1 0 1 0 1 0 0 1 0 1 0 1

%e 1 1 0 0 1 0 0 1 1 0 0

%e 1 1 1 0 0 0 0 1 1

%e 1 1 1 1 1 1

%e E.g., ZTri(9) = A278038(9) = 1010. (End)

%p M:=17; S[1]:=`0`; S[2]:=`01`; S[3]:=`0102`;

%p for n from 4 to M do S[n]:=cat(S[n-1], S[n-2], S[n-3]); od:

%p t0:=S[M]: l:=length(t0); for i from 1 to l do lprint(i,substring(t0,i..i)); od:

%p # _N. J. A. Sloane_, Nov 01 2006

%p # A version that uses the letters a,b,c:

%p M:=10; B[1]:=`a`; B[2]:=`ab`; B[3]:=`abac`;

%p for n from 4 to M do B[n]:=cat(B[n-1], B[n-2], B[n-3]); od:

%p B[10]; # _N. J. A. Sloane_, Oct 30 2018

%t Nest[Flatten[ # /. {0 -> {0, 1}, 1 -> {0, 2}, 2 -> {0}}] &, {0}, 8] (* updated by _Robert G. Wilson v_, Nov 07 2010 *)

%t SubstitutionSystem[{0->{0,1},1->{0,2},2->{0}},{0},{8}]//Flatten (* _Harvey P. Dale_, Nov 21 2021 *)

%o (PARI)

%o strsub(s, vv, off=0)=

%o {

%o my( nl=#vv, r=[], ct=1 );

%o while ( ct <= #s,

%o r = concat(r, vv[ s[ct] + (1-off) ] );

%o ct += 1;

%o );

%o return( r );

%o }

%o t=[0]; for (k=1, 10, t=strsub( t, [[0,1], [0,2], [0]], 0 ) ); t

%o \\ _Joerg Arndt_, Sep 14 2013

%Y Cf. A003849 (the Fibonacci word), A092782.

%Y See A092782 for a version over the alphabet {1,2,3}.

%Y See A278045 for another construction.

%Y Cf. A000073, A278038.

%Y First differences: A317950. Partial sums: A319198.

%K nonn,easy

%O 0,4

%A _N. J. A. Sloane_, Mar 29 2003

%E More terms from Antonio G. Astudillo (afg_astudillo(AT)lycos.com), Apr 06 2003