2014 dxdy logo

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

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




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


07/01/16
1426
Аязьма
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$ второе по величине.

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


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

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


07/03/06
1898
Москва
$$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}$$

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


21/11/12
1870
Санкт-Петербург
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$ ) По поводу "первичных" любопытно, но чем это может нам помочь?

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


07/03/06
1898
Москва
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$

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

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


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

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


07/01/16
1426
Аязьма
Интересно, можно ли это превратить в рабочий алгоритм? Мы как бы ставим в соответствие числу $\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$ их логарифмически малое количество

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


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

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


07/01/16
1426
Аязьма
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}$; так что это мимо

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


21/11/12
1870
Санкт-Петербург
Ладно. Случается.

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


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

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


07/01/16
1426
Аязьма
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$ за счет погрешности вычисления

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


21/11/12
1870
Санкт-Петербург
Да. А четные все свободны от квадратов, там по низу тоже просто:
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$. Как-то правило нужно формулировать иначе.

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


07/01/16
1426
Аязьма
У меня прогресс минимальный, написал аккуратную программку, обрабатывающую несвободные от квадратов и четные числа отдельно. Она конечно для огромных $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]

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


21/11/12
1870
Санкт-Петербург
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)$, которое, кстати, вовсе не обязано быть свободным от квадратов.

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

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



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

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


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

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