√m≈√x+√y

[waxtep]

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

Она такая э... как клюква в сахаре — пока коробка не опустеет.

А, мое высказывание касается исключительно моей зашоренности, - я как-то всерьез считал, что здесь два независимых параметра.
А такое наблюдение принесет ли какую-нибудь пользу? - по всей видимости, оптимальное $x$ соответствует случаю, когда

$$r=4mx-\left\lceil{2\sqrt{mx}}\right\rceil^2$$

максимально (минимально по модулю), либо второе по величине. Или это просто переформулировка, я честно говоря не соображу. По крайней мере, это выполняется и для "приличных", и для "противных" чисел:
- $77, 79, 85, 87, 91, 93, 95, 103$ - $r$ максимально среди всех возможных;
- $83, 89$ - $r$ второе по величине.

[Andrey A]

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

... касается исключительно моей зашоренности

Это у Вас клюква в коробке кончается ) $4mx,4my,4xy$ — всё квадраты без маленького квадратичного вычета, он же $(x-y)^2 \mod m$. Как-то его надо обозвать, пусть пока будет $R.$ Для составных чисел $R=1$, для простых $R \equiv 0,1 \mod 4$, причем не квадрат. А вот $m$ брать по $\mod 4$ не очень понимаю зачем. Вы ведь хорошо понимаете, что задача равносильная факторизации не может решаться такими косметическими мерами. Впрочем, я тут рассуждаю, будто сам ее решил, а это не так. Но уверен — надо искать алгоритмическое решение и математические к тому основания. В идеале хорошо бы научится сортировать арифметические суммы радикалов в малой окрестности $m.$ Вот только как объяснить ему разницу между арифметическими и алгебраическими суммами? Это должен быть такой надежный допотопно-античный алгоритм.

[juna]

$$y=m+x-2\sqrt{m\cdot x}$$

Отсюда видно, что задача сводится к поиску для заданного $m$ такого $1\leq x\leq\left(\lfloor\sqrt{m}\rfloor\right)^2-1$, чтобы $\sqrt{mx}$ было близко к целому числу снизу или сверху. Это дает простой перебор. Вот лучшие нижние и верхние ограничения для $m=4\ldots 100$.
4 [1,1] [2,1]
5 [3,0] [2,1]
6 [2,1] [3,1]
7 [2,1] [3,1]
8 [2,2] [1,4]
9 [1,4] [3,2]
10 [3,2] [5,1]
11 [5,1] [6,1]
12 [3,3] [7,1]
13 [6,1] [7,1]
14 [4,3] [8,1]
15 [6,2] [5,3]
16 [1,9] [7,2]
17 [15,0] [10,1]
18 [2,8] [11,1]
19 [11,1] [7,3]
20 [5,5] [13,1]
21 [10,2] [13,1]
22 [6,5] [14,1]
23 [14,1] [8,4]
24 [6,6] [13,2]
25 [1,16] [13,2]
26 [7,6] [17,1]
27 [3,12] [18,1]
28 [7,7] [11,4]
29 [19,1] [10,5]
30 [20,1] [17,2]
31 [11,5] [21,1]
32 [2,18] [22,1]
33 [14,4] [19,2]
34 [9,8] [13,5]
35 [12,6] [18,3]
36 [1,25] [26,1]
37 [35,0] [19,3]
38 [10,9] [27,1]
39 [18,4] [13,7]
40 [10,10] [29,1]
41 [29,1] [25,2]
42 [30,1] [26,2]
43 [23,3] [31,1]
44 [11,11] [32,1]
45 [5,20] [33,1]
46 [12,11] [29,2]
47 [34,1] [30,2]
48 [3,27] [17,8]
49 [1,36] [19,7]
50 [2,32] [37,1]
51 [22,6] [38,1]
52 [13,13] [39,1]
53 [39,1] [17,10]
54 [6,24] [19,9]
55 [36,2] [27,5]
56 [14,14] [37,2]
57 [26,6] [43,1]
58 [15,14] [29,5]
59 [19,11] [45,1]
60 [15,15] [46,1]
61 [31,5] [37,3]
62 [16,15] [42,2]
63 [7,28] [43,2]
64 [1,49] [22,11]
65 [24,10] [50,1]
66 [45,2] [51,1]
67 [63,0] [21,13]
68 [17,17] [47,2]
69 [30,8] [37,5]
70 [44,3] [55,1]
71 [55,1] [22,14]
72 [2,50] [46,3]
73 [23,14] [57,1]
74 [19,18] [25,13]
75 [3,48] [59,1]
76 [19,19] [49,3]
77 [40,6] [46,4]
78 [55,2] [26,14]
79 [31,11] [39,7]
80 [5,45] [57,2]
81 [1,64] [43,6]
82 [21,20] [65,1]
83 [80,0] [66,1]
84 [21,21] [67,1]
85 [30,14] [61,2]
86 [22,21] [53,4]
87 [38,10] [63,2]
88 [22,22] [43,8]
89 [71,1] [34,13]
90 [10,40] [47,7]
91 [66,2] [73,1]
92 [23,23] [74,1]
93 [42,10] [49,7]
94 [24,23] [76,1]
95 [60,4] [48,8]
96 [6,54] [61,4]
97 [71,2] [39,13]
98 [2,72] [38,14]
99 [11,44] [73,2]
100 [1,81] [74,2]

