√m≈√x+√y

[Andrey A]

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

приводить не к другим худшим, а к лучшим...

Думаю, от перебора $m''=m' \pm Q_n$ всё равно не уйти, но это мелочи — там ведь сильные ограничения по величине. А начинать вроде бы с любого можно, всяко доберемся с $17$-й попытки. Лучше, конечно, поближе подпустить, есть у нас методы.

[Andrey A]

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

... всяко доберемся с $17$-й попытки.

Да, я понял Ваши опасения, вопрос не праздный. Нам требуются арифметические суммы, а для алгоритма одни не хуже всех остальных. В зоне плохих приближений появляются длинные периоды, что соответствует как раз алгебраическим суммам, они ведут себя иначе, что хорошо видно на примере наших последовательностей:
$\sqrt{260}-\sqrt{187} \approx 6,001133788...$
$\sqrt{187}-\sqrt{126} \approx 6,001628669...$
$\sqrt{126}-\sqrt{77}\ \approx 6,002538087...$
$\sqrt{77}-\sqrt{40}\ \approx 6,002538087...$
Для алгоритма это именно "соседние суммы", он их честно и выдает.

[juna]

Andrey A

А как быть вот с такими приближениями:

$$\sqrt{119}\approx\sqrt{21}+\sqrt{40}, R=4, m'=58, v'=19$$

$$\sqrt{16\cdot 21\cdot 40}=[115; 1, 13, 2, 57, 2, 13, 1, 230]$$

$$Q_2=14,Q_3=29, Q_4=1667, Q_5=3363, Q_6=45386, Q_7=48749$$

Какую часть цепной дроби брать для коррекции $m''=m'\pm Q_n$?

[Andrey A]

Боюсь никакую, с предыдущим примером просто повезло. Возможно, работают палиндромы из $3-5$ знаков. Тут $7$ знаков, получим алгебраическую сумму, которая после "приземления" через последовательность даст что-то по соседству. Короче напрямую это не работает, о причинах писал выше. Сами решения $p,q$ тем не менее существуют, но алгоритм предлагает более близкого соседа, объяснить ему разницу между алгебраическими и арифметическими суммами невозможно. Брать несколько начальных знаков тем более бессмысленно — грубое приближение чего-то без того ненужного. Очередной тупичок. Ну, если только у Вас какие-то спасительные идеи найдутся.

[juna]

Идей нет, к сожалению.

Но мы должны отдавать себе отчет, что если мы находим какой-то беспереборный способ, то тут же находим беспереборный способ решения сравнения $(m-v)^2\equiv R \mod 4m$ для заданных $m, R$, затем тут же следует решение всех рассмотренных выше диофантовых уравнений.

Если известно, что $(m-v')^2\equiv R' \mod 4m$, то фактически Вы предлагали алгоритм нахождения из них новых $v'', R''<R'$.
Может быть здесь и есть какие-то групповые свойства.

В качестве интересного замечания:

$$\sqrt{R}e^{arcsinh\left(\frac{\gamma}{\sqrt{R}}\right)}=\gamma+\sqrt{\gamma^2+R}=2\gamma+\cfrac{R}{2\gamma+\cfrac{R}{2\gamma+\cfrac{R}{2\gamma+\ldots}}}$$

$$\sqrt{R}e^{-i\cdot arccos\left(\frac{\gamma}{\sqrt{R}}\right)}=\gamma+\sqrt{\gamma^2-R}=2\gamma-\cfrac{R}{2\gamma-\cfrac{R}{2\gamma-\cfrac{R}{2\gamma-\ldots}}}$$

Если рассматривать частные дроби:

$$2\,\gamma, \frac{4\,\gamma^2+R}{2\,\gamma}, \frac{8\,\gamma^3+4\,R\,\gamma}{4\,\gamma^2+R}, \frac{16\,\gamma^4+12\,R\,\gamma^2+R^2}{8\,\gamma^3+4\,R\,\gamma}$$

Видно, что числители и знаменатели получаемых дробей связаны с так называемыми массивами Риордана: https://oeis.org/A099089

Можно еще поколдовать:

$$4m=\sqrt{R}e^{-i\cdot acos{\frac{m-(y-x)}{\sqrt{R}}}}+\sqrt{R}e^{-i\cdot acos{\frac{m+(y-x)}{\sqrt{R}}}}$$

$$\sqrt{R}e^{-i\cdot acos{\frac{m-(y-x)}{\sqrt{R}}}}\cdot \sqrt{R}e^{-i\cdot acos{\frac{m+(y-x)}{\sqrt{R}}}}=$$

$$=\left((m-(y-x))+\sqrt{(m-(y-x))^2-R}\right)\cdot \left((m+(y-x))+\sqrt{(m+(y-x))^2-R}\right)$$

$$arccos(x)+arccos(y)=arccos\left(xy-\sqrt{(1-x^2)(1-y^2)}\right)$$

$$R\cdot e^{-iarccos\left(\frac{m^2-(y-x)^2}{R}-\sqrt{\left(1-\frac{(m-(y-x))^2}{R}\right)\cdot \left(1-\frac{(m+(y-x))^2}{R}\right) }\right)}$$

с неясными перспективами..)

