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

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A003849 The infinite Fibonacci word (start with 0, apply 0->01, 1->0, take limit). 169
0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 1, 0, 0, 1 (list; graph; refs; listen; history; text; internal format)
OFFSET

0,1

COMMENTS

A Sturmian word.

Define strings S(0)=0, S(1)=01, S(n)=S(n-1)S(n-2); iterate; sequence is S(infinity). If the initial zero is omitted from S(n) for n>0, we obtain A288582(n+1).

The 0's occur at positions in A022342 (i.e., A000201 - 1), the 1's at positions in A003622.

Replace each run (1;1) with (1;0) in the infinite Fibonacci word A005614 (and add 0 as prefix) A005614 begins: 1,0,1,1,0,1,0,1,1,0,1,1,... changing runs (1,1) with (1,0) produces 1,0,0,1,0,1,0,0,1,0,0,1,... - Benoit Cloitre, Nov 10 2003

Characteristic function of A003622. - Philippe Deléham, May 03 2004

The fraction of 0's in the first n terms approaches 1/phi (see for example Allouche and Shallit). - N. J. A. Sloane, Sep 24 2007

The limiting mean and variance of the first n terms are 2-phi and 2*phi-3, respectively. - Clark Kimberling, Mar 12 2014, Aug 16 2018

REFERENCES

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

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

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.

W. Lang, The Wythoff and the Zeckendorf representations of numbers are equivalent, in G. E. Bergum et al. (edts.) Application of Fibonacci numbers vol. 6, Kluwer, Dordrecht, 1996, pp. 319-337.

G. Melancon, Factorizing infinite words using Maple, MapleTech journal, vol. 4, no. 1, 1997, pp. 34-42, esp. p. 36.

Michel Rigo, Formal Languages, Automata and Numeration Systems, 2 vols., Wiley, 2014. Mentions this sequence - see "List of Sequences" in Vol. 2.

LINKS

N. J. A. Sloane, Table of n, a(n) for n = 0..10945

A. G. M. Ahmed, AA Weaving, in Proceedings of Bridges 2013: Mathematics, Music, Art, Architecture, Culture.

Jean-Paul Allouche, Julien Cassaigne, Jeffrey Shallit, Luca Q. Zamboni, A Taxonomy of Morphic Sequences, arXiv preprint arXiv:1711.10807, Nov 29 2017

J.-P. Allouche and M. Mendes France, Automata and Automatic Sequences.

P. Arnoux and E. Harriss, What is a Rauzy Fractal?, Notices Amer. Math. Soc., 61 (No. 7, 2014), 768-770, also p. 704 and front cover.

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

Jean Berstel, Home Page

J. Berstel and J. Karhumaki, Combinatorics on words - a tutorial, Bull. EATCS, #79 (2003), pp. 178-228.

Bryce Emerson Blackham, Subtraction Games: Range and Strict Periodicity, masters thesis, 2018.

Fabien Durand, Julien Leroy, and Gwenaël Richomme, Do the Properties of an S-adic Representation Determine Factor Complexity?, Journal of Integer Sequences, Vol. 16 (2013), #13.2.6.

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.

L. Goldberg and A. V. Fraenkel, Patterns in the generalized Fibonacci word, applied to games, Discrete Math., 341 2018 1675-1687.

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.

Tyler Hoffman, B. Steinhurst, Hausdorff Dimension of Generalized Fibonacci Word Fractals, arXiv preprint arXiv:1601.04786 [math.MG], 2016.

T. Karki, A. Lacroix, M. Rigo, On the recognizability of self-generating sets, JIS 13 (2010) #10.2.2.

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

Kerry Mitchell, Spirolateral-Type Images from Integer Sequences, 2013

Kerry Mitchell, Spirolateral image for this sequence [taken, with permission, from the Spirolateral-Type Images from Integer Sequences article]

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

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

J. L. Ramírez, G. N. Rubiano, Properties and Generalizations of the Fibonacci Word Fractal, The Mathematica Journal, Vol. 16 (2014).

José L. Ramírez, Gustavo N. Rubiano, and Rodrigo de Castro, A Generalization of the Fibonacci Word Fractal and the Fibonacci Snowflake, arXiv preprint arXiv:1212.1368 [cs.DM], 2012.

Aayush Rajasekaran, Using Automata Theory to Solve Problems in Additive Number Theory, MS thesis, University of Waterloo, 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.

M. Rigo, P. Salimov, and E. Vandomme, Some Properties of Abelian Return Words, Journal of Integer Sequences, Vol. 16 (2013), #13.2.5.

