From: Bob <bob@...>
Date: 2007-03-27T09:20:09+09:00
Subject: Re: Golfing the Farey Sequence

> Phrogz wrote:
> 
> > 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 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

> 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],", ") }





--