[Andrey A]

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

с неясными перспективами..)

Именно. Фактуры любопытной у нас немало накопилось, отчаиваться пока не будем, лучше пронумеровать основные формулы и привести дела в порядок. Важное добавление:

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

$$\begin{Vmatrix} n & (\sqrt{m}-\sqrt{x_n})^2\approx y_n & 1/\delta \\ --- & ---------- & ---\\ 1 & (\sqrt{1957}-\sqrt{467})^2\approx 512,02 & 56\\ 2 & (\sqrt{1957}-\sqrt{466})^2\approx 513,07 & 15\\ 3 & (\sqrt{1957}-\sqrt{465})^2\approx 514,12 & 9\\ 4 & (\sqrt{1957}-\sqrt{464})^2\approx 515,17 & 6\\ 5 & (\sqrt{1957}-\sqrt{463})^2\approx 516,22 & 4\\ 6 & (\sqrt{1957}-\sqrt{462})^2\approx 517,28 & 4\\ 7 & (\sqrt{1957}-\sqrt{461})^2\approx 518,34 & 3\\ 8 & (\sqrt{1957}-\sqrt{460})^2\approx 519,40 & 2\\ 9 & (\sqrt{1957}-\sqrt{459})^2\approx 520,47 & 2\\ 10 & (\sqrt{1957}-\sqrt{458})^2\approx 521,53 & 2\\ 11 & (\sqrt{1957}-\sqrt{457})^2\approx 522,60 & 2\\ 12 & (\sqrt{1957}-\sqrt{456})^2\approx 523,67 & 1\\ 13 & (\sqrt{1957}-\sqrt{455})^2\approx 524,74 & 1\\ 14 & (\sqrt{1957}-\sqrt{454})^2\approx 525,82 & 1\\ 15 & (\sqrt{1957}-\sqrt{453})^2\approx 526,90 & 1\\ 16 & (\sqrt{1957}-\sqrt{452})^2\approx 527,97 & 1\\ 17 & (\sqrt{1957}-\sqrt{451})^2\approx 529,06 & 18\\ 18 & (\sqrt{1957}-\sqrt{450})^2\approx 530,14 & 7\\ 19 & (\sqrt{1957}-\sqrt{449})^2\approx 531,23 & 4\\ 20 & (\sqrt{1957}-\sqrt{448})^2\approx 532,32 & 3\\ 21 & (\sqrt{1957}-\sqrt{447})^2\approx 533,41 & 2\\ 22 & (\sqrt{1957}-\sqrt{446})^2\approx 534,50 & 2\\ 23 & (\sqrt{1957}-\sqrt{445})^2\approx 535,60 & 2\\ 24 & (\sqrt{1957}-\sqrt{444})^2\approx 536,70 & 1\\ 25 & (\sqrt{1957}-\sqrt{443})^2\approx 537,80 & 1\\ 26 & (\sqrt{1957}-\sqrt{442})^2\approx 538,90 & 1\\ 27 & (\sqrt{1957}-\sqrt{441})^2\approx 540,00 & 232\\ 28 & (\sqrt{1957}-\sqrt{440})^2\approx 541,11 & 9\\ 29 & (\sqrt{1957}-\sqrt{439})^2\approx 542,22 & 4 \end{Vmatrix}$$

