найти корешок по двум элементам цепной дроби

[maxal]

Для двух заданных целых положительных чисел $u,v$, найдите наименьшее целое число $m>0$ такое, что в разложении $\sqrt{m}$ в цепную дробь

$$\sqrt{m} = [a_0;a_1,a_2,a_3,\dots]$$

выполняются равенства $a_1=u$ и $a_2=v$.

[Dendr]

Явная формула так сразу не получилась. Зато алгоритм.

Представим число в виде $m=n^2+d, 0<d\le2n$, тогда можно начать расписывать цепную дробь из его корня, и ввести такое число: $r=2n-ud, 0\le r<d$.
Если продолжить вычисление дроби дальше, получим условие:
$\frac{d}{v+1}-\frac{v+1}{u(v+1)+1}<r\le\frac{d}{v}-\frac{v}{uv+1}$, что эквивалентно
$rv+\frac{v^2}{uv+1}\le d<r(v+1)+\frac{(v+1)^2}{u(v+1)+1}$

Тогда сам алгоритм выглядит следующим образом: при заданных $u, v$ рассматриваем пары $d, r<d$ такие, что $ud+r$ - четно, тогда $n$ (целая часть корня из n) - половина этого выражения. Перебор происходит по возрастанию $d$, вторым уровнем - $r$. Первая пара, удовлетворяющая всем условиям и определяет искомое число.

Например, для $u=5, v=4$. Нечетность $u$ означает, что перебираем пары одинаковой четности: (2,0), (3,1), (4,0), (4,2), (5,1), (5,3)... Поочередно подставляя их в неравенства, получаем, что первым годится (5,1). Тогда $n=13$, $m=174$.

Алгоритм можно сократить, заметив, что следует учесть, что $d>rv+\frac{v^2}{uv+1}>r$, так что границы, в которых может находиться $d$, перемещаются по числовой оси в большую сторону с ростом подставляемого $r$, причем при больших $v$ - очень быстро.

Итак, алгоритм таков:
1. Перебираем $r$, начиная с нуля.
2. Выбираем, так же по возрастанию, целые d, удовлетворяющие $rv+\frac{v^2}{uv+1}\le d<r(v+1)+\frac{(v+1)^2}{u(v+1)+1}$, и переходим к следующей проверке.
3. Если $ud+r=2n$ - четно, то это наш случай, и $m=n^2+d$.

В том же примере, получаем, что для $r=0$ решается неравенстно $0.76<d<0.96$, то есть без целых решений. При $r=1$ - $4.76<d<5.96$, у которого одно решение - $d=5$, а поскольку $5\cdot5+1=26$ - четно, и $m=13^2+5=174$

[maxal]

Dendr, похоже, ваш алгоритм экспоненциален (от длины $u$ и $v$ в битах). Условно говоря, если я вам дам значения $u$ и $v$ около $2^{32}$, то ответа можно и не дождаться.
Имейте в виду, что минимальное значение $m$ в этой задаче не меньше чем $\frac{\max(u,v)^2}4$.

[mihaild]

Если я не обсчитался, задача эквивалентна нахождению минимального $a_0$ такого что между $\left(\frac{a_0 a_2}{a_1a_2+1}\right)^2$ и $\left(\frac{a_0(a_2 + 1)}{a_1a_2+a_1+1}\right)^2$ есть целое число (а $m$ будет этим самым числом). Не то чтобы это было чем-то глубокомысленным или полезным... Ну кроме верхней оценки $m = O(u^2 + v^2)$.

[Null]

mihaild в сообщении #1488215 писал(а):

$\left(\frac{a_0 a_2}{a_1a_2+1}\right)^2$ и $\left(\frac{a_0(a_2 + 1)}{a_1a_2+a_1+1}\right)^2$

Скорее $\left(a_0+\frac{ a_2}{a_1a_2+1}\right)^2$ и $\left(a_0+\frac{(a_2 + 1)}{a_1a_2+a_1+1}\right)^2$

[Dendr]

maxal в сообщении #1488214 писал(а):

алгоритм экспоненциален

