A144595 -id:A144595 - cp's OEIS frontend

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

N. J. A. Sloane, Jun 22 2004

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

J.-P. Allouche and J. Shallit, Automatic Sequences, Cambridge Univ. Press, 2003.

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

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

[-1+Floor(n*(1+Sqrt(5))/2)-Floor((n-1)*(1+Sqrt(5))/2): n in [1..100]]; // Wesley Ivan Hurt, Aug 29 2022

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

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

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

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

More terms from John W. Layman, Jun 29 2004

A144597 Christoffel word of slope 3/7.

Original entry on oeis.org

0, 0, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 0, 1, 0

Offset: 0

N. J. A. Sloane, Jan 13 2009

nonn

Periodic with period 10: repeat (0, 0, 0, 1, 0, 0, 1, 0, 0, 1). - M. F. Hasler, Oct 07 2016

See A144595 for further details.

Differs from A125117 from a(102) on.

A144597(n)=(n%=10)&&!(n%3) \\ M. F. Hasler, Oct 07 2016

A144611 Sturmian word of slope 2-sqrt(2).

Original entry on oeis.org

0, 1, 0, 1, 0, 1, 1, 0, 1, 0, 1, 1, 0, 1, 0, 1, 0, 1, 1, 0, 1, 0, 1, 1, 0, 1, 0, 1, 0, 1, 1, 0, 1, 0, 1, 1, 0, 1, 0, 1, 1, 0, 1, 0, 1, 0, 1, 1, 0, 1, 0, 1, 1, 0, 1, 0, 1, 0, 1, 1, 0, 1, 0, 1, 1, 0, 1, 0, 1, 1, 0, 1, 0, 1, 0, 1, 1, 0, 1, 0, 1, 1, 0, 1, 0, 1, 0, 1, 1, 0, 1, 0, 1, 1, 0, 1, 0, 1, 0, 1, 1, 0, 1, 0, 1

Offset: 0

N. J. A. Sloane, Jan 13 2009

nonn

Old name was: Sturmian word of slope 2.
Conjecture: a(n) = floor((n+1)*log(3)/log(2)) - floor(n*log(3)/log(2)) - 1.
This is not true: Let b(n) = floor((n+1)*log(3)/log(2)) - floor(n*log(3)/log(2)) - 1. Then b(40) = 0, whereas a(40) = 1. This is the first term at which a(n) and b(n) disagree. - Danny Rorabaugh, Mar 14 2015
From Benoit Cloitre, Oct 16 2016: (Start)
Let u(n) = n + floor(sqrt(2)*n) (A003151) and v(n) = n + floor(n/sqrt(2)) (A003152) then u,v form a partition of the positive integers and we have, for n >= 1, a(u(n))=0 and a(v(n))=1.
Another way to construct the sequence: merge the sequences x(n) = 2n^2+1 and y(n) = 4n^2 (n >= 1) into an increasing sequence z(n) which then begins: 3,4,9,16,19,33,36,51,64,73 (not in the OEIS). Then for n >= 1, a(n) = z(n) mod 2. (End)
From Michel Dekking, Feb 16 2020: (Start)
This sequence is a Sturmian sequence s(alpha,rho) with slope alpha = 2-sqrt(2), and intercept rho = 0.
In general, one passes from slope alpha to slope 1-alpha by exchanging 0 and 1. It therefore follows from the Comments of A006337 that (a(n+1)) is the unique fixed point of the morphism 0 -> 101, 1 -> 10. (End)

Danny Rorabaugh, Table of n, a(n) for n = 0..10000
M. Lothaire, Algebraic combinatorics on words, Cambridge University Press. Online publication date: April 2013; Print publication year: 2002.
Mike Winkler, On the structure and the behaviour of Collatz 3n+ 1 sequences, arXiv:1412.0519 [math.GM], 2014.

See A144595 for further details. Cf. A006337, A074840.

christoffel[s_, M_] := Module[{n, x = 1, y = 0, ans = {0}}, Do[If[y + 1 <= s*x, AppendTo[ans, 1]; y++, AppendTo[ans, 0]; x++], {n, 1, M}]; ans] (* or Sturmian word, Jean-François Alcover, Sep 19 2016, A274170 *); christoffel[Sqrt[2], 105] (* Robert G. Wilson v, Feb 02 2017 *)

\\ to get N terms
a(n)=if(n<1,0,vecsort(concat(vector(floor(sqrt(2)*N),i,2*i^2+1),vector(N,j,4*j^2)))[n]%2) \\ Benoit Cloitre, Oct 16 2016