Далее, если помните, описывался способ вычисления пиковых $x$. Но всё гораздо проще, стоит лишь заметить, что суммы $s=x+y$ на межпиковом участке одинаковы и меняются как раз на острие зубца: $467+512=466+513=...=979;\ 452+527=979,451+529=980.$ А для заданной суммы оптимальное значение $v$ только одно: $\left \lceil \sqrt{s^2-(m-s)^2} \right \rceil$ или $\left \lceil \sqrt{(m-m')^2-m'^2} \right \rceil$, если угодно. Все остальные решения заведомо не могут быть лучшими, и возникает необходимость расширить понятие "приведенного решения". Углубляться не буду, скажем так:

Существует "точка смены дат", обозначим ее $\Omega=\dfrac{m-3}{9}$, характеризуемая также отношением $y \approx 4x+2.$

Для $x<\Omega$ решение считается приведенным, если $y=\left \lfloor (\sqrt{m}-\sqrt{x})^2 \right \rfloor.$

Для $\dfrac{(\sqrt{m}-1)^2}{4}>x>\Omega$ решение считается приведенным, если $v=\left | x-y \right |=\left \lceil \sqrt{(x+y)^2-(m-x-y)^2} \right \rceil$.

Во избежание лишних вычислений в процессе воображаемого перебора, в нижней части решения генерируются от последовательных $1 \leqslant x <\Omega$, в верхней части — от последовательных $\dfrac{m+1}{2} \leqslant s<s_{\Omega}=\dfrac{5m+3}{9}$ по формуле $x,y=\dfrac{\left ( m \pm v \right )^2-R}{4m}.$ И пора наконец пронумеровать формулы

$$x,y=\dfrac{\left ( m \pm v \right )^2-R}{4m}\ \ \ \ \ \ (1).$$

$$v=\left \lceil \sqrt{(x+y)^2-(m-x-y)^2} \right \rceil\ (2)$$

или

$$v^2=m(2s-m)+R\ \ \ \ \ \ (3).$$

[Andrey A]

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

Выходит, в первом случае обратная задача решается на пятерку, а тут затык... это как минимум странно. Просто она сложная.

Но не безнадежная. Напомню:

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

Обозначим $\beta_n=\dfrac{p_n}{q_n},\ a+b=s,\ a-b=v$ и приравняем остатки дробей разложений $\sqrt{m}$ и $\sqrt{a}+\sqrt{b}:$

$$\dfrac{2\beta_n}{\beta_n^2-m} \cdot \dfrac{(-1)^n}{q_n^2}-\dfrac{q_{n-1}}{q_n}=\dfrac{4\beta_n(\beta_n^2-s)}{\beta_n^4-2s\beta_n^2+v^2} \cdot \dfrac{(-1)^n}{q_n^2}-\dfrac{q_{n-1}}{q_n}$$

После тотального взаимоуничтожения переменных получаем хорошо знакомое

$$v^2-m(2s-m)=R\ \ (3)$$

при бесконечно малом $R=(\beta_n^2-m)^2.$

Дальше такая высшая математика пошла, что без стакана было не обойтись. Я-то почти не пью, а тут пришлось, и кажется впрок. Всех с Новым Годом! Наутро подумалось примерно так: выражение $\beta_n^4-2s\beta_n^2+v^2$ суть убывающая погрешность разложения $\sqrt{x}+\sqrt{y}$. Равенство $(3)$ позволяет избавиться от переменной $v$. Подставляя в первое $v^2=m(2s-m)+R$ и приравнивая его к нулю, получаем линейное уравнение относительно $s$, но $R$ следует брать не бесконечно малым, понятно, а реально отвечающим условию задачи. И вот оказалось, оно отлично работает:

$$s_n=\lim_{n \to \infty}\dfrac{\beta_n^4-m^2+R}{2(\beta_n^2-m)}.$$

Рискнул поставить точное равенство, хотя не уверен что последовательность сходится именно к целой точке, но к очень близкой. Впрочем, пока проверял только случаи $R=1.$ Выражение верно для последовательности подходящих дробей $\beta_n=\dfrac{p_n}{q_n}$ разложения $\sqrt{x}+\sqrt{y}$, а зная $s=x+y,$ легко получаем искомые $x,y$ с помощью равенств $(3),(1).$ Так что обратная задача решена. Но! Этих "но" тут с лихвой, и главный вопрос оказался вовсе не пустяковым: сколько верных дробей содержит разложение $\sqrt{m},$ действительно ли их "станет хватать" при достаточно больших модулях и что делать, если это не так. Для $m=15403$ их всего $6$ (даже меньше чем для $m=913$), а нужно $12!$ Сильно против работает присутствие больших знаков дроби (в разложении $\sqrt{15403}\approx $ их два: $u_7=27,u_8=82$). Короче, нужен анализ статистики, тут вся моя надежда на сообщество. Заранее признателен! Есть и хорошие новости:

— Для положительного $R$ достаточно исследовать только нечетные дроби $(s<m)$, остальные случаи пока не разбирал, но всё к тому что четные понадобятся для $R<0$ (верхние приближения), а $R=0$ — пожалуйста и те и другие. Члены последовательности $s_{n=2k-1}$ ложатся на некоторую плавную кривую, которая в искомой целой точке $s$ почти вырождается в прямую параллельную оси $n$ (абсцисс). Если бы удалось экстраполировать ее по нескольким начальным значениям — это было бы отличное, действительно аналитическое решение.

И пока хватит. Мало ли, может не всем попалась такая хорошая водка ) "Зона совпадения знаков" всё-таки должна расти, но похоже, и необходимое количество знаков не стоит на месте. Самый трудный вопрос.

