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

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)

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

Formula

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

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

Example

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)

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

Prog

(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

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.

Sequence in context: A281458 A178781 A287174 * A287112 A296238 A309475

Adjacent sequences: A080840 A080841 A080842 * A080844 A080845 A080846

Keyword

nonn,easy

Author

N. J. A. Sloane, Mar 29 2003

Extensions

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

Status

approved