Даны числа $%a$% и $%b$%. Далее проводят такие операции, пока не получат нулевой остаток:

$%a= q_1b + r_1$%

$%b = q_2r_1 + r_2$%

$%r_1 = q_3r_2 + r_3$%

...

В общем, всё как в обычном алгоритме Евклида. Но остаток здесь может быть и отрицательным. Из двух возможных остатков выбирается тот, который меньше по модулю (словом, сохраняется правило $%|r_i| \leq \frac{|r_{i-1}|} {2}$%).

Для для какой пары натуральных чисел (a, b), не превышающих заранее заданного $%n$%, такой алгоритм будет иметь наибольшее количество шагов?

задан 20 Фев '18 19:05

изменен 21 Фев '18 18:06

1

У меня ответ получился, но я пока строго его не доказывал. Здесь "рекордсменами" будут рациональные приближения не к "золотому сечению", как для обычного алгоритма, а приближения к sqrt(2) в виде подходящих дробей 2/1, 3/2, 7/5, 17/12, ... и так далее. Требуется обдумать, как этот факт лучше обосновать.

(21 Фев '18 1:33) falcao

@falcao Мне кажется, тут сложнее. Да, вроде бы такие приближения дают лексикографически первое вхождение каждого значения числа шагов. Но кроме них есть и другие пары с таким же значением, совсем рядом. Скажем, d(17,12)=4 и d(19,12)=4. В стандартном алгоритме никаких таких близких пар не было. Там между (f_n+1,f_n) и (f_n+2,f_n+1) было хорошо и четко СЧИТАЕМОЕ количество пар, для которых длина алгоритма была такой же, как у (f_n+1,f_n), и все такие пары легко описать: ровно те, которые после k шагов "алгоритма вычитания из большего меньшего" приходили к паре (f_n+1-k,f_n-1-k).

(21 Фев '18 11:42) knop

@knop: полный анализ ситуации, конечно, интересен. Скорее всего, он возможен, хотя я не знаю, сколько там типов "рекордных" пар, и как они в целом классифицируются. Но задача так поставлена, что надо для каждого n найти максимум, указав хотя бы одну пару (единственное число!), на которой он достигается.

(21 Фев '18 12:21) falcao

@falcao имелось в виду именно утверждение @knop. Я исправил вопрос.

(21 Фев '18 12:36) Shizofrenik

@falcao - ну, доказать нужное свойство для конкретной последовательности очень несложно. Сложнее доказать справедливость оценки числа шагов для всего промежутка между соседними членами такой последовательности.

(21 Фев '18 12:57) knop

@Shizofrenik - мне кажется, вы хотите чрезмерного.

(21 Фев '18 13:53) knop

@knop Оценка-то как раз и не требуется. Необходимо лишь найти все пары-"рекордсмены".

(21 Фев '18 15:49) Shizofrenik

@Shizofrenik: я думаю, что задача об описании всех пар выглядит естественно лишь тогда, когда их мало. Вот мы знаем, что d(17,12)=4. Значение 5 получается лишь для пары 41,29. При n<=40 операций всегда не больше 4, и значение 4 тут, понятное дело, получается для очень многих пар. То есть это почти все пары за вычетом тех, где значение <=3. Значит, описание должно задействовать критерий того, чему равно d. А это задача "рыхлая", то есть надо применить алгоритм и посмотреть. То есть я к тому, что первоначальная версия была интереснее, и там есть что доказывать.

(21 Фев '18 16:01) falcao

@falcao Действительно, я подумал и понял, что прошлое условие было более интересным. Вернул:)

(21 Фев '18 18:06) Shizofrenik

@Shizofrenik: да, это правильно. Сейчас я постараюсь собраться с мыслями и написать.

Проделал такой эксперимент: рассмотрел случай n=98, когда максимальная длина равна 5. Программа нашла 174 пары, на которых наблюдается это значение. Типа: 96,83 или 92,58 или 43,31 (взял три случайных). Остальное столь же "безликое". Даже для n=40 получается 67 пар, которые дают 4 шага алгоритма. Они явно никак хорошо не классифицируются. Или вот для n=16 список из 24 пар, когда у алгоритма три шага: [7, 5], [8, 5], [9, 7], [10, 7], ..., [16, 9], [16, 10], [16, 11], [16, 13] (начало и конец). Явный "хаос".

(21 Фев '18 21:49) falcao
показано 5 из 10 показать еще 5
10|600 символов нужно символов осталось
Знаете, кто может ответить? Поделитесь вопросом в Twitter или ВКонтакте.

Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×879

задан
20 Фев '18 19:05

показан
359 раз

обновлен
21 Фев '18 22:34

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru