# Greetings from The On-Line Encyclopedia of Integer Sequences! http://oeis.org/
Search: id:a003842
Showing 1-1 of 1
%I A003842 #164 Mar 30 2023 05:13:05
%S A003842 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,
%T A003842 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,
%U A003842 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
%N 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).
%C A003842 Or, fixed point of the morphism 1->12, 2->1, starting from a(1) = 2.
%C A003842 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).
%C A003842 The limiting mean of the first n terms is 3 - phi, where phi is the golden ratio (A001622); the limiting variance is 2 - phi. - _Clark Kimberling_, Mar 12 2014
%C A003842 The Wikipedia article on L-system Example 1 is "Algae" given by the axiom: A and rules: A -> AB, B -> A. The sequence G(n) = G(n-1)G(n-2) yields this sequence when A -> 1, B -> 2. - _Michael Somos_, Jan 12 2015
%C A003842 In the limit #1's : #2's = phi : 1. - _Frank M Jackson_, Mar 12 2018
%D A003842 J.-P. Allouche and J. Shallit, Automatic Sequences, Cambridge Univ. Press, 2003.
%D A003842 Jean Berstel, "Fibonacci words—a survey." In The book of L, pp. 13-27. Springer Berlin Heidelberg, 1986.
%D A003842 J. Berstel and J. Karhumaki, Combinatorics on words - a tutorial, Bull. EATCS, #79 (2003), pp. 178-228.
%D A003842 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.
%D A003842 Aldo de Luca and Stefano Varricchio, 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.
%D A003842 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.
%D A003842 G. Melançon, Factorizing infinite words using Maple, MapleTech journal, vol. 4, no. 1, 1997, pp. 34-42, esp. p. 36.
%H A003842 T. D. Noe, Table of n, a(n) for n=0..10945 (20 iterations)
%H A003842 J.-P. Allouche and M. Mendes France, Automata and Automatic Sequences, in: Axel F. and Gratias D. (eds), Beyond Quasicrystals. Centre de Physique des Houches, vol 3. Springer, Berlin, Heidelberg, pp. 293-367, 1995; DOI https://doi.org/10.1007/978-3-662-03130-8_11.
%H A003842 J.-P. Allouche and M. Mendes France, Automata and Automatic Sequences, in: Axel F. and Gratias D. (eds), Beyond Quasicrystals. Centre de Physique des Houches, vol 3. Springer, Berlin, Heidelberg, pp. 293-367, 1995; DOI https://doi.org/10.1007/978-3-662-03130-8_11. [Local copy]
%H A003842 Scott Balchin and Dan Rust, Computations for Symbolic Substitutions, Journal of Integer Sequences, Vol. 20 (2017), Article 17.4.1.
%H A003842 Jean Berstel, Home Page
%H A003842 Julien Cassaigne, On extremal properties of the Fibonacci word, RAIRO-Theor. Inf. Appl. 42 (2008) 701-715.
%H A003842 J. Endrullis, D. Hendriks and J. W. Klop, Degrees of streams.
%H A003842 S. Ferenczi, Complexity of sequences and dynamical systems, Discrete Math., 206 (1999), 145-154.
%H A003842 J. Grytczuk, Infinite semi-similar words, Discrete Math. 161 (1996), 133-141.
%H A003842 A. Hof, O. Knill and B. Simon, Singular continuous spectrum for palindromic Schrödinger operators, Commun. Math. Phys. 174 (1995), 149-159.
%H A003842 Clark Kimberling, A Self-Generating Set and the Golden Mean, J. Integer Sequences, 3 (2000), #00.2.8.
%H A003842 Clark Kimberling, Intriguing infinite words composed of zeros and ones, Elemente der Mathematik (2021).
%H A003842 M. Lothaire, Algebraic Combinatorics on Words, Cambridge, 2002, see p. 41, etc.
%H A003842 G. Melançon, Lyndon factorization of sturmian words, Discr. Math., 210 (2000), 137-149.
%H A003842 F. Mignosi, A. Restivo and M. Sciortino, 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
%H A003842 F. Mignosi and L. Q. Zamboni, On the number of Arnoux-Rauzy words, Acta arith., 101 (2002), no. 2, 121-129.
%H A003842 T. D. Noe, The first 1652 subwords of A003849, including leading zeros.
%H A003842 Giuseppe Pirillo, Fibonacci numbers and words, Discrete Math. 173 (1997), no. 1-3, 197--207. MR1468849 (98g:68135).
%H A003842 Patrice Séébold, Look and Say Fibonacci, RAIRO-Theor. Inf. Appl. 42 (2008) 729-746.
%H A003842 N. J. A. Sloane, The first 10946 terms, concatenated
%H A003842 N. J. A. Sloane, Families of Essentially Identical Sequences, Mar 24 2021 (Includes this sequence)
%H A003842 P. Steinbach, Golden fields: a case for the heptagon, Math. Mag. 70 (1997), no. 1, 22-31.
%H A003842 Eric Weisstein's World of Mathematics, Golden Ratio
%H A003842 Wikipedia, L-system Example 1: Algae
%H A003842 Index entries for sequences that are fixed points of mappings
%F A003842 Define strings S(0)=2, S(1)=1, S(n)=S(n-1)S(n-2); iterate. Sequence is S(infinity).
%F A003842 a(n) = n + 2 - A120613(n+1). - _Benoit Cloitre_, Jul 28 2005 [Corrected by _N. J. A. Sloane_, Jun 30 2018]
%e A003842 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, ...
%t A003842 Nest[ Flatten[ # /. {1 -> {1, 2}, 2 -> {1}}] &, {1}, 10] (* _Robert G. Wilson v_, Mar 04 2005 *)
%t A003842 Table[n + 1 - Floor[((1 + Sqrt[5])/2)*Floor[2*(n + 1)/(1 + Sqrt[5])]], {n, 1, 50}] (* _G. C. Greubel_, May 18 2017 *)
%t A003842 SubstitutionSystem[{1->{1,2},2->{1}},{1},{10}][[1]] (* _Harvey P. Dale_, Nov 19 2022 *)
%o A003842 (Haskell)
%o A003842 a003842 n = a003842_list !! n
%o A003842 a003842_list = tail $ concat fws where
%o A003842 fws = [2] : [1] : (zipWith (++) fws $ tail fws)
%o A003842 -- _Reinhard Zumkeller_, Oct 26 2013
%o A003842 (PARI) for(n=1,50, print1(n+1 - floor(((1+sqrt(5))/2)*floor(2*(n+1)/(1+sqrt(5)))), ", ")) \\ _G. C. Greubel_, May 18 2017
%o A003842 (Python) def A003842(length):
%o A003842 a = [1]
%o A003842 while len(a)