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

%I #85 Mar 28 2024 21:55:49

%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) = floor((n+1)*(phi-1)) - floor(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.

%H A.H.M. Smeets, <a href="/A096270/b096270.txt">Table of n, a(n) for n = 0..20000</a>

%H Scott Balchin and Dan Rust, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL20/Rust/rust3.html">Computations for Symbolic Substitutions</a>, Journal of Integer Sequences, Vol. 20 (2017), Article 17.4.1.

%H J-P. Borel and François Laubie, <a href="https://gallica.bnf.fr/ark:/12148/bpt6k57325582/f487.item">Construction de mots de Christoffel</a>, Comptes rendus de l'Académie des sciences. Série 1, Mathématique 313.8 (1991): 483-485.

%H N. J. A. Sloane, <a href="/A115004/a115004.txt">Families of Essentially Identical Sequences</a>, Mar 24 2021 (Includes this sequence)

%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-indexed Fibonacci number smaller than or equal to n. (This has been confirmed for more than nine million terms.) The odd-indexed 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-indexed 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

%o (Python)

%o from math import isqrt

%o def A096270(n): return (n+1+isqrt(5*(n+1)**2)>>1)-(n+isqrt(5*n**2)>>1)>>1 # _Chai Wah Wu_, Aug 29 2022

%o (Magma) [-1+Floor(n*(1+Sqrt(5))/2)-Floor((n-1)*(1+Sqrt(5))/2): n in [1..100]]; // _Wesley Ivan Hurt_, Aug 29 2022

%Y Cf. A003849, A096268, A001519. See A005614, A114986 for other versions.

%Y 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

%K nonn,easy

%O 0,1

%A _N. J. A. Sloane_, Jun 22 2004

%E More terms from _John W. Layman_, Jun 29 2004