Forum: Ruby Golfing the Farey Sequence

Announcement (2017-05-07): www.ruby-forum.com is now read-only since I unfortunately do not have the time to support and maintain the forum any more. Please see rubyonrails.org/community and ruby-lang.org/en/community for other Rails- und Ruby-related community platforms.
on 2007-03-18 06:10
```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-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```
This topic is locked and can not be replied to.