В связи с задачей возник еще один вопрос. Числа $1, \sqrt{2}, \sqrt{3}$ являются своеобразными первичными.
Любой корень можно попытаться ограничить суммами этих корней.
Например, имеем:

$$\sqrt{84}+\sqrt{5}<\sqrt{130}<\sqrt{53}+\sqrt{17}$$

а вот лучшее ограничение из указанных корней:

$$1+6\sqrt{3}<\sqrt{130}<10+\sqrt{2}$$

[Andrey A]

juna в сообщении #1569424 писал(а):

... чтобы $\sqrt{mx}$ было близко к целому числу снизу или сверху.

Лучше бы так: ... чтобы $\sqrt{4mx}$ было близко к целому числу снизу. В условии говорится о нижнем приближении $m$. Если потребуются другие, можно обобщить и на верхние, но пока оно скорее складывается в отдельную задачу. Спасибо за список, помогает в размышлениях. Четверка под радикалом — чтобы сохранить целочисленность в рассуждениях. Ну, и, если исходить из различных свойств $m$ помимо величины, можно расширить формулу

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

$$x,y=\dfrac{\left ( m \pm v \right )^2-1}{4m}.$$

на простые: $x,y=\dfrac{\left ( m \pm v \right )^2-R}{4m}$, где $ v^2 \equiv R \mod m$, причем параметры $v,R$ различной четности, $R \equiv 0,1 \mod 4$ и не является целым квадратом. На обобщение это пока не тянет, поскольку качество приближения находится в обратной зависимости от величин $v,R$, а от какой больше и при каких обстоятельствах — вопрос. Есть у меня подозрение, что для достаточно большого простого вида $10k \pm 1$ $R=5$, но тут могу ошибаться. Для $m=43$ источником решения служат уже сравнительно большие $20^2 \equiv 13 \mod 43.$
Вопрос сортировки арифметических сумм радикалов необычайно сложен. По минимуму, исходя из величин параметров, важно ответить на вопрос существует ли на интервале ( $\sqrt{a}+\sqrt{b},\ \sqrt{m}$ ) иррациональность вида $\sqrt{x}+\sqrt{y}$ (с прицелом на среднее арифметическое $(\sqrt{a}+\sqrt{b}+\sqrt{m}\ )/2$ ) ? И остается только вопрос каковы $x,y$ ) По поводу "первичных" любопытно, но чем это может нам помочь?

[juna]

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

По поводу "первичных" любопытно, но чем это может нам помочь?

Просто здесь возможны своеобразные рассуждения по цепочке. Ведь в виду симметрии к целому должно стремиться не только $\sqrt{4mx}$, но и $\sqrt{4my}, \sqrt{4xy}$. Значит мы можем подменять $m,x,y$ спускаясь вниз, пока не придем к точному равенству, или первичному корню.

Например, $\sqrt{179}\approx\sqrt{61}+\sqrt{31}$

значит $\sqrt{61}\approx\sqrt{31}+\sqrt{y}$, откуда легко находим $y=5$,

значит $\sqrt{31}\approx \sqrt{5}+\sqrt{y}\Rightarrow y=11$,

значит $\sqrt{11}\approx\sqrt{5}+\sqrt{y}\Rightarrow y=1$

Видимо, также можно подниматься и вверх.

[Andrey A]

juna в сообщении #1569679 писал(а):

Видимо, также можно подниматься и вверх.

