Упростить условие

[questioner]

Здравствуйте!

Нужно найти способ оптимального нахождения четвёрок натуральных чисел $(a,b,c,d)$, что $a, b, c, d$ взаимно просты, $a^2 + b^2 = c^2 + d^2$, и при заданном $n$ выполняется условие 1 \leq a < c \leq d < b \leq n. Нужно находить такие чётверки для достаточно больших $n$. Поэтому вопрос: можно ли свести данное условие к эквивалентному, но более простому, чтобы можно было реализовать некий эффективный алгоритм?

[maxal]

questioner в сообщении #21167 писал(а):

Нужно найти способ оптимального нахождения четвёрок натуральных чисел $(a,b,c,d)$, что $a, b, c, d$ взаимно просты, $a^2 + b^2 = c^2 + d^2$, и при заданном $n$ выполняется условие 1 \leq a < c \leq d < b \leq n.

Последнее условие излишне. Дело в том, что без потери общности можно считать, что $a$ и $c$ - наименьшие числа в парах и что $a<c$. Тогда указанное условие выполняется автоматически.

А по сути задача сводится к нахождению различных разложений числа $m$ в сумму двух квадратов (два таких разложения с взаимно-простыми компонентами и дадут искомую четверку). Это довольно просто в случае, когда известно разложение $m$ на простые. Но и в случае, когда оно неизвестно, кое-что можно (попытаться) сделать. Есть готовый ява-апплет, разлагающий заданное $n$ в сумму квадратов, с подробным описанием метода.

Кроме того, есть формула (номер 17), дающая количество различных разложений $m$ в сумму двух квадратов. Понятно, что для получения искомой четверки, таких разложений должно быть как минимум 2.

[Руст]

А условие взаимной простоты чисел?
На самом деле на задачу можно рассмотреть как нахождение гауссовых целых чисел с заданной нормой. Соответственно этот подход дает ответ и на вопрос о возможности нахождения с взаимно простыми разложениями.