√m≈√x+√y

[waxtep]

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

О другом методе поподробней. Возьмем тождество $(a^2+b^2)(c^2+d^2)=(ac+bd)^2+(ad-bc)^2$ и подставим вместо всех $4$-х параметров соответствующие радикалы: $(a+b)(c+d)=\left ( \sqrt{ac}+\sqrt{bd} \right )^2+\left ( \sqrt{ad}-\sqrt{bc} \right )^2.$ Чтобы величиной последнего квадрата можно было "пренебречь", положим $ad-bc=\pm1.$ Тогда $\left ( \sqrt{ad}-\sqrt{bc} \right )^2=\left ( \dfrac{ad-bc}{\sqrt{ad}+\sqrt{bc}} \right )^2=\dfrac{1}{\left ( \sqrt{ad}+\sqrt{bc} \right )^2}.$ Откинув это в качестве погрешности, получаем $\sqrt{(a+b)(c+d)} \approx \sqrt{ad}+\sqrt{bc}.$ Такая схема действительно выражает общее решение для составного $m$ и хорошо описывается в цепных дробях. Любая пара множителей $m$ взаимно проста, поскольку $m$ свободно от квадратов.

Тогда, получается, это рассуждение тоже требует модификации? Смотрю на пример $m=5251=59\cdot89$ и не соображу как: $\dfrac{89}{59}=1,1,1,29$ и $1,1,1,28=\dfrac11,\dfrac21,\dfrac32,\dfrac{86}{57}$, но решение имеет другую структуру: $\sqrt{5251}\approx\sqrt{1091}+\sqrt{1555}$, и ведь $1091$ вообще простое!

-- 23.11.2022, 00:42 --

(Оффтоп)

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

Кстати, пресловутые числа-рекордсмены по глубине поиска не только все простые, но и все имеют $R=5$;

Поправлюсь, это неправда: $m=1487,R=12$, остальные (докуда смог досчитать), действительно, пятерки

[Andrey A]

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

... требует модификации?

Другой модификации тут быть не может, всё по схеме, но полученное решение $\sqrt{5251} \approx \sqrt{6}+\sqrt{4902}$ строго говоря, решением не является, поскольку указанная Вами аппроксимация лучше. Однако $R=5,$ вот и получаем квазипростое, об том и речь.

[juna]

В пределах 20000 это все:

[1711 (5), 2501 (5), 4351 (5), 5251 (5), 9641 (5), 10121 (5), 10811 (5), 11183 (13), 12403 (13), 13207 (8), 13861 (12), 15109 (5), 15931 (5), 16669 (5), 16769 (5), 17063 (8), 18721 (8), 19189 (5)]

[Andrey A]

juna
Ваши наблюдения как всегда содержательны. Хочу предложить еще одну табличку Радикалы против Полларда. Имеется в виду $\rho$-алгоритм Полларда. Из названия, в общем, всё понятно, но есть подозрение, что оба алгоритма скорее дополняют друг друга, чем соперничают, и часто вместе выходит быстрее чем по отдельности. Пчелы против меда? Проверить бы это на больших числах, Excel тут явно не достаточно. Спасибо.

[juna]

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

Хочу предложить еще одну табличку Радикалы против Полларда

Хотелось бы на кривой, но лихой козе сначала эту задачу объехать.

Вернусь к классификации $m$ от заданного $m_1$, о чем я писал выше. При этом вместо исходного равенства для красоты будем говорить о приближении средним арифметическим, средним геометрическим:

$$(1): \frac{m}{2}\approx \frac{x+y}{2}+\sqrt{xy} $$

Возьмем произвольное $m_1$. Было показано, что $xy=\left\lceil\frac{m_1}{2}\right\rceil^2-\left\lceil\frac{m_1}{2}\right\rceil$ дает приближение для (1) порядка $R=1$, при нечетном $m_1$, и $R=0$ при четном $m_1$ (его далее рассматривать не будем ввиду тривиальности).

Поскольку для $\frac{m_1}{2}\approx\sqrt{xy}=\sqrt{\left\lceil\frac{m_1}{2}\right\rceil^2-\left\lceil\frac{m_1}{2}\right\rceil}$ дает лучшее приближение, то, играясь с четностью $x,y$ можно получать лучшие приближения для (1) c $R=1$ при нечетном $m_1$ и $m=m_1+x+y$

Рассмотрим примеры. Возьмем к примеру $m_1=153$

$$xy=\left\lceil\frac{153}{2}\right\rceil^2-\left\lceil\frac{153}{2}\right\rceil=77^2-77=2^2\cdot 7\cdot 11\cdot 19$$

