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:
“Most literature on the culture of adolescence focuses on peer pressure as a negative force. Warnings about the “wrong crowd” read like tornado alerts in parent manuals. . . . It is a relative term that means different things in different places. In Fort Wayne, for example, the wrong crowd meant hanging out with liberal Democrats. In Connecticut, it meant kids who weren’t planning to get a Ph.D. from Yale.”
—Mary Kay Blakely (20th century)
“We now demand the light artillery of the intellect; we need the curt, the condensed, the pointed, the readily diffused—in place of the verbose, the detailed, the voluminous, the inaccessible. On the other hand, the lightness of the artillery should not degenerate into pop-gunnery—by which term we may designate the character of the greater portion of the newspaper press—their sole legitimate object being the discussion of ephemeral matters in an ephemeral manner.”
—Edgar Allan Poe (1809–1845)