|
| |
|
|
A003842
|
|
The infinite Fibonacci word: start with 1, repeatedly apply the morphism 1->12, 2->1, take limit; or, start with S(0)=2, S(1)=1, and for n>1 define S(n)=S(n-1)S(n-2), then the sequence is S(oo).
|
|
24
|
|
|
|
1, 2, 1, 1, 2, 1, 2, 1, 1, 2, 1, 1, 2, 1, 2, 1, 1, 2, 1, 2, 1, 1, 2, 1, 1, 2, 1, 2, 1, 1, 2, 1, 1, 2, 1, 2, 1, 1, 2, 1, 2, 1, 1, 2, 1, 1, 2, 1, 2, 1, 1, 2, 1, 2, 1, 1, 2, 1, 1, 2, 1, 2, 1, 1, 2, 1, 1, 2, 1, 2, 1, 1, 2, 1, 2, 1, 1, 2, 1, 1, 2, 1, 2, 1, 1, 2, 1, 1, 2, 1, 2, 1, 1, 2, 1, 2, 1, 1, 2, 1, 1, 2, 1, 2, 1
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
0,2
|
|
|
COMMENTS
|
Or, fixed point of the morphism 1->12, 2->1, starting from a(1) = 2.
A Sturmian word, as are all versions of this sequence. This means that if one slides a window of length n along the sequence, one sees exactly n+1 different subwords (see A213975). For a proof, see for example Chap. 2 of Lothaire (2002).
|
|
|
REFERENCES
|
J.-P. Allouche and J. Shallit, Automatic Sequences, Cambridge Univ. Press, 2003.
J. Berstel and J. Karhumaki, Combinatorics on words - a tutorial, Bull. EATCS, #79 (2003), pp. 178-228.
E. Bombieri and J. Taylor, Which distribution of matter diffracts? An initial investigation, in International Workshop on Aperiodic Crystals (Les Houches, 1986), J. de Physique, Colloq. C3, 47 (1986), C3-19 to C3-28.
de Luca, Aldo; Varricchio, Stefano. Finiteness and regularity in semigroups and formal languages. Monographs in Theoretical Computer Science. An EATCS Series. Springer-Verlag, Berlin, 1999. x+240 pp. ISBN: 3-540-63771-0 MR1696498 (2000g:68001). See p. 25.
J. Endrullis, D. Hendriks and J. W. Klop, Degrees of streams, http://www.cs.vu.nl/~diem/publication/pdf/degrees.pdf
S. Ferenczi, Complexity of sequences and dynamical systems, Discrete Math., 206 (1999), 145-154.
J. Grytczuk, Infinite semi-similar words, Discrete Math. 161 (1996), 133-141.
A. Hof, O. Knill and B. Simon, Singular continuous spectrum for palindromic Schroedinger operators, Commun. Math. Phys. 174 (1995), 149-159.
J. C. Lagarias, Number Theory and Dynamical Systems, pp. 35-72 of S. A. Burr, ed., The Unreasonable Effectiveness of Number Theory, Proc. Sympos. Appl. Math., 46 (1992). Amer. Math. Soc. - see p. 64.
G. Melancon, Factorizing infinite words using Maple, MapleTech journal, vol. 4, no. 1, 1997, pp. 34-42, esp. p. 36.
G. Melancon, Lyndon factorization of sturmian words, Discr. Math., 210 (2000), 137-149.
Mignosi, F.; Restivo, A.; Sciortino, M. Words and forbidden factors. WORDS (Rouen, 1999). Theoret. Comput. Sci. 273 (2002), no. 1-2, 99--117. MR1872445 (2002m:68096) - From N. J. A. Sloane, Jul 10 2012
F. Mignosi and L. Q. Zamboni, On the number of Arnoux-Rauzy words, Acta Arith. 101 (2002), 121-129.
Pirillo, Giuseppe. Fibonacci numbers and words. Discrete Math. 173 (1997), no. 1-3, 197--207. MR1468849 (98g:68135)
P. Steinbach, Golden fields: a case for the heptagon, Math. Mag. 70 (1997), no. 1, 22-31.
|
|
|
LINKS
|
T. D. Noe, Table of n, a(n) for n=0..10945 (20 iterations)
J.-P. Allouche and M. Mendes France, Automata and Automatic Sequences.
Jean Berstel, Home Page
C. Kimberling, A Self-Generating Set and the Golden Mean, J. Integer Sequences, 3 (2000), #00.2.8.
M. Lothaire, Algebraic Combinatorics on Words, Cambridge, 2002, see p. 41, etc.
T. D. Noe, The first 1652 subwords of A003849, including leading zeros.
N. J. A. Sloane, The first 10946 terms, concatenated
Eric Weisstein's World of Mathematics, Golden Ratio
|
|
|
FORMULA
|
Define strings S(0)=2, S(1)=1, S(n)=S(n-1)S(n-2); iterate. Sequence is S(infinity).
a(n-1)=n-floor(phi*floor(n/phi)) - Benoit Cloitre, Jul 28 2005
|
|
|
EXAMPLE
|
Over the alphabet {a,b} this is the sequence a, b, a, a, b, a, b, a, a, b, a, a, b, a, b, a, a, b, a, b, a, a, b, a, a, b, a, b, a, a, b, a, a, b, a, b, a, a, b, a, b, a, a, b, a, a, b, a, b, a, a, b, a, b, a, a, b, a, a, b, a, b, a, a, b, a, a, b, a, b, a, a, b, a, b, a, a, b, a, a, b, a, b, a, a, b, a, a, b, a, b, a, a, b, a, b, a, a, b, a, a, b, a, b, a, ...
|
|
|
MATHEMATICA
|
Nest[ Flatten[ # /. {1 -> {1, 2}, 2 -> {1}}] &, {1}, 10] (from Robert G. Wilson v Mar 04 2005)
|
|
|
CROSSREFS
|
A003849 is another common version of this sequence. A003842 is the {1, 2}-version.
See also A014675, A005614, A001468, A106750, A213975, A213976, A214317, A214318, A182028.
Sequence in context: A078316 A207668 A055443 * A095771 A007421 A103921
Adjacent sequences: A003839 A003840 A003841 * A003843 A003844 A003845
|
|
|
KEYWORD
|
nonn,nice,easy
|
|
|
AUTHOR
|
N. J. A. Sloane. Entry revised by N. J. A. Sloane, Jul 03 2012
|
|
|
STATUS
|
approved
|
| |
|
|