Есть такое, детерминированность серьезно хромает. Хотя, на поверку, $r$ больше двух брать уже не нужно, так что перебор не такой уж и высокий. Но если угадать, что по модулю чего брать, то выйдет уже однозначно:

Обозначим $w=v\bmod2u, p=\left\lfloor v/2u\right\rfloor$.
1а. Если $w=0$ или $w=u$ - четное число, берем $d=v/u, r=0$.
1б. Если $w=u$ - нечетное, $d=v+u/v+1, r=1$.

2. Если $w\in[1, u-1]$:
а. при четном $u$: $d=2v+2p+1, r=2$
б. при нечетном $u$, четном $v$: $d=v+1+2p, r=1$
в. при нечетных $u, v$: $d=2v+2p+2, r=2$

3. Если $w\in[u+1, 2u-1]$:
а. при нечетных $u, v$: $d=v+2p+2, r=1$
б. в остальных случаях: $d=2v+2p+2, r=2$

Тогда $m=(\frac{ud+r}{2})^2+d$

Минимальность показывается из скрупулезного выписывания всех соотношений при разных $w$ и сравнения четности компонентов (если по-честному, сейчас очень неохота выписывать всю простыню в теховских тегах, а рукописные выкладки - сплошные каракули и черкания...).
В том же примере $u=5, v=4$ получаем $p=0, w=4$ - это случай 2б, так что $d=5, r=1$, что совпадает с решением выше - $m=174$.

Загнал в Эксель, для не очень больших чисел минимальность $m$ удовлетворяется.

[Andrey A]

Совсем без перебора тут вряд ли получится. Разве что частный случай $u \mid v$ при четном $v.$ Tогда $m=\left ( \dfrac{v}{2} \right )^2+\dfrac{v}{u}$ возможно наименьшее, но кто знает... Тем не менее, получить некоторое целое с нужными знаками в разложении радикала — не проблема.

(Об этом было тут)

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

... возникает любопытный вопрос: для всякого ли палиндрома $a_1,a_2,…,a_2,a_1$ разрешимо уравнение в целых числах

$$(x,a_1,a_2,…,a_2,a_1,x,0)=\sqrt{y}$$

