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

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

Offset: 0

Author

N. J. A. Sloane, Jun 22 2004

Keywords

• nonn
• easy

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 phi-1 and intercept 0: a(n) = floor((n+1)*(phi-1)) - floor(n*(phi-1)), 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

• A.H.M. Smeets, Table of n, a(n) for n = 0..20000
• Scott Balchin and Dan Rust, Computations for Symbolic Substitutions, Journal of Integer Sequences, Vol. 20 (2017), Article 17.4.1.
• J-P. 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): 483-485.
• 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

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

Programs

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

Mathematica

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

PARI

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

Python

from math import isqrt
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

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(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

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(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:

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(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)

(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

Extensions

More terms from John W. Layman, Jun 29 2004