Генерация пифагорейских троек с использованием гауссовых (комплексных) целых чисел

Question

Я только недавно узнал о способе генерации пифагорейских троек с помощью этого видео, объясняющего это, включая использование гауссовых (сложных) целых чисел. До сих пор мне удалось написать функцию, возвращающую список пифагорейских троек, генерируемых каждым гауссовым целым числом, где мнимая часть меньше реальной части.

def pyt(max_real):
    t = []
    real = 2
    imag = 1
    while real <= max_real:
        z = complex(real, imag)**2
        t.append((z.real, z.imag, abs(z)))
        if imag + 1 == real:
            real += 1
            imag = 1
        else:
            imag += 1
    return t

Проблема в том, что некоторые триплеты (такие как {9, 12, 15}) не генерируются на начальном этапе видео, на котором основана функция, и я не уверен, как их сгенерировать.

>>> for i in pyt(4):
        print(i)


(3.0, 4.0, 5.0)
(8.0, 6.0, 10.0)
(5.0, 12.0, 13.0)
(15.0, 8.0, 17.0)
(12.0, 16.0, 20.0)
(7.0, 24.0, 25.0)
>>> # missing: (9, 12, 15), possibly others

Как бы я мог генерировать все возможные триплеты, используя те, которые у меня уже есть, или иначе?

Answer 1

Изменить: я понял, что это может пропустить некоторые тройки, см. Уведомление на последней строке.

Этот ответ основан на предоставленной вами ссылке. Мы будем использовать следующую информацию:

• Мы можем использовать метод гауссовых целых, чтобы найти все тройные генераторы

• Любая тройка кратна одному из указанных выше генераторов.

• Чтобы найти тройку, нам никогда не нужно масштабировать генератор менее чем на 1/2, давая верхнюю границу для самого большого генератора, который нам понадобится.

Итак, вот некоторый псевдокод того, как мы можем действовать. Ниже приведены некоторые подробности возможной реализации.

def pyt(max_real):
    max_generator = 2 * max_real
    generators = set()

    # Find every generator inside our upper bound
    for x in [Gaussian integers if abs(x) < max_generator and x.imag < x.real]:
        y = x**2
        triple = (y.real, y.imag, abs(y))
        generators.add(triple)


    # Scale up
    scaled_up_generators = set()

    for a, b, c in generators:

        for i in range(max_real / c):
            scaled_up_generators.add((i * a, i * b, i * c))

    # Scale down
    triples = set()

    for a, b, c in generators:

        common_factors = find_common_factors(a, b, c)
        for factor in common_factors:
            triples.add((a / factor, b / factor, c / factor))

    triples = set()

    # Before returning we filter out the triples that are too big.
    return filter(lambda triple: triple[2] <= max_real, triples)

Приведенный выше код восстанавливает все тройные генераторы, вдвое превышающие указанную границу. Затем, масштабируя их вверх и вниз, мы возвращаем все тройки внутри нашей границы.

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

Опять же, эта реализация основана исключительно на информации, указанной в вашей ссылке. Кроме того, он поймает более тройной, но может не поймать тройки, которые должны быть масштабированы на более мелкие дроби. Возможно, есть более эффективный способ продолжить, но для этого я рекомендую обратиться к MathExchange.

Answer 2

Рассмотрим этот абзац ¹ со страницы Википедии о тройках Пифагора:

Несмотря на создание всех примитивных троек, формула Евклида не создает все тройки — например, (9, 12, 15) не может быть сгенерировано с использованием целых чисел m и n . Это можно исправить, вставив в формулу дополнительный параметр k . Следующие команды однозначно генерируют все пифагоровы тройки:

а знак равно k ⋅ ( м ² - п ² ), б знак равно k ⋅ ( 2 ⋅ м ⋅ п ) , c знак равно k ⋅ ( м ² + п ² )

где m , n и k — положительные целые числа с m > n и с m и n взаимно простыми, а не оба нечетными.

Хотя ОП использовалcomplex, в следующей реализации я избегаю типов с плавающей запятой.

      from math import gcd as gcd

def pythagorean_triples(max_c):
    triples = []
    m = 2
    while m * m < max_c:
        # "... not both odd..."
        for n in range(1 + m % 2, m, 2):

            # "... with m and n coprime ..."
            if gcd(m, n) != 1:
                continue
            
            c = m * m + n * n
            if c > max_c:
                break

            a = m * m - n * n
            b = 2 * m * n
            if b < a:
                a, b = b, a            
            
            k = 1
            while c * k <= max_c:
                triples.append((a * k, b * k, c * k))
                k += 1
        m += 1
    return triples

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

      >>> for a, b, c in sorted(pythagorean_triples(25)):
       print(a, b, c)

3 4 5
5 12 13
6 8 10
7 24 25
8 15 17
9 12 15
12 16 20
15 20 25

^{1) https://en.wikipedia.org/wiki/Pythagorean_triple#Generating_a_triple}