2014 dxdy logo

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

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




Начать новую тему Ответить на тему На страницу Пред.  1, 2, 3, 4, 5, 6, 7, 8 ... 12  След.
 
 Re: √m≈√x+√y
Сообщение18.11.2022, 03:19 
Аватара пользователя


07/01/16
1426
Аязьма
И довольно интересное распределение количества $n$ чисел $m$, имеющих данное $G$: $$\begin{tabular}{c|c|c}
$G$&$n$&$\Delta n$\\
\hline
$1$&$31600$&$27204$\\
$2$&$4396$&$2844$\\
$3$&$1552$&$802$\\
$4$&$750$&$219$\\
$5$&$531$&$33$\\
$6$&$498$&$24$\\
$7$&$474$&$92$\\
$8$&$382$&$171$\\
$9$&$211$&$118$\\
$10$&$93$&$60$\\
$11$&$33$&$28$\\
$12$&$5$&$-$\\
\end{tabular}$$Интересное посерединке, где первая разность $\Delta n$ болтается в районе нуля, за счет чего ее (довольно гладко выглядящий в целом) график напоминает какой-то Бессель что ли

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


07/03/06
1898
Москва
Получил простой способ размножения нелучших, но хороших решений.
Если
$$xy=\left\lceil\frac{m}{2}\right\rceil^2-\left\lceil\frac{m}{2}\right\rceil, m\equiv 1\mod 2$$
где $xy$ - факторизация указанного числа $\left\lceil\frac{m}{2}\right\rceil^2-\left\lceil\frac{m}{2}\right\rceil$, то
$$\sqrt{m+x+y}\approx\sqrt{x}+\sqrt{y}$$

Пример:
$m=39, xy=20^2-20=2^2\cdot 5\cdot 19$
$$x=2\cdot 5=10, y=2\cdot 19=38\Rightarrow \sqrt{39+10+38}\approx\sqrt{10}+\sqrt{38}\Rightarrow \sqrt{87}\approx \sqrt{10}+\sqrt{38}$$
$$\sqrt{87}\approx 9.32737905$$
$$ \sqrt{10}+\sqrt{38}\approx 9.32669166$$

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


21/11/12
1870
Санкт-Петербург
Чуть назад. Полезные формулировки для тестирования $R$ на принадлежность указанной Вами последовательности:
Нечетное $R$ вида $4k+1$ принадлежит A003658, если оно свободно от квадратов $>1$.
Четные $R$ вида $16k+8$ и $16k+12$ принадлежат A003658, если они свободны от нечетных квадратов $>1$.
Другие не принадлежат.

Еще проще: последовательность A003658 можно получить из последовательности свободных от квадратов A005117, умножая на $4$ все члены вида $4k+2,\ 4k+3.$
Тоже в качестве наблюдения.

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


09/11/22

39
juna А целые числа тоже можно округлять, когда они слишком большие?

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


07/01/16
1426
Аязьма
Дополню табличку рекордсменов значениями для $G(m)\in\{13,14\}$:$$\begin{tabular}{c|c|l}
$G(m)$&$\min m$&$\text{symbolic}$\\
\hline
$1$&$5$&$1\ast1\equiv1^{\ast2}$\\
$2$&$11$&$1\ast5=1\ast1\ast1\equiv1^{\ast3}$\\
$3$&$19$&$1\ast11=1^{\ast4}$\\
$4$&$29$&$1\ast19=1^{\ast5}$\\
$5$&$101$&$5\ast61=1^{\ast2}\ast1^{\ast2}\ast1^{\ast2}\ast1^{\ast3}(\neq1^{\ast9})$\\
$6$&$151$&$5\ast101=1^{\ast2}\ast1^{\ast2}\ast1^{\ast2}\ast1^{\ast2}\ast1^{\ast3}$\\
$7$&$211$&$5\ast151=1^{\ast2}\ast1^{\ast2}\ast1^{\ast2}\ast1^{\ast2}\ast1^{\ast2}\ast1^{\ast3}$\\
$8$&$719$&$151\ast211$\\
$9$&$1487$&$\underline{138}\ast719$\\
$10$&$3121$&$211\ast1709=211\ast211\ast719 (\neq211^{\ast2}\ast719)$\\
$11$&$18869$&$1801\ast9011=1801\ast1801\ast\underline{2755}, 1801=101\ast101\ast101\ast151$\\
$12$&$45949$&$\underline{929}\ast33811=\underline{929}\ast\underline{929}\ast\underline{929}\ast\underline{5945}\ast\underline{979}\ast211$\\
$13$&$107071$&$9011\ast53959=9011\ast9011\ast9011\ast1801$\\
$14$&$376171$&$20011\ast222659=20011\ast20011\ast20011\ast\underline{35701},20011=\underline{2255}\ast\underline{2255}\ast\underline{387}\ast719$\\
\end{tabular}$$Толку от этого скорее всего немного, но уж очень диковинные последовательности получаются, в самом деле. Для $G=13$ мой древний нотик считал восемь минут, а для $G=14$ уже $19$ часов, так что для нахождения чисел (особенно рекордсменов) с большей глубиной дерева понадобятся какие-то идеи, более креативные, чем сплошной перебор

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