Или в виде задачи: всякий ли палиндром может быть приближением дробной части целого радикала с точностью до периода?
Две последние подх. дроби палиндрома имеют вид $\frac{B}{C};\frac{A}{B}$, причем $B^2\mp 1=AC.$ Разложению дробной части соответствуют обратные дроби $\frac{C}{B};\frac{B}{A}.$ Прибавим к ним целую часть $x:\ \frac{Bx+C}{B};\frac{Ax+B}{A}.$ Тогда тройка дробей перед нулем принимает вид $\frac{Bx+C}{B};\frac{Ax+B}{A};\frac{x(Ax+B)+Bx+C}{Ax+B}.$ В случае целого радикала числитель последней дроби должен делиться на знаменатель предпоследней: $\frac{Ax^2+2Bx+C}{A}=y=x^2+\frac{2Bx+C}{A}$ Остается выяснить, при каких условях последняя дробь оказывается сократимой. Из $ \left\{\begin{matrix}2Bx\equiv & -C \\ B^2\equiv & \pm 1 \end{matrix}\right. \mod A$ и взаимной простоты $A,B$ получаем ключевое выражение

$$2x\equiv \mp BC \mod A,$$

которое нужно рассмотреть поподробнее. Если $B,C$ – нечетные, $A$ вынужденно четное, и такое сравнение неразрешимо. Дробь $\frac{11}{24}$, к примеру, не может быть приближением дробной части целого радикала т.к. оба знаменателя последней пары $\frac{11}{5};\frac{24}{11}=2,5,2$ – нечетные. Если же одно из чисел $B,C$ – четное, то

$$\left\{\begin{matrix} x \equiv & (-1)^n\cdot BC/2 \mod A & \text {в случае нечетного}\ A\\ x \equiv & (-1)^n\cdot BC/2 \mod A/2 & \text {в случае четного}\ A \end{matrix}\right.$$

Где $n$ – количество знаков палиндрома.

Пример: $2,6,2=\frac{2}{1};\frac{13}{6};\frac{28}{13}.\ -39 \mod 14=3,17,…$ Отсюда $(3+\frac{13}{28})^2 \approx 12;\ (17+\frac{13}{28})^2\approx 305;…$
$\sqrt{12}=(3,2,6,2,3,0);\ \sqrt{305}=(17,2,6,2,17,0);\ \sqrt{990}=(31,2,6,2,31,0)... $… и т.д. Произведение соседних членов последовательности $y_k$ – число вида $t^2\pm 1$ или $t(t+1).$ Рекуррентное правило: $y_{k+1}=2(y_k+A^2)-y_{k-1}$ или $y_{k+1}=2(y_k+(A/2)^2)-y_{k-1}$ в зависимости от четности $A.$ Подобные «арифметические прогрессии» из радикалов несовершенны: разность прогрессии, не является целым числом, но стремится к целому числу.

Обозначим такое целое $m_1.$ Если существует меньшее $m_2$ с теми же знаками в разложении, то дробные части их примерно равны, и существует целое $x$ такое, что $\sqrt{m_1}-\sqrt{m_2} \approx x,$ или так: $\sqrt{m_1}-x \approx \sqrt{m_2}.$ Возводя обе части в квадрат, получаем $m_1-2\sqrt{m_1}x+x^2 \approx m_2$, или $m_1-m_2+x^2 \approx 2\sqrt{m_1}x$, или так: $(m_1-m_2+x^2)^2-4m_1x^2 \approx 1.$ Обозначим $m_1-m_2+x^2=p,\ x=q.$ Тогда из разложения

$$\sqrt{4m_1} \approx \dfrac{p}{q}$$

следует $m_1+q^2-p=m_2.$ Из каждой подходящей дроби разложения $\sqrt{4m_1}$ имеем претендента на звание "наименьшее", и тут без перебора не обойтись. Практика показывает, что из дробей полупериода можно получить несколько $m_i$ с нужными знаками (если таковые имеются), но высокая точность тут как раз не нужна.

Думаю, оптимальный алгоритм таков:

1) Получаем $m_1$ описанным выше способом из дробей $u,v,u$ или $u,v,v,u.$
2) Раскладываем $\sqrt{4m_1}$ в непрерывную дробь до первого $m$, отвечающего условиям задачи. Если такого не находится, считаем $m_1$ решением. Тут слабое место, но контрпримера пока не нашел.
3) Если на предыдущем этапе нашлось меньшее $m$, назначаем его $m_2$ и повторяем процедуру 2). Далее по кругу.

Такой алгоритм можно продолжить на любое фиксированное количество начальных знаков. Позже приведу пример.

[Andrey A]

Пример $u=7,v=11.$

Продолжим дробь до палиндрома: $7,11,7=\dfrac{7}{1},\dfrac{78}{11},\dfrac{553}{78}.$
Два последних знаменателя содержат четное число, значит существует соотв. целый радикал с целой частью $-\dfrac{11\cdot 78}{2} \mod 553=124.$
$\left ( 124+\dfrac{78}{553} \right )^2 \approx 15411.$ Проверяем: $\sqrt{15411}=124,7,11,7,...$

Назначаем $m_1=15411$ и далее $\sqrt{4 \cdot 15411}=248,3,1,1,5,...=\dfrac{248}{1},\dfrac{745}{3},$ $\dfrac{993}{4},\dfrac{1738}{7},\dfrac{9683}{39},...$ Из пятой дроби получаем $m_2=15411+39^2-9683=7249,$ удовлетворяющее заявленным требованиям: $\sqrt{7249}=85,7,11,...$
Далее $\sqrt{4 \cdot 7249}=170,3,1,1,5,...=\dfrac{170}{1},\dfrac{511}{3},$ $\dfrac{681}{4},\dfrac{1192}{7},\dfrac{6641}{39},...$ Далее $m_3=7249+39^2-6641=2129.\ \ \ \sqrt{2129}=46,7,11,...$ Из разложения $\sqrt{4 \cdot 2129}$ уже не получаем числа с нужными свойствами и заключаем отсюда, что $m_3=2129$ наименьшее.

