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
1870
Санкт-Петербург
Задача в натуральных числах: для достаточно большого фиксированного $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
1870
Санкт-Петербург
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
1870
Санкт-Петербург
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
1426
Аязьма
Не уверен, что это чем-то поможет, скорее наблюдение, вдохновленное примером $\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
1426
Аязьма
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
1870
Санкт-Петербург
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
1426
Аязьма
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
1870
Санкт-Петербург
Обратные подстановки ведут к $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
1426
Аязьма
Andrey A в сообщении #1569167 писал(а):
получаем $x=15,y=24.$ Оно хорошее приближение, но не лучшее.
Действительно, оно только второе по "лучшине", $\sqrt{6}+\sqrt{40}$ симпатичнее, и оба числа очень далеки от ожидаемого среднего $19$, то есть вообще не там. Хм-хм

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


21/11/12
1870
Санкт-Петербург
Да, здесь много мелких обстоятельств, которые суть "грабельки для наступания". Обратите внимание: $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
1426
Аязьма
Посмотрел на график $\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
1870
Санкт-Петербург
waxtep в сообщении #1569204 писал(а):
что общего может быть у "противных" чисел?

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

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


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

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


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

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


21/11/12
1870
Санкт-Петербург
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  След.

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



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

Сейчас этот форум просматривают: Majestic-12 [Bot]


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

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