Дальневосточный математический журнал

К содержанию выпуска


Достижимость неравенств из теоремы Ламе


И.Д. Кан

2024, выпуск 1, С. 45-54
DOI: https://doi.org/10.47910/FEMJ202405


Аннотация
В настоящей работе доказывается следующий результат. Число шагов в алгоритме Евклида для двух натуральных аргументов, меньший из которых имеет $v$ цифровых разрядов в десятичной системе счисления, не превосходит целой части от дроби $ (v+\lg ({\sqrt{5}}/ {\Phi}))/ \lg \Phi$, где $\Phi=(1+\sqrt{5})/2$, причем эта оценка достигается при каждом натуральном $v$. Доказывается также, что для двух других известных верхних оценок длины алгоритма Евклида справедливы частичная или асимптотическая достижимости.

Ключевые слова: теорема Ламе, алгоритм Евклида.

Полный текст статьи (файл PDF)

Библиографический список

[1] Нестеренко Ю.В., Теория чисел, Издательский центр “Академия”, М., 2008.
[2] Кнут Д.Э., Искусство программирования. Т.2, Издательство “Диалектика-Вильямс”, 1998.
[3] Воробьёв Н.Н., Числа Фибоначчи, Главная редакция физико-математической литературы издательства “Наука”, М., 1978.
[4] Вейль Г., “О равномерном распределении чисел по модулю”, Избранные труды, Наука, М., 1984, 58–93.

К содержанию выпуска