cp's OEIS Frontend

A144595 Christoffel word of slope 4/7.

%I A144595 #24 Dec 12 2023 08:30:24
%S A144595 0,0,1,0,0,1,0,0,1,0,1,0,0,1,0,0,1,0,0,1,0,1,0,0,1,0,0,1,0,0,1,0,1,0,
%T A144595 0,1,0,0,1,0,0,1,0,1,0,0,1,0,0,1,0,0,1,0,1,0,0,1,0,0,1,0,0,1,0,1,0,0,
%U A144595 1,0,0,1,0,0,1,0,1,0,0,1,0,0,1,0,0,1,0,1,0,0,1,0,0,1,0,0,1,0,1,0,0,1,0,0,1
%N A144595 Christoffel word of slope 4/7.
%C A144595 The Christoffel word (or path) of slope s is defined as follows.
%C A144595 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 = s*x. Write down 0 with a horizontal move, 1 for a vertical move. The first move is necessarily horizontal, so the sequence always begins with 0.
%C A144595 If s is irrational this is called a Sturmian word.
%C A144595 If the first 9 terms are deleted we get the "Upper Christoffel word of slope 4/7" (see Berstal et al., p. 6, Fig. 2).
%C A144595 The length of a Christoffel word of fraction a/b > 0 is a + b, with a ones. - _David A. Corneth_, Sep 19 2016
%D A144595 J. Berstel et al., Combinatorics on Words: Christoffel Words and Repetitions in Words, Amer. Math. Soc., 2008.
%H A144595 J. Berstel et al., <a href="http://www-igm.univ-mlv.fr/~berstel/LivreCombinatoireDesMots/2008wordsbookMtlUltimate.pdf">Combinatorics on Words: Christoffel Words and Repetitions in Words</a>
%F A144595 Period 11: 0,0,1,0,0,1,0,0,1,0,1.
%F A144595 a(n) = a(n-11).
%F A144595 G.f. -x^2*(1+x^3+x^6+x^8) / ( (x-1)*(1+x^10+x^9+x^8+x^7+x^6+x^5+x^4+x^3+x^2+x) ). - _R. J. Mathar_, Jul 09 2013
%p A144595 christoffel:=proc(s,M) local n,x,y,ans;
%p A144595 ans:=[0]; x:=1; y:=0;
%p A144595 for n from 1 to M do
%p A144595 if y+1 <= s*x then ans:=[op(ans),1]; y:=y+1; else ans:=[op(ans),0]; x:=x+1; fi;
%p A144595 od: ans; end; christoffel(4/7,120);
%t A144595 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[4/7, 120] (* _Jean-François Alcover_, Sep 19 2016, adapted from Maple *)
%o A144595 (PARI) \\ Christoffel word for nonnegative rational f.
%o A144595 Cword(f) = {my(n = numerator(f), d = denominator(f), v = vector(n + d), c, s, t = 1, i = 1); v[#v] = 1; while(t<=#v-4, i++; c=(i*f>=s+1); if(c, i-=2; s++, t++); v[t+2]=c); v}
%o A144595 a(n) = my(c = Cword(4/7)); c[(n-1)%#c+1] \\ _David A. Corneth_, Sep 19 2016
%Y A144595 Cf. A144596-A144608.
%K A144595 nonn,easy
%O A144595 0,1
%A A144595 _N. J. A. Sloane_, Jan 13 2009