farey_sequences.sf

#!/usr/bin/ruby

# The nth Farey sequence in ascending order.

# See also:
#   https://en.wikipedia.org/wiki/Farey_sequence

func farey_sequence(n) {
    var (a, b, c, d) = (0, 1, 1, n)

    var seq = [a/b]

    while (c <= n) {
        var k = (n+b)//d
        (a, b, c, d) = (c, d, k*c - a, k*d - b)
        seq << a/b
    }

    return seq
}

for n in (0..10) {
    say farey_sequence(n)
}

__END__
[0]
[0, 1]
[0, 1/2, 1]
[0, 1/3, 1/2, 2/3, 1]
[0, 1/4, 1/3, 1/2, 2/3, 3/4, 1]
[0, 1/5, 1/4, 1/3, 2/5, 1/2, 3/5, 2/3, 3/4, 4/5, 1]
[0, 1/6, 1/5, 1/4, 1/3, 2/5, 1/2, 3/5, 2/3, 3/4, 4/5, 5/6, 1]
[0, 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]
[0, 1/8, 1/7, 1/6, 1/5, 1/4, 2/7, 1/3, 3/8, 2/5, 3/7, 1/2, 4/7, 3/5, 5/8, 2/3, 5/7, 3/4, 4/5, 5/6, 6/7, 7/8, 1]
[0, 1/9, 1/8, 1/7, 1/6, 1/5, 2/9, 1/4, 2/7, 1/3, 3/8, 2/5, 3/7, 4/9, 1/2, 5/9, 4/7, 3/5, 5/8, 2/3, 5/7, 3/4, 7/9, 4/5, 5/6, 6/7, 7/8, 8/9, 1]
[0, 1/10, 1/9, 1/8, 1/7, 1/6, 1/5, 2/9, 1/4, 2/7, 3/10, 1/3, 3/8, 2/5, 3/7, 4/9, 1/2, 5/9, 4/7, 3/5, 5/8, 2/3, 7/10, 5/7, 3/4, 7/9, 4/5, 5/6, 6/7, 7/8, 8/9, 9/10, 1]