

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 2dimensional 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+b1); for n to a+b1 do if y+1 <= a*x/b then y := y+1 else ans := ans+2^(a+bn1); x := x+1 end if end do; ans end proc;
for n from 2 to 12 do for b to n1 do a := nb; if gcd(a, n) = 1 then printf("%4d, ", christoffel(a, b)) end if end do end do


CROSSREFS

Cf. A144595A144602 (with slightly different definition of Christoffel word).
Sequence in context: A344001 A152973 A089747 * A173144 A049015 A005250
Adjacent sequences: A274167 A274168 A274169 * A274171 A274172 A274173


KEYWORD

easy,nonn


AUTHOR

Jamie Simpson, Jun 11 2016


STATUS

approved



