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

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A096270 Fixed point of the morphism 0->01, 1->011. 15

%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 phi-1 and intercept 0: a(n) = [(n+1)*(phi-1)]-[n*(phi-1)], 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, J-P., and Francois Laubie. "Construction de mots de Christoffel." Comptes rendus de l'Académie des sciences. Série 1, Mathématique 313.8 (1991): 483-485.

%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(n-F(2k+1)) otherwise, where F(2k+1) is the largest odd-index Fibonacci number smaller than or equal to n. (This has been confirmed for more than nine million terms.) The odd-index bisection of the Fibonacci numbers (A001519) is {1, 2, 5, 13, 34, 89, ...}. So by the conjecture, we would expect that a(30) = a(30-13) = a(17) = a(17-13) = a(4) = a(4-2) = 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(n-1))0 and v(n)=0*g(v(n-1))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(2n-1), which is the largest odd-index Fibonacci number smaller than or equal to m for all m between F(2n-1) 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((n-1)*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((n-1)*(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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified November 16 22:05 EST 2019. Contains 329208 sequences. (Running on oeis4.)