使用常量 space 迭代所有互质对？

Question

我可以按照维基百科上列出的三元树算法生成所有互素对： https://en.wikipedia.org/wiki/Coprime_integers

快点：

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)

然而，每生产一双（比如印刷，否则不保存在内存中），使用的 space 将增长三倍。

haskell 中可能有一个解决方案：

但我在 python 中寻找一些东西，它没有惰性求值或无限列表。

Answer 1

Python 已接受 Haskell 解决方案的版本

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

只得到几个：

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

输出：

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

Answer 2

这使用对数 space，也许这样就足够了？而且它是线性时间（使用 O(k) 时间来产生前 k 对）。

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)

您可以在 David Eppstein 的这些文章中阅读有关此类 self-recursive 生成器的更多信息：

显示前 20 对的演示：

>>> 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)

显示第十亿对的演示，这需要我的 PC 大约 4 分钟，而 Python 进程的内存使用保持在 9.5 MB 的基线，任何 Python 过程至少需要我。

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

Answer 3

问题没有说明生成的互质对的条件（例如，是特定范围内的数字之一吗？）。不过，我发现以下两个示例很有趣（都需要常量 space）。

首先考虑Farey sequence，这里以Python3为例：

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)

它将枚举所有满足 1 <= a <= b <= n 的互质对 a, b。

第二个例子有点好奇，使用基于Calkin–Wilf tree的想法，你可以无限制地枚举所有互素对。好吧，至少在数学上，在实践中你只受限于你能在内存中表示多少数字。不管怎样，这是一个 Python 3 的例子：

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

如果您想找到满足特定属性但不知道边界的有理数示例，这可能会很方便。当然你可以尝试所有可能的自然数对，但这会直接生成互质对。

使用常量 space 迭代所有互质对？

Iterate all coprime pairs using constant space?

python

algorithm

primes

ternary-tree