Заметим, что все непрерывные дроби, возникшие в процессе разложений отличаются между собой лишь первым знаком. Подходящие дроби в этом случае имеют общие знаменатели, а целые части радикалов образуют поэтапно арифметические прогрессии. Если бы знать наверняка, что эта ситуация общая для любых $u,v$, алгоритм упрощался бы до предела. В данном случае после вычисления $m_2=7249$ и целой части $\sqrt{7249}=85$ достаточно найти разность $124-85=39$ и проверить "арифметическую прогрессию" из радикалов:
$85-39=46;\ \left ( 46+\dfrac{11}{78} \right )^2 \approx 2129;\ \sqrt{2129}=46,7,11...$ Годится.
$46-39=7;\ \left ( 7+\dfrac{11}{78} \right )^2 \approx 51;\ \sqrt{51}=7,7,14...$ Уже не годится.
Это был бы хороший выход. Хотя, если разность окажется мала, такая проверка может оказаться утомительной. Ну, а если брать поздние подх. дроби, сразу имеем дело с большими числами, и на прогрессии рассчитывать не приходится, т.к. разложения радикалов в поздних знаках уже различны. Где найдешь, где потеряешь...

[Dendr]

Вот обещанный полный ход моего решения:
Пусть
$\sqrt{m}=n+\frac{1}{u+\frac{1}{v+\eta}} (0<\eta<1)$
Введем также, для удобства записи, обозначение $\xi^{-1}=v+\eta$

Будем искать решение в виде $m=n^2+d$, где $0<d\le2n$, причем нам неоходимо минимизировать $n$, а при необходимости, "вторым уровнем" - $d$. Заметим, что, по конструкции, $0<\sqrt{m}-n<1$.

Перепишем исходное выражение: $u+\xi=\frac{1}{\sqrt{m}-n}=\frac{\sqrt{m}+n}{d}=\frac{2n+\sqrt{m}-n}{d}$
Введем $0\ler<d$: $2n=ud+r$, тогда $u+\xi=u+\frac{r+\sqrt{m}-n}{d}$.
Убеждаемся: числитель положителен и не превышает $d$, поэтому все второе слагаемое положительно и меньше единицы, следовательно, это та самая величина, получаемая при выделении очередного компонента (в данном случае, $u$) цепной дроби, то есть равна $\xi$.

Таким образом, перед нами стоит следующая задача: подобрать $(d, r)$ такими, чтобы $v+\eta=\frac{d}{r+\sqrt{m}-n}$. При этом требуется условие четности $ud+r=2n$, тогда $m=n^2+d$.

Как видно, минимальное $n$ достигается при минимальном $d$.

(уточнение)

при фиксированном $u$, если некое $d$ годится, $2n$ не больше $ud+(d-1)<(u+1)d$. Если же годится $d+\delta$ ($\delta$ - натуральное), то $2n'=u(d+\delta)+r\ge u(d+\delta)$. Если утверждение выше ошибочно, то $n'<n$, то есть $u(d+\delta)<(u+1)d$, или $u\le u\delta<d$. Другими словами, надо с осторожностью рассматривать $d>u$. Однако, как ниже будет показано, некоторые решения возникают для $r\le2$, а тогда $2n\le ud+2, 2n'\ge u(d+\delta)$, следовательно, сравниваем $u(d+\delta)\le ud+2$, или $u\delta\le2$. Это возникает лишь при $u\in{1,2}$, но эти случаи можно рассмотреть отдельно, - в том числе убедиться, что они удовлетворяют общему решению.

Так как $0\le\eta<1$, то дробь заключена в пределах $(v, v+1)$ (включая левый конец). Тогда
$v\le \frac{d}{r+\sqrt{m}-n}<v+1$,

$\frac{d}{v+1}+n-r<\sqrt{m}\le \frac{d}{v}+n-r$
Возводя в квадрат и упрощая, приходим к выражению:

(промежуточные выкладки)

