# Golfing the Farey Sequence

**URL:** <https://www.ruby-forum.com/t/golfing-the-farey-sequence/89174>\
**Category:** Ruby\
**Created:** [March 18, 2007, 6:10am UTC](https://www.ruby-forum.com/t/golfing-the-farey-sequence/89174 "2007-03-18T06:10:41Z")\
**Posts on this page:** 8\
**Page:** 1

<div class="post-metadata">

**Author:** ![phrogz](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/p/2acd7d/32.png) [@phrogz](https://www.ruby-forum.com/u/phrogz)\
**Post date:** [March 18, 2007, 6:10am UTC](https://www.ruby-forum.com/t/golfing-the-farey-sequence/89174/1 "2007-03-18T06:10:41Z")

</div>

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] [Farey sequence - Wikipedia](http://en.wikipedia.org/wiki/Farey_sequence)

---

<div class="post-metadata">

**Author:** ![phrogz](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/p/2acd7d/32.png) [@phrogz](https://www.ruby-forum.com/u/phrogz)\
**Post date:** [March 19, 2007, 11:14pm UTC](https://www.ruby-forum.com/t/golfing-the-farey-sequence/89174/2 "2007-03-19T23:14:08Z")

</div>

On Sun, 18 Mar 2007, Phrogz wrote:

Here’s a cheap shot 😛

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

- N = 7

- N = 8

- 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] [Farey sequence - Wikipedia](http://en.wikipedia.org/wiki/Farey_sequence)

John C. Phone : (64)(3) 358 6639  
Tait Electronics Fax : (64)(3) 359 4632  
PO Box 1645 Christchurch Email : removed\_email\_address@domain.invalid  
New Zealand

---

<div class="post-metadata">

**Author:** ![phrogz](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/p/2acd7d/32.png) [@phrogz](https://www.ruby-forum.com/u/phrogz)\
**Post date:** [March 19, 2007, 11:21pm UTC](https://www.ruby-forum.com/t/golfing-the-farey-sequence/89174/3 "2007-03-19T23:21:09Z")

</div>

On Mar 19, 4:12 pm, John C. [removed\_email\_address@domain.invalid](mailto:removed_email_address@domain.invalid) 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.

---

<div class="post-metadata">

**Author:** ![phrogz](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/p/2acd7d/32.png) [@phrogz](https://www.ruby-forum.com/u/phrogz)\
**Post date:** [March 20, 2007, 12:08am UTC](https://www.ruby-forum.com/t/golfing-the-farey-sequence/89174/4 "2007-03-20T00:08:17Z")

</div>

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 C. Phone : (64)(3) 358 6639  
Tait Electronics Fax : (64)(3) 359 4632  
PO Box 1645 Christchurch Email : removed\_email\_address@domain.invalid  
New Zealand

---

<div class="post-metadata">

**Author:** ![phrogz](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/p/2acd7d/32.png) [@phrogz](https://www.ruby-forum.com/u/phrogz)\
**Post date:** [March 20, 2007, 12:44am UTC](https://www.ruby-forum.com/t/golfing-the-farey-sequence/89174/5 "2007-03-20T00:44:27Z")

</div>

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-

---

<div class="post-metadata">

**Author:** ![phrogz](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/p/2acd7d/32.png) [@phrogz](https://www.ruby-forum.com/u/phrogz)\
**Post date:** [March 27, 2007, 12:01am UTC](https://www.ruby-forum.com/t/golfing-the-farey-sequence/89174/6 "2007-03-27T00:01:13Z")

</div>

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] [Farey sequence - Wikipedia](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],", ") }

---

<div class="post-metadata">

**Author:** ![phrogz](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/p/2acd7d/32.png) [@phrogz](https://www.ruby-forum.com/u/phrogz)\
**Post date:** [March 20, 2007, 12:27am UTC](https://www.ruby-forum.com/t/golfing-the-farey-sequence/89174/7 "2007-03-20T00:27:26Z")

</div>

On Tue, 20 Mar 2007, John C. 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 C. Phone : (64)(3) 358 6639  
Tait Electronics Fax : (64)(3) 359 4632  
PO Box 1645 Christchurch Email : removed\_email\_address@domain.invalid  
New Zealand

---

<div class="post-metadata">

**Author:** ![phrogz](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/p/2acd7d/32.png) [@phrogz](https://www.ruby-forum.com/u/phrogz)\
**Post date:** [March 27, 2007, 2:21am UTC](https://www.ruby-forum.com/t/golfing-the-farey-sequence/89174/8 "2007-03-27T02:21:26Z")

</div>

> > 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