Вы тут прочувствовали следствие (одно из). Действительно, $\dfrac{\sqrt{179}}{\sqrt{31}} \approx 2$ означает, что можем не менее двух раз вычитать меньшее из большего, оставаясь в рамках положительных чисел: $\sqrt{179}-\sqrt{31} \approx \sqrt{61},\ \sqrt{61}-\sqrt{31} \approx \sqrt{5}.$ $\dfrac{\sqrt{31}}{\sqrt{5}} \approx 2 \rightarrow \sqrt{31}-\sqrt{5} \approx \sqrt{11},\ \sqrt{11}-\sqrt{5} \approx \sqrt{1}.$ И даже $\dfrac{\sqrt{5}}{\sqrt{1}} \approx 2.$ Двойка тут, кажется, не случайна. Конечно, такой процесс можно продолжить и вверх. Решение задачи оно не приближает, поскольку качество аппроксимации по $R$ ( в данном случае $R=5$ ) — величина постоянная, но сами по себе последовательности любопытны необычайно. Достаточно заметить, что все члены кроме начальных $\sqrt{1},\sqrt{5}$ — кв. корни из простых вида $10k \pm 1.$ Не сомневаюсь, что появятся и дальше, но вот каковы закономерности в номерах их появления — вопрос интересный. Благодаря отмеченной Вами тройственности ($\sqrt{4mx},\sqrt{4my},\sqrt{4xy}$ — все квадраты без $R$) на каждом шаге построения такой последовательности имеем выбор из $2$-х типов операций: $\sqrt{p_{n+1}} \approx \sqrt{x}+\sqrt{m}$ и $\sqrt{p_{n+1}} \approx \sqrt{y}+\sqrt{m},$ а самих последовательностей с фиксированной парой начальных членов имеем двоичное дерево. Надо бы выбрать форму записи, предлагаю так: первые два члена $p_{n-1},p_0$ записываются в радикалах (порядок имеет значение), а далее по принципу образования подходящих дробей: $p_{n+1} \approx u_{n+1}p_{n}+p_{n-1}$, где под $u_{n+1}p_{n}$, строго говоря, понимается не умножение, а $u_{n+1}$ операций $1$-го типа. А нестрого (для хороших приближений и небольших знаков) — так и буквально. Ваша последовательность записывается так:

$$\left ( \sqrt{1},\sqrt{5} \right ),3,1.$$

Читается так:

$$\sqrt{5}+\sqrt{1} \approx \sqrt{11};\sqrt{5}+\sqrt{11} \approx \sqrt{31};\sqrt{5}+\sqrt{31} \approx \sqrt{61};\sqrt{61}+\sqrt{31} \approx \sqrt{179}.$$

Для начальных членов последовательности диофантовых троек ($R=1$) годится любая пара множителей числа вида $k(k+1),$ например $\left ( \sqrt{2},\sqrt{3} \right ),3,1$ можно прочесть как $\sqrt{2};\sqrt{3}; 3 \cdot \sqrt{3}+\sqrt{2} \approx \sqrt{44};1 \cdot \sqrt{44}+\sqrt{3} \approx \sqrt{70}.$

[waxtep]

Интересно, можно ли это превратить в рабочий алгоритм? Мы как бы ставим в соответствие числу $\sqrt{m}$ комбинацию $F_n\cdot r_1+F_{n-1}\cdot r_0$, где $F_n$ - числа Фибоначчи, $r_0\in\{1,\sqrt2,\sqrt3\}$ - один из "примитивных" корней, а $r_1$ предстоит угадать. Для больших $m$ максимальное $n\sim\ln{m}$, и при условии, что $r_1$ угадано (или перебрано из небольшого количества), мы получим желаемый быстрый алгоритм. Для небольших $m$ видимо работает $r_1^2=\left\lceil\left(\frac{\sqrt{m}-F_{n-1}r_0}{F_n}\right)^2\right\rceil$, но вообще надо гонять-проверять, хочу попробовать на досуге. Для приведенного примера $\sqrt{179}$ оптимальный результат дает комбинация $5r_1+3$ при $r_1=5$, но можно же просто не задумываясь прочесать все $12$ возможных в данном случае комбинаций, от $r_1+\sqrt3$ до $8r_1+5$, для больших $m$ их логарифмически малое количество

[Andrey A]

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

... надо гонять-проверять, хочу попробовать на досуге.

Заодно дайте пожалуйста подробный пример. А то не очень пока понятно.

[waxtep]

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

Заодно дайте пожалуйста подробный пример. А то не очень пока понятно.

Нет, это так в лоб не работает, понял в процессе запрограммирования. У меня была иллюзия, что "поднимаясь вверх" для $179$ мы двигаемся так: $(1,5)\rightarrow(5,11)\rightarrow(11,31)\rightarrow\ldots$ - а это же не так, точки $\sqrt{11}+\sqrt{31}$ на пути вверх нет (отсюда мечты о Фибоначчи, что всегда $r_n\approx r_{n-1}+r_{n-2}$), есть $\sqrt{5}+\sqrt{31}$; так что это мимо

[Andrey A]

Ладно. Случается.

[waxtep]

juna в сообщении #1569424 писал(а):

Вот лучшие нижние и верхние ограничения для $m=4\ldots 100$.

Тут, видимо, некоторое количество неточностей: несколько записей с $x=0$, помимо этого у меня не сошлись наилучшие нижние ограничения для $m\in\{13,27,30,41,42,47,53,66,70,78,89,98\}$. Например, $\sqrt{47}\approx\sqrt{3}+\sqrt{26}$ все же чуть лучше, чем $1+\sqrt{34}$

