Лучшее приближение корня суммой 2-х корней

[Sonic86]

Не знаю как решать, мне задачка понравилась

Найти для натурального $A$ натуральные $x,y$ такие, чтобы выражение $\sqrt{A}\approx \sqrt{x}+\sqrt{y}$ являлось лучшим приближением.

Позаимствовано у Андрея А отсюда:
http://www.mathhelpplanet.com/viewtopic.php?f=48&t=8809 (новая тема)
http://e-science.ru/forum/index.php?s=e ... opic=11670 (старая тема)

[Shadow]

(Оффтоп)

Цитата:

Если эту штуку можно решить, не прибегая к подбору значений, то существует, кажется, очень красивый способ нахождения делителей целого числа вообще

А не слишком ли амбициозную (и вредную) задачу поставил себе Андрей.

[Sonic86]

(Оффтоп)

Shadow в сообщении #496501 писал(а):

А не слишком ли амбициозную (и вредную) задачу поставил себе Андрей.

А что, это какая-то известная сложная задача? Может NP-полная?
Согласен насчет вредности - трудная задачка, по-моему.

[Legioner93]

$x=A$, $y=0$

[xmaister]

(Оффтоп)

Legioner93, 0- не натуральное

[AKM]

Legioner93,

в РФ ноль не считается натуральным (номер статьи не помню).

[Legioner93]

(Оффтоп)

у меня считается

Sonic86 в сообщении #496516 писал(а):

Может NP-полная?

Кстати тоже так подумал.

[Sonic86]

Legioner93 в сообщении #496561 писал(а):

Кстати тоже так подумал.

Просто автор задачи утверждает, что он решил задачку для всех составных чисел - это уже множество меры 1. Может она и не NP-полная. Короче, решить надо.

[Cash]

Cоображения следующие:
$\sqrt{A} - \sqrt{x} = \sqrt{y}$
$\sqrt{4Ax} = A+x-y$
Меняя $y$ справа можно сделать любое целое нужного диапазона.
Соответственно нужно подобрать множитель к числу $4A$ сделав его близким к квадрату.
Если в лоб, то можно решить уравнение $4Ax=(z-1)(z+1)$
в случае составного $A$ - оно элементарно. Хорошие приближения мы точно получим, но гарантии наилучшего, правда, нет.

[Sonic86]

Для числа $805$ точное приближение такое:
$\sqrt{805} \approx \sqrt{66} + \sqrt{410}, \epsilon \approx 2,6 \cdot 10^{-5}$. Я какую-то формулу нашел, но это - первый контрпример к ней. Было бы интересно знать соображения, из которых такое приближение находится точно.

[bot]

(Оффтоп)

AKM в сообщении #496559 писал(а):

в РФ ноль не считается натуральным

В РФ нет логиков?

[Sonic86]

В общем, целиком задача не решилась.
Основную часть решения ТС изложил в теме по ссылке, полученное решение в итоге упирается в перебор, что плохо. У ТС изначально были только приближения снизу, но существенной разницы между задачами похоже нет.
В случае составных $n$ используется такой прием:
$(A^2+B^2)(C^2+D^2)=(AC+BD)^2+(AD-BC)^2$. Заменяя переменные на корни из них, имеем $(A+B)(C+D)=(\sqrt{AC}+\sqrt{BD})^2+(\sqrt{AD}-\sqrt{BC})^2$ При $AD-BC= \pm 1$ получаем
$\sqrt{(A+B)(C+D)} \approx \sqrt{AC}+\sqrt{BD}$. В случае, когда $n=pq, p,q \in \mathbb{P}$ мы, решая уравнение $AD-BC= \pm 1$, получаем 2 приближения сверху и снизу и выбираем точное. А в случае большего числа делителей перебор увеличивается. Оптимальное значение достигается при наиболее близких друг к другу значениях корней $\sqrt{AC},\sqrt{BD}$
Другой прием - формула $\sqrt{A} \approx \sqrt{\frac{(A-B)^2+\Delta}{4A}}+\sqrt{\frac{(A+B)^2+\Delta}{4A}}$, где $B:B^2 \equiv - \Delta \pmod{A}$ - наименьшее по модулю (чем меньше, тем точнее приближение). Прием работает как для составных, так и для простых. Для составных $A$ поиск наименьшего $B$ сводится к перебору решений, число вариантов выбора растет с увеличением числа делителей (экспоненциально). Для простых $A$ решения для заданного $\Delta$ могут не существовать или быть тривиальными, поэтому приходится перебирать $\Delta$ + не получилось доказать (скорее, это просто неверно), то погрешность растет с ростом $\Delta$. Величина $\Delta$ растет не быстрее, чем $\ln A$.
Сведение $\sqrt{n} \approx \sqrt{x} + \sqrt{y}$ к уравнению $t^2-(n-k)t+\frac{k^2+ \Delta}{4}=0$ дает в лучшем случае то же самое ($t=x;y$)