Python code to enumerate rationals

rationals.py

from math import gcd

def rationals():
    """
    Enumerates rational numbers as [numerator, denominator] pairs
    in simplest form but not in order.
    """

    yield [0, 1]
    # Now we have enumerated all values that have neither
    # a reciprocal nor a distinct negative.

    # From now on, we will only enumerate adjacent positive
    # negative pairs, so we will not miss a rational but
    # yield its negation.

    yield [-1, 1]
    yield [1, 1]
    # Now we have enumerated all values that lack a distinct
    # reciprocal so from now on, when we enumerate a value
    # we will also enumerate its reciprocal.
    # This means we will neither miss a value in (-1, 1)
    # but emit one in (-inf, -1) or in (1, inf); nor vice versa.
    # The convention here where numerator is signed or zero
    # and denominator is in [1, inf) is followed below, so
    # there will be no redundant outputs due to signs on the denominator.

    denominator = 1
    # We have yielded all simplest form rationals with numerator and denominator <= 1
    while True:
        denominator += 1
        # Python has bigint semantics so no risk of overflow.
        # First time here, denominator is 2, so we're not repeating
        # anything above, and we step by one, so we will eventually
        # reach here for every denominator in a rational in (0, 1).
        for numerator in range(1, denominator):
            if gcd(numerator, denominator) == 1:
                # (numerator / denominator) is in simplest form.
                # 4 yields for all combinations of negation/reciprocal
                yield [-numerator, denominator]
                yield [numerator, denominator]
                yield [-denominator, numerator]
                yield [denominator, numerator]
    # Because of the gcd check above, we will not output redundant
    # rationals, e.g. 2/4 and 1/2.  And we output in simplest form.
    # A gcd of 1 means there exists no integer other than 1 by which
    # both numerator and denominator can be divided to simplify.

    # Because the inner loop is over a finite range (bounded by denominator),
    # it will terminate as long as the coroutine is scheduled.
    # There exists an upper bound on the number of inner loop steps
    # taken to yield the rational [x, y].  That happens before the outer loop
    # continues (max(x, y)/gcd(x, y) + 1) times.
    # Since the inner loop is bounded by the outer's counter, the square
    # of that is greater than the number of inner loop steps before it's yielded.
    # This bound is not the tightest we can compute, but it establishes
    # coverage; to show that there exists a finite number of steps for any
    # value in the set being enumerated.


if __name__ == '__main__':
    printed = 0
    for [n, d] in rationals():
        print('%s%d/%d' % ((n >= 0 and " " or ""), n, d))
        printed += 1
        if printed > 200: break