Наберем разные факторизации:

$$x=2^2\cdot 7=28, y=11\cdot 19=209, m=153+28+209=390$$

Ясно, что $\frac{153}{2}=76.5\approx\sqrt{28\cdot 209}=76.49836599562111$ - лучшее нижнее приближение.

$\frac{390}{2}\approx\frac{28+209}{2}+\sqrt{28\cdot 209}$ - ясно, что здесь лучшесть приближения не обязана сработать, поскольку приближаемся с другой стороны $195\approx 118.5+76.49836599562111$

Возьмем оба $x,y$ четные: $x=2\cdot 7\cdot 11=154, y=2\cdot 19=38, m=153+154+38=345$, для них лучшесть приближения обязана сработать.

$$\frac{345}{2}\approx\frac{154+38}{2}+\sqrt{154\cdot 38}$$

$$172.5\approx 96+76.49836599562111=172.4983659956211$$

Таким образом, действительно получаем $(m,x,y,R)=(345,38,154,1)$ оптимально.

Берем другое представление четных: $x=2\cdot 7=14, y=2\cdot 11\cdot 19=418, m=153+14+418=585$ - опять должно сработать с $R=1$.

$$\frac{585}{2}=292.5\approx \frac{14+418}{2}+\sqrt{14\cdot 418}\approx 216+76.49836599562111=292.4983659956211$$

Какой вывод отсюда следует - это лучшее приближение для $(m,x,y,R)=(585,14,418,1)$, но это не значит, что это лучшее приближение вообще, поскольку существует $(m,x,y,R)=(585,65,260,0)$

Идем дальше, попробуем минимально ухудшить приближение:

$$\frac{m_1}{2}\approx\sqrt{xy}=\sqrt{\left\lceil\frac{m_1}{2}\right\rceil^2-\left\lceil\frac{m_1}{2}\right\rceil-1}$$

Возьмем все тоже $m_1=153$, тогда имеем:

$$xy=\left\lceil\frac{153}{2}\right\rceil^2-\left\lceil\frac{153}{2}\right\rceil-1=77^2-77-1=5851\cdot 1$$

Здесь без вариантов получаем:

$$x=1, y=5851, m=153+1+5851=6005$$

Т.е. $(m,x,y,R)=(6005,1,5851,5)$ - лучшее приближение в классе $R=5$, но оно не лучшее в целом, поскольку для $6005$ существует приближение в классе $R=1$.

Пробуем далее ухудшать качество:

$$xy=\left\lceil\frac{153}{2}\right\rceil^2-\left\lceil\frac{153}{2}\right\rceil-2=2\cdot 3^2\cdot 5^2\cdot 13=5850$$

Поскольку $x,y$ вынуждено разной четности, а $m=m_1+x+y$ четное, то ни одна комбинация не обязана сработать.
Все это можно продолжить и далее.

[waxtep]

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

Мы так же знаем, что $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$ по возрастанию

Если пытаться (для нечетных $m$) перебирать разные $R$ по возрастанию и искать соответствующие $v$, "где остановиться" определяется элементарно: пусть мы нашли приближение $(R_1,v_1)$ с наименьшим возможным $R$ и хотим понять, какие приближения $R_2=kR_1,v_2\geqslant1$ могут иметь меньшую погрешность. Поскольку погрешность приближения $\delta\sim\dfrac{R}{m^2-v^2}$ (примерно; можно точнее записать с корнями), получим

$$\delta(R_2,v_2)<\delta(R_1,v_1)\Rightarrow k<\frac{m^2-1}{m^2-v_1^2}\Rightarrow R_2<kR_1$$

Пара примеров:
1) $m=683,R_1=12,v_1=609\Rightarrow k<4,879\ldots, R_2\leqslant58$ (решению соответствует $R=53$)
2) (квазипростое) $m=79003=199\cdot397,R_1=1,v_1=78208\Rightarrow k<49,938\ldots, R_2\leqslant49$ (решению соответствует $R=29$, одно из двух, то, которое с $v=34260$)

Это вселяет некоторую надежду, перебор по $R$ получается вполне локализованным; нижнюю оценку для $v_2$ можно еще улучшить, вспомнив, что для нечетных $m, x\leqslant\dfrac{(\sqrt{m}-1)^2}4$\Rightarrow v_2\geqslant m-\sqrt{m^2-4m\sqrt{m}+m+R_2}$, но вроде бы и грубейшей оценки $v_2\geqslant1$ или $v_2\geqslant0$ достаточно

