Farey sequence

func farey_count(n) {   # A005728
    1 + sum(1..n, {|k| euler_phi(k) })
}

func farey(n) {

    var seq = [0]
    var (a,b,c,d) = (0,1,1,n)

    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
}

say "Farey sequence for order 1 through 11 (inclusive):"
for n in (1..11) {
    say("F(%2d): %s" % (n, farey(n).map{.as_frac}.join(" ")))
}

say "\nNumber of fractions in the Farey sequence:"
for n in (100..1000 -> by(100)) {
    say ("F(%4d) =%7d" % (n, farey_count(n)))
}

Output:

Farey sequence for order 1 through 11 (inclusive):
F( 1): 0/1 1/1
F( 2): 0/1 1/2 1/1
F( 3): 0/1 1/3 1/2 2/3 1/1
F( 4): 0/1 1/4 1/3 1/2 2/3 3/4 1/1
F( 5): 0/1 1/5 1/4 1/3 2/5 1/2 3/5 2/3 3/4 4/5 1/1
F( 6): 0/1 1/6 1/5 1/4 1/3 2/5 1/2 3/5 2/3 3/4 4/5 5/6 1/1
F( 7): 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
F( 8): 0/1 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/1
F( 9): 0/1 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/1
F(10): 0/1 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/1
F(11): 0/1 1/11 1/10 1/9 1/8 1/7 1/6 2/11 1/5 2/9 1/4 3/11 2/7 3/10 1/3 4/11 3/8 2/5 3/7 4/9 5/11 1/2 6/11 5/9 4/7 3/5 5/8 7/11 2/3 7/10 5/7 8/11 3/4 7/9 4/5 9/11 5/6 6/7 7/8 8/9 9/10 10/11 1/1

Number of fractions in the Farey sequence:
F( 100) =   3045
F( 200) =  12233
F( 300) =  27399
F( 400) =  48679
F( 500) =  76117
F( 600) = 109501
F( 700) = 149019
F( 800) = 194751
F( 900) = 246327
F(1000) = 304193

Last updated