A100619 -id:A100619 - cp's OEIS frontend

A113535 Ascending descending base exponent transform of the tribonacci substitution (A100619).

1, 3, 8, 19, 32, 9, 11, 16, 26, 19, 29, 24, 47, 70, 28, 31, 58, 89, 35, 50, 65, 108, 65, 51, 52, 90, 101, 82, 101, 88, 122, 63, 81, 92, 153, 110, 89, 125, 110, 92, 101, 155, 90, 127, 196, 142, 87, 138, 207, 112, 112, 135, 217, 150, 124, 115, 204, 245, 139, 158, 189, 268, 121, 155, 154

Offset: 1

Jonathan Vos Post, Jan 13 2006

Sirvent comments that in spite of the similarity of this map to the one in A092782, the two sequences have very different properties. They have different complexities, different Rauzy fractals, etc.

			a(1) = A100619(1)^A100619(1) = 1^1 = 1.
a(2) = A100619(1)^A100619(2) + A100619(2)^A100619(1) = 1^2 + 2^1 = 3.
a(3) = 1^3 + 2^2 + 3^1 = 8.
a(4) = 1^1 + 2^3 + 3^2 + 1^1 = 19.
a(5) = 1^1 + 2^1 + 3^3 + 1^2 + 1^1 = 32.
a(6) = 1^1 + 2^1 + 3^1 + 1^3 + 1^2 + 1^1 = 9.
a(7) = 1^2 + 2^1 + 3^1 + 1^1 + 1^3 + 1^2 + 2^1 = 11.
a(8) = 1^1 + 2^2 + 3^1 + 1^1 + 1^1 + 1^3 + 2^2 + 1^1 = 16.
a(9) = 1^1 + 2^1 + 3^2 + 1^1 + 1^1 + 1^1 + 2^3 + 1^2 + 2^1 = 26.
a(10) = 1^1 + 2^2 + 3^1 + 1^2 + 1^1 + 1^1 + 2^1 + 1^3 + 2^2 + 1^1 = 19.
a(11) = 1^2 + 2^1 + 3^2 + 1^1 + 1^2 + 1^1 + 2^1 + 1^1 + 2^3 + 1^2 + 2^1 = 29.
a(12) = 1^3 + 2^2 + 3^1 + 1^2 + 1^1 + 1^2 + 2^1 + 1^1 + 2^1+ 1^3 + 2^2 + 3^1 = 24.

G. C. Greubel, Table of n, a(n) for n = 1..500
V. F. Sirvent, Semigroups and the self-similar structure of the flipped tribonacci substitution, Applied Math. Letters, 12 (1999), 25-29. [Contains many further references.]

Cf. A100619, A092782, A103269, A113320, A005408, A113122, A113153, A113154, A113336, A113271, A113258, A113257, A113231, A087316, A113208, A113498.

A100619:= Nest[Function[l, {Flatten[(l /. {1 -> {1, 2}, 2 -> {3, 1}, 3 -> {1}})]}], {1}, 8][[1]]; Table[Sum[(A100619[[k]])^(A100619[[n-k+1]]), {k, 1, n}], {n, 1, 100}] (* G. C. Greubel, May 18 2017 *)

a(n) = Sum_{k=1..n} A100619(k)^(A100619(n-k-1)). - G. C. Greubel, May 18 2017

Terms a(13) to a(50) from G. C. Greubel, May 18 2017

Terms a(51) onward added by G. C. Greubel, Jan 03 2019

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.

Original entry on oeis.org

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

Offset: 1

Philippe Deléham, Apr 23 2004

See A080843 for the {0,1,2} version, which in a sense is the most basic version.
See also A103269 for another version with further references and comments.
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
a(n)-1 is the number of trailing 0's in the maximal tribonacci representation of n (A352103). - Amiram Eldar, Feb 29 2024

			From _Joerg Arndt_, Sep 14 2013: (Start)
The first few steps of the substitution are
Start: 1
Maps:
  1 --> 12
  2 --> 13
  3 --> 1
