|
%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
|
