fixfix
2014 dxdy logo

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

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




Начать новую тему Ответить на тему
 
 аля теорема Ламе для коэффициентов Безу
Сообщение22.03.2008, 14:40 
Модератор
Аватара пользователя


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

Пусть $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$, имеющих максимальную сложность Безу.

 Профиль  
                  
 
 
Сообщение22.03.2008, 15:07 
Заслуженный участник


09/02/06
4401
Москва
Разве это не длина непрерывной дроби для $$p/q=q_0+\frac{1}{q_1+\frac{1}{q_2+..}}}.$$

 Профиль  
                  
 
 
Сообщение22.03.2008, 15:50 
Модератор
Аватара пользователя


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

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

 Профиль  
                  
 
 
Сообщение22.03.2008, 16:15 
Заслуженный участник


09/02/06
4401
Москва
Самая длинная из дробей получается, когда все частные 1, поэтому максимум когда числа p и q последовательные числа Фибоначчи
$(F_m, F_{m+1})$ не превосходящие n и искомая величина есть $$m=[\frac{ln(n\sqrt 5)}{ln(\frac{1+\sqrt 5}{2})}].$$ точнее m может оказаться на 1 меньше в некоторых условияхю

 Профиль  
                  
 
 
Сообщение22.03.2008, 16:21 
Модератор
Аватара пользователя


11/01/06
5710
Ну и чем не теорема Ламе? :lol:

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

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

 Профиль  
                  
 
 
Сообщение22.03.2008, 18:54 
Заслуженный участник


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

 Профиль  
                  
 
 
Сообщение23.03.2008, 03:02 
Модератор
Аватара пользователя


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

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

$$a = q b + r$$, где $$-\frac{b}{2} < r \leq \frac{b}{2}$$

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

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 7 ] 

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



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

Сейчас этот форум просматривают: YandexBot [bot]


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

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