[lnkForumImage]
TotalShareware - Download Free Software
Confronta i prezzi di migliaia di prodotti.
Asp Forum
 Home | Login | Register | Search 


 

Forums >

comp.lang.ruby

Golfing the Farey Sequence

Gavin Kistner

3/18/2007 5:09:00 AM

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/Fare...
4 Answers

John Carter

3/19/2007 10:12:00 PM

0

Gavin Kistner

3/19/2007 10:17:00 PM

0

On Mar 19, 4:12 pm, John Carter <john.car...@tait.co.nz> wrote:
> 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

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.

Bob

3/26/2007 9:54:00 PM

0

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 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/Fare...


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

Bob

3/27/2007 12:18:00 AM

0

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





--