# Greetings from The On-Line Encyclopedia of Integer Sequences! http://oeis.org/

Search: id:a080843
Showing 1-1 of 1

%I A080843 #131 Feb 02 2024 04:18:57
%S A080843 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 A080843 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 A080843 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 A080843 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 A080843 An Arnoux-Rauzy or episturmian word.
%C A080843 From _N. J. A. Sloane_, Jul 10 2018: (Start)
%C A080843 The initial terms in a form suitable for copying:
%C A080843 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 A080843 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 A080843 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 A080843 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 A080843 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 A080843 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 A080843 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 A080843 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 A080843 ...
%C A080843 Let TTW(a,b,c) denote this sequence written over the alphabet {a,b,c}. It begins:
%C A080843 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 A080843 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 A080843 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 A080843 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 A080843 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 A080843 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 A080843 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 A080843 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 A080843 ... (End)
%C A080843 From _Wolfdieter Lang_, Aug 14 2018: (Start)
%C A080843 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 A080843   E.g., l = 4:  0 1  0 2  0 1  0 with T(6) = 7 leaves (nodes). See the example below.
%C A080843 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 A080843 The entry A092782 has a more complete list of references and links. - _N. J. A. Sloane_, Aug 17 2018
%D A080843 J.-P. Allouche and J. Shallit, Automatic Sequences, Cambridge Univ. Press, 2003, p. 246.
%H A080843 N. J. A. Sloane, <a href="/A080843/b080843.txt">Table of n, a(n) for n = 0..20000</a>
%H A080843 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 A080843 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 A080843 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 A080843 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 A080843 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 A080843 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 A080843 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 A080843 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 A080843 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 A080843 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 A080843 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 A080843 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 A080843 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 A080843 <a href="/index/Fi#FIXEDPOINTS">Index entries for sequences that are fixed points of mappings</a>
%F A080843 Fixed point of morphism 0 -> 0, 1; 1 -> 0, 2; 2 -> 0.
%F A080843 a(n) = A092782(n+1) - 1. - _Joerg Arndt_, Sep 14 2013
%e A080843 From _Joerg Arndt_, Mar 12 2013: (Start)
%e A080843 The first few steps of the substitution are
%e A080843 Start: 0
%e A080843 Rules:
%e A080843   0 --> 01
%e A080843   1 --> 02
%e A080843   2 --> 0
%e A080843 -------------
%e A080843 0:   (#=1)
%e A080843   0
%e A080843 1:   (#=2)
%e A080843   01
%e A080843 2:   (#=4)
%e A080843   0102
%e A080843 3:   (#=7)
%e A080843   0102010
%e A080843 4:   (#=13)
%e A080843   0102010010201
%e A080843 5:   (#=24)
%e A080843   010201001020101020100102
%e A080843 6:   (#=44)
%e A080843   01020100102010102010010201020100102010102010
%e A080843 7:   (#=81)
%e A080843   010201001020101020100102010201001020101020100102010010201010201001020102010010201
%e A080843 (End)
%e A080843 From _Wolfdieter Lang_, Aug 14 2018: (Start)
%e A080843 The levels l of the tree TriT begin (the branches (edges) have been omitted):
%e A080843 Substitution rule: 0 -> 0 1; 1 -> 0 2; 2 -> 0.
%e A080843 l=1:                                 0
%e A080843 l=2:                  0                                 1
%e A080843 l=3:             0             1                  0             2
%e A080843 l=4:         0      1       0     2          0       1          0
%e A080843 l=5:      0    1  0   2   0   1   0        0   1   0   2      0    1
%e A080843 ...
%e A080843 ----------------------------------------------------------------------------------
%e A080843 n =       0    1  2   3   4   5   6        7   8   9  10     11   12
%e A080843 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 A080843           0    1  0   1   0   1   0        0   1   0  1      0    1
%e A080843                   1   1   0   0   1        0   0   1  1      0    0
%e A080843                           1   1   1        0   0   0  0      1    1
%e A080843                                            1   1   1  1      1    1
%e A080843 E.g., ZTri(9) = A278038(9) = 1010. (End)
%p A080843 M:=17; S[1]:=`0`; S[2]:=`01`; S[3]:=`0102`;
%p A080843 for n from 4 to M do S[n]:=cat(S[n-1], S[n-2], S[n-3]); od:
%p A080843 t0:=S[M]: l:=length(t0); for i from 1 to l do lprint(i,substring(t0,i..i)); od:
%p A080843 # _N. J. A. Sloane_, Nov 01 2006
%p A080843 # A version that uses the letters a,b,c:
%p A080843 M:=10; B[1]:=`a`; B[2]:=`ab`; B[3]:=`abac`;
%p A080843 for n from 4 to M do B[n]:=cat(B[n-1], B[n-2], B[n-3]); od:
%p A080843 B[10]; # _N. J. A. Sloane_, Oct 30 2018
%t A080843 Nest[Flatten[ # /. {0 -> {0, 1}, 1 -> {0, 2}, 2 -> {0}}] &, {0}, 8] (* updated by _Robert G. Wilson v_, Nov 07 2010 *)
%t A080843 SubstitutionSystem[{0->{0,1},1->{0,2},2->{0}},{0},{8}]//Flatten (* _Harvey P. Dale_, Nov 21 2021 *)
%o A080843 (PARI)
%o A080843 strsub(s, vv, off=0)=
%o A080843 {
%o A080843     my( nl=#vv, r=[], ct=1 );
%o A080843     while ( ct <= #s,
%o A080843         r = concat(r, vv[ s[ct] + (1-off) ] );
%o A080843         ct += 1;
%o A080843     );
%o A080843     return( r );
%o A080843 }
%o A080843 t=[0];  for (k=1, 10, t=strsub( t, [[0,1], [0,2], [0]], 0 ) );  t
%o A080843 \\ _Joerg Arndt_, Sep 14 2013
%Y A080843 Cf. A003849 (the Fibonacci word), A092782.
%Y A080843 See A092782 for a version over the alphabet {1,2,3}.
%Y A080843 See A278045 for another construction.
%Y A080843 Cf. A000073, A278038.
%Y A080843 First differences: A317950. Partial sums: A319198.
%K A080843 nonn,easy
%O A080843 0,4
%A A080843 _N. J. A. Sloane_, Mar 29 2003
%E A080843 More terms from Antonio G. Astudillo (afg_astudillo(AT)lycos.com), Apr 06 2003

# Content is available under The OEIS End-User License Agreement: http://oeis.org/LICENSE