(я понимаю, что для составных нечетных это все применимо лишь условно, поскольку корень по модулю упирается в факторизацию)

[waxtep]

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

получим

$$\delta(R_2,v_2)<\delta(R_1,v_1)\Rightarrow k<\frac{m^2-1}{m^2-v_1^2}\Rightarrow R_2<kR_1$$

Тут, конечно, неаккуратно написано, имею в виду

$$\delta(R_2,v_2)<\delta(R_1,v_1)\Rightarrow k<\frac{m^2-1}{m^2-v_1^2}\Rightarrow R_2<\frac{m^2-1}{m^2-v_1^2}R_1$$

Ну и единица в числителе тут никакой роли не играет, или уж писать точно с корнями и более точной оценкой минимального $v_2$, или достаточно грубого $R_2<\dfrac{m^2}{m^2-v_1^2}R_1$

[Andrey A]

Я прошу прощенья, отвечу позже, у меня с таблицей запарка. Excel перевирает большие квадраты по $\mod$ как хочет. Видимо переводит в экспоненту (была не была), а там как получится. Я всполошился, только заметив $68$ шагов по $\mod 17$ в алгоритме Полларда. Короче, с таблицей (которая выше) можно работать только по маленьким числам, а они ни о чем не свидетельствуют. Беда.

[Andrey A]

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

$$\delta(R_2,v_2)<\delta(R_1,v_1)\Rightarrow k<\frac{m^2-1}{m^2-v_1^2}\Rightarrow R_2<\frac{m^2-1}{m^2-v_1^2}R_1$$

Это дает верхнюю границу для $R_2$. И сама оценка погрешности $\delta\sim\dfrac{R}{m^2-v^2}$ заинтересовала, из нее в частности следует, что $v$ для любого $R$ определено как минимально возможное. Вы проверяли ее на списке квазипростых от juna?
Ага, а имея верхнюю границу, остается конечное число опытов — уже кое что. Дальше подставляем $R_2,v_2$ и пока не упремся? Интересно. Проверить бы это хорошенько. И еще вопрос — ничего, если я помучаю Вас в личку на счет PARI/GP? Немножко. Надо ж когда-то начинать.

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

Хотелось бы на кривой, но лихой козе сначала эту задачу объехать.

Это бы здорово, конечно, но пока Вы не спешите, и правильно. Эта тройственность, которую Диофант еще приметил, она довольно сильная вещь, ею нужно наиграться, прежде чем дальше идти. Искренне Вас понимаю. Я, правда, дробями мыслил: произведение элементов любой пары подходящих дробей $\dfrac{a}{c},\dfrac{b}{d}$ есть число вида $k(k+1),$ поскольку $ad-bc=\pm 1.$ Но существует третья дробь $\dfrac{a+b}{c+d}$. Всё сказанное справедливо и для нее, вернее для любой из трех новых пар, поэтому все три попарные произведения — также числа вида $k(k+1).$ В нашем случае это тройка $mx,my,xy$, но не знаю мыслил ли Диофант радикалами. А удобно, мне нравится. Вот и Вы, исходя их параметра $m_1$ пробуете строить семейства решений. Ну конечно любая пара множителей числа $k(k+1)$ образует решение вида $R=1$, и пар таких для фиксированного $m_1$ может быть сколь угодно много, но конечное число. Однако, переходя к $R>1$ оставлять привязку к числам вида $k(k+1)$ не очень мудро. Тут сталкиваемся с квадратичными вычетами, а это хорошо изученная область. Удобней рассматривать множители числа ($m_1^2-R)/4.$

[juna]

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

Удобней рассматривать множители числа $(m_1^2-R)/4.$

Это тоже самое, всегда можно перейти, при необходимости:

$$\left\lceil\frac{m_1}{2}\right\rceil^2-\left\lceil\frac{m_1}{2}\right\rceil-r=\frac{(m_1+1)^2}{4}-\frac{m_1+1}{2}-r=\frac{m_1^2-1}{4}-r=\frac{m_1^2-(4r+1)}{4}$$

Только вот если под $R$ мы сохраняем понимание, что это фундаментальные дискриминанты, то здесь у нас $4r+1, r=0,1,2,\ldots$ - это просто сравнимые с 1 по модулю 4 числа.

[Andrey A]

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

Это тоже самое, всегда можно перейти, при необходимости... $0,1,2,...$- это просто сравнимые с 1 по модулю 4 числа.

