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:
“There’s no term to the work of a scientist.”
—Walter Reisch (1903–1963)
“Frankly, I do not like the idea of conversations to define the term “unconditional surrender.” ... The German people can have dinned into their ears what I said in my Christmas Eve speech—in effect, that we have no thought of destroying the German people and that we want them to live through the generations like other European peoples on condition, of course, that they get rid of their present philosophy of conquest.”
—Franklin D. Roosevelt (1882–1945)