From: Phrogz <gavin@...>
Date: 2007-03-18T14:10:08+09:00
Subject: Golfing the Farey Sequence

A Farey Sequence is all the fractions between 0 and 1 (inclusive) with
a denominator no bigger than N, arranged in increasing order of
magnitude.

For example, the Farey Sequence of order 3 is:
0/1, 1/3, 1/2, 2/3, 1/1

and the Farey Sequence of order 7 is:
0/1, 1/7, 1/6, 1/5, 1/4, 2/7, 1/3, 2/5, 3/7, 1/2, 4/7, 3/5, 2/3, 5/7,
3/4, 4/5, 5/6, 6/7, 1/1

My challenge - come up with the least-bytes Ruby code that, given a
constant N set to the order, can print out the sequence (one value per
line).

Here's starting code, based on the algorithm included in the Wikipedia
article for the Farey Sequence:[1]

N = 7

a,b,c,d=0,1,1,N
puts "#{a}/#{b}"
while c<N
  k = (N+b)/d
  e = k*c-a
  f=k*d-b
  a,b,c,d=c,d,e,f
  puts "#{a}/#{b}"
end

[1] http://en.wikipedia.org/wiki/Farey_sequence