Luke Schaeffer, Jeffrey Shallit, Closed, Palindromic, Rich, Privileged, Trapezoidal, and Balanced Words in Automatic Sequences, Electronic Journal of Combinatorics 23(1) (2016), #P1.25.

Eric Weisstein's World of Mathematics, Golden Ratio

Jiemeng Zhang, Zhixiong Wen, Wen Wu, Some Properties of the Fibonacci Sequence on an Infinite Alphabet, Electronic Journal of Combinatorics, 24(2) (2017), #P2.52.

Index entries for sequences that are fixed points of mappings

Index entries for characteristic functions

FORMULA

a(n) = floor((n+2)*r) - floor((n+1)*r) where r=phi/(1+2*phi) and phi is the Golden Ratio. - Benoit Cloitre, Nov 10 2003

a(n) = A003714(n) mod 2 = A014417(n) mod 2. - Philippe Deléham, Jan 04 2004

The first formula by Cloitre is just one of an infinite family of formulas. Using phi^2=1+phi, it follows that r=phi/(1+2*phi)=2-phi. Then from floor(-x)=-floor(x)-1 for non-integer x, it follows that a(n)=2-A014675(n)=2-(floor((n+2)* phi)-floor((n+1)*phi)). - Michel Dekking, Aug 27 2016

EXAMPLE

The word is 010010100100101001010010010100...

Over the alphabet {a,b} this is 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, ...

MAPLE

z := proc(m) option remember; if m=0 then [0] elif m=1 then [0, 1] else [op(z(m-1)), op(z(m-2))]; fi; end; z(12);

M:=19; S[0]:=`0`; S[1]:=`01`; for n from 2 to M do S[n]:=cat(S[n-1], S[n-2]); od:

t0:=S[M]: l:=length(t0); for i from 1 to l do lprint(i-1, substring(t0, i..i)); od: # N. J. A. Sloane, Nov 01 2006

MATHEMATICA

Nest[ Flatten[ # /. {0 -> {0, 1}, 1 -> {0}}] &, {0}, 10] (* Robert G. Wilson v, Mar 05 2005 *)

Flatten[Nest[{#, #[[1]]} &, {0, 1}, 9]] (* IWABUCHI Yu(u)ki, Oct 23 2013 *)

Table[Floor[(n + 2) #] - Floor[(n + 1) #], {n, 0, 120}] &[2 - GoldenRatio] (* Michael De Vlieger, Aug 15 2016 *)

PROG

(MAGMA) t1:=[ n le 2 select ["0", "0, 1"][n] else Self(n-1) cat ", " cat Self(n-2) : n in [1..12]]; t1[12];

(Haskell)

a003849 n = a003849_list !! n

a003849_list = tail $ concat fws where

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

-- Reinhard Zumkeller, Nov 01 2013, Apr 07 2012

(PARI) a(n)=my(k=2); while(fibonacci(k)<=n, k++); while(n>1, while(fibonacci(k--)>n, ); n-=fibonacci(k)); n==1 \\ Charles R Greathouse IV, Feb 03 2014

(Python)

def fib(n):

....a, b='1', '0'

....if n==1: return a

....elif n==2: return b

....else:

........for i in range(n-2):

........a, b=b, b+a

....return(b) # Robert FERREOL, Apr 15 2016

CROSSREFS

There are several versions of this sequence in the OEIS. This one and A003842 are probably the most important. See also A008352, A076662, A288581, A288582.

Binary complement of A005614. Cf. A014675, A036299, A003714, A014417, A096268, A096270, A133235, A182028, A213975.

Positions of 1's gives A003622.

Sequences mentioned in the Allouche et al. "Taxonomy" paper, listed by example number: 1: A003849, 2: A010060, 3: A010056, 4: A020985 and A020987, 5: A191818, 6: A316340 and A273129, 18: A316341, 19: A030302, 20: A063438, 21: A316342, 22: A316343, 23: A003849 minus its first term, 24: A316344, 25: A316345 and A316824, 26: A020985 and A020987, 27: A316825, 28: A159689, 29: A049320, 30: A003849, 31: A316826, 32: A316827, 33: A316828, 34: A316344, 35: A043529, 36: A316829, 37: A010060.

Sequence in context: A091446 A164349 A094186 * A115199 A085242 A059620

Adjacent sequences:  A003846 A003847 A003848 * A003850 A003851 A003852

KEYWORD

nonn,easy,nice

AUTHOR

N. J. A. Sloane

EXTENSIONS

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 | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified September 20 14:41 EDT 2018. Contains 315240 sequences. (Running on oeis4.)