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 = kc − a and q = kd − b. 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 kd − b ≤ n, 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:
“A radical is one of whom people say “He goes too far.” A conservative, on the other hand, is one who “doesn’t go far enough.” Then there is the reactionary, “one who doesn’t go at all.” All these terms are more or less objectionable, wherefore we have coined the term “progressive.” I should say that a progressive is one who insists upon recognizing new facts as they present themselves—one who adjusts legislation to these new facts.”
—Woodrow Wilson (1856–1924)
“When “reality” is sought for at large, it is without intellectual import; at most the term carries the connotation of an agreeable emotional state.”
—John Dewey (1859–1952)