ISSN 1608-845X
Язык: ru

ДОСТИЖИМОСТЬ НЕРАВЕНСТВ ИЗ ТЕОРЕМЫ ЛАМЕ (2024)

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

Тип: Статья
Автор (ы): КАН Игорь
Ключевые фразы: ТЕОРЕМА ЛАМЕ, АЛГОРИТМ ЕВКЛИДА

Идентификаторы и классификаторы

УДК
511.321. Рациональные тригонометрические суммы (включая кратные суммы). Суммы Гаусса и Клостермана. Суммы характеров. Суммы Дедекинда
Текстовый фрагмент статьи