Не все. Только свободные от квадратов, $2$ уже не подходит. Всё равно приходится перископ поднимать ) Если Вам интересны не мультипликативные формы, у меня даже работа была о треугольных числах. Но, в конце концов, каждый пишет как ему удобно, главное не запутаться. Вы в начале, помнится, упомянули о верхних приближениях. Возьмем $m=97=7^2+3 \cdot 4^2=9^2+4^2.$
Из первого представления:
$\dfrac{7}{4}=1,1,3;\ 1,1,2=\dfrac{1}{1},\dfrac{2}{1},\dfrac{5}{3};\ 2^2+3 \cdot 1^2=7,\ 5^2+3 \cdot 3^2=52.$ Отсюда $ \sqrt{97} \approx \sqrt{7}+\sqrt{52}.$ Получили верхнее приближение приведенное, но не примитивное. Примитивное такое $ \sqrt{97} \approx \sqrt{13}+\sqrt{39}.$ Но $R=-3.$
Из второго представления:
$\dfrac{9}{4}=2,4;\ 2,3=\dfrac{2}{1},\dfrac{7}{3};\ 2^2+1^2=5,\ 7^2+3^2=58.$ Примитивное приведенное $ \sqrt{97} \approx \sqrt{5}+\sqrt{58}.$ Но $R=-4.$ Тут всё иначе. Ладно, оставим на потом. Из первого получаем последовательность типа Фибоначчи:
$\sqrt{13},\sqrt{39},\sqrt{97},\sqrt{259},\sqrt{673},\sqrt{1767},\sqrt{4621},\sqrt{12103},\sqrt{31681},\sqrt{82947},...$
Или типа арифметической прогрессии:
$\sqrt{13},\sqrt{39},\sqrt{97},\sqrt{181},\sqrt{291},\sqrt{427},\sqrt{589},\sqrt{777},\sqrt{991},\sqrt{1231},...$
Под радикалами тройка и простые множители вида $3k+1$.

[waxtep]

Andrey A, конечно, буду рад помочь. Тут кстати есть топик, куда заходят проконсультировать участники, знающие PARI/GP получше меня, сам им пару раз пользовался.

Что касается оценки погрешности, здесь же, кажется, просто:

$$2\sqrt{m}(\sqrt{m}-\sqrt{x}-\sqrt{y})=2m-\sqrt{(m-v)^2-R}-\sqrt{(m+v)^2-R}\approx\frac{mR}{m^2-v^2}+\frac{mR^2(m^2+3v^2)}{4(m^2-v^2)^3}+\ldots$$

Поскольку для решения явно $m-v\gg R$, корни можно разложить в ряд Тейлора, в к-ром каждый член "просит" минимального $v$ при данном $R$ (и минимального $R$ при данном $v$). Специально не проверял, запущу на всякий случай сплошную проверку. Насчитал тоже квазипростых до $100000$, вот список, отсортированный по $R,m$:

(190 штук)

