Golfing the Farey Sequence

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

Here's a cheap shot :stuck_out_tongue:

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] Farey sequence - Wikipedia

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 Sun, 18 Mar 2007, Phrogz wrote:

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] Farey sequence - Wikipedia

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

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

> 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

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

--

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 Tue, 20 Mar 2007, Phrogz wrote:

You've left off the final "1/1" for the sequence
this way.

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 Tue, 20 Mar 2007, John Carter wrote:

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!

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-