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)

Answer 2

The question does not state conditions on generated coprime pairs (e.g. is one of the numbers within specific bounds?). Nevertheless, I found following two examples interesting (both requiring constant space).

First consider Farey sequence, here is an example in Python 3:

a, b, c, d = 0, 1, 1, n
while c <= n:
    k = (n + b) // d
    a, b, c, d = c, d, k * c - a, k * d - b
    print(a, b)

It will enumerate all coprime pairs a, b with 1 <= a <= b <= n.

Second example is sort of couriosity, using idea based on Calkin–Wilf tree, you can enumerate all coprime pairs without bounds. Well, mathematically at least, in practice you are only limited by how big numbers you are able to represent in the memory. Anyway here is a Python 3 example:

a, b = 0, 1
while True:
    a, b = b, 2*(a//b) * b - a + b
    print(a, b)

This might be handy if you want to find example of some rational number that satisfies certain property, yet you don't know the bounds. Of course you could just try all possible pairs of natural numbers, but this generates coprime pairs directly.

Answer 3

Python version of the accepted Haskell solution

def find_coprimes():
    l = 1
    while True:
        i = 2
        while i < l-i:
            if gcd(i, l-i) == 1:
                yield i, l-i
            i += 1
        l += 1

To get only a few:

iterator = find_coprimes()
for i in range(10):
    print(next(iterator))

Output:

(2, 3)
(2, 5)
(3, 4)
(3, 5)
(2, 7)
(4, 5)
(3, 7)
(2, 9)
(3, 8)
(4, 7)