$(\frac{d}{v+1})^2+\frac{2d}{v+1}(n-r)+n^2-2nr+r^2<n^2+d\le (\frac{d}{v})^2+ \frac{2d}{v}(n-r)+n^2-2nr+r^2$ ;

$(\frac{d}{v+1})^2+\frac{d}{v+1}(2n-2r)<d+2nr-r^2\le (\frac{d}{v})^2+ \frac{d}{v}(2n-2r)$;

$(\frac{d}{v+1})^2+\frac{d}{v+1}(ud-r)<d+udr\le (\frac{d}{v})^2+ \frac{d}{v}(ud-r)$;

$\frac{d}{(v+1)^2}+\frac{ud-r}{v+1}<1+ur\le \frac{d}{v^2}+ \frac{ud-r}{v}$.

Оно равносильно
$rv+\frac{v^2}{uv+1}\le d<r(v+1)+\frac{(v+1)^2}{u(v+1)+1}$

Здесь так же видно, что наименьшие $d$ возникают при меньших $r$, что облегчает перебор. Но перебор можно еще и формализовать!
Заметим также, что $\frac{v^2}{uv+1}=\frac{v}{u}-u^{-2}+\frac{1}{u^2(uv+1)}=\frac{v}{u}-u^{-2}+\alpha_1$,
$\frac{(v+1)^2}{u(v+1)+1}=\frac{v+1}{u}-u^{-2}+\frac{1}{u^2(u(v+1)+1)}=\frac{v+1}{u}-u^{-2}+\alpha_2$, где $0<\alpha_{1,2}<1$



Таким образом, мы пришли к неравенству:
$rv+\frac{v}{u}-\frac{1}{u^2}+\alpha_1\le d<r(v+1)+\frac{v+1}{u}-\frac{1}{u^2}+\alpha_2$
При этом $ud+r$ должно быть четным, и $m$ выражается по ранее указанной формуле.

Пусть $v=2up+w, 0\le w<2u, p\ge0$. Тогда нам надо рассмотреть два особых случая, и два общих: $w=0, w=u$ и промежуточные.

Надо обратить внимание, что такая процедура позволяет найти любые пары $(d, r)$, определяющие $m$, которые подходят к условию задачи. Минимальное $m$ выбирается непосредственно из них.

Продолжение следует...

[Dendr]

Решаем, при данных $(u, p, w<2u; v=2pu+w)$, в целых числах неравенство
$r(2pu+w)+2p+\frac{w}{u}-\frac{1}{u^2}+\alpha_1\le d<r(2pu+w+1)+2p+\frac{w+1}{u}-\frac{1}{u^2}+\alpha_2$
где $\alpha_1^{-1}=u^2(uv+1), \alpha_2^{-1}=u^2(u(v+1)+1)$ (следовательно, $\alpha_i^{-1}>u^2, -1<-u^{-2}+\alpha_i<0$)
при условиях: $r<d$, $ud+r$ - четно, $0\le w<2u$.
Нас интересует наименьшее возможное $ud+r$, и решение оригинальной задачи - $(\frac{ud+r}{2})^2+d$.

1а. Пусть $w=0$.
$2rpu+2p-\frac{1}{u^2}+\alpha_1\le d<r(2pu+1)+2p+\frac{1}{u}-\frac{1}{u^2}+\alpha_2$
Избавляясь от дробных частей (слева она отрицательна и по модулю меньше 1, справа - положительна, и также меньше 1) получаем уже целочисленное неравенство:
$2rpu+2p\le d<2rpu+2p+r+1$
Его решение - все числа вида $d=2p(ur+1), 2p(ur+1)+1, ... 2p(ur+1)+r$.
Переберем $r$.

$r=0$: $2p\le d<2p+1$, откуда $d=2p$. Тогда $ud+r=2up=v$ - четное число, и $m=(v/2)^2+v/u$

При больших $r$ получаем, что $d>2p$, тогда $ud+r>ud>2pu>v$, уже не минимальные решения.

