Комбинации трех положительных чисел x, y, z, так что x + y, x - y, y + z, y - z, x + z и x - z являются идеальными квадратами

Question

Доброе утро, я новичок здесь и принес небольшую проблему. У меня проблемы с разработкой эффективного алгоритма для следующей задачи: мне нужно найти комбинации из трех положительных чисел x, y и z, чтобы x + y, x - y, y + z, y - z, x + z и x - z - идеальные квадраты. Проблема заключается в разработке алгоритма, который находит все комбинации x, y и z в диапазоне от 1 до 2 000 000.

В настоящее время я использую for в пределах for это конечно не закончится, пока у меня не появятся мои внуки.

Answer 1

Основная идея начать с замены, например:

 u = x + y
 v = x - y
 w = y + z

Тогда x + y, x - y, y + z, y - z, x + z и x - z становится

 u, v, w, u - v - w, v + w, u - w   [all have to be squares]

Затем с другой заменой, u = a², v = b², w = c², вы получите:

 a², b², c², a² - b² - c², b² + c², a² - c²    [all have to be squares]

Теперь вы можете перечислить все a, b, cs, которые уже могут быть достаточно быстрыми.

Дальнейшие идеи могут состоять в том, чтобы сначала перечислить все b², c², b²+c², используя пифагорейские тройки (подставив его в m и n, перечислив все взаимно простые числа (m,n) и затем используя формулу Евклида), а затем найти для заданного (b,c) аналогично (например, измените a² - c² = x² на a² = x² + c² и снова используйте тройки).

Answer 2

Расширяя ответ BeniBela,

x + y = (x - z) + (y + z)
x + y = (x + z) + (y - z)

Таким образом, триплеты действительны, только если гипотенуза может быть представлена ​​в двух разных формах. Дальнейшая фильтрация может быть выполнена, наблюдая, что (x - z) и (x + z) также формируют гипотенузу пифагорейского триплета.