[waxtep]

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

не сошлись наилучшие нижние ограничения для $m\in\{13,27,30,41,42,47,53,66,70,78,89,98\}$.

$27,98$ в этом списке конечно лишние, они же точно представимы. Не сразу заметил, что написанная в лоб программка иногда для натурального $x$ выдает сюрприз в виде $\lfloor\sqrt{x^2}\rfloor=x-1$ за счет погрешности вычисления

[Andrey A]

Да. А четные все свободны от квадратов, там по низу тоже просто:

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

$$\sqrt{4d+2} \approx \sqrt{d}+\sqrt{d+1}.$$

Остаются нечетные кроме $27$, они простые.

-- 12.11.2022, 17:35 --

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

$$\sqrt{m} \approx \sqrt{x}+\sqrt{y}\ \ (1)$$

Возведем почленно в квадрат и разделим пополам: $m/2 \approx (x+y)/2+\sqrt{xy}.$ Такой школьный взгляд: решить $(1)$ значит наилучшим образом представить $m/2$ суммой среднего арифметического и геометрического. Соответствующие разности для нечетного $m$ — относительно малые числа с дробной частью близкой к $0,5.$

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

(последовательности) Надо бы выбрать форму записи, предлагаю так:

Что-то в этом предложении как раз и не так. Аналогия с цепными дробями вполне удачна, но тогда последовательность радикалов должна соответствовать простой логике алгоритма Евклида. И простыми вычитаниями, начиная с $\sqrt{179}-\sqrt{61}$ получаем дробь $1,1,2,2.$ Начальные члены, видимо, нужно заменить радикалами, но в основе хочется видеть именно ее. Это надежно. А у меня там выстреливает почему-то $3,1$. Как-то правило нужно формулировать иначе.

[waxtep]

У меня прогресс минимальный, написал аккуратную программку, обрабатывающую несвободные от квадратов и четные числа отдельно. Она конечно для огромных $m$ не годится, использует факторизацию для детектирования этих случаев и выдачи стандартизованного ответа; затем для оставшегося случая нечетного свободного от квадратов запускается перебор:

fra_d(m,x,y)={return(sqrt(m)-sqrt(x)-sqrt(y))};

fra_y(m,x)={return(m+x-ceil(sqrt(4*m*x)))};

fra_base(m)={mf=factor(m); np=matsize(mf)[1]; p=vector(np,i,mf[i,1]); ed=vector(np,i,floor(mf[i,2]/2)); msq=factorback(p,ed); msqf=m/msq^2;
if(msq>1, return([0,msqf,msqf*(msq-1)^2]));
if(mf[1,1]==2, return([fra_d(m,floor(m/4),ceil(m/4)),floor(m/4),ceil(m/4)])); 
sm=floor(m/4); x=vector(sm,x,x); y=vector(sm,x,fra_y(m,x)); d=vector(sm,x,fra_d(m,x,y[x])); dxy=vecsort(matconcat([d;x;y])); return([dxy[1,1],dxy[2,1],dxy[3,1]])};

fra_base_arr(m1,m2)={for(m=m1,m2,print([m,fra_base(m)]))};

Для $m=ka^2$, для определенности, выдается представление с наименьшим $x: \sqrt{ka^2}=\sqrt{k}+\sqrt{k(a-1)^2}$. При размере стека примерно в 1 Гб ее хватает для чисел где-то до $9\cdot10^6$:

(21:35) gp > fra_base(8876543)
  ***   Warning: increasing stack size to 128000000.
  *** sqrt: Warning: increasing stack size to 256000000.
  ***   Warning: increasing stack size to 512000000.
  *** matconcat: Warning: increasing stack size to 1024000000.
%16 = [6.6565529074175425346985226702409235731 E-11, 52524, 7563444]

[Andrey A]

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

... При размере стека примерно в 1 Гб ее хватает для чисел где-то до $9\cdot10^6$

Вам не кажется, что тут телега впереди лошади немножко заехала? Четные откинуть не проблема, а нечетное кратное квадрату $>1$ — как раз хороший тест для итогового алгоритма, если он отыщется. Ведь это частный случай $R=0.$ Если программа составлена корректно, она найдет точное решение $(1)$, и получим маленький квадрат $(x-y)^2 \equiv 0 \mod m$, т.е. кратный $m.$ При том, что $\left | x-y \right |<m$ — это равносильно факторизации. Из $\sqrt{12}+\sqrt{27}=\sqrt{75}$, к примеру, следует $75 \mid 15^2.$

P.S. И проверить заодно $\gcd (x,y)$, которое, кстати, вовсе не обязано быть свободным от квадратов.