аля теорема Ламе для коэффициентов Безу

[maxal]

Как известно, теорема Ламе определяет для каких чисел алгоритм Евклида (т.е. итерации операций деления с остатком) наиболее трудоемок. Я предлагаю решить аналогичную задачу для операции вычисления коэффициентов Безу для пар взаимно-простых чисел.

Пусть $p,q$ - натуральные взаимно-простые числа. Их коэффициентами Безу называются целые числа $a$ и $b$ такие, что

$$ap + bq = 1.$$

(вообще коэффициенты Безу определяются и для не взаимно простых чисел с заменой 1 на НОД этих чисел, но в этой задаче нас интересуют только взаимно-простые числа)
Коэффициенты Безу легко вычисляются расширенным алгоритмом Евклида.

Нетрудно видеть, что коэффициенты Безу взаимно-простых чисел сами являются взаимно простыми числами. Также понятно, что для одной и той же пары чисел $p$ и $q$, вообще говоря, существует бесконечно много пар коэффициентов Безу.

Назовем коэффициенты Безу $a,b$ минимальными, если значение $|a|+|b|$ является минимально возможным. Легко понять, что всегда существует только единственная минимальная пара коэффициентов Безу (за исключением случая $p=q=1$, когда минимальных пар две: $(0,1)$ и $(1,0)$, но они симметричны и можно выбрать любую).

Для пары взаимно-простых чисел натуральных чисел $p$ и $q$ определим функцию:

$$f(p,q)=(|a|,|b|)$$

, где $(a,b)$ - минимальные коэффициенты Безу для пары $(p,q)$.

Сложностью Безу пары $(p,q)$ назовем такое минимальное натуральное число $k$, что

$$f^{(k)}(p,q) = (0,1)$$

или

$$(1,0)$$

.

Например, сложность пары $(17,13)$ равна $3$, так как под действием $f$ получается такая цепочка пар:

$$(17,13)\quad\mapsto\quad (3,4) \quad\mapsto\quad (1,1) \quad\mapsto\quad (1,0).$$

Задача. Для заданного натурального $n$, найдите пару взаимно-простых натуральных чисел $(p,q)$, где $p\leq n$ и $q\leq n$, имеющих максимальную сложность Безу.

[Руст]

Разве это не длина непрерывной дроби для

$$p/q=q_0+\frac{1}{q_1+\frac{1}{q_2+..}}}.$$

[maxal]

Ну да, она.
$f(p,q)$ - это по сути вычисление предпоследней подходящей дроби к $\frac{p}{q}.$
Остается ответить на вопрос, для какой дроби эта длина будет максимальной.

Я тут пока граф этого отображения на $[1,30]^2$ нарисовал - красивая картинка:

[Руст]

Самая длинная из дробей получается, когда все частные 1, поэтому максимум когда числа p и q последовательные числа Фибоначчи
$(F_m, F_{m+1})$ не превосходящие n и искомая величина есть

$$m=[\frac{ln(n\sqrt 5)}{ln(\frac{1+\sqrt 5}{2})}].$$

точнее m может оказаться на 1 меньше в некоторых условияхю

[maxal]

Ну и чем не теорема Ламе?

Почти один к одному. Хотя странно было бы ожидать другого - и там, и там все завязано на алгоритм Евклида (ну или разложение в цепную дробь, если угодно).

Кстати, а условия, когда $m$ на 1 меньше, можешь сформулировать в простой форме?

[Руст]

Почти всегда, так как $F_{m+1}\le n<F_{m+2}$. Я несколько приближённо решал это неравенство.

[maxal]

Предлагаю разобрать, что изменится в алгоритме Евклида, разложении в непрерывную дробь и теореме Ламе, если вместо стандартного деления с остатком будет использоваться деление с минимальным по модулю остатком.

Результом деления натуральных чисел $a$ на $b$ является представление:

$$a = q b + r$$

, где

$$-\frac{b}{2} < r \leq \frac{b}{2}$$

целые числа $q$ и $r$ как и прежде называются частным и остатком от деления.