

A096270


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


15



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) = [(n+1)*(phi1)][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.
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.


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.
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 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
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 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)
(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.
Sequence in context: A193496 A284533 A286665 * A159689 A174282 A189301
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