[Andrey A]

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

Для положительного $R$ достаточно исследовать только нечетные дроби...

Имелось в виду нечетные дроби разложения $\sqrt{m}$, конечно. Вместо параметра $s$, кстати, можно вычислять по той же схеме параметр $v$, и вроде бы с меньшими затратами (если это не иллюзия).

$$v_n=\lim_{n \to \infty}p_n\sqrt{\dfrac{m}{q_n^2}+\dfrac{R}{p_n^2-mq_n^2}}.$$

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

[juna]

Andrey A

Я не понял ваш новогодний инсайт.))
Можно продемонстрировать на числах, например, $m=195,v=14, s=98, R=1$, подходящие дроби разложения $\sqrt{m}$:

$$\frac{13}{1}, \frac{14}{1}, \frac{377}{27}, \frac{391}{28}, \frac{10543}{755}$$

Кстати, если $n$ - период цепной дроби разложения $\sqrt{m}$, а $\frac{p_{n-1}}{q_{n-1}}$ - предпоследняя перед окончанием периода подходящая дробь, то $v^2=p_{n-1}^2\equiv 1\mod m$. Это иногда тоже дает не совсем нетривиальные результаты.
Например, для первого квазипростого $m=1711$ имеем:

$$\sqrt{1711}=41.36423575989287\approx\sqrt{2}+\sqrt{1596}=41.36418227324945, R=1$$

но это хуже чем:

$$\sqrt{1711}\approx\sqrt{181}+\sqrt{779}=41.36419552097944, R=5$$

Если же допустить рациональные приближения, то это:

