Итерировать все пары взаимно простых чисел, используя постоянное пространство?

Я могу сгенерировать все простые пары, следуя алгоритму троичного дерева, указанному в Википедии: 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: Генерация отсортированного списка всех возможных копримов

Но я искал что-то в python, у которого нет отложенных вычислений или бесконечных списков.

Источник

2 ответа

Решение

Это использует логарифмическое пространство, может быть, этого достаточно? И это линейное время (использует 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)

Вы можете прочитать больше о таких саморекурсивных генераторах в этих статьях Дэвида Эппштейна:

Демо, показывающее первые 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)

Демонстрация, показывающая миллиардную пару, которая занимает у моего компьютера около 4 минут, в то время как использование памяти процессом Python остается на базовом уровне 9,5 МБ, что, по крайней мере, занимает любой процесс Python.

>>> from itertools import islice
>>> next(islice(coprimes(), 10**9-1, None))
(175577, 63087)
Источник

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)
Источник

Вопрос не устанавливает условия для сгенерированных взаимно простых пар (например, одно из чисел находится в определенных пределах?). Тем не менее, мне показались интересными следующие два примера (оба требуют постоянного места).

Сначала рассмотрим последовательность Фарея, вот пример на 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)

Он перечислит все взаимно простые пары a, b с 1 <= a <= b <= n.

Второй пример - это своего рода любопытство: используя идею, основанную на дереве Калкина-Уилфа, вы можете перечислить все взаимно простые пары без ограничений. Что ж, по крайней мере математически, на практике вы ограничены только тем, насколько большие числа вы можете представить в памяти. В любом случае, вот пример Python 3:

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

Это может быть удобно, если вы хотите найти пример некоторого рационального числа, удовлетворяющего определенному свойству, но вы не знаете границ. Конечно, вы можете просто попробовать все возможные пары натуральных чисел, но это напрямую генерирует взаимно простые пары.

Источник
Другие вопросы по тегам