A274170 - OEIS

%I #11 Jun 13 2016 08:57:39

%S 2,4,6,8,14,16,20,26,30,32,62,64,72,84,106,118,126,128,164,218,254,

%T 256,272,340,426,494,510,512,584,950,1022,1024,1056,1160,1316,1364,

%U 1706,1754,1910,2014,2046,2048,2708,3434,4094,4096,4160,4368,4680,5284,5460,6826,7002,7606,7918,8126,8190

%N Christoffel words as binary numbers.

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

%C 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.

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

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

%p 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;

%p 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

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

%K easy,nonn

%O 1,1

%A _Jamie Simpson_, Jun 11 2016