07/03/06
1898
Москва
Распишу подробнее содержание своего предыдущего поста.

$$\frac{m-x-y}{2}\approx\sqrt{xy}\Rightarrow \frac{m_1}{2}\approx\sqrt{xy}$$
Значит, если существует решение для $m_1$, то существует решение и для $m=m_1+x+y$

Пусть $\frac{m_1}{2}\approx\sqrt{xy}=\sqrt{U^2-R}$, где $U^2$ - ближайший больший к $\frac{m_1}{2}$ квадрат: $U=\left\lceil\frac{m_1}{2}\right\rceil$ при нечетном $m_1$, и $U=\frac{m_1}{2}$ при четном $m_1$.

$$\sqrt{U^2-R}\approx U-\cfrac{R}{2U}$$

$$m_1\equiv 1\mod 2\Rightarrow \frac{R}{2U}=\frac{1}{2}\Rightarrow R=U=\left\lceil\frac{m_1}{2}\right\rceil$$
$$m_1\equiv 0\mod 2\Rightarrow\frac{R}{2U}=0\Rightarrow R=0$$

$$xy=\left\lceil\frac{m_1}{2}\right\rceil^2-\left\lceil\frac{m_1}{2}\right\rceil, m_1\equiv 1\mod 2$$
$$xy=\left(\frac{m_1}{2}\right)^2, m_1\equiv 0\mod 2$$
Таким образом, если $x\cdot y$ какая-либо факторизация указанных чисел, то имеем:
$$\sqrt{m_1+x+y}\approx\sqrt{x}+\sqrt{y}$$

Зная оптимальные $x,y$ для заданного $m$, переберем различные возможные значения разности $m_1=m-x-y$. Также интересны такие $m$, для которых соответствующий им $m_1$ одинаков (своеобразные дружественные $m$).

Оказывается, не для любого $m_1$ можно подобрать такие $x,y$, что они будут давать оптимальное решение для $m=m_1+x+y$.
Вот начало последовательности для $m_1$, для которых мы не получим ни одного оптимального значения $x,y$.

Код:
[27, 75, 99, 147, 171, 225, 243, 245, 256, 261, 324, 325, 363, 384, 387, 400, 432, 448, 459, 477, 486, 495, 500, 507, 513, 525, 531, 539, 549, 567, 578, 603, 605, 621, 625, 640, 648, 676, 686, 711, 720, 722, 726, 735, 747, 756, 765, 768, 784, 800, 810, 819, 837, 864, 867, 875, 882, 891, 896, 918, 925, 927, 928, 931, 960, 963, 968, 972, 980, 981, 992, 999, 1000, 1014, 1017]


-- Вс ноя 20, 2022 14:37:21 --

Avdij в сообщении #1570422 писал(а):
juna А целые числа тоже можно округлять, когда они слишком большие?

Что значит округлять целые числа, и что значит "слишком большие"???

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


09/11/22

39
juna Это вопрос мировоззрения истинного математика. Если предположим, заходит простой, обычный парень в магазин, скажем он забыл карту дома, а в кармане минимум 10000 и так получилось, что молоденькая, голубоглазая, блонда, продавщица должна ему ну скажем 99 копеек, и ей не хватает одной копейки, что он сделает? 1. Вызовет полицию? 2. Поставит на счетчик? 3. Поймет и простит одну, целую, копейку? Скажем здесь, компьютер, программа не выдержала и тоже округлила. Вразумите, как правильно и Богоугодно должен поступить истинный математик, где же у него находятся разумные пределы? Каких размеров должно быть т.с. море цифр, чтобы т.с. округлить? Только математик может сказать, что мол в этом море не хватает капельки?

 Профиль  
                  
 
 Re: √m≈√x+√y
