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).

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

Offset: 0

Author

N. J. A. Sloane, Mar 29 2003

Keywords

• nonn
• easy

Comments

An Arnoux-Rauzy or episturmian word.

From N. J. A. Sloane, Jul 10 2018: (Start)

The initial terms in a form suitable for copying:

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,

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,

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,

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,

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,

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,

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,

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,

...

Let TTW(a,b,c) denote this sequence written over the alphabet {a,b,c}. It begins:

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,

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,

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,

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

... (End)

From Wolfdieter Lang, Aug 14 2018: (Start)

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).

E.g., l = 4: 0 1 0 2 0 1 0 with T(6) = 7 leaves (nodes). See the example below.

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)

Examples

			From _Joerg Arndt_, Mar 12 2013: (Start)
The first few steps of the substitution are
Start: 0
Rules:
  0 --> 01
  1 --> 02
  2 --> 0
-------------
0:   (#=1)
  0
1:   (#=2)
  01
2:   (#=4)
  0102
3:   (#=7)
  0102010
4:   (#=13)
  0102010010201
5:   (#=24)
  010201001020101020100102
6:   (#=44)
  01020100102010102010010201020100102010102010
7:   (#=81)
  010201001020101020100102010201001020101020100102010010201010201001020102010010201
(End)
From _Wolfdieter Lang_, Aug 14 2018: (Start)
The levels l of the tree TriT begin (the branches (edges) have been omitted):
Substitution rule: 0 -> 0 1; 1 -> 0 2; 2 -> 0.
l=1:                                 0
l=2:                  0                                 1
l=3:             0             1                  0             2
l=4:         0      1       0     2          0       1          0
l=5:      0    1  0   2   0   1   0        0   1   0   2      0    1
...
----------------------------------------------------------------------------------
n =       0    1  2   3   4   5   6        7   8   9  10     11   12
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.
          0    1  0   1   0   1   0        0   1   0  1      0    1
                  1   1   0   0   1        0   0   1  1      0    0
                          1   1   1        0   0   0  0      1    1
                                           1   1   1  1      1    1
E.g., ZTri(9) = A278038(9) = 1010. (End)
		

References

• The entry A092782 has a more complete list of references and links. - N. J. A. Sloane, Aug 17 2018
• J.-P. Allouche and J. Shallit, Automatic Sequences, Cambridge Univ. Press, 2003, p. 246.

Links

• N. J. A. Sloane, Table of n, a(n) for n = 0..20000
• 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.
• D. Damanik and L. Q. Zamboni, Arnoux-Rauzy subshifts: linear recurrence, powers and palindromes, arXiv:math/0208137 [math.CO], 2002.
• 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]
• Robbert Fokkink and Dan Rust, Queen reflections: a modification of Wythoff Nim, Int'l J. Game Theory (2022).
• Wolfdieter Lang, The Tribonacci and ABC Representations of Numbers are Equivalent, arXiv:1810.09787v1 [math.NT], 2018.
• Joseph Meleshko, Pascal Ochem, Jeffrey Shallit, and Sonja Linghui Shan, Pseudoperiodic Words and a Question of Shevelev, arXiv:2207.10171 [math.CO], 2022.
• 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.
• Bo Tan and Zhi-Ying Wen, Some properties of the Tribonacci sequence, European Journal of Combinatorics, 28 (2007) 1703-1719.
• O. Turek, Abelian Complexity Function of the Tribonacci Word, J. Int. Seq. 18 (2015) # 15.3.4
• Index entries for sequences that are fixed points of mappings

Crossrefs

Cf. A003849 (the Fibonacci word), A092782.

See A092782 for a version over the alphabet {1,2,3}.

See A278045 for another construction.

Cf. A000073, A278038.

First differences: A317950. Partial sums: A319198.

Programs

Maple

M:=17; S[1]:=`0`; S[2]:=`01`; S[3]:=`0102`;
for n from 4 to M do S[n]:=cat(S[n-1], S[n-2], S[n-3]); od:
t0:=S[M]: l:=length(t0); for i from 1 to l do lprint(i,substring(t0,i..i)); od:
# N. J. A. Sloane, Nov 01 2006
# A version that uses the letters a,b,c:
M:=10; B[1]:=`a`; B[2]:=`ab`; B[3]:=`abac`;
for n from 4 to M do B[n]:=cat(B[n-1], B[n-2], B[n-3]); od:
B[10]; # N. J. A. Sloane, Oct 30 2018

Mathematica

Nest[Flatten[ # /. {0 -> {0, 1}, 1 -> {0, 2}, 2 -> {0}}] &, {0}, 8] (* updated by Robert G. Wilson v, Nov 07 2010 *)
SubstitutionSystem[{0->{0,1},1->{0,2},2->{0}},{0},{8}]//Flatten (* Harvey P. Dale, Nov 21 2021 *)

PARI

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=[0];  for (k=1, 10, t=strsub( t, [[0,1], [0,2], [0]], 0 ) );  t
\\ Joerg Arndt, Sep 14 2013

Formula

Fixed point of morphism 0 -> 0, 1; 1 -> 0, 2; 2 -> 0.

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

Extensions

More terms from Antonio G. Astudillo (afg_astudillo(AT)lycos.com), Apr 06 2003