$$\sqrt{1711}\approx\sqrt{\frac{1953}{4}}+\sqrt{\frac{1485}{4}}=41.36422866198204$$

будет уже лучше.

[Andrey A]

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

... новогодний инсайт.))

Да, такой выход из-за печки с расчетом на эффект ) Ничего, разберемся. Насчет $m=1711$ нет ли ошибки? Там 24 знака в периоде. Дробь, о которой Вы говорите всегда была $n$-ой: $p_n^2-mq_n^2=1.$ Пелль. Но он легко может дать тривиальный квадрат, ему это без разницы, а нам важно. Вообще говоря, двойка — решение вида $R=1$ для всех треугольных чисел. $t_{2n}=n(2n+1);\ \dfrac{2n+1}{n}=2,n;\ 2,n-1= \dfrac{2}{1},\dfrac{2n-1}{n-1} \rightarrow$ $\sqrt{2}+\sqrt{t_{2n-2}} \approx \sqrt{t_{2n}}.$ С $t_{2n+1}$ чуть по-другому, общий случай $\sqrt{2}+\sqrt{t_n} \approx \sqrt{t_{n+2}},$ но $v=t_n-2$ очень большое; если нет других делителей, имеем кандидата в квазипростые.

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

$m=195,v=14, s=98, R=1$

$\sqrt{195} \approx \sqrt{42}+\sqrt{56}$

$\sqrt{195}=13,(1,26)$

$\sqrt{42}+\sqrt{56}=13,1,26,1,4,1,1,2,1,4,4,1,3,...$

Как видим, совпадают $4$ знака, из них всего $2$ нечетных. Для нашей задачи этого мало, в том и проблема. Выпишу нечетные подходящие дроби последнего разложения.

$\sqrt{42}+\sqrt{56} \approx \dfrac{13}{1},\dfrac{377}{27},\dfrac{1941}{139},$ $\dfrac{4273}{306},\dfrac{15151}{1085},\dfrac{301079}{21561},\dfrac{1418762}{101601},...$ Подставляя числители и знаменатели в формулу $\approx p_n\sqrt{\dfrac{m}{q_n^2}+\dfrac{R}{p_n^2-mq_n^2}}$, где $m=195,R=1,$ получаем последовательность

$$v_n=181,52;\ 180,42;\ 70,54;\ 28,94;\ 15,21;\ 14,01;\ 14,00;...$$

Из двух последних знаков уже видно целую точку $v$, к которой сходится последовательность, и которая была бы решением, если бы в нашем распоряжении имелось $L=7$ нечетных дробей разложения, но у нас их только $l=2.$ По большим модулям картина менее удручающая, конечно, но надежды мало. Хорошо бы иметь статистику. Спрашивайте, если что непонятно, я умею невнятно выражаться.

[juna]

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

Насчет $m=1711$ нет ли ошибки? Там 24 знака в периоде
.

Да нет, все верно. Вы же берёте для Пелля 23 знака периода, т.е. в общем случае $kn-1$ знаков. Просто я в нумерации подходящих дробей целую часть (41) не считал как номер (что, конечно, некорректно):

$$\sqrt{1711}=[41; \overline {2, 1, 2, 1, 13, 16, 2, 8, 1, 2, 2, 2, 2, 2, 1, 8, 2, 16, 13, 1, 2, 1, 2, 82}]$$

$$[41; 2, 1, 2, 1, 13, 16, 2, 8, 1, 2, 2, 2, 2, 2, 1, 8, 2, 16, 13, 1, 2, 1, 2]=\frac{12257063847449}{296320326540}=\frac{p_{23}}{q_{23}}$$

$$12257063847449\equiv 1594\mod 1711\Rightarrow 1594^2\equiv 1\mod 1711, (1711-1594)^2=117^2\equiv 1\mod 1711$$

Т.е. можно брать $v=1594, 117$

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

Как видим, совпадают $4$ знака, из них всего $2$ нечетных.