Сообщение20.11.2022, 17:37 
Админ форума


02/02/19
1991
 !  Avdij, бан на месяц за бессмысленную болтовню в математических темах. Следующий бан за то же нарушение будет постоянным.

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


21/11/12
1870
Санкт-Петербург
Avdij в сообщении #1570563 писал(а):
как правильно и Богоугодно должен поступить истинный математик...
Математики вечно не о том думают. Например, Гаусса (создателя теории сравнений) интересуют именно эти несчастные 99 копеек, а 10000 ему по барабану. Типа барышне — цветок, а землю раздайте крестьянам. Если серьезно, дробное до целого округлить можно, а целое до дробного — нельзя. Даже очень большое.
juna в сообщении #1570560 писал(а):
Значит, если существует решение для $m_1$, то существует решение и для $m=m_1+x+y$
Важный вопрос: существует ли решение для заданного $m$? Хотя бы одного из двух. Вообще говоря, если $\sqrt{m_1+x+y}\approx\sqrt{x}+\sqrt{y}$, и решение точности $R=1$ (а у Вас вроде бы оно и есть), то $m_1=\sqrt{4xy+1}.$ Таких красивых закономерностей тут много, но как это соотнести с величинами, ведь в условии арифметическая сумма. Или сумма среднего арифметического и геометрического — тоже как насмешка. Я посмотрю Ваш пост повнимательней, просто другим был занят. Скоро выложу.

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


07/03/06
1898
Москва
Andrey A в сообщении #1570577 писал(а):
Хотя бы одного из двух. Вообще говоря, если $\sqrt{m_1+x+y}\approx\sqrt{x}+\sqrt{y}$, и решение точности $R=1$ (а у Вас вроде бы оно и есть), то $m_1=\sqrt{4xy+1}.$


Нет, Вы можете брать любое $m_1$, это своеобразное решение задом наперед. Вы не отвечаете на вопрос, для заданного $m$, а классифицируете их по $m_1$.

Например, возьмем $m_1=209$, этого числа нет в указанной последовательности, значит разложение $ifactors(105^2-105)=2^3\cdot 3\cdot 5\cdot 7\cdot 13=xy$ дает хотя бы одну оптимальную пару $x,y$.

Так, $x=2\cdot 3\cdot 13=78, y=2^2\cdot 5\cdot 7=140, m=209+78+140=427$.
Действительно, $$\sqrt{427}\approx \sqrt{78}+\sqrt{140}, R=1$$
оптимально.
Andrey A в сообщении #1570577 писал(а):
Или сумма среднего арифметического и геометрического — тоже как насмешка


Да, на это тоже внимание обратил).

Да, я видимо ошибся. Эта схема не всегда работает. Например, для:
$$\sqrt{431}\approx\sqrt{19}+\sqrt{269}, R=5$$
$$m_1=431-19-269=143$$
но $ifactors(72^2-72)=2^3\cdot3^2\cdot71$ не содержит 19.

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


21/11/12
1870
Санкт-Петербург
Ну да, $105^2-105$ это и есть $(209^2-1)/4$. Если бы для заданного $m=427$ знать $m_1=209$, задача была бы решена. Всё равно что знать сумму $x+y$. Пропорции $x/y$ или разности $x-y$ тоже было бы достаточно. Мы этого ничего не знаем, но эффективный алгоритм поиска одного из этих параметров был бы решением. Кстати, точка $m/4$ почти равноудалена от ср. геометрического $\sqrt{xy}$ и ср. арифметического $(x+y)/2$. Найти расстояние до нее тоже было бы достаточно, правда там не все числа целые.

P.S.
$19$ содержит $(143^2-5)/4.$

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


07/03/06
1898
Москва
Andrey A в сообщении #1570594 писал(а):
$19$ содержит $(143^2-5)/4.$

Таки $(72^2-72)-1=72^2-73=19\cdot 269$ - вру немного.

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


21/11/12
1870
Санкт-Петербург
Кое-что удалось продвинуть, но всё это нуждается в проверке, подтверждении и т.д., тут без программных средств никак. Заранее благодарен. Возьмем пример $m=1957.$ Вычислим максимальное значение $x_{\max}=\left \lfloor \dfrac {(\sqrt{1957}-1)^2}{4} \right \rfloor =467$ и посмотрим, как ведут себя игреки при равномерном убывании $x.$ Во второй колонке беру $y_n$ c двумя десятичными знаками дробной части (погрешности), а в третьей для наглядности — величину обратную погрешности, округленную до целого.

