|
| |
|
|
A003849
|
|
The infinite Fibonacci word (start with 0, apply 0->01, 1->0, take limit).
|
|
59
|
|
|
|
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.
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
|
|
|
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.
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
Pirillo, Giuseppe. Fibonacci numbers and words. Discrete Math. 173 (1997), no. 1-3, 197--207. MR1468849 (98g:68135)
|
|
|
LINKS
|
N. J. A. Sloane, Table of n, a(n) for n = 0..10945
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, including leading zeros.
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, 2012
Eric Weisstein's World of Mathematics, Golden Ratio
Index entries for characteristic functions
|
|
|
FORMULA
|
Define strings S(0)=0, S(1)=01, S(n)=S(n-1)S(n-2); iterate; sequence is S(infinity).
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
|
|
|
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] (from Robert G. Wilson v Mar 05 2005)
|
|
|
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 = 0 : 1 : zs where
zs = 0 : concatMap fw zs
fw 0 = [0, 1]; fw 1 = [0]
-- Reinhard Zumkeller, Apr 07 2012
|
|
|
CROSSREFS
|
There are several versions of this sequence in the OEIS. This one and A003842 are probably the most important. See also A008352, A076662.
Binary complement of A005614. Cf. A014675, A036299, A003714, A014417, A096268, A096270, A133235.
Positions of 1's gives A003622.
Cf. A182028, A213975.
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. Revised by N. J. A. Sloane, Jul 03 2012
|
|
|
STATUS
|
approved
|
| |
|
|
