Комбинации трех положительных чисел 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, y и z между 1 и 2,000,000.

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

Answer 1

Основная идея, чтобы начать с замещением, как:

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

Тогда х + у, х - у, у + х, у - г, х + г и х - г становится

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

Тогда с другой заменой, и = a², V = b², ш = c², вы получите:

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

теперь вы можете перечислить все в ВВПр, которые могут уже быть быстро е nough.

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

Answer 2

Расширение BeniBela's answer,

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

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