Да, теперь понял, что Вы делаете. Т.е. подходящие дроби берутся для $\sqrt{x}+\sqrt{y}$, а в $\sqrt{m}$ уж как повезет...
Например,

$$\sqrt{181}+\sqrt{779}\approx [41; 2, 1, 2, 1, 14, 18, 1, 8, 8, 4, 1, 8, 7, 2, 2, 2, 1, 1, 1, 1, 1, 14, 3, 3, 1, 1, 9, 1, 3, \ldots]$$

Берем 8-ю (при нумерации с нуля) подходящую дробь $\frac{1143265}{27639}=[41; 2, 1, 2, 1, 14, 18, 1, 8]$, получаем $v\approx 598.0084055087813$

$$\sqrt{1711}=[41; \overline {2, 1, 2, 1, 13, 16, 2, 8, 1, 2, 2, 2, 2, 2, 1, 8, 2, 16, 13, 1, 2, 1, 2, 82}]$$

Т.е. не хватило 4 верных знака.

[juna]

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

Короче, нужен анализ статистики, тут вся моя надежда на сообщество.

А какая конкретно статистика нужна?
Могу, например, рассчитать количество членов цепной дроби для $\sqrt{x}+\sqrt{y}$, дающих лучшее приближение, которое достаточно для получения $v$ в сравнении с соответствующими членами для $\sqrt{m}$ для всех $m\leq m_0$.

[Andrey A]

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

Т.е. не хватило 4 верных знака.

У меня для обоих приближений получилось $L=6,l=3.$ С этим удвоенным знаком в радикале вечная путаница, можно ведь взять вместо $82$ так: $41,0,41,...$ и последнее $41$ принадлежит уже новому периоду, а сам период есть точный палиндром от $1$-го знака с нулем в конце или в начале (если подкоренное значение $<0$). Вопрос записи, но вот уже начинаем путаться. Принципиально важно "чистый" период, или "со вступлением". Последнее всегда осложняет дело, а тут и так хватает заморочек. $p$-ичная дробь, к примеру, приближается снизу, а тут с двух сторон. Сравнивая две непрерывные дроби по величине, нечетные знаки следует понимать в обычном смысле, а четные — в обратном (больше — меньше). У нас нечетные оказываются как раз между радикалом и нижним приближением, отсюда и предпочтение. Но о терминах лучше договориться. Бывают еще и нечетные периоды: $18^2-13 \cdot 5^2=-1.$
Насчет статистики — да, нужно понять как ведут себя $L/l$ с ростом модулей и возможно ли принципиально $L=l$. Подозреваю что нет.

[Andrey A]

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

(если подкоренное значение $<0$)

Тут ошибка. Правильно "(если подкоренное значение $<1$)"

[juna]

В файле выполнена сортировка по возрастанию отношения $\frac{L}{l}$, при необходимости можно пересортировать по $m$.
Исключал полные квадраты и случаи $R=0$. В пределах $m_0\leq 3000$ совпадений $L=l$, кроме тривиальных $m=5$, или $R=0$, нет.
Можно проводить классификацию чисел по отношению $\frac{L}{l}$, что собственно и сделано в файле, но чтобы это как-то помогло в решении задачи - не видно как. Даже в лучших случаях $l=L-1$, например, $m=501, L=8, l=7, x=56, y=222, R=1,v=166 $:

$$\sqrt{501}=[22; 2, 1, 1, 1, 1, 3, 8,\ldots]$$

$$\sqrt{56}+\sqrt{222}=[22; 2, 1, 1, 1, 1, 3, 952,\ldots]$$

разброс в первом несовпадающем знаке слишком велик, чтобы перебор имел смысл (8 против 952).
$l$ - определяет количество совпадающих знаков в разложениях $\sqrt{m}$ и $\sqrt{x}+\sqrt{y}$.
$L$ - определяет минимальное количество знаков в разложении $\sqrt{x}+\sqrt{y}$, чтобы выполнялось условие $|v-v_n|<1$