1б. Пусть $w=u$.
$r(2pu+u)+2p+1-\frac{1}{u^2}+\alpha_1\le d<r(2pu+u+1)+2p+1+\frac{1}{u}-\frac{1}{u^2}+\alpha_2$
Как и в предыдущем случае, избавляемся от дробей:
$r(2pu+u)+2p+1\le d<r(2pu+u)+2p+2+r$

$r=0$ ($ud$ - четно): $2p+1\le d<2p+2$. Единственное решение - $d=2p+1=v/u$. Но оно годится лишь при четном $u$, и, проверяя аналогично, убеждаемся, что оно минимально. Что при нечетном $u$?

Рассмотрим $r=1$ ($ud$ - нечетно, следовательно, $d$ - нечетно): $2pu+u+2p+1\le d<2pu+u+2p+3$. Как видно, следует выбрать $d=2pu+u+2p+2=v+v/u+1$.

Если будем искать $r\ge2$, то $d$ только возрастает, и эти решения (каждое в своем случае) - действительно минимальны.

2. $0<w<u$.
Тогда $\frac{1}{u}\ge\frac{w}{u}<1$, и дробная часть левого неравенства положительна и меньше 1,
а $\frac{2}{u}<\frac{w+1}{u}\le1$, то есть дробная часть правого неравенства положительна и не превышает 1. Тогда все неравенство выглядит так:

$r(2pu+w)+2p+1\le d<r(2pu+w+1)+2p+1$

Видно, что при $r=0$ возникает выражение $2p+1<2p+1$, поэтому сразу переходим к следующим значениям.
$r=1$ ($ud$ нечетно): $2pu+w+2p+1\le d<2pu+w+2p+2$. У него только одно решение - $d=v+2p+1$, и оно удовлетворяет всем условиям только для четного $v$ и нечетного $u$.
$r=2$ ($ud$ четно): $2v+2p+1\le d<2v+2p+3$. У него два решения: $d=2v+2p+1, d=2v+2p+2$. При четном $u$ выбираем минимальное - $2v+2p+1$ (для минимизации $ud+2$), при нечетном $u$ - годится только одно, и это $2v+2p+2$, причем $v$ тоже должно быть нечетно, иначе годится меньшее решение - с $r=1$.
Перечислим $ud+r$: $u(v+2p+1)+1<u(2v+2p+1)+2<u(2v+2p+2)+2=2vu+2pu+w+2u-(w-1)+1=2vu+v+u2u-(w-1)+1<2vu+v+2u+1
Заметим, что при больших $r\ge3$ имеем: $d>3v+2p+1$, так что $ud+r\ge3vu+2pu+u+3>3vu+v+3$
Но $3vu+v+3-(2vu+v+2u+1)=vu+2-u=u(v-1)+2\ge2$, поэтому найденные пары дают наименьшие $ud+r$, то есть, наименьшие $m$.

Аналогично, рассматриваем противоположный случай:
3. $u<w<2u-1$.
Тогда $1<\frac{w}{u}<2$, и дробная часть левого неравенства положительна и меньше 1, после выделения 1;
а $1+\frac{2}{u}<\frac{w+1}{u}\le2$, и, выделив единицу, опять справа получаем дробнуючасть, которая положительна и не превышает 1. Неравенство похоже на предыдущее с одним отличием (так мы сможем воспользоваться предыдущими результатами):

$r(2pu+w)+2p+1\le d-1<r(2pu+w+1)+2p+1$

Здесь так же не годится $r=0$.
Для $r=1$, то есть нечетного $ud$, одно решение $d=v+2p+2$. Здесь $u$ должно быть нечетным, как и $d$, то есть это решение годится для нечетного $v$: $d=v+2p+2$.
Для $r=2$, четного $ud$, два решения: $d=2v+2p+2, d=2v+2p+3$. Видно, что, выбрав меньшее, получим гарантированно четное $ud$, так что это тоже решение.
Рассмотрим условие минимальности $ud+r$ при данном $u$. Одновременно минимально и $u(d-1)+r$:
$u(v+2p+1)+1<u(2v+2p+2)+2=2uv+2pu+w+u-w+u+2=2uv+v+(u-w)+u+2<2uv+v+u+2$
Тогда как при $r\ge3$ получаем $d-1\ge3v+2p+1$, $u(d-1)+r\geu(3v+2p+1)+3=3uv+2pu+u+3=3uv+2pu+w-w+u+3=3uv+v+u+3-w$
Рассмотрим разность. $3uv+v+u+3-w-(2uv+v+u+2)=uv+1-w>uv+1+1-2u=u(v-2)$
Как видно, при $v\ge2$ она положительна, поэтому следующие решения больше найденных.

