√m≈√x+√y

[waxtep]

Хорошо, а чем плох (или, наоборот, хорош), такой подход: вот, мы же знаем, что $x,y$, - это лишь фасад, мираж, а на самом деле рулят $v,R$. Мы так же знаем, что $v^2\equiv R\pmod m$, где $R$ принадлежит определенной последовательности и слишком большим быть не должно (тут конечно вопрос, что такое "слишком", и традиционное "когда остановиться?"). При этом, точность приближения тем лучше, чем больше величина $\sqrt{(m+v)^2-R}+\sqrt{(m-v)^2-R}$, или, приближенно, чем меньше $\frac R{m^2-v^2}$. Тогда, для простого $m$, можно попробовать перебирать значения $R$ по возрастанию (причем, не все $R$ будут разрешены по соображениям взаимности) и в лоб извлекать из них корни по модулю $m$, - здесь же есть быстрые алгоритмы (не имел реального опыта реализации, но вот пишут: Алгоритм Тонелли—Шенкса; есть некоторые оговорки, но, на первый взгляд, алгоритм не выглядит устрашающим/безнадежным). Если же нам еще больше повезло и $m=4d+3$, то это вообще сводится к задаче возведения в степень по модулю: $v\equiv\pm R^{d+1}\pmod{4d+3}$, где точно быстрые алгоритмы есть. Хочу попробовать, когда будет чуть больше досуга, в ближайшую среду, видимо

[juna]

waxtep в сообщении #1570810 писал(а):

Хорошо, а чем плох (или, наоборот, хорош), такой подход: вот, мы же знаем, что $x,y$, - это лишь фасад, мираж, а на самом деле рулят $v,R$.

При $v=R=0$ выполнятся сразу все условия.

[waxtep]

juna в сообщении #1570828 писал(а):

При $v=R=0$ выполнятся сразу все условия.

Но для простого $m$ ведь не бывает $R=0$, да и $R=1$ кажется тоже, смело начинаем с $R=5$

[Andrey A]

waxtep в сообщении #1570810 писал(а):

... а на самом деле рулят $v,R$.

Вовсе нет. В случае $R=1$ нужное $v$ (которое рулит) еще нужно поискать.

waxtep в сообщении #1570810 писал(а):

При этом, точность приближения тем лучше, чем больше величина $\sqrt{(m+v)^2-R}+\sqrt{(m-v)^2-R}$

На глаз видно, что $ \approx 2m.$ Если имеется в виду дробная часть, попробуйте выразить ее через $v,R$, учитывая $v^2-R=m(2x+2y-m)$, и решить относительно них соотв. неравенство.

Я погорячился, когда сказал, что задача равносильна факторизации. Из решения $(1)$ действительно имеем либо пару делителей $m$, либо положительный тест на простоту. Но обратный вывод, как видим, можно сделать только для составного $m,$ и то не на прямую. Для простого задача стоит особняком. И сдается мне, что вопрос нахождения/отсутствия на заданном интервале арифметической суммы радикалов на кривой козе не объедешь. А что, красиво получается: целое число и чуть левее его иррациональная тень. Как у Шварца. Или вы хотели простую задачу?

(Оффтоп)

— Голубчики, — сказал Фёдор Симеонович озабоченно, разобравшись в почерках. — Это же проблема Бен Бецалеля. Калиостро же доказал, что она не имеет решения.
— Мы сами знаем, что она не имеет решения, — сказал Хунта, немедленно ощетиниваясь. — Мы хотим знать, как её решать.
— Как-то странно ты рассуждаешь, Кристо… Как же искать решение, когда его нет? Бессмыслица какая-то…
— Извини, Теодор, но это ты очень странно рассуждаешь. Бессмыслица — искать решение, если оно и так есть. Речь идёт о том, как поступать с задачей, которая решения не имеет. Это глубоко принципиальный вопрос…

[juna]

waxtep в сообщении #1570840 писал(а):

Но для простого $m$ ведь не бывает $R=0$, да и $R=1$ кажется тоже, смело начинаем с $R=5$

Согласен, и там решений $v$ для $v^2\equiv R\mod m$ мало.

-- Вт ноя 22, 2022 10:17:47 --

Andrey A в сообщении #1570845 писал(а):

В случае $R=1$ нужное $v$ (которое рулит) еще нужно поискать.

А такие простые $m$ бывают?

[Andrey A]

Нет, $R=1$ — жестко составное, но вариантов $v$ в этом случае может быть сколько угодно, но конечное число. И кстати. Лучшее приближение для многомерных чисел — всегда $R=1$, но остальные не факт, что все лучше какого-нибудь $R=5$, требует доказательства. Как-то не задумывался. В случае простого $v$ нужной четности для каждого $R$ определено однозначно.

[juna]

Обозначим $P(r,N)$ - количество простых чисел, меньших $N$, для которых $R=r$:

$$P(0,1000)=0, P(1,1000)=0, P(5,1000)=61, P(8,1000)=42, P(12,1000)=21, P(13,1000)=20,$$

