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

on 2007-03-18 06:10

on 2007-03-19 23:14

On Sun, 18 Mar 2007, Phrogz wrote: Here's a cheap shot :-P > Here's starting code, based on the algorithm included in the Wikipedia > article for the Farey Sequence:[1] - N = 7 + N = 8 a,b,c,d=0,1,1,N - puts "#{a}/#{b}" while c<N + puts "#{a}/#{b}" 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 > > John Carter Phone : (64)(3) 358 6639 Tait Electronics Fax : (64)(3) 359 4632 PO Box 1645 Christchurch Email : john.carter@tait.co.nz New Zealand

on 2007-03-19 23:21

On Mar 19, 4:12 pm, John Carter <john.car...@tait.co.nz> wrote: > a,b,c,d=0,1,1,N > - puts "#{a}/#{b}" > while c<N > + puts "#{a}/#{b}" > k = (N+b)/d > e = k*c-a > f=k*d-b > a,b,c,d=c,d,e,f > - puts "#{a}/#{b}" > end I don't think there are any cheap shots in golf...except those that change the output. You've left off the final "1/1" for the sequence this way.

on 2007-03-20 00:08

On Tue, 20 Mar 2007, Phrogz wrote: > You've left off the final "1/1" for the sequence > this way. Drat! You're right. I didn't notice N went into the front of the sequence. Ah well, I'm obliged to hunt an expensive shot then. Ooh. Wait, there is a very very cheap shot available... a,b,c,d=0,1,1,7 puts "#{a}/#{b}" while c<7 k = (N+b)/d e = k*c-a f=k*d-b a,b,c,d=c,d,e,f puts "#{a}/#{b}" end Now that's really low! Another less silly is... a,b,c,d=0,1,1,7 puts "#{a}/#{b}" while c<7 k = (N+b)/d e = k*c-a a,b,c,d=c,d,e,k*d-b puts "#{a}/#{b}" end But not much better. I suspect the next level up will be to trade storage space for lines of code. John Carter Phone : (64)(3) 358 6639 Tait Electronics Fax : (64)(3) 359 4632 PO Box 1645 Christchurch Email : john.carter@tait.co.nz New Zealand

on 2007-03-20 00:27

On Tue, 20 Mar 2007, John Carter wrote: > > Now that's really low! Low as in the ethical sense, not the byte count. Way lower in the ethical sense and pretty nifty in the byte count is... puts "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 " John Carter Phone : (64)(3) 358 6639 Tait Electronics Fax : (64)(3) 359 4632 PO Box 1645 Christchurch Email : john.carter@tait.co.nz New Zealand

on 2007-03-20 00:44

A little shorter: N=7 a={} 0.upto(N) { |i| 1.upto(N) { |j| a[(i+0.0)/j] ||= "#{i}/#{j}" }} a.sort.each{|k,v|puts v if k<=1} -rr-

on 2007-03-27 00:01

Phrogz wrote: > > 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 Longer, but builds numerator/denominator arrays based on direct definition of Farey sequence. n=[0,1] d=[1,1] (N-1).times { i=0 while (i<d.length-1) if d[i]+d[i+1]<=N d[i,1]=[d[i],d[i]+d[i+1]] n[i,1]=[n[i],n[i]+n[i+1]] i+=2 else i+=1 end end } d.each_index{ |i| print(n[i],"/", d[i],", ") }

on 2007-03-27 02:21

> > 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 a minor improvement on size (Still keeping N as parameter). N=7 a,b,c,d=0,1,1,N puts "#{a}/#{b}" while c<N a,b,c,d=c,d,(N+b)/d*c-a,N-(N+b)%d puts "#{a}/#{b}" end > > Longer, but builds numerator/denominator arrays based on direct > definition of Farey sequence. Still working on this approach too, but original post should have included: N=7