|
%I #102 Feb 29 2024 01:52:14
%S 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 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 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 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 See A080843 for the {0,1,2} version, which in a sense is the most basic version.
%C See also A103269 for another version with further references and comments.
%C 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 a(n)-1 is the number of trailing 0's in the maximal tribonacci representation of n (A352103). - _Amiram Eldar_, Feb 29 2024
%D This entry has a fairly complete list of references and links concerning the ternary tribonacci word. - _N. J. A. Sloane_, Aug 17 2018
%D J.-P. Allouche and J. Shallit, Automatic Sequences, Cambridge Univ. Press, 2003, p. 246.
%D Michel Rigo, Formal Languages, Automata and Numeration Systems, 2 vols., Wiley, 2014. Mentions this sequence - see "List of Sequences" in Vol. 2.
%H N. J. A. Sloane, <a href="/A092782/b092782.txt">Table of n, a(n) for n = 1..19513</a>
%H 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 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 Elena Barcucci, Luc Belanger and Srecko Brlek, <a href="http://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 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 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 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 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 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 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 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 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 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 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 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 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 <a href="/index/Fi#FIXEDPOINTS">Index entries for sequences that are fixed points of mappings</a>.
%F a(n) = 1 for n in A003144; a(n) = 2 for n in A003145; a(n) = 3 for n in A003146.
%F a(n) = A080843(n-1) + 1. - _Joerg Arndt_, Sep 14 2013
%e From _Joerg Arndt_, Sep 14 2013: (Start)
%e The first few steps of the substitution are
%e Start: 1
%e Maps:
%e 1 --> 12
%e 2 --> 13
%e 3 --> 1
%e -------------
%e 0: (#=1)
%e 1
%e 1: (#=2)
%e 12
%e 2: (#=4)
%e 1213
%e 3: (#=7)
%e 1213121
%e 4: (#=13)
%e 1213121121312
%e 5: (#=24)
%e 121312112131212131211213
%e 6: (#=44)
%e 12131211213121213121121312131211213121213121
%e 7: (#=81)
%e 121312112131212131211213121312112131212131211213121121312121312112131213121121312
%e (End)
%p f(1):= (1, 2): f(2):= (1, 3): f(3):= (1): A:= [1]:
%p for i from 1 to 16 do A:= map(f, A) od:
%p A; # 19513 terms of A092782; A103269; from _N. J. A. Sloane_, Aug 06 2018
%t 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 (PARI) w=vector(9,x,[]); w[1]=[1];
%o 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 w[9] \\ _Gerald McGarvey_, Dec 18 2009
%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=[1]; for (k=1, 10, t=strsub( t, [[1,2], [1,3], [1]], 1 ) ); t
%o \\ _Joerg Arndt_, Sep 14 2013
%o (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 Cf. A003144, A003145, A003146, A100619, A103269, A073058, A245553, A245554, A105083, A352103.
%Y See A080843 for a {0,1,2} version.
%Y First differences: A317950.
%K easy,nonn
%O 1,2
%A _Philippe Deléham_, Apr 23 2004
%E Additional references and links added by _N. J. A. Sloane_, Aug 17 2018
|
