login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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). 53
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 (list; graph; refs; listen; history; text; internal format)
OFFSET

0,4

COMMENTS

An Arnoux-Rauzy or episturmian word.

The initial terms in a form suitable for mousing:

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,

... - From N. J. A. Sloane, Jul 10 2018

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.

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]

Wolfdieter Lang, The Tribonacci and ABC Representations of Numbers are Equivalent, arXiv:1810.09787v1 [math.NT], 2018.

Aayush Rajasekaran, Narad Rampersad, 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 *)

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 A221314

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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified July 17 18:47 EDT 2019. Contains 325109 sequences. (Running on oeis4.)