√m≈√x+√y

[Andrey A]

Задача в натуральных числах: для достаточно большого фиксированного $m$ найти лучшее нижнее приближение $\sqrt{m} \approx \sqrt{x}+\sqrt{y}\ \ (1)$. В свое время долго ломал над ней голову, но так ничего и не придумал. Вопрос немножко детский в силу простоты условия, и может быть решен перебором, но всегда ведь хочется чего-то большего. Рассмотрим три случая.

1) $m$ кратно целому квадрату $>1.$ Тогда возможно точное равенство

$$\sqrt{a\left ( b+c \right )^2}=\sqrt{ab^2}+\sqrt{ac^2}.$$

2) Четное $m$ свободно от квадратов. В этом случае решением является выражение

$$\sqrt{4d+2} \approx \sqrt{d}+\sqrt{d+1}.$$

3) Нечетное $m$, свободное от квадратов. Если $m$ составное, и пара $(x,y)$ — решение $(1),$ справедливы следующие сравнения:

$$\left\{\begin{matrix} (m-x)^2 \equiv 1 \mod y\\ (m-y)^2 \equiv 1 \mod x\\ (x-y)^2 \equiv 1 \mod m \end{matrix}\right.$$

В случае простого $m$ выполняются похожие соотношения с той разницей, что вместо единицы в правой части сравнения оказывается некая малая величина (положительный квадратичный вычет). Для $m=103$, к примеру, имеем решение $\sqrt{103} \approx \sqrt{14}+\sqrt{41}$, и выполняются сравнения $(103-14)^2 \equiv 8 \mod 41,\ (103-41)^2 \equiv 8 \mod 14,\ (41-14)^2 \equiv 8 \mod 103. $ Таким образом, решение предложенной задачи равносильно не только тесту на простоту, но и факторизации $m$ и вряд ли предполагает простые методы. Речь скорее об алгоритмическом подходе. Что касается составного $m$ — тут возможны различные методы, один из них основан на формуле сложного радикала:
пусть $v$ — основание наименьшего из четных квадратов, сравнимых с единицей по $\mod m.$ Тогда $x,y=\dfrac{\left ( m \pm v \right )^2-1}{4m}.$
О другом методе поподробней. Возьмем тождество $(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=77=11 \cdot 7$, разложим $\dfrac{11}{7}=1,1,1,3$ и выпишем подходящие дроби, уменьшив последний знак на единицу: $1,1,1,2=\dfrac{1}{1},\dfrac{2}{1},\dfrac{3}{2},\dfrac{8}{5}.$ Элементы двух последних дробей возвращают нужные $a,b,c,d$ из описанной выше схемы: $\sqrt{3 \cdot 2}+\sqrt{8 \cdot 5}=\sqrt{(8+3)(5+2)}.$

Если мне память не изменяет, Диофант описывает тройки чисел $A,B,C$ такие, что все три числа $AB,AC,BC$ являются числами вида $k(k+1).$ Это и есть $m,x,y.$ О радикалах, правда, он ничего не говорит. Ну, а вопрос прежний: найти $x,y,$ исходя из величины $m$. Как это с точки зрения теории алгоритмов — совсем безнадежное дело?

[Andrey A]

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

$\sqrt{3 \cdot 2}+\sqrt{8 \cdot 5}=\sqrt{(8+3)(5+2)}.$

Правильно конечно так: $\sqrt{3 \cdot 2}+\sqrt{8 \cdot 5}\approx \sqrt{(8+3)(5+2)}.$ Кстати. Стартовой парой парой для разложения в цепную дробь может служить не только пара множителей $m$, но и другие пары вз. простых чисел, определяющие величину $m.$ Разность квадратов, например, или даже основания квадратов формы $kp^2-lq^2=m.$ Решение для $m=103$ в частности может быть получено из равенства $11^2-2 \cdot 3^2=103:$
$\dfrac{11}{3}=3,1,2.$ Откуда $3,1,1=\dfrac{3}{1},\dfrac{4}{1},\dfrac{7}{2}$ и $4^2-2 \cdot 1^2=14,\ 7^2-2 \cdot 2^2=41.$ Но вывода о том, что решение $\sqrt{103} \approx \sqrt{14}+\sqrt{41}$ — лучшее (хотя это так и есть) отсюда сделать нельзя. Можно заключить только, что если оно лучшее, то $103$ простое. Короче, тут лишь способ получить относительно хорошее приближение для начала некоторого (загадочного) процесса. Я пробовал сортировать по величине арифметические суммы радикалов. Сильных закономерностей (как в дробях Фаррея) что-то не увидел.

И еще. Если $\sqrt{a}+\sqrt{bc^2} \approx \sqrt{m}$ и $a \equiv m \mod c$, то $b$ — элемент лучшего приближения $\sqrt{a'}+\sqrt{b} \approx \sqrt{m},$ где $a'$ вычисляется без труда.

[Andrey A]

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

Откинув это в качестве погрешности, получаем $\sqrt{(a+b)(c+d)} \approx \sqrt{ad}+\sqrt{bc}.$

Еще ошибка. Правильно: $\sqrt{(a+b)(c+d)} \approx \sqrt{ac}+\sqrt{bd}.$

[waxtep]

Не уверен, что это чем-то поможет, скорее наблюдение, вдохновленное примером $\sqrt{103}=\sqrt{14}+\sqrt{41}$.
Пусть $m=4k+r,k,r\in\mathbb{N},1\leqslant r\leqslant3,x=k-a,y=k+b,\sqrt{m}+\delta=\sqrt{x}+\sqrt{y}$. Возведем последнее равенство в квадрат и разложим $\sqrt{xy}$ до первого порядка малости по $1/k$:

$$2\delta\sqrt{m}+\delta^2\approx2(b-a)-r-\frac{ab}k$$

т.е. было бы неплохо найти такие $a,b$, что

$$(2(b-a)-r)k\approx ab$$

В упомянутом примере $k=25,a=11,b=16$ и, действительно, $(2\cdot(16-11)-3)\cdot25=175\approx176=11\cdot16$

-- 06.11.2022, 20:35 --

Кстати, а $\sqrt{103}\approx\sqrt{21}+\sqrt{31}$ вроде еще получше выглядит, здесь, соответственно, $a=4,b=6,(2\cdot(6-4)-3)\cdot25=25\approx24=4\cdot6$. Это, правда, верхнее приближение.

-- 06.11.2022, 20:59 --

В общем, если поверить в эту звезду, то, видимо, следует искать наименьшее $a$, такое, что

$$(2(b-a)-r)k=ab-1$$

[waxtep]

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

В общем, если поверить в эту звезду, то, видимо, следует искать наименьшее $a$, такое, что

$$(2(b-a)-r)k=ab-1$$

И это вроде еще вот так можно записать, в виде корней некоторого квадратного уравнения, возвращаясь к $x,y$:

$$\begin{cases}xy=kp-1\\x+y=3k-p+r \end{cases}$$

Если ввести $t=k-p$, то по крайней мере для квадратности дискриминанта надо найти такое (и желательно наименьшее) $t$, чтобы $(2t+r)m+t^2+4$ было квадратом целого

[Andrey A]

waxtep
Спасибо, надо это дело обмозговать. Первое впечатление — не многовато ли переменных для устойчивой конструкции? Ладно, перепишем это

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

$$(2(b-a)-r)k=ab-1$$

так: $a = \dfrac{2 b k - k r + 1}{b + 2 k}$ Целой, на сколько понял, дробь в правой части быть и не должна, а убрав единицу из числителя, получаем $a = \dfrac{k(2b-r)}{b + 2 k}.$ Можно исходить из соображений сравнимости, но тут возникают неприятности, которые оставим с Вашего позволения на попозже.

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

$(2t+r)m+t^2+4$

Оно квадрат? $(2t+r)m+t^2+4=s^2$ Имеем квадратное уравнение по $t$, и $t = \sqrt{m^2 - m r + s^2 - 4} - m$. Отсюда $m^2-mr-4=(m+t)^2-s^2$. В левой части конкретное число и, значит, конечное число решений. Как-то слишком гладко )

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

Это, правда, верхнее приближение.

Это существенно.

[waxtep]

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

Первое впечатление — не многовато ли переменных для устойчивой конструкции?

Вообще, всего две, $a,b$ - насколько сильно $x,y$ отклоняются от $\lfloor\frac m4\rfloor$, ведь $k,r$ - известные числа.

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

Целой, на сколько понял, дробь в правой части быть и не должна

Здесь имел в виду точное равенство; правда, это только надежда, что всегда можно подобрать такие $a,b$, чтобы разница была в единицу (и вторая надежда - что это оптимум)

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

Оно квадрат? $(2t+r)m+t^2+4=s^2$ Имеем квадратное уравнение по $t$, и $t = \sqrt{m^2 - m r + s^2 - 4} - m$. Отсюда $m^2-mr-4=(m+t)^2-s^2$. В левой части конкретное число и, значит, конечное число решений. Как-то слишком гладко )

Причем, если следовать той же логике, следует искать наименьшее такое $t$; в примере с $\sqrt{103}, t=2$ и

$$\begin{cases}14\cdot41=25\cdot(25-2)-1\\14+41=3\cdot25-(25-2)+3\end{cases}$$

[Andrey A]

Обратные подстановки ведут к $x,y=\dfrac{2k+t+r \pm s}{2}$. Да, иногда работает. А иногда не хватает нужных квадратов, ведь может выпасть и учетверенное простое. Хуже другое — для $m=77$, к примеру, $k=19,r=1,t=0,s=9$ и получаем $x=15,y=24.$ Оно хорошее приближение, но не лучшее. Получить некоторое относительно хорошее приближение способы есть (выше), однако для теста на простоту что-то нужно знать точно. Такая незадача.

[waxtep]

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

получаем $x=15,y=24.$ Оно хорошее приближение, но не лучшее.

Действительно, оно только второе по "лучшине", $\sqrt{6}+\sqrt{40}$ симпатичнее, и оба числа очень далеки от ожидаемого среднего $19$, то есть вообще не там. Хм-хм

[Andrey A]

Да, здесь много мелких обстоятельств, которые суть "грабельки для наступания". Обратите внимание: $24=6 \cdot 2^2$ и $77 \equiv 15 \mod 2.$ То есть одно следует из другого, а $(40-6)^2 \equiv 1 \mod 77.$ Лучшее? Да. Если нет других делителей ) Для составного $m$ вопрос не принципиальный, а для простого — важный. Вообще говоря, из любого решения с малым $x$ можем получить серию несколько худших приближений, домножая $x$ на последовательные квадраты, и каждое из них можем вернуть к первоначальному состоянию, решив соотв. сравнение. Надо бы ввести термин "примитивное приближение".
Теперь следующее. Ваш метод, насколько понял, неявно задействует пропорцию $\dfrac{y}{x}$, заранее усредняя ее. Это, конечно, неприемлемо, поскольку решение $(1)$ единственно, вполне определяет такую пропорцию и может быть к ней сведено. Обозначим $\gamma = \dfrac{y}{x}$ и решим систему $\left\{\begin{matrix} \sqrt{x}+\sqrt{y} \approx \sqrt{m}\\ \dfrac{y}{x}=\gamma \end{matrix}.\right.$ Получаем

$$\left\{\begin{matrix} x \approx \dfrac{m}{\left ( 1+\sqrt{\gamma} \right )^2} \\ y=\gamma x \approx \dfrac{\gamma m}{\left ( 1+\sqrt{\gamma} \right )^2} \end{matrix}.\right.$$

Нижняя граница $\gamma_{\min} \approx \left ( \dfrac{\sqrt{m}+1}{\sqrt{m}-1} \right )^2$ с ростом $m$ стремится к единице, верхняя $\approx \left ( \sqrt{m}-1 \right )^2 $ порядка $m$. И в каждой точке можем получить некоторое хорошее/плохое приближение, хотя шкала неравномерна. Знать бы где оно лежит — слева или справа от искомого $\gamma$, и можно включать двоичный поиск. А так... Но мне кажется, тут у нас ключиком больше в кармане зазвенело.

[waxtep]

Посмотрел на график $\delta=\sqrt{m}-\sqrt{x}-\sqrt{y}$ в зависимости от "лучшины" приближения (1 - наилучшее, 2 - следующее и т.п.) для нескольких $m$ - такие аккуратно сшитые кусочки перевернутых корневых парабол. Если же по оси $Ox$ откладывать $a=\lfloor m/4\rfloor-x$, картинки становятся безобразными, и надежды на какой-либо автоматизированный поиск локального минимума не оставляют. При этом, есть "приличные" числа, для которых оптимум находится в точке наименьшей по модулю разницы между $(2(a-b)-r)k$ и $ab-1$ (правда, это необязательно ноль): $79, 83, 85$, а есть "противные", где в этих координатах он далеко справа и вообще непонятно где - $77,87$. Это конечно колдунство уже какое-то пошло, но, интересно, что общего может быть у "противных" чисел?

[Andrey A]

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

что общего может быть у "противных" чисел?

Не знаю. Два колдуна на одной кухне не разойдутся.

[waxtep]

Видимо, то, что их большинство... при том некоторые просто таки гипер-противные, типа $\sqrt{91}\approx\sqrt2+\sqrt{66}$. В общем, метод работает лишь изредка

[waxtep]

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

Ваш метод, насколько понял, неявно задействует пропорцию $\dfrac{y}{x}$, заранее усредняя ее. Это, конечно, неприемлемо, поскольку решение $(1)$ единственно, вполне определяет такую пропорцию и может быть к ней сведено.

На третий день Зоркий Глаз заметил, что задача однопараметрическая, и если $x$ задано, то $y$ тоже известно. Да уж Тогда ещё повоюем

[Andrey A]

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

гипер-противные

Это треугольные числа ) $\sqrt{t_{n+1}} \approx \sqrt{2}+\sqrt{t_{n-1}}$ и заметьте, попарные произведения — все числа вида $k(k+1).$ Для $m=91$ приближение действительно лучшее, но не для четных.

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

Зоркий Глаз заметил, что задача однопараметрическая...

Она такая э... как клюква в сахаре — пока коробка не опустеет. Решение всегда есть и при желании находится перебором. С другой стороны арифметические суммы радикалов теоретически могут быть отсортированы по величине, остается взять нужные. Казалось бы...