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. 14
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

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, 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.

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

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

(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

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((n-1)*(1+sqrt(5))/2) \\ Benoit Cloitre, Apr 01 2006

CROSSREFS

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

Sequence in context: A117872 A089809 A165211 * A159689 A174282 A123640

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

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

License Agreements, Terms of Use, Privacy Policy .

Last modified October 20 17:39 EDT 2017. Contains 293648 sequences.