$$ P(17,1000)=10, P(21,1000)=5, P(24,1000)=4, P(28,1000)=1, P(29,1000)=1, P(53,1000)=1$$

И похоже не бывает составных с $R\not=0,1$ (в пределах 1000 нет ни одного).

[Andrey A]

juna в сообщении #1570852 писал(а):

И похоже не бывает составных с $R\not=0,1$.

Так это просто: $R=0$ — точное равенство, верно для всех "несвободных" от квадратов $>1$, и только для них. $R=1$ там тоже возможно, но не лучшее: $\sqrt{75} \approx \sqrt{8}+\sqrt{34}.$ Остальное почитаю.

[juna]

Нет, уже нашел исключения для $m=1711, 2501, 4351, 5251, R=5$

[waxtep]

Andrey A в сообщении #1570845 писал(а):

Вовсе нет. В случае $R=1$ нужное $v$ (которое рулит) еще нужно поискать.

Я, конечно, сразу на простые нацелился, для составных-то корень извлекать замаемся, для них это требует факторизации. Может быть, "пощупав" таким образом простые, удастся и что-то для составных придумать.

Andrey A в сообщении #1570845 писал(а):

На глаз видно, что $ \approx 2m.$ Если имеется в виду дробная часть, попробуйте выразить ее через $v,R$, учитывая $v^2-R=m(2x+2y-m)$, и решить относительно них соотв. неравенство.

Ммм, я имел в виду $\sqrt{4m}(\sqrt{m}-\sqrt{x}-\sqrt{y})=2m-\sqrt{(m-v)^2-R}-\sqrt{(m+v)^2-R}$, и для наилучшего приближения сумма корней должна быть максимальной (при известных ограничениях на $v,R$)

juna в сообщении #1570864 писал(а):

Нет, уже нашел исключения для $m=1711, 2501, 4351, 5251, R=5$

Кстати, пресловутые числа-рекордсмены по глубине поиска не только все простые, но и все имеют $R=5$; своеобразная дуальность: с одной стороны, число самое "трудное" в своем классе (наименьшее по величине с заданной глубиной дерева поиска), а, с другой, решение соответствует первому же возможному значению $R$

[Andrey A]

juna
Вы меня на обе лопатки кладете. Одно из самых ранних "открытий" оказывается неверным! Как это в голову не пришло проверить, не знаю. А может как раз за давностью лет. Спасибо! А то и дальше эту хрень проповедовал бы. Но тогда всё поскучнее становится, простое/составное без гарантий, уверенность дает только $R=0.$ В соотношении $v/R$ надо разбираться подробно. Собственно, не то чтобы всё пропало, но касательно природы чисел утверждения теперь возможны лишь вероятностного свойства, проверять требуется как минимум несколько вычетов, и сразу встает вопрос сколько? Всё. Я в дауне...

[juna]

Andrey A в сообщении #1570851 писал(а):

Лучшее приближение для многомерных чисел — всегда $R=1$, но остальные не факт, что все лучше какого-нибудь $R=5$, требует доказательства.

Вы про это открытие?

[Andrey A]

juna в сообщении #1570896 писал(а):

Вы про это открытие?

Да, про это и про составные вообще. Для простого не может быть $R=1$, поскольку квадрат. А для составного из $n$ простых множителей количество квадратов сравнимых с единицей — по количеству пар множителей, т.е. $2^{n-1}-1$ (кроме пары $m \cdot 1$), и любое другое $R$ имеет столько же вариантов $v.$ При таком раскладе возможность $R>1$ в решении вполне себе вероятна. В итоге как всегда: $R=1$ свидетельствует о составном, но $R>1$ ни о чем еще не говорит. Или говорит, но с некоторой вероятностью. Можем считать такие числа $(m=1711, 2501,...)$ квазипростыми относительно данного алгоритма. Которого у нас еще нет )

[juna]

Andrey A в сообщении #1570945 писал(а):

Можем считать такие числа $(m=1711, 2501,...)$ квазипростыми относительно данного алгоритма.

Для качественного пусть вероятностного теста на простоту они слишком кучно идут в сравнении с числами Кармайкла. Вот начало этой цепочки (в скобках указано соответствующее $R$):

$1711 (5), 2501 (5), 4351 (5), 5251 (5), 9641 (5), 10121 (5), 10811 (5), 11183 (13), 12403 (13), 13207 (8), 13861 (12) $.

Запустил до 20000, по мере получения добавлю. Пока общее у всех - они равны произведению только двух простых чисел.

[Andrey A]

juna в сообщении #1571032 писал(а):

общее у всех - они равны произведению только двух простых

И отношение этих простых — короткая дробь с большим последним знаком: $349/29=12,29.$ Таких немало наберется. С геометрическими прогрессиями сравнивать вряд ли уместно, у нас ведь выбор из всех нечетных свободных от квадратов, конечно плотнее будет. Если же брать относительно количества опытов (грубо говоря, один из тысячи) — то и реже значительно. За многомерными тоже, думаю, дело не встанет.