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.
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
KEYWORD
easy,nonn
AUTHOR
Jamie Simpson, Jun 11 2016
STATUS
approved