2

我可以按照维基百科上列出的三叉树算法生成所有互质对： 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)

然而，每生产一对（例如打印，或者不保存在内存中），使用的空间将增加三倍。

这可能是haskell中的一个解决方案： Generating sorted list of all possible coprimes

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

4

3 回答 3

12

这使用对数空间，也许这已经足够好了？它是线性时间（使用 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 的这些文章中阅读有关此类自递归生成器的更多信息：

演示前 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)

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

>>> from itertools import islice
>>> next(islice(coprimes(), 10**9-1, None))
(175577, 63087)
于 2017-01-14T22:36:42.073 回答
2

公认的 Haskell 解决方案的 Python 版本

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)
于 2017-01-14T20:57:37.753 回答
1

该问题没有说明生成的互质对的条件（例如，某个数字是否在特定范围内？）。尽管如此，我发现以下两个示例很有趣（都需要恒定空间）。

首先考虑Farey 序列，这是 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)

它将枚举所有具有 1 <= a <= b <= n 的互质数对 a、b。

第二个例子是一种好奇心，使用基于Calkin–Wilf 树的思想，你可以无限制地枚举所有互质对。好吧，至少在数学上，在实践中你只受到你能够在内存中表示的数字的限制。无论如何，这是一个 Python 3 示例：

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

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

于 2020-07-23T21:32:17.353 回答