m;x;y;R
1711;181;779;5
2501;521;739;5
4351;1055;1121;5
5251;1091;1555;5
9641;2201;2629;5
10121;661;5609;5
10811;2651;2755;5
15109;2099;5945;5
15931;1199;8389;5
16669;2071;6989;5
16769;1769;7645;5
19189;3581;6191;5
20131;2641;8189;5
20819;2869;8231;5
23501;4379;7591;5
26909;5795;7729;5
26941;1555;15551;5
27169;5701;7979;5
27331;5861;7879;5
27679;6109;7781;5
28799;5039;9745;5
29651;5249;9949;5
30299;2245;16049;5
30721;5429;10321;5
32731;4405;13121;5
33259;3401;15389;5
33661;3781;14879;5
34709;6109;11695;5
35689;2981;18041;5
36121;5249;13831;5
36521;4801;14839;5
36991;7139;11629;5
38191;8591;10555;5
38279;4351;16819;5
39101;7909;11839;5
40331;2179;23761;5
40399;6101;15101;5
41831;8605;12491;5
42079;8711;12499;5
42761;8401;13255;5
42781;10355;11041;5
43621;5939;17369;5
43739;8941;13129;5
44581;5909;18029;5
45649;10121;12781;5
45719;9145;13969;5
46159;10039;13145;5
47561;1159;33871;5
48019;11761;12251;5
48151;6599;19099;5
49051;5401;21899;5
49849;2831;28921;5
50339;11381;13849;5
50389;5549;22495;5
50471;8455;17611;5
50489;2789;29545;5
50851;6911;20269;5
53489;10391;16729;5
53519;11329;15601;5
54071;3751;29339;5
54889;6491;23629;5
55481;7561;22079;5
57691;5771;26969;5
58841;2879;35689;5
59329;10529;19871;5
60581;4279;32659;5
61351;14555;16141;5
62599;8261;25379;5
63731;12749;19471;5
63919;2449;41345;5
64261;1891;44105;5
64321;10469;22891;5
64369;6121;30791;5
64739;10399;23245;5
65291;8341;26959;5
65311;4331;36005;5
65491;7031;29605;5
66379;9521;25621;5
67721;8201;28789;5
67909;3041;42209;5
68869;6479;33101;5
69679;15191;19801;5
70561;2071;48455;5
72419;6869;34681;5
73979;18359;18631;5
74141;7855;33731;5
74281;17981;19169;5
75661;9755;31081;5
76591;17111;21299;5
77281;7859;35851;5
77629;3319;48845;5
81709;12449;30371;5
83141;15949;26261;5
83189;11759;32395;5
84599;12419;32191;5
85079;12661;32099;5
85769;14845;29249;5
85801;5281;48509;5
86459;19561;23771;5
86521;15455;28841;5
87371;19169;24691;5
88381;21605;22591;5
88831;12221;35155;5
89801;16699;29051;5
90809;17839;28151;5
91829;20911;25099;5
92539;5419;53171;5
93781;19079;28261;5
93829;14741;34189;5
95141;3781;60989;5
96571;13805;37351;5
97219;22439;26245;5
13207;1442;5921;8
17063;3118;5593;8
18721;2914;6863;8
24257;3086;10039;8
26471;4882;8617;8
29273;5234;9751;8
32047;2417;16862;8
35297;6946;10927;8
37241;9214;9407;8
40303;7378;13193;8
40393;9998;10199;8
46513;10094;13271;8
46847;6209;18946;8
47689;4766;22303;8
48551;10057;14414;8
49601;3298;27319;8
53063;12313;14254;8
57481;9422;20359;8
61207;7586;25697;8
61247;6601;27634;8
62609;11543;20386;8
62759;12946;18697;8
62977;7951;26174;8
63551;15289;16498;8
65623;5153;33998;8
66223;10654;23753;8
70519;5081;37742;8
72463;4369;41246;8
73153;12719;24866;8
75311;5474;40177;8
75953;3266;47719;8
84529;4463;50146;8
84769;13006;31367;8
88313;14671;30994;8
89359;13697;33086;8
94319;21881;25342;8
94697;3359;62386;8
96647;19534;29281;8
97457;18671;30814;8
98503;19241;30674;8
13861;2377;4758;12
30973;7246;8257;12
34453;7449;9862;12
41917;5109;17758;12
48793;6981;18862;12
52033;7501;20022;12
60563;13211;17202;12
64021;7678;27357;12
68807;7563;30746;12
74533;5577;39334;12
76523;14531;24362;12
82751;6722;42303;12
90119;20042;25163;12
94187;19331;28178;12
96529;18574;30417;12
98843;22586;26931;12
11183;2041;3669;13
12403;1403;5463;13
22387;4437;6891;13
31979;6057;10201;13
38503;8763;10529;13
48233;7393;17859;13
49141;3747;25749;13
60031;9117;22359;13
61307;13029;17811;13
68513;5083;36273;13
68587;6341;33219;13
72517;11397;26417;13
74909;6421;37467;13
76501;12003;27899;13
82111;18399;22773;13
91699;3741;58397;13
33227;7204;9488;17
55577;6838;23426;17
41417;9761;10965;21
64643;15357;16985;21
77423;11490;29261;24
79003;6335;40595;29

[Andrey A]

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

Тут кстати есть топик

Знаю, спасибо.

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

Насчитал тоже квазипростых до $100000$...

Отлично! Интересно бы знать, существует ли среди них хотя бы одна пара из $3$-х простых сомножителей. Из двух дробь $A/B$ — короткая с очень большим последним знаком, что порождает большое $v$ и, как следствие, относительно слабую аппроксимацию при $R=1.$ Это позволяет другим приближениям вырваться вперед. Но при трех множителях все три дроби $AB/C,BC/A,CA/B$ должны иметь большие последние знаки. Это сильное требование, даже не знаю на сколько такое возможно (сначала-то не учел). Если так, оно может служить в качестве "фильтра от квазипростых" для воображаемого алгоритма. Имеется в виду "предумножение" исследуемого $m$ на некий малый модуль $m'.$

[waxtep]

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

Интересно бы знать, существует ли среди них хотя бы одна пара из $3$-х простых сомножителей.

До $100000$ все квазипростые имеют два простых сомножителя

[waxtep]

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

До $100000$ все квазипростые имеют два простых сомножителя

$282367=41\cdot71\cdot97$ - квазипростое! $R=8$