#Generate the first n terms (plus a few) of the Sturmian word of slope a
def Sturmian(a,n):
    y = 0
    A = []
    while len(A)<=n:
        y += a
        A.extend([0]+[1]*(floor(y)-floor(y-a)))
    return A
Sturmian(sqrt(2),104)
# Danny Rorabaugh, Mar 14 2015

a(n) = floor((n+1)*alpha) - floor(n*alpha), where alpha = 2-sqrt(2). - Michel Dekking, Feb 16 2020

Name corrected by Michel Dekking, Feb 16 2020

A274170 Christoffel words as binary numbers.

Original entry on oeis.org

2, 4, 6, 8, 14, 16, 20, 26, 30, 32, 62, 64, 72, 84, 106, 118, 126, 128, 164, 218, 254, 256, 272, 340, 426, 494, 510, 512, 584, 950, 1022, 1024, 1056, 1160, 1316, 1364, 1706, 1754, 1910, 2014, 2046, 2048, 2708, 3434, 4094, 4096, 4160, 4368, 4680, 5284, 5460, 6826, 7002, 7606, 7918, 8126, 8190

Offset: 1

Jamie Simpson, Jun 11 2016

The Christoffel word of slope b/a is defined as follows:

Start at (0,0) in the 2-dimensional integer lattice and move up if possible, otherwise right, always keeping below or on the line y = b*x/a. Write down x for a horizontal move and y for a vertical move. The first move is necessarily horizontal, so the sequence always begins with x. Stop when you get to (a,b). The word then has length a+b and contains a copies of x and b of y (see Berstel et al., p. 6, Fig. 2). The symbols x and y are arbitrary: we replace x with 1 and y with 0 and treat the resulting word as a binary number. The sequence is in increasing order of decimal equivalents. The Christoffel word with least decimal equivalent is 10 with decimal equivalent 2.

			The Christoffel word of slope 4/7 is xxyxxyxxyxy which becomes 11011011010 with decimal equivalent 1754.

J. Berstel et al., Combinatorics on Words: Christoffel Words and Repetitions in Words, Amer. Math. Soc., 2008.

Cf. A144595-A144602 (with slightly different definition of Christoffel word).

christoffel := proc (a, b) local n, x, y, ans; x := 1; y := 0; ans := 2^(a+b-1); for n to a+b-1 do if y+1 <= a*x/b then y := y+1 else ans := ans+2^(a+b-n-1); x := x+1 end if end do; ans end proc;
for n from 2 to 12 do for b to n-1 do a := n-b; if gcd(a, n) = 1 then printf("%4d, ", christoffel(a, b)) end if end do end do

A144596 Christoffel word of slope 2/7.

Original entry on oeis.org

0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0

Offset: 0

N. J. A. Sloane, Jan 13 2009

The path is on the slope after 0, 9, 18, 27, 36 ,.... (A008591) steps, which gives the C-finite recurrence.

See A144595 for further details.

a(n) = a(n-9). - R. J. Mathar, May 28 2025

G.f.: -x^4*(1+x^4) / ( (x-1)*(1+x+x^2)*(x^6+x^3+1) ). - R. J. Mathar, May 28 2025

A144602 Christoffel word of slope 4/11.

Original entry on oeis.org

0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 1

Offset: 0

N. J. A. Sloane, Jan 13 2009

The path is on the slope after 0, 15, 30, 45, 60, 75,... (A008597) steps, which gives a simple C-finite recurrence. - R. J. Mathar, May 28 2025

See A144595 for further details.

a(n) = a(n-15). - R. J. Mathar, May 28 2025

G.f.: -x^3*(1+x^4+x^8+x^11) / ( (x-1)*(1+x^4+x^3+x^2+x)*(1+x+x^2)*(1-x+x^3-x^4+x^5-x^7+x^8) ). - R. J. Mathar, May 28 2025

A144608 Christoffel word of slope 10/11.

Original entry on oeis.org

0, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1

Offset: 0

N. J. A. Sloane, Jan 13 2009

The path is on the slope after 0, 21, 42, 63, 84,... steps (A008603), which gives the simple C-finite recurrence. - R. J. Mathar, May 28 2025

See A144595 for further details.

a(n) = a(n-21). - R. J. Mathar, May 28 2025

G.f.: -x^2*(1+x^2)*(x^8-x^6+x^4-x^2+1)*(x^4-x^3+x^2-x+1)*(1+x+x^2+x^3+x^4) / ( (x-1)*(1+x^6+x^5+x^4+x^3+x^2+x)*(1+x+x^2)*(1-x+x^3-x^4+x^6-x^8+x^9-x^11+x^12) ). - R. J. Mathar, May 28 2025

A144609 Sturmian word of slope Pi.

Original entry on oeis.org