-------------
0:   (#=1)
  1
1:   (#=2)
  12
2:   (#=4)
  1213
3:   (#=7)
  1213121
4:   (#=13)
  1213121121312
5:   (#=24)
  121312112131212131211213
6:   (#=44)
  12131211213121213121121312131211213121213121
7:   (#=81)
  121312112131212131211213121312112131212131211213121121312121312112131213121121312
(End)

This entry has a fairly complete list of references and links concerning the ternary tribonacci word. - N. J. A. Sloane, Aug 17 2018
J.-P. Allouche and J. Shallit, Automatic Sequences, Cambridge Univ. Press, 2003, p. 246.
Michel Rigo, Formal Languages, Automata and Numeration Systems, 2 vols., Wiley, 2014. Mentions this sequence - see "List of Sequences" in Vol. 2.

N. J. A. Sloane, Table of n, a(n) for n = 1..19513
Pierre Arnoux and Edmund Harriss, What is a Rauzy Fractal?, Notices Amer. Math. Soc., 61 (No. 7, 2014), 768-770, also p. 704 and front cover.
Scott Balchin and Dan Rust, Computations for Symbolic Substitutions, Journal of Integer Sequences, Vol. 20 (2017), Article 17.4.1.
Elena Barcucci, Luc Belanger and Srecko Brlek, On tribonacci sequences, Fib. Q., 42 (2004), 314-320. See T on page 315.
Marcy Barge and Jaroslaw Kwapisz, Geometric theory of unimodular Pisot substitutions, Amer. J. Math. 128 (2006), no. 5, 1219--1282. MR2262174 (2007m:37039). See Fig. 18.1. - _N. J. A. Sloane_, Aug 06 2014
Jean Berstel and J. Karhumaki, Combinatorics on words - a tutorial, Bull. EATCS, #79 (2003), pp. 178-228.
Nataliya Chekhova, Pascal Hubert, and Ali Messaoudi, Propriétés combinatoires, ergodiques et arithmétiques de la substitution de Tribonacci, Journal de théorie des nombres de Bordeaux, 13.2 (2001): 371-394.
David Damanik and Luca Q. Zamboni, Arnoux-Rauzy subshifts: linear recurrence, powers and palindromes, arXiv:math/0208137 [math.CO], 2002.
Aldo de Luca and Luca Q. Zamboni, On prefixal factorizations of words, arXiv:1505.02309 [math.CO], 2015. See Example 2.
Aldo de Luca and Luca Q. Zamboni, On prefixal factorizations of words, European Journal of Combinatorics, Volume 52, Part A, 2016, pp. 59-73. See Example 2.
F. Michel Dekking, Morphisms, Symbolic Sequences, and Their Standard Forms, Journal of Integer Sequences, Vol. 19 (2016), Article 16.1.1.
F. Michel Dekking, Jeffrey Shallit, and N. J. A. Sloane, Queens in exile: non-attacking queens on infinite chess boards, Electronic J. Combin., 27:1 (2020), #P1.52.
Eric Duchêne and Michel Rigo, A morphic approach to combinatorial games: the Tribonacci case. RAIRO - Theoretical Informatics and Applications, 42, 2008, pp 375-393. doi:10.1051/ita:2007039. [Also available here]
Jacques Justin and Laurent Vuillon, Return words in Sturmian and episturmian words, RAIRO-Theoretical Informatics and Applications 34.5 (2000): 343-356. See Example on page 345.
Aayush Rajasekaran, Narad Rampersad, and Jeffrey Shallit, Overpals, Underlaps, and Underpals, In: Brlek S., Dolce F., Reutenauer C., Vandomme É. (eds) Combinatorics on Words, WORDS 2017, Lecture Notes in Computer Science, vol 10432.
Gérard Rauzy, Nombres algébriques et substitutions, Bull. Soc. Math. France 110.2 (1982): 147-178. See page 148.
Victor F. Sirvent, Semigroups and the self-similar structure of the flipped tribonacci substitution, Applied Math. Letters, 12 (1999), 25-29. [Contains further related references.]
Victor F. Sirvent, The common dynamics of the Tribonacci substitutions, Bulletin of the Belgian Mathematical Society-Simon Stevin 7.4 (2000): 571-582.
Bo Tan and Zhi-Ying Wen, Some properties of the Tribonacci sequence, European Journal of Combinatorics, 28 (2007) 1703-1719.
Ondřej Turek, Abelian Complexity Function of the Tribonacci Word, J. Int. Seq. 18 (2015) Article 15.3.4.
Index entries for sequences that are fixed points of mappings.

Cf. A003144, A003145, A003146, A100619, A103269, A073058, A245553, A245554, A105083, A352103.
See A080843 for a {0,1,2} version.
First differences: A317950.

f(1):= (1, 2): f(2):= (1, 3): f(3):= (1): A:= [1]:
for i from 1 to 16 do A:= map(f, A) od:
A; # 19513 terms of A092782; A103269; from N. J. A. Sloane, Aug 06 2018

Nest[ Flatten[# /. {1 -> {1, 2}, 2 -> {1, 3}, 3 -> 1}] &, {1}, 8] (* Robert G. Wilson v, Mar 04 2005 and updated Apr 29 2018 *)

w=vector(9,x,[]); w[1]=[1];
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)));
w[9] \\ Gerald McGarvey, Dec 18 2009

strsub(s, vv, off=0)=
{
    my( nl=#vv, r=[], ct=1 );
    while ( ct <= #s,
        r = concat(r, vv[ s[ct] + (1-off) ] );
        ct += 1;
    );
    return( r );
}
t=[1];  for (k=1, 10, t=strsub( t, [[1,2], [1,3], [1]], 1 ) );  t
\\ Joerg Arndt, Sep 14 2013

A092782_vec(N,s=[[1,2],[1,3],1],A=[1])={while(#AM. F. Hasler, Dec 14 2018

a(n) = 1 for n in A003144; a(n) = 2 for n in A003145; a(n) = 3 for n in A003146.

a(n) = A080843(n-1) + 1. - Joerg Arndt, Sep 14 2013

Additional references and links added by N. J. A. Sloane, Aug 17 2018

A071858 (Number of 1's in binary expansion of n) mod 3.

Original entry on oeis.org

0, 1, 1, 2, 1, 2, 2, 0, 1, 2, 2, 0, 2, 0, 0, 1, 1, 2, 2, 0, 2, 0, 0, 1, 2, 0, 0, 1, 0, 1, 1, 2, 1, 2, 2, 0, 2, 0, 0, 1, 2, 0, 0, 1, 0, 1, 1, 2, 2, 0, 0, 1, 0, 1, 1, 2, 0, 1, 1, 2, 1, 2, 2, 0, 1, 2, 2, 0, 2, 0, 0, 1, 2, 0, 0, 1, 0, 1, 1, 2, 2, 0, 0, 1, 0, 1, 1, 2, 0, 1, 1, 2, 1, 2, 2, 0, 2, 0, 0, 1, 0, 1, 1, 2, 0

Offset: 0

Benoit Cloitre, Jun 09 2002

This is the generalized Thue-Morse sequence t_3 (Allouche and Shallit, p. 335).
Ternary sequence which is a fixed point of the morphism 0 -> 01, 1 -> 12, 2 -> 20.
Sequence is T^(oo)(0) where T is the operator acting on any word on alphabet {0,1,2} by inserting 1 after 0, 2 after 1 and 0 after 2. For instance T(001)=010112, T(120)=122001. - Benoit Cloitre, Mar 02 2009

J.-P. Allouche and J. Shallit, Automatic Sequences, Cambridge Univ. Press, 2003.

G. C. Greubel, Table of n, a(n) for n = 0..10000
Jin Chen, Zhixiong Wen, Wen Wu, On the additive complexity of a Thue-Morse like sequence, arXiv:1802.03610 [math.CO], 2018.
Index entries for sequences that are fixed points of mappings

Cf. A000120, A010872.
Cf. A010060, A001285, A010059, A048707, A096271, A100619, A179868.
See A245555 for another version.

f[n_] := Mod[ Count[ IntegerDigits[n, 2], 1], 3]; Table[ f[n], {n, 0, 104}] (* Or *)
Nest[ Flatten[ # /. {0 -> {0, 1}, 1 -> {1, 2}, 2 -> {2, 0}}] &, {0}, 7] (* Robert G. Wilson v Mar 03 2005, modified May 17 2014 *)
Table[Mod[DigitCount[n,2,1],3],{n,0,110}] (* Harvey P. Dale, Jul 01 2015 *)

for(n=1,200,print1(sum(i=1,length(binary(n)), component(binary(n),i))%3,","))

map(d)=if(d==2,[2,0],if(d==1,[1,2],[0,1]))
{m=53;v=[];w=[0];while(v!=w,v=w;w=[];for(n=1,min(m,length(v)),w=concat(w,map(v[n]))));for(n=1,2*m,print1(v[n],","))} \\ Klaus Brockhaus, Jun 23 2004

a(n) = A010872(A000120(n)).
Recurrence: a(2*n) = a(n), a(2*n+1) = (a(n)+1) mod 3.
a(n) = A000695(n) mod 3. - John M. Campbell, Jul 16 2016

Edited by Ralf Stephan, Dec 11 2004

A277735 Unique fixed point of the morphism 0 -> 01, 1 -> 20, 2 -> 0.

Original entry on oeis.org

0, 1, 2, 0, 0, 0, 1, 0, 1, 0, 1, 2, 0, 0, 1, 2, 0, 0, 1, 2, 0, 0, 0, 1, 0, 1, 2, 0, 0, 0, 1, 0, 1, 2, 0, 0, 0, 1, 0, 1, 0, 1, 2, 0, 0, 1, 2, 0, 0, 0, 1, 0, 1, 0, 1, 2, 0, 0, 1, 2, 0, 0, 0, 1, 0, 1, 0, 1, 2, 0, 0, 1, 2, 0, 0, 1, 2, 0, 0, 0, 1, 0, 1, 2, 0, 0, 0, 1, 0, 1, 0, 1, 2, 0, 0, 1, 2, 0, 0, 1

Offset: 1

N. J. A. Sloane, Nov 07 2016

nonn

From Clark Kimberling, May 21 2017: (Start)
Let u be the sequence of positions of 0, and likewise, v for 1 and w for 2.  Let U, V, W be the limits of u(n)/n, v(n)/n, w(n)/n, respectively.  Then 1/U + 1/V + 1/W = 1, where
U = 1.8392867552141611325518525646532866...,
V = U^2 = 3.3829757679062374941227085364...,
W = U^3 = 6.2222625231203986266745611011....
If n >=2, then u(n) - u(n-1) is in {1,2,3}, v(n) - v(n-1) is in {2,4,5}, and w(n) - w(n-1) is in {4,7,9}. (u = A277736, v = A277737, w = A277738). (End)
Although I believe the assertions in Kimberling's comment above to be correct, these results are quite tricky to prove, and unless a formal proof is supplied at present these assertions must be regarded as conjectures. - N. J. A. Sloane, Aug 20 2018
From Michel Dekking, Oct 03 2019: (Start)
Here is a proof of Clark Kimberling's conjectures (and more).
The incidence matrix of the defining morphism
    sigma:  0 -> 01, 1 -> 20, 2 -> 0
is  the same as the incidence matrix of the tribonacci morphism
            0 -> 01, 1 -> 02, 2 -> 0
(see A080843  and/or A092782).
This implies that the frequencies  f0, f1 and f2 of the letters 0,1, and 2 in (a(n)) are the same as the corresponding frequencies in the tribonacci word, which are 1/t, 1/t^2  and 1/t^3 (see, e.g., A092782).
Since   U = 1/f0,  V = 1/f1, and W = 1/f2, we conclude that
    U = t = A058265,  V = t^2 = A276800 and W = t^3 = A276801.
The statements on the difference sequences u, v, and w of the positions of 0,1, and 2 are easily verified by applying sigma to the return words of  these three letters.
Here the return words of an arbitrary word w in a sequence x are all the words occurring in x with prefix w that do not have other occurrences of w in them.
The return words of 0 are 0, 01, and 012, which indeed have length 1, 2
and 3. Since
    sigma(0) = 01, sigma(1) = 0120, and sigma(012) = 01200,
one sees that u is the unique fixed point of the morphism
    1 -> 2, 2-> 31, 3 ->311.
With a little more work, passing to sigma^2, and rotating, one can show that v is the unique fixed point of the morphism
    2->52, 4->5224, 5->52244 .
Similarly, w is the unique fixed point of the morphism
    4->94, 7->9447, 9->94477.
Interestingly, the three morphisms having u,v, and w as fixed point are essentially the same morphism (were we replaced sigma by sigma^2) with standard form
    1->12, 2->1223, 3->12233.
(End)
The kind of phenomenon observed at the end of the previous comment holds in a very strong way for the tribonacci word. See Theorem 5.1. in the paper by Huang and Wen. - Michel Dekking, Oct 04 2019

N. J. A. Sloane, Table of n, a(n) for n = 1..20000
Y.-K. Huang, Z.-Y. Wen, Kernel words and gap sequence of the Tribonacci sequence, Acta Mathematica Scientia (Series B). 36.1 (2016) 173-194.
Victor F. Sirvent, Semigroups and the self-similar structure of the flipped tribonacci substitution, Applied Math. Letters, 12 (1999), 25-29.
Victor F. Sirvent, The common dynamics of the Tribonacci substitutions, Bulletin of the Belgian Mathematical Society-Simon Stevin 7.4 (2000): 571-582.
Index entries for sequences that are fixed points of mappings

Cf. A277736, A277737, A277738.

Equals A100619(n)-1.

with(ListTools);
T:=proc(S) Flatten(subs( {0=[0,1], 1=[2,0], 2=[0]}, S)); end;
S:=[0];
for n from 1 to 10 do S:=T(S); od:
S;

s = Nest[Flatten[# /. {0 -> {0, 1}, 1 -> {2, 0}, 2 -> 0}] &, {0}, 10] (* A277735 *)
Flatten[Position[s, 0]] (* A277736 *)
Flatten[Position[s, 1]] (* A277737 *)
Flatten[Position[s, 2]] (* A277738 *)
(* Clark Kimberling, May 21 2017 *)

Name clarified by Michel Dekking, Oct 03 2019

A317953 Apply the morphism 1 -> {1, 2}, 2 -> {3,1}, 3 -> {1} n times to 1, and concatenate the resulting string.

Original entry on oeis.org

1, 12, 1231, 1231112, 1231112121231, 123111212123112311231112, 12311121212311231123111212311121231112121231, 123111212123112311231112123111212311121212311231112121231123111212123112311231112

Offset: 1

N. J. A. Sloane, Aug 21 2018

nonn

For the tribonacci word A092782, each block b(n) (see A103269) is the concatenation of the three previous blocks: b(n) = b(n-1).b(n-2).b(n-3). Instead, here we have a(n) = a(n-1).a(n-3).a(n-2), as can be seen in the examples section below.

			a(1): 1,
a(2): 12,
a(3): 1231,
a(4): 1231112,
a(5): 1231112121231,
a(6): 123111212123112311231112,
a(7): 12311121212311231123111212311121231112121231,
equals a(6).a(4).a(5), look:
a(6):123111212123112311231112,
a(4):                        1231112,
a(5):                               1231112121231,
a(8): 123111212123112311231112123111212311121212311231112121231123111212123112311231112
equals a(7).a(5).a(6), look:
a(7): 12311121212311231123111212311121231112121231,
a(5):                                             1231112121231,
a(6):                                                          123111212123112311231112,

V. F. Sirvent, Semigroups and the self-similar structure of the flipped tribonacci substitution, Applied Math. Letters, 12 (1999), 25-29.

Cf. A100619 (the limiting string), A277735, A317953.

A103269 is the analog for the word A092782.

cp's OEIS Frontend

A113535 Ascending descending base exponent transform of the tribonacci substitution (A100619).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

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.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

PARI

PARI

PARI

Formula

Extensions

A071858 (Number of 1's in binary expansion of n) mod 3.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Mathematica

PARI

PARI

Formula

Extensions

A277735 Unique fixed point of the morphism 0 -> 01, 1 -> 20, 2 -> 0.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

Extensions

A317953 Apply the morphism 1 -> {1, 2}, 2 -> {3,1}, 3 -> {1} n times to 1, and concatenate the resulting string.

Views

Author

Keywords

Comments

Examples

References

Crossrefs

A317954 Fixed point of the morphism 1 -> 12, 2 -> 13, 3 -> 14, 4 -> 1, starting from a(1) = 1.

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

Mathematica