cp's OEIS Frontend

A092782 The ternary tribonacci word; also a Rauzy fractal sequence: fixed point of the morphism 1 -> 12, 2 -> 13, 3 -> 1, starting from a(1) = 1.

%I A092782 #104 Jan 05 2025 19:51:37
%S A092782 1,2,1,3,1,2,1,1,2,1,3,1,2,1,2,1,3,1,2,1,1,2,1,3,1,2,1,3,1,2,1,1,2,1,
%T A092782 3,1,2,1,2,1,3,1,2,1,1,2,1,3,1,2,1,1,2,1,3,1,2,1,2,1,3,1,2,1,1,2,1,3,
%U A092782 1,2,1,3,1,2,1,1,2,1,3,1,2,1,2,1,3,1,2,1,1,2,1,3,1,2,1,2,1,3,1,2,1,1,2,1,3
%N A092782 The ternary tribonacci word; also a Rauzy fractal sequence: fixed point of the morphism 1 -> 12, 2 -> 13, 3 -> 1, starting from a(1) = 1.
%C A092782 See A080843 for the {0,1,2} version, which in a sense is the most basic version.
%C A092782 See also A103269 for another version with further references and comments.
%C A092782 Also called a tribonacci word. In the limit the ratios #1's : #2's : #3's are t^2 : t : 1 where t is the tribonacci constant 1.839286755... (A058265). - _Frank M Jackson_, Mar 29 2018
%C A092782 a(n)-1 is the number of trailing 0's in the maximal tribonacci representation of n (A352103). - _Amiram Eldar_, Feb 29 2024
%D A092782 This entry has a fairly complete list of references and links concerning the ternary tribonacci word. - _N. J. A. Sloane_, Aug 17 2018
%D A092782 J.-P. Allouche and J. Shallit, Automatic Sequences, Cambridge Univ. Press, 2003, p. 246.
%D A092782 Michel Rigo, Formal Languages, Automata and Numeration Systems, 2 vols., Wiley, 2014. Mentions this sequence - see "List of Sequences" in Vol. 2.
%H A092782 N. J. A. Sloane, <a href="/A092782/b092782.txt">Table of n, a(n) for n = 1..19513</a>
%H A092782 Pierre Arnoux and Edmund Harriss, <a href="http://www.ams.org/notices/201407/rnoti-p768.pdf">What is a Rauzy Fractal?</a>, Notices Amer. Math. Soc., 61 (No. 7, 2014), 768-770, also p. 704 and front cover.
%H A092782 Scott Balchin and Dan Rust, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL20/Rust/rust3.html">Computations for Symbolic Substitutions</a>, Journal of Integer Sequences, Vol. 20 (2017), Article 17.4.1.
%H A092782 Elena Barcucci, Luc Belanger and Srecko Brlek, <a href="https://web.archive.org/web/2024*/https://www.fq.math.ca/Papers1/42-4/quartbarcucci04_2004.pdf">On tribonacci sequences</a>, Fib. Q., 42 (2004), 314-320. See T on page 315.
%H A092782 Marcy Barge and Jaroslaw Kwapisz, <a href="http://www.jstor.org/stable/40068030">Geometric theory of unimodular Pisot substitutions</a>, Amer. J. Math. 128 (2006), no. 5, 1219--1282. MR2262174 (2007m:37039). See Fig. 18.1. - _N. J. A. Sloane_, Aug 06 2014
%H A092782 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 A092782 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 A092782 David Damanik and Luca 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 A092782 Aldo de Luca and Luca Q. Zamboni, <a href="https://arxiv.org/abs/1505.02309">On prefixal factorizations of words</a>, arXiv:1505.02309 [math.CO], 2015. See Example 2.
%H A092782 Aldo de Luca and Luca Q. Zamboni, <a href="https://doi.org/10.1016/j.ejc.2015.08.007">On prefixal factorizations of words</a>, European Journal of Combinatorics, Volume 52, Part A, 2016, pp. 59-73. See Example 2.
%H A092782 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 A092782 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 A092782 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 A092782 Jacques Justin and Laurent Vuillon, <a href="http://www.numdam.org/item/ITA_2000__34_5_343_0/">Return words in Sturmian and episturmian words</a>, RAIRO-Theoretical Informatics and Applications 34.5 (2000): 343-356. See Example on page 345.
%H A092782 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 A092782 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 A092782 Victor F. Sirvent, <a href="http://dx.doi.org/10.1016/S0893-9659(98)00121-9">Semigroups and the self-similar structure of the flipped tribonacci substitution</a>, Applied Math. Letters, 12 (1999), 25-29. [Contains further related references.]
%H A092782 Victor F. Sirvent, <a href="https://doi.org/10.36045/bbms/1103055617">The common dynamics of the Tribonacci substitutions</a>, Bulletin of the Belgian Mathematical Society-Simon Stevin 7.4 (2000): 571-582.
%H A092782 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 A092782 Ondřej 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) Article 15.3.4.
%H A092782 <a href="/index/Fi#FIXEDPOINTS">Index entries for sequences that are fixed points of mappings</a>.
%F A092782 a(n) = 1 for n in A003144; a(n) = 2 for n in A003145; a(n) = 3 for n in A003146.
%F A092782 a(n) = A080843(n-1) + 1. - _Joerg Arndt_, Sep 14 2013
%e A092782 From _Joerg Arndt_, Sep 14 2013: (Start)
%e A092782 The first few steps of the substitution are
%e A092782 Start: 1
%e A092782 Maps:
%e A092782   1 --> 12
%e A092782   2 --> 13
%e A092782   3 --> 1
%e A092782 -------------
%e A092782 0:   (#=1)
%e A092782   1
%e A092782 1:   (#=2)
%e A092782   12
%e A092782 2:   (#=4)
%e A092782   1213
%e A092782 3:   (#=7)
%e A092782   1213121
%e A092782 4:   (#=13)
%e A092782   1213121121312
%e A092782 5:   (#=24)
%e A092782   121312112131212131211213
%e A092782 6:   (#=44)
%e A092782   12131211213121213121121312131211213121213121
%e A092782 7:   (#=81)
%e A092782   121312112131212131211213121312112131212131211213121121312121312112131213121121312
%e A092782 (End)
%p A092782 f(1):= (1, 2): f(2):= (1, 3): f(3):= (1): A:= [1]:
%p A092782 for i from 1 to 16 do A:= map(f, A) od:
%p A092782 A; # 19513 terms of A092782; A103269; from _N. J. A. Sloane_, Aug 06 2018
%t A092782 Nest[ Flatten[# /. {1 -> {1, 2}, 2 -> {1, 3}, 3 -> 1}] &, {1}, 8] (* _Robert G. Wilson v_, Mar 04 2005 and updated Apr 29 2018 *)
%o A092782 (PARI) w=vector(9,x,[]); w[1]=[1];
%o A092782 for(n=2,9,for(k=1,#w[n-1],m=w[n-1][k];v=[];if(m-1,if(m-2,v=[1],v=[1,3]),v=[1,2]);w[n]=concat(w[n],v)));
%o A092782 w[9] \\ _Gerald McGarvey_, Dec 18 2009
%o A092782 (PARI)
%o A092782 strsub(s, vv, off=0)=
%o A092782 {
%o A092782     my( nl=#vv, r=[], ct=1 );
%o A092782     while ( ct <= #s,
%o A092782         r = concat(r, vv[ s[ct] + (1-off) ] );
%o A092782         ct += 1;
%o A092782     );
%o A092782     return( r );
%o A092782 }
%o A092782 t=[1];  for (k=1, 10, t=strsub( t, [[1,2], [1,3], [1]], 1 ) );  t
%o A092782 \\ _Joerg Arndt_, Sep 14 2013
%o A092782 (PARI) A092782_vec(N,s=[[1,2],[1,3],1],A=[1])={while(#A<N,A=concat(vecextract(s,A)));A} \\ Return at least N terms. - _M. F. Hasler_, Dec 14 2018
%Y A092782 Cf. A003144, A003145, A003146, A100619, A103269, A073058, A245553, A245554, A105083, A352103.
%Y A092782 See A080843 for a {0,1,2} version.
%Y A092782 First differences: A317950.
%K A092782 easy,nonn
%O A092782 1,2
%A A092782 _Philippe Deléham_, Apr 23 2004
%E A092782 Additional references and links added by _N. J. A. Sloane_, Aug 17 2018