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

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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). 25
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).

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

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

In the limit #1's : #2's = phi : 1. - Frank M Jackson, Mar 12 2018

REFERENCES

J.-P. Allouche and J. Shallit, Automatic Sequences, Cambridge Univ. Press, 2003.

Berstel, Jean. "Fibonacci words—a survey." In The book of L, pp. 13-27. Springer Berlin Heidelberg, 1986.

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

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.

Scott Balchin and Dan Rust, Computations for Symbolic Substitutions, Journal of Integer Sequences, Vol. 20 (2017), Article 17.4.1.

Jean Berstel, Home Page

Julien Cassaigne, On extremal properties of the Fibonacci word, RAIRO-Theor. Inf. Appl. 42 (2008) 701-715.

J. Endrullis, D. Hendriks and J. W. Klop, Degrees of streams.

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 Schrödinger operators, Commun. Math. Phys. 174 (1995), 149-159.

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.

G. Melancon, Lyndon factorization of sturmian words, Discr. Math., 210 (2000), 137-149.

F. Mignosi, A. Restivo, 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

F. Mignosi and L. Q. Zamboni, On the number of Arnoux-Rauzy words, Acta arith., 101 (2002), no. 2, 121-129.

T. D. Noe, The first 1652 subwords of A003849, including leading zeros.

Giuseppe Pirillo, Fibonacci numbers and words, Discrete Math. 173 (1997), no. 1-3, 197--207. MR1468849 (98g:68135).

Patrice Séébold, Look and Say Fibonacci, RAIRO-Theor. Inf. Appl. 42 (2008) 729-746.

N. J. A. Sloane, The first 10946 terms, concatenated

P. Steinbach, Golden fields: a case for the heptagon, Math. Mag. 70 (1997), no. 1, 22-31.

Eric Weisstein's World of Mathematics, Golden Ratio

Wikipedia, L-system Example 1: Algae

Index entries for sequences that are fixed points of mappings

FORMULA

Define strings S(0)=2, S(1)=1, S(n)=S(n-1)S(n-2); iterate. Sequence is S(infinity).

a(n) = n + 2 - A120613(n+1). - Benoit Cloitre, Jul 28 2005 [Corrected by N. J. A. Sloane, Jun 30 2018]

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] (* Robert G. Wilson v, Mar 04 2005 *)

Table[n + 1 - Floor[((1 + Sqrt[5])/2)*Floor[2*(n + 1)/(1 + Sqrt[5])]], {n, 1, 50}] (* G. C. Greubel, May 18 2017 *)

PROG

(Haskell)

a003842 n = a003842_list !! n

a003842_list = tail $ concat fws where

   fws = [2] : [1] : (zipWith (++) fws $ tail fws)

-- Reinhard Zumkeller, Oct 26 2013

(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

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, A120613.

Sequence in context: A207668 A293838 A055443 * A095771 A245933 A268318

Adjacent sequences:  A003839 A003840 A003841 * A003843 A003844 A003845

KEYWORD

nonn,nice,easy

AUTHOR

N. J. A. Sloane, revised by N. J. A. Sloane, Jul 03 2012

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 March 18 22:11 EDT 2019. Contains 321305 sequences. (Running on oeis4.)