НОД

[Atij]

Всем привет)
Все мы прекрасно знаем алгоритм Евклида для нахождения НОД`а.
Вот такой вопрос: как вывести формулу при кот-ой алгоритм работает максимально долго?
Или по-другому: как вывести формулу нахождения числа m, такого,что при заданном n, происходит наибольшее кол-во шагов для вывода НОД`a?
Первое что пришло мне в голову, написать прогу кот-ая меняет n и m, и выводит кол-во итераций при очередном m и n, а потом попытаться найти зависимость, мне это не помогло, могу выложить код программы, или результаты вычислений.
Всем заранее спасибо)

[enko]

По-моему, формулу вывести нельзя

[Atij]

А вообще есть какие-нибудь идеи по этому поводу, незнаю, можно ли скажем математически доказать невозможность вывода этой формулы?..

[Brukvalub]

Вва вопрос давно исследован и на него получен точный ответ. См., например, http://rain.ifmo.ru/cat/view.php/theory/math/number-theory-2005

[Atij]

Спасибо большое, я конечно понимаю, что там наверное дан ответ на мой вопрос, но ввиду своей не состоятельности в математике, можно меня как полного чайника носом ткнуть в ответ, плз)

[Brukvalub]

Цитирую: "Время работы алгоритма Евклида

Обозначим e(m, n) число шагов алгоритма Евклида, примененного к натуральным числам n и m. До сих пор наиболее известным результатом о функции e(m, n) остается найденная французским математиком Габриэлем Ламе (Gabriel Lamé, 1795–1870) в первой половине 19-го века (1844) оценка сверху:
e(m, n) ≤ [logφ51⁄2(max(m, n) + 1⁄2)] − 1, где φ = (1 + 51⁄2) ⁄ 2

Данная оценка является точной и достигается при соседних числах Фибоначчи: m = Fk+1, n = Fk.

Доказательство и различные интерпретации алгоритма Евклида см. [5] "

[Профессор Снэйп]

Там большим жирным шрифтом написано: "Время работы алгоритма Евклида", почти что в начале страницы. Ну и дальше по тексту...

[Brukvalub]

На самом деле, в точности на Ваш вопрос:

Atij писал(а):

Или по-другому: как вывести формулу нахождения числа m, такого,что при заданном n, происходит наибольшее кол-во шагов для вывода НОД`a

указанная мной ссылка не отвечает. Она отвечает на Ваш вопрос:

Atij писал(а):

Вот такой вопрос: как вывести формулу при кот-ой алгоритм работает максимально долго?

и указывает, на каких парах чисел реализуется оценка сверху времени работы алгоритма.

[Atij]

Всем большое спасибо, вопрос решён.

[maxal]

Кстати, этот факт теоремой Ламе называется.