Welcome, guest | Sign In | My Account | Store | Cart

Farey Sequence (Python recipe) by James Kassemi
ActiveState Code (http://code.activestate.com/recipes/496821/)

Function provides farey sequence, F(n), for any integer n.

Python, 21 lines
Download
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
def farey(n):
    def gcd(a,b):
        while b: a,b = b,a%b
        return a

    def simplify(a,b):
        g = gcd(a,b)
        return (a/g,b/g)

    fs = dict()
    for i in xrange(1,n+1):
        for i2 in xrange(1,i+1):
            if i2 < n and i != i2:
                r = simplify(i2,i)
                fs[float(i2)/i] = r

    return [fs[k] for k in sorted(fs.keys())]

# Usage:
# print farey(5)
# => [(1, 5), (1, 4), (1, 3), (2, 5), (1, 2), (3, 5), (2, 3), (3, 4), (4, 5)]

There's probably a more elegant solution out there, but I couldn't find it. Note: it doesn't prepend (0,1) and append (1,1)...

For more info: http://mathworld.wolfram.com/FareySequence.html

Tags: algorithms

3 comments

Scott David Daniels 17 years, 10 months ago  # | flag

Some simpler ways based on the Farey properties. See also my Recipe 52317 (whose comments section seems mangled now).

In the following we have a straight-forward recursive generator named "Farey_r" and an equivalent, but more efficient, generator named "farey". "Farey_r" is provided simply to make it 'clear' (and more provable) what the generator is computing.

def Farey_r(limit, start=(0, 1), stop=(1, 1)):
    '''recursive definition of a Farey sequence generator'''
    n, d = start
    N, D = stop
    mediant_d = d + D
    if mediant_d &lt;= limit:
        mediant = (n + N), mediant_d
        for pair in Farey_r(limit, start, mediant): yield pair
        for pair in Farey_r(limit, mediant, stop): yield pair
    else:
        yield start


def farey(limit):
    '''Fast computation of Farey sequence as a generator'''
    # n, d is the start fraction n/d (0,1) initially
    # N, D is the stop fraction N/D (1,1) initially
    pend = []
    n = 0
    d = N = D = 1
    while True:
        mediant_d = d + D
        if mediant_d &lt;= limit:
            mediant_n = n + N
            pend.append((mediant_n, mediant_d, N, D))
            N = mediant_n
            D = mediant_d
        else:
            yield n, d
            if pend:
                n, d, N, D = pend.pop()
            else:
                break
James Kassemi (author) 17 years, 10 months ago  # | flag

Yep. Sorry about not referencing your recipe, I thought I did a search, but I must have missed it.

For those who didn't see it, take a look, the mediant calculation approach is certainly more effective.

soma biswas 9 years ago  # | flag

could you please write farey sequence code in MATLAB

Created by James Kassemi on Sat, 24 Jun 2006 (PSF)
◄ Python recipes (4591) ►
◄ James Kassemi's recipes (4) ►

Required Modules

  • (none specified)

Other Information and Tasks