login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A274170 Christoffel words as binary numbers. 2
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 (list; graph; refs; listen; history; text; internal format)
OFFSET

1,1

COMMENTS

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.

REFERENCES

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

LINKS

Table of n, a(n) for n=1..57.

EXAMPLE

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

MAPLE

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

CROSSREFS

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

Sequence in context: A054409 A152973 A089747 * A173144 A049015 A005250

Adjacent sequences:  A274167 A274168 A274169 * A274171 A274172 A274173

KEYWORD

easy,nonn

AUTHOR

Jamie Simpson, Jun 11 2016

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
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified August 12 11:10 EDT 2020. Contains 336438 sequences. (Running on oeis4.)