%I
%S 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,
%T 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,
%U 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
%N Fixed point of the morphism 0>01, 1>011.
%C This is another version of the Fibonacci word A005614.
%C (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
%C (With offset 1) for n>1 a(A000045(n))=(1(1)^n)/2.
%C Equals the Fibonacci word A005614 with an initial zero.
%C Also the Sturmian word of slope phi (cf. A144595).  _N. J. A. Sloane_, Jan 13 2009
%C More precisely: (a(n)) is the inhomogeneous Sturmian word of slope phi1 and intercept 0: a(n) = [(n+1)*(phi1)][n*(phi1)], n>=0.  _Michel Dekking_, May 21 2018
%C 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
%D J.P. Allouche and J. Shallit, Automatic Sequences, Cambridge Univ. Press, 2003.
%D Borel, JP., and Francois Laubie. "Construction de mots de Christoffel." Comptes rendus de l'Académie des sciences. Série 1, Mathématique 313.8 (1991): 483485.
%H Scott Balchin and Dan Rust, <a href="http://www.emis.ams.org/journals/JIS/VOL20/Rust/rust3.html">Computations for Symbolic Substitutions</a>, Journal of Integer Sequences, Vol. 20 (2017), Article 17.4.1.
%H Richard Southwell and Jianwei Huang, <a href="http://arxiv.org/abs/1205.0596">Complex Networks from Simple Rewrite Systems</a>, arXiv preprint arXiv:1205.0596 [cs.SI], 2012.
%H <a href="/index/Fi#FIXEDPOINTS">Index entries for sequences that are fixed points of mappings</a>
%F 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 oddindex Fibonacci number smaller than or equal to n. (This has been confirmed for more than nine million terms.) The oddindex 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
%F From _Michel Dekking_, Apr 13 2016: (Start)
%F Proof of the above conjecture:
%F 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.
%F 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:
%F 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.
%F Since v(n) has length F(2n1), which is the largest oddindex 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)
%F (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
%t Nest[ Function[l, {Flatten[(l /. {0 > {0, 1}, 1 > {0, 1, 1}})]}], {0}, 6] (* _Robert G. Wilson v_, Feb 04 2005 *)
%o (PARI) a(n)=1+floor(n*(1+sqrt(5))/2)floor((n1)*(1+sqrt(5))/2) \\ _Benoit Cloitre_, Apr 01 2006
%Y Cf. A003849, A096268, A001519. See A005614, A114986 for other versions.
%K nonn,easy
%O 0,1
%A _N. J. A. Sloane_, Jun 22 2004
%E More terms from _John W. Layman_, Jun 29 2004
