2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему На страницу 1, 2, 3, 4, 5 ... 12  След.
 
 √m≈√x+√y
Сообщение06.11.2022, 03:55 
Заслуженный участник
Аватара пользователя


21/11/12
1902
Санкт-Петербург
Задача в натуральных числах: для достаточно большого фиксированного $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$. Как это с точки зрения теории алгоритмов — совсем безнадежное дело?

 Профиль  
                  
 
 Re: √m≈√x+√y
Сообщение06.11.2022, 12:40 
Заслуженный участник
Аватара пользователя


21/11/12
1902
Санкт-Петербург
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'$ вычисляется без труда.

 Профиль  
                  
 
 Re: √m≈√x+√y
Сообщение06.11.2022, 15:01 
Заслуженный участник
Аватара пользователя


21/11/12
1902
Санкт-Петербург
Andrey A в сообщении #1569081 писал(а):
Откинув это в качестве погрешности, получаем $\sqrt{(a+b)(c+d)} \approx \sqrt{ad}+\sqrt{bc}.$
Еще ошибка. Правильно: $\sqrt{(a+b)(c+d)} \approx \sqrt{ac}+\sqrt{bd}.$

 Профиль  
                  
 
 Re: √m≈√x+√y
Сообщение06.11.2022, 20:17 
Аватара пользователя


07/01/16
1448
Аязьма
Не уверен, что это чем-то поможет, скорее наблюдение, вдохновленное примером $\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$$

 Профиль  
                  
 
 Re: √m≈√x+√y
Сообщение06.11.2022, 21:44 
Аватара пользователя


07/01/16
1448
Аязьма
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$ было квадратом целого

 Профиль  
                  
 
 Re: √m≈√x+√y
Сообщение06.11.2022, 23:22 
Заслуженный участник
Аватара пользователя


21/11/12
1902
Санкт-Петербург
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 писал(а):
Это, правда, верхнее приближение.

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

 Профиль  
                  
 
 Re: √m≈√x+√y
Сообщение07.11.2022, 00:02 
Аватара пользователя


07/01/16
1448
Аязьма
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}$$

 Профиль  
                  
 
 Re: √m≈√x+√y
Сообщение07.11.2022, 01:38 
Заслуженный участник
Аватара пользователя


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

 Профиль  
                  
 
 Re: √m≈√x+√y
Сообщение07.11.2022, 04:22 
Аватара пользователя


07/01/16
1448
Аязьма
Andrey A в сообщении #1569167 писал(а):
получаем $x=15,y=24.$ Оно хорошее приближение, но не лучшее.
Действительно, оно только второе по "лучшине", $\sqrt{6}+\sqrt{40}$ симпатичнее, и оба числа очень далеки от ожидаемого среднего $19$, то есть вообще не там. Хм-хм

 Профиль  
                  
 
 Re: √m≈√x+√y
Сообщение07.11.2022, 10:21 
Заслуженный участник
Аватара пользователя


21/11/12
1902
Санкт-Петербург
Да, здесь много мелких обстоятельств, которые суть "грабельки для наступания". Обратите внимание: $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$, и можно включать двоичный поиск. А так... Но мне кажется, тут у нас ключиком больше в кармане зазвенело.

 Профиль  
                  
 
 Re: √m≈√x+√y
Сообщение07.11.2022, 12:54 
Аватара пользователя


07/01/16
1448
Аязьма
Посмотрел на график $\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$. Это конечно колдунство уже какое-то пошло, но, интересно, что общего может быть у "противных" чисел?

 Профиль  
                  
 
 Re: √m≈√x+√y
Сообщение07.11.2022, 13:42 
Заслуженный участник
Аватара пользователя


21/11/12
1902
Санкт-Петербург
waxtep в сообщении #1569204 писал(а):
что общего может быть у "противных" чисел?

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

 Профиль  
                  
 
 Re: √m≈√x+√y
Сообщение07.11.2022, 17:15 
Аватара пользователя


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

 Профиль  
                  
 
 Re: √m≈√x+√y
Сообщение07.11.2022, 18:45 
Аватара пользователя


07/01/16
1448
Аязьма
Andrey A в сообщении #1569191 писал(а):
Ваш метод, насколько понял, неявно задействует пропорцию $\dfrac{y}{x}$, заранее усредняя ее. Это, конечно, неприемлемо, поскольку решение $(1)$ единственно, вполне определяет такую пропорцию и может быть к ней сведено.
На третий день Зоркий Глаз заметил, что задача однопараметрическая, и если $x$ задано, то $y$ тоже известно. Да уж :facepalm: Тогда ещё повоюем :-)

 Профиль  
                  
 
 Re: √m≈√x+√y
Сообщение07.11.2022, 19:30 
Заслуженный участник
Аватара пользователя


21/11/12
1902
Санкт-Петербург
waxtep в сообщении #1569235 писал(а):
гипер-противные
Это треугольные числа ) $\sqrt{t_{n+1}} \approx \sqrt{2}+\sqrt{t_{n-1}}$ и заметьте, попарные произведения — все числа вида $k(k+1).$ Для $m=91$ приближение действительно лучшее, но не для четных.
waxtep в сообщении #1569248 писал(а):
Зоркий Глаз заметил, что задача однопараметрическая...
Она такая э... как клюква в сахаре — пока коробка не опустеет. Решение всегда есть и при желании находится перебором. С другой стороны арифметические суммы радикалов теоретически могут быть отсортированы по величине, остается взять нужные. Казалось бы...

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 180 ]  На страницу 1, 2, 3, 4, 5 ... 12  След.

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group