Editing Farey sequence (section)

==Next term==
A surprisingly simple algorithm exists to generate the terms of ''F<sub>n</sub>'' 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 {{sfrac|''a''|''b''}} and {{sfrac|''c''|''d''}} are the two given entries, and {{sfrac|''p''|''q''}} is the unknown next entry, then {{math|1={{sfrac|''c''|''d''}} = {{sfrac|''a'' + ''p''|''b'' + ''q''}}}}. Since {{sfrac|''c''|''d''}} is in lowest terms,  there must be an integer ''k'' such that {{math|1=''kc'' = ''a'' + ''p''}} and {{math|1=''kd'' = ''b'' + ''q''}}, giving {{math|1=''p'' = ''kc'' &minus; ''a''}} and {{math|1=''q'' = ''kd'' &minus; ''b''}}. If we consider ''p'' and ''q'' to be functions of ''k'', then
:<math> \frac{p(k)}{q(k)}- \frac{c}{d} = \frac{cb - da}{d(kd - b)}</math>
so the larger ''k'' gets, the closer {{sfrac|''p''|''q''}} gets to {{sfrac|''c''|''d''}}.

To give the next term in the sequence ''k'' must be as large as possible, subject to {{math|1=''kd'' &minus; ''b'' ≤ ''n''}} (as we are only considering numbers with denominators not greater than ''n''), so ''k'' is the greatest {{nowrap|integer ≤ {{sfrac|''n'' + ''b''|''d''}}}}. Putting this value of ''k'' back into the equations for ''p'' and ''q'' gives
:<math> p = \left\lfloor\frac{n+b}{d}\right\rfloor c - a</math>
:<math> q = \left\lfloor\frac{n+b}{d}\right\rfloor d - b</math>

This is implemented in [[Python (programming language)|Python]] as follows:
<syntaxhighlight lang="python">
from fractions import Fraction
from collections.abc import Generator

def farey_sequence(n: int, descending: bool = False) -> Generator[Fraction]:
    """
    Print the n'th Farey sequence. Allow for either ascending or descending.

    >>> print(*farey_sequence(5), sep=' ')
    0 1/5 1/4 1/3 2/5 1/2 3/5 2/3 3/4 4/5 1
    """
    a, b, c, d = 0, 1, 1, n
    if descending:
        a, c = 1, n - 1
    yield Fraction(a, b)
    while 0 <= c <= n:
        k = (n + b) // d
        a, b, c, d = c, d, k * c - a, k * d - b
        yield Fraction(a, b)

if __name__ == "__main__":
    import doctest

    doctest.testmod()
</syntaxhighlight>

Brute-force searches for solutions to [[Diophantine equation]]s in rationals can often take advantage of the Farey series (to search only reduced forms). While this code uses the first two terms of the sequence to initialize ''a'', ''b'', ''c'', and ''d'', one could substitute any pair of adjacent terms in order to exclude those less than (or greater than) a particular threshold.<ref>{{cite magazine |first=Norman |last=Routledge |title=Computing Farey series |magazine=[[The Mathematical Gazette]] |volume=92 |issue=523 |pages=55–62 |date=March 2008}}</ref>