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