

A096270


Fixed point of the morphism 0>01, 1>011.


35



0, 1, 0, 1, 1, 0, 1, 0, 1, 1, 0, 1, 1, 0, 1, 0, 1, 1, 0, 1, 0, 1, 1, 0, 1, 1, 0, 1, 0, 1, 1, 0, 1, 1, 0, 1, 0, 1, 1, 0, 1, 0, 1, 1, 0, 1, 1, 0, 1, 0, 1, 1, 0, 1, 0, 1, 1, 0, 1, 1, 0, 1, 0, 1, 1, 0, 1, 1, 0, 1, 0, 1, 1, 0, 1, 0, 1, 1, 0, 1, 1, 0, 1, 0, 1, 1, 0, 1, 1, 0, 1, 0, 1, 1, 0, 1, 0, 1, 1, 0, 1, 1, 0, 1, 0
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

0,1


COMMENTS

This is another version of the Fibonacci word A005614.
(With offset 1) for k>0, a(ceiling(k*phi^2))=0 and a(floor(k*phi^2))=1 where phi=(1+sqrt(5))/2 is the Golden ratio.  Benoit Cloitre, Apr 01 2006
(With offset 1) for n>1 a(A000045(n)) = (1(1)^n)/2.
Equals the Fibonacci word A005614 with an initial zero.
Also the Sturmian word of slope phi (cf. A144595).  N. J. A. Sloane, Jan 13 2009
More precisely: (a(n)) is the inhomogeneous Sturmian word of slope phi1 and intercept 0: a(n) = floor((n+1)*(phi1))  floor(n*(phi1)), n >= 0.  Michel Dekking, May 21 2018
The ratio of number of 1's to number of 0's tends to the golden ratio (1+sqrt(5))/2 = 1.618...  Zak Seidov, Feb 15 2012


REFERENCES

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


LINKS

Table of n, a(n) for n=0..104.
Scott Balchin and Dan Rust, Computations for Symbolic Substitutions, Journal of Integer Sequences, Vol. 20 (2017), Article 17.4.1.
JP. Borel and François Laubie, Construction de mots de Christoffel, Comptes rendus de l'Académie des sciences. Série 1, Mathématique 313.8 (1991): 483485.
N. J. A. Sloane, Families of Essentially Identical Sequences, Mar 24 2021 (Includes this sequence)
Richard Southwell and Jianwei Huang, Complex Networks from Simple Rewrite Systems, arXiv preprint arXiv:1205.0596 [cs.SI], 2012.
Index entries for sequences that are fixed points of mappings


FORMULA

Conjecture: a(n) is given recursively by a(1)=0 and, for n>1, by a(n)=1 if n=F(2k+1) and a(n)=a(nF(2k+1)) otherwise, where F(2k+1) is the largest oddindexed Fibonacci number smaller than or equal to n. (This has been confirmed for more than nine million terms.) The oddindexed bisection of the Fibonacci numbers (A001519) is {1, 2, 5, 13, 34, 89, ...}. So by the conjecture, we would expect that a(30) = a(3013) = a(17) = a(1713) = a(4) = a(42) = a(2) = 1, which is in fact correct.  John W. Layman, Jun 29 2004
From Michel Dekking, Apr 13 2016: (Start)
Proof of the above conjecture:
Let g be the morphism above: g(0)=01, g(1)=011. Then g^n(0) has length F(2n+1), and (a(n)) starts with g^n(0) for all n>0. Obviously g^n(0) ends in 1 for all n, proving the first part of the conjecture.
We extend the semigroup of words with letters 0 and 1 to the free group, adding the inverses 0*:=0^{1} and 1*:=1^{1}. Easy observation: for any word w one has g(w1)= g(w0)1. We claim that for all n>1 one has g^n(0)=u(n)v(n)v(n)0*1, where u(n)=g(u(n1))0 and v(n)=0*g(v(n1))0. The recursion starts with u(2)=0, v(2)=10. Indeed: g^2(0)=01011=u(2)v(2)v(2)0*1. Induction step:
g^{n+1}(0)=g(g^n(0))= g(u(n)v(n)v(n)0*1)= g(u(n)v(n)v(n))1= g(u(n))00*g(v(n))00*g(v(n))00*1=u(n+1)v(n+1)v(n+1)0*1.
Since v(n) has length F(2n1), which is the largest oddindexed Fibonacci number smaller than or equal to m for all m between F(2n1) and F(2n+1), the claim proves the second part of the conjecture. (End)
(With offset 1) a(n) = 1 + floor(n*phi)  floor((n1)*phi) where phi=(1+sqrt(5))/2 so a(n) = 1 + A082389(n).  Benoit Cloitre, Apr 01 2006


MATHEMATICA

Nest[ Function[l, {Flatten[(l /. {0 > {0, 1}, 1 > {0, 1, 1}})]}], {0}, 6] (* Robert G. Wilson v, Feb 04 2005 *)


PROG

(PARI) a(n)=1+floor(n*(1+sqrt(5))/2)floor((n1)*(1+sqrt(5))/2) \\ Benoit Cloitre, Apr 01 2006


CROSSREFS

Cf. A003849, A096268, A001519. See A005614, A114986 for other versions.
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
Sequence in context: A193496 A284533 A286665 * A334820 A308185 A159689
Adjacent sequences: A096267 A096268 A096269 * A096271 A096272 A096273


KEYWORD

nonn,easy


AUTHOR

N. J. A. Sloane, Jun 22 2004


EXTENSIONS

More terms from John W. Layman, Jun 29 2004


STATUS

approved



