Golfing the Farey Sequence

[Phrogz]

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

 

[John Carter]

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

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 : (e-mail address removed)
New Zealand

 

[Phrogz]

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

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.

 

[John Carter]

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 : (e-mail address removed)
New Zealand

 

[John Carter]

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!

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 : (e-mail address removed)
New Zealand

 

[Bob]

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

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+d[i+1]<=N
d[i,1]=[d,d+d[i+1]]
n[i,1]=[n,n+n[i+1]]
i+=2
else
i+=1
end
end
}


d.each_index{ |i| print(n,"/", d,", ") }

 

[Bob]

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+d[i+1]<=N
d[i,1]=[d,d+d[i+1]]
n[i,1]=[n,n+n[i+1]]
i+=2
else
i+=1
end
end
}


d.each_index{ |i| print(n,"/", d,", ") }

--