Я пытаюсь разработать алгоритм для поиска положительных целочисленных решений с верхней границей диофантовых уравнений, например:
a^3 + b^3 + c^3 = d^3
Например:
3^3 + 4^3 + 5^3 = 6^3
Я хочу замучить вас множеством уравнений, которые дадут нам ответ на вопрос, как найти a, b, c и d.Джейкоб Перельман, автор статьи, называемой чем-то вроде «неопределенных уравнений третьей степени», дает нам:
a = 28r^2 + 11rs - 3s^2,
b = 21r^2 - 11rs - 4s^2,
c = 35r^2 + 7rs + 6s^2,
d = -42r^2 - 7rs - 5s^2,
При любых заданных r и s, например, при заданных r = 1 и s = 1, мы получаем:
a = 36, b = 6, c = 48 d = -54, // reducing by the common factor of 6:
a = 6, b = 1, c = 8, d = 9
Таким образом, алгоритм (с учетом верхней границы b) может быть: 1. Возьмите произвольные r и s, например, r = 1, s = 2 2. Выполните вычисления и получитеa, b, c, d 3. Проверьте, что у нас есть только одно отрицательное число, если не продолжить.4. Проверьте, если x, y, z, t Возникают следующие вопросы:
Если мы изменим порядок начальной группы из четырех (3, 4, 5,-6) => (3, 5, 4, -6) получаем новую формулу решения:
a = 20r ^ 2 + 10rs - 3s ^ 2,
b = 12r ^ 2- 10rs - 5s ^ 2,
c = 16r ^ 2 + 8rs + 6s ^ 2,
d = -24r ^ 2 - 8rs - 4s ^ 2.
Так что, поступая так, я получу бесконечно много новых формул.Как мне с этим справиться?
GCD-вычисления, особенно для 4 довольно больших чисел, очень ресурсоемки, как мне с этим справиться?
Из-за GCD даже довольно большие r и s могут в конечном итогепроизвести довольно маленькие a, b, c и d.Какова стратегия выбора начальных точек r и s для прохождения цикла?
Знаете ли вы более простое решение для этого?