2

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.

Community
  • 1
  • 1
user318904
  • 2,968
  • 4
  • 28
  • 37
  • Please clarify: do you want the same restrictions as in the Haskell problem? `The first element in each pair must be less than the second. The sorting must be done in ascending order -- by the sum of pair's elements; and if two sums are equal, then by the pair's first element.` If so, you want to swap those pairs in your algorithm. And Python does have infinite generators, which are probably like your "infinite lists." And are you trying to avoid the "grow by a factor of three" issue or do you just want simple Python code? – Rory Daulton Jan 14 '17 at 20:55
  • *"But I was looking for something in python, which does not have lazy evaluation or infinite lists."* Python has generators (which yield values lazily) and functions (notably in `itertools`) that yield potentially infinite sequences, though. – Tagc Jan 14 '17 at 22:52
  • I was not looking for the restrictions from the haskell solution, I should have stated that. And any idiomatic python solution would work, regardless of lazy/infinite terminology. – user318904 Jan 15 '17 at 00:32

3 Answers3

12

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:

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)
Stefan Pochmann
  • 27,593
  • 8
  • 44
  • 107
2

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)
IVlad
  • 43,099
  • 13
  • 111
  • 179
1

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.

Sil
  • 200
  • 1
  • 12