Аннотация:
В середине 40-х годов ХIХ века Ламе оценил максимальную длину алгоритма Евклида для случая, когда меньший из двух его аргументов (назовем его $b$) не превосходит границы $N=10^k-1,$ а через год Дюпре уточнил эту оценку и обобщил ее на произвольные $N.$ Его неулучшаемый ответ является числом Фибоначчи. Однако чисел $b$ с одинаковой длиной алгоритма Евклида может оказаться несколько. Тогда для выбора конкретного из них требуется уточнить постановку задачи; по условию можем выбирать: или не число Фибоначчи, или число с наибольшей суммой неполных частных, или с наибольшим количеством неединиц среди них. Это все варианты максимума — можно сказать, первого максимума. Та пара аргументов $(a,b),$ для которой $b$ не больше $N$ и которая дает не максимальную длину алгоритма Евклида, а следующую за ней, предоставляет так называемый второй максимум этой длины. Для этой величины также возможны уточнения по количеству неединиц среди неполных частных или по их сумме. Для каждого из перечисленных вариантов задачи можно доказать, что соответствующие континуанты состоят из большого количества единиц (если единицы все — это число Фибоначчи), разбавленных какими-то другими неполными частными.
Ссылка на онлайн трансляцию семинара https://mian.ktalk.ru/awo7gpxikhtb?pinCode=9201
|