Таким образом, перечислены все случаи соотношения $u, v$, кроме особого: $v=1$. (сводная таблица в одном из предыдущих сообщений)

Но в этом случае $1=2pu+w$ - то есть $p=0, w=1$. Неопределенность возникла только в третьей секции, то есть должно быть $u<1<2u-1$, или $u<1, u>1$ одновременно, что невозможно, поэтому указанное решение исчерпывающе и минимально.

Собственно, таким образом можно найти параметрическое решение для всех $m(u,v)$, не только минимального. Если требуется найти решение(-я) не для двух, а для трех первых элементов цепной дроби, то это тоже должно быть возможно похожим путем, но потребуются чересчур многоэтажные дроби, а количество параметров растет в геометрической прогресии...

[maxal]

Получилась хорошая задачка на программирование.
Andrey A, Dendr, не хотите запрограммировать свои алгоритмы, чтобы посмотреть на точность и быстродействие?

[Andrey A]

maxal
Я попробую сделать это в Excel, но и так ясно что будет либо "сразу", либо ошибка больших чисел. Дело в том что длинных периодов в описанной схеме не образуется, самое затратное — проверки. Удастся ли оценить быстродействие — вот вопрос. Если хотите попробовать в PARI/GP, пожалуйста, чем могу. Сложностей тут пока не вижу.

[Dendr]

Я, признаться, в целочисленное программирование не умею совсем. В эксель загнал (ссылка выше), и руками проверил, что до 1000 работает, в том числе и минимальность определения, но на что посерьёзнее...

А поскольку выходит, что $\sqrt m\leO(u\cdot v)$, то если суммарно в них наберётся 32 бита и больше, long long уже не справится. Впрочем, в качестве чисто развлечения, было, писал int-расширяющие костыли-классы с эмуляцией вычисления "в столбик", но времени они съедают много.

Соответственно, найти $m(u,v)$ (даже для зашкаливающих аргументов) и потом доказать, что в цепи эти числа появятся, смогу. Обосновать минимальность в обозримом время - вряд ли.
Код (в плюсах), как будет время, накидаю, если будут советы по расширению - будет интересно.

P.S. Прикинул на коленке - так-то алгоритм (но не формулу) поиска $d, r$ можно продлить для любой длины цепи, надо только ограничить $\eta$ соответственно.

[Someone]

Dendr в сообщении #1488592 писал(а):

в качестве чисто развлечения, было, писал int-расширяющие костыли-классы с эмуляцией вычисления "в столбик", но времени они съедают много.

Есть же готовые библиотеки для вычислений неограниченной точности: NTL, GMP,…

[Andrey A]

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

maxal
Я попробую сделать это в Excel...

Готово. Два знака радикала.xlsx

Всё пошло не по плану, конечно. Поскольку не только длинных дробей в разложении $\sqrt{4m_1}$ не возникает, но и количество возможных $m_i=m_1+q_i^2-p_i$ на интервале $(0,m_1)$ вроде бы ограничено, надо смотреть в больших числах. В таких условиях имеет смысл тупо брать наименьший результат и повторять процедуру по кругу, но сколько понадобится таких шагов заранее неизвестно, поэтому в Excel приходится вводить пальчиками (макросы мой Excel отвергает).
Я сделал две версии. Вторая дальше $m_5$ вообще не заходит, но использует свойства "арифметических прогрессий", первая — по описанному простейшему сценарию с небольшим исключением (вариант $M$). Инструкции прилагаются.

P.S. Таблица исправлена 25.10.2020