$$\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$ на единицу $y$ увеличивается тоже почти на единицу. Чуть более того. Но это "чуть" тоже почти линейно, имеется в виду приращение дробной части — оно мало́ само по себе и когда "переваливается" через целое, с большой вероятностью получаем "скачек качества" аппроксимации. Целая часть $y$ при этом увеличивается на $2.$ Уже упоминал — такие "пилообразные" процессы. Первый зубец в данном случае составил $16$ знаков, второй — $10$ и далее на убывание, но не строгое. Если бы знать величину зубцов, стало бы возможным вместо $29$ опытов произвести всего $3$, тем более, что с ростом $m$ растут и сами зубцы. Оказывается, эта задача решается хорошо, то есть полностью. И, в общем, не сложно. Обозначим буквой $h$ количество знаков $1$-го зубца. После первого опыта нами получены $x_1,y_1.$ С каждым новым опытом $x$ уменьшается на $1$, $y$ увеличивается на $1$. Но в конце зубца $x$ уменьшается на $h$, а $y$ увеличивается на $h+1$. Для описания ситуации этого вполне достаточно. Простое уравнение: $\sqrt{m}-\sqrt{x_1-h}\approx \sqrt{y_1+h+1}.$ Решение такое: $$h=\left \lceil \dfrac{x_1-y_1-1+\sqrt{m(2x_1+2y_1+2-m)}}{2} \right \rceil.$$ Скобки "потолок" добыты эмпирически, у меня сомнения не вызывают, но доказательства приветствуются. В нашем случае $h=\left \lceil \dfrac{-46+\sqrt{1957 \cdot 3}}{2} \right \rceil=16.$ Теперь можем получить новый $x=467-16=451$, новый $y=\left \lfloor  (\sqrt{1957}-\sqrt{451})^2  \right \rfloor=529$, вычислить новый $h$ и далее по кругу. Таким образом на определенном этапе получаем возможность эффективно отсеять заведомо лишние аппроксимации, но далее процедура превращается в обычный перебор и теряет смысл. Визуально — зубцы мельчают, пила застревает. Задачу $(1)$ таким способом не решить, но всё-таки... новая методика. Может, получится обобщить? Вот соорудил из этого новый алгоритм факторизации (таблица Excel). Он прилично работает с произведением двух простых, но странно. Иногда запрашивает $10000$ итераций, иногда две :shock: А с маленькими простыми — плохо, особенно с тройкой. Просто не видит ее. На всякий случай сделал превентивный $\gcd (m,\#30) $.

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


07/01/16
1426
Аязьма
Andrey A в сообщении #1570635 писал(а):
Он прилично работает с произведением двух простых, но странно. Иногда запрашивает $10000$ итераций, иногда две
Ага, с простыми тоже по-разному: $683$ - $8$ итераций, $3121$ - уже $308$, довольно быстро сваливается сначала в почти сплошной, а затем и в сплошной перебор. У меня была похожая идея с перескоком через целое, но почему-то забросил ее, посмотрев пару примеров.
Andrey A в сообщении #1570635 писал(а):
Решение такое: $$h=\left \lceil \dfrac{x_1-y_1-1+\sqrt{m(2x_1+2y_1+2-m)}}{2} \right \rceil.$$ Скобки "потолок" добыты эмпирически, у меня сомнения не вызывают, но доказательства приветствуются.
Факт, мы же приходим к квадратному по $h$ неравенству$$h^2+(y-x+1)h+\left(\frac{m-x-y-1}2\right)^2-x(y+1)\geqslant0$$откуда потолок (большего из корней) получается натуральным образом.
Еще такой коварный вопрос конечно возникает: вот, мы пришли за $8$ итераций к $\sqrt{683}\approx\sqrt{121}+\sqrt{229}$, но почему пора остановиться? Может быть, дальше есть еще более симпатичное приближение

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


21/11/12
1870
Санкт-Петербург
waxtep в сообщении #1570642 писал(а):
... но почему пора остановиться?
Да, всё тот же коварный вопрос. Не знаю почему, нет у нас надежного критерия простоты. А был бы, так и всё равно неясно почему именно сейчас )

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

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



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

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


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

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