Farey Sequence - Next Term

Next Term

A surprisingly simple algorithm exists to generate the terms in either traditional order (ascending) or non-traditional order (descending). The algorithm computes each successive entry in terms of the previous two entries using the mediant property given above. If a/b and c/d are the two given entries, and p/q is the unknown next entry, then c/d = (a + p)/(b + q). c/d is in lowest terms, so there is an integer k such that kc = a + p and kd = b + q, giving p = kca and q = kdb. The value of k must give a value of p/q which is as close as possible to c/d, which implies that k must be as large as possible subject to kdbn, so k is the greatest integer ≤ (n + b)/d. In other words, k = (n+b)/d, and

This is implemented in Python as:

def farey( n, asc=True ): """Python function to print the nth Farey sequence, either ascending or descending.""" if asc: a, b, c, d = 0, 1, 1, n # (*) else: a, b, c, d = 1, 1, n-1, n # (*) print "%d/%d" % (a,b) while (asc and c <= n) or (not asc and a > 0): k = int((n + b)/d) a, b, c, d = c, d, k*c - a, k*d - b print "%d/%d" % (a,b)

Brute-force searches for solutions to Diophantine equations in rationals can often take advantage of the Farey series (to search only reduced forms). The lines marked (*) can also be modified to include any two adjacent terms so as to generate terms only larger (or smaller) than a given term.

Read more about this topic:  Farey Sequence

Famous quotes containing the word term:

    Why did you give no hint that night
    That quickly after the morrow’s dawn,
    And calmly, as if indifferent quite,
    You would close your term here, up and be gone
    Thomas Hardy (1840–1928)

    Art, if one employs this term in the broad sense that includes poetry within its realm, is an art of creation laden with ideals, located at the very core of the life of a people, defining the spiritual and moral shape of that life.
    Ivan Sergeevich Turgenev (1818–1883)