Iterate all coprime pairs using constant space?

Question

I can generate all coprime pairs by following the ternary-tree algorithm listed on wikipedia: https://en.wikipedia.org/wiki/Coprime_integers

Quickly:

Start with two coprime branches: (2,1), (3,1), then iterate:
Branch 1: (2m-n,m)
Branch 2: (2m+n,m)
Branch 3: (m+2n,n)

However the space used will grow by a factor of three for each pair produced (and say printed, or otherwise not kept in memory).

Here might be a solution in haskell: Generating sorted list of all possible coprimes

But I was looking for something in python, which does not have lazy evaluation or infinite lists.

Answer 1

This uses logarithmic space, maybe that's good enough? And it's linear time (uses O(k) time to produce the first k pairs).

def coprimes():
    yield (2, 1)
    yield (3, 1)
    for m, n in coprimes():
        yield (2*m - n, m)
        yield (2*m + n, m)
        yield (m + 2*n, n)

You can read more about such self-recursive generators in these articles by David Eppstein:

• Breadth first traversal of tree (Python recipe)
• Self-recursive generators (Python recipe)
• The Kolakoski tree

Demo showing the first 20 pairs:

>>> pairs = coprimes()
>>> for _ in range(20):
        print(next(pairs))

(2, 1)
(3, 1)
(3, 2)
(5, 2)
(4, 1)
(5, 3)
(7, 3)
(5, 1)
(4, 3)
(8, 3)
(7, 2)
(8, 5)
(12, 5)
(9, 2)
(7, 4)
(9, 4)
(6, 1)
(7, 5)
(13, 5)
(11, 3)

Demo showing the billionth pair, which takes my PC about 4 minutes while the memory usage of the Python process stays at the 9.5 MB baseline that any Python process takes me at least.

>>> from itertools import islice
>>> next(islice(coprimes(), 10**9-1, None))
(175577, 63087)