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:
“The developments in the North were those loosely embraced in the term modernization and included urbanization, industrialization, and mechanization. While those changes went forward apace, the antebellum South changed comparatively little, clinging to its rural, agricultural, labor-intensive economy and its traditional folk culture.”
—C. Vann Woodward (b. 1908)
“There’s no term to the work of a scientist.”
—Walter Reisch (1903–1963)