0, 1, 1, 1, 0, 1, 1, 1, 0, 1, 1, 1, 0, 1, 1, 1, 0, 1, 1, 1, 0, 1, 1, 1, 0, 1, 1, 1, 0, 1, 1, 1, 1, 0, 1, 1, 1, 0, 1, 1, 1, 0, 1, 1, 1, 0, 1, 1, 1, 0, 1, 1, 1, 0, 1, 1, 1, 0, 1, 1, 1, 1, 0, 1, 1, 1, 0, 1, 1, 1, 0, 1, 1, 1, 0, 1, 1, 1, 0, 1, 1, 1, 0, 1, 1, 1, 0, 1, 1, 1, 1, 0, 1, 1, 1, 0, 1, 1, 1, 0, 1, 1, 1, 0, 1

Offset: 0

N. J. A. Sloane, Jan 13 2009

nonn

A063438 seems to contain the run lengths of 1's. - R. J. Mathar, May 30 2025

See A144595 for further details.
Seems to be very similar to A070127. Is this a coincidence?
Cf. A063438, A076539 (partial sums).

Digits := 500 :
x :=1 ;
y :=0 ;
slop := Pi ;
printf("0,") ;
for n from 1 to 300 do
    if evalf((y+1)/x-slop) > 0 then
        x := x+1 ;
        printf("0,") ;
    else
        y := y+1 ;
        printf("1,") ;
    end if;
end do: # R. J. Mathar, May 30 2025

christoffel[s_, M_] := Module[{n, x = 1, y = 0, ans = {0}}, Do[ If[y + 1 <= s*x, AppendTo[ans, 1]; y++, AppendTo[ans, 0]; x++], {n, 1, M}]; ans]; christoffel[Pi, 105] (* Robert G. Wilson v, Feb 02 2017, after Jean-François Alcover, Sep 19 2016, A274170 *)

A144610 Sturmian word of slope e.

Original entry on oeis.org

0, 1, 1, 0, 1, 1, 1, 0, 1, 1, 1, 0, 1, 1, 0, 1, 1, 1, 0, 1, 1, 1, 0, 1, 1, 1, 0, 1, 1, 0, 1, 1, 1, 0, 1, 1, 1, 0, 1, 1, 0, 1, 1, 1, 0, 1, 1, 1, 0, 1, 1, 1, 0, 1, 1, 0, 1, 1, 1, 0, 1, 1, 1, 0, 1, 1, 0, 1, 1, 1, 0, 1, 1, 1, 0, 1, 1, 1, 0, 1, 1, 0, 1, 1, 1, 0, 1, 1, 1, 0, 1, 1, 0, 1, 1, 1, 0, 1, 1, 1, 0, 1, 1, 1, 0

Offset: 0

N. J. A. Sloane, Jan 13 2009

nonn

See A144595 for further details.

Cf. A085369. [From R. J. Mathar, Feb 21 2009]

A144598 Christoffel word of slope 5/7.

Original entry on oeis.org

0, 0, 1, 0, 1, 0, 0, 1, 0, 1, 0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 1, 0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 1, 0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 1, 0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 1, 0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 1, 0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 1, 0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 1, 0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0

Offset: 0

N. J. A. Sloane, Jan 13 2009

The path is on the slope after 0, 12, 24, 36, 48,... (A008594) steps, which gives the C-finite recurrence. - R. J. Mathar, May 28 2025

See A144595 for further details.

a(n) = a(n-12). - R. J. Mathar, May 28 2025

G.f.: -x^2*(1+x^2+x^5+x^7+x^9) / ( (x-1)*(1+x+x^2)*(1+x)*(1-x+x^2)*(1+x^2)*(x^4-x^2+1) ). - R. J. Mathar, May 28 2025

cp's OEIS Frontend

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

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Magma

Mathematica

PARI

Python

Formula

Extensions

A144597 Christoffel word of slope 3/7.

Views

Author

Keywords

Comments

Crossrefs

Programs

PARI

A144611 Sturmian word of slope 2-sqrt(2).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

Sage

Formula

Extensions

A274170 Christoffel words as binary numbers.

Views

Author

Keywords

Comments

Examples

References

Crossrefs

Programs

Maple

A144596 Christoffel word of slope 2/7.

Views

Author

Keywords

Comments

Crossrefs

Formula

A144602 Christoffel word of slope 4/11.

Views

Author

Keywords

Comments

Crossrefs

Formula

A144608 Christoffel word of slope 10/11.

Views

Author

Keywords

Comments

Crossrefs

Formula

A144609 Sturmian word of slope Pi.

Views

Author

Keywords

Comments

Crossrefs

Programs

Maple

Mathematica

A144610 Sturmian word of slope e.

Views

Author