√m≈√x+√y

[waxtep]

И довольно интересное распределение количества $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$ болтается в районе нуля, за счет чего ее (довольно гладко выглядящий в целом) график напоминает какой-то Бессель что ли

[juna]

Получил простой способ размножения нелучших, но хороших решений.
Если

$$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$$

[Andrey A]

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

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

[Avdij]

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

[waxtep]

Дополню табличку рекордсменов значениями для $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$ часов, так что для нахождения чисел (особенно рекордсменов) с большей глубиной дерева понадобятся какие-то идеи, более креативные, чем сплошной перебор

[juna]

Распишу подробнее содержание своего предыдущего поста.

$$\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 А целые числа тоже можно округлять, когда они слишком большие?

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

[Avdij]

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

[Ende]

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

[Andrey A]

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}.$ Таких красивых закономерностей тут много, но как это соотнести с величинами, ведь в условии арифметическая сумма. Или сумма среднего арифметического и геометрического — тоже как насмешка. Я посмотрю Ваш пост повнимательней, просто другим был занят. Скоро выложу.

[juna]

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.

[Andrey A]

Ну да, $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.$

[juna]

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

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

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

[Andrey A]

Кое-что удалось продвинуть, но всё это нуждается в проверке, подтверждении и т.д., тут без программных средств никак. Заранее благодарен. Возьмем пример $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$ итераций, иногда две А с маленькими простыми — плохо, особенно с тройкой. Просто не видит ее. На всякий случай сделал превентивный $\gcd (m,\#30) $.

[waxtep]

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}$, но почему пора остановиться? Может быть, дальше есть еще более симпатичное приближение

[Andrey A]

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

... но почему пора остановиться?

Да, всё тот же коварный вопрос. Не знаю почему, нет у нас надежного критерия простоты. А был бы, так и всё равно неясно почему именно сейчас )