|
| |
|
|
A003849
|
|
The infinite Fibonacci word (start with 0, apply 0->01, 1->0, take limit).
|
|
203
|
|
|
|
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 0 is omitted from S(n) for n>0, we obtain A288582(n+1).
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
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
Let S(n) be defined as above. Then this sequence is S(1) + Sum_{n=0..} S(n), where the addition of strings represents concatenation. - Isaac Saffold, May 03 2019
The word is a concatenation of three runs: 0, 1, and 00. The limiting proportions of these are respectively 1 - phi/2, 1/2, and (phi - 1)/2. The mean runlength is (phi + 1)/2. - Clark Kimberling, Dec 26 2010
a(n) is the number of the trailing 0's in the dual Zeckendorf representation of (n+1) (A104326).
The asymptotic density of the occurrences of k (0 or 1) is 1/phi^(k+1), where phi is the golden ratio (A001622).
The asymptotic mean of this sequence is 1/phi^2 (A132338). (End)
|
|
|
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.
Wolfdieter 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. [See A317208 for a link.]
G. Melançon, 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
|
A. G. M. Ahmed, AA Weaving, in Proceedings of Bridges 2013: Mathematics, Music, Art, Architecture, Culture.
Jean-Paul Allouche, Julien Cassaigne, Jeffrey Shallit, and Luca Q. Zamboni, A Taxonomy of Morphic Sequences, arXiv preprint arXiv:1711.10807 [cs.FL], Nov 29 2017.
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.
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]
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.
Aayush Rajasekaran, Narad Rampersad, and 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.
|
|
|
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
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 *)
Table[Floor[(n + 2) #] - Floor[(n + 1) #], {n, 0, 120}] &[2 - GoldenRatio] (* Michael De Vlieger, Aug 15 2016 *)
SubstitutionSystem[{0->{0, 1}, 1->{0}}, {0}, {10}][[1]] (* Harvey P. Dale, Dec 20 2021 *)
|
|
|
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)
(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
(PARI) M3849=[2, 2, 1, 0]/*L(k), S(k), L(k-1), S(k-1)*/; A003849(n)={while(n>M3849[1], M3849=vecextract(M3849, [1, 2, 1, 2])+[M3849[3], M3849[4]<<M3849[1], 0, 0]); bittest(M3849[2], n)} \\ Much faster at the expense of using ~ Nmax/5 bytes of memory (~ 250 KB for n <= 1.3e6). - M. F. Hasler, Apr 07 2021
(Python)
def fib(n):
"""Return the concatenation of A003849(0..F-1) where F is the smallest
Fibonacci number > n, so that the result contains a(n) at index n."""
a, b = '10'
while len(b)<=n:
a, b = b, b + a
(Python)
from math import isqrt
def A003849(n): return 2-(n+2+isqrt(m:=5*(n+2)**2)>>1)+(n+1+isqrt(m-10*n-15)>>1) # Chai Wah Wu, Aug 25 2022
|
|
|
CROSSREFS
|
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.
The following sequences are all essentially the same, in the sense that they are simple transformations of each other, with A000201 as the parent: A000201, A001030, A001468, A001950, A003622, A003842, A003849, A004641, A005614, A014675, A022342, A088462, A096270, A114986, A124841. - N. J. A. Sloane, Mar 11 2021
|
|
|
KEYWORD
|
nonn,easy,nice
|
|
|
AUTHOR
|
|
|
|
EXTENSIONS
|
|
|
|
STATUS
|
approved
|
| |
|
|
