Начнём с числа 1. Далее, если число чётно, то уменьшаем его вдвое. Если нечётно, увеличиваем его на наименьшее натуральное число, на которое мы ещё не увеличивали ни один из членов нашей последовательности.

Получим вот такую последовательность: 1 2 1 3 6 3 7 12 6 3 9 16 ...

Все ли натуральные числа встретятся в этой последовательности?

задан 17 Дек '18 3:12

1

@Казвертеночка: последовательность очень "крутая"! В ней долго не встречается 11, но потом оно всё же появляется. А вот есть ли 13 -- это большой вопрос! Вообще, это всё напоминает сложные вещи типа (3x+1)-проблемы.

P.S. Проверка показала, что и 13 появляется -- на шаге с номером 45887. Но это, наверное, доказать будет очень сложно!

P.P.S. Обнаружено "упорное" число 305. Оно появляется, но только на шаге с номером 2050771. "Круть"!!!

(17 Дек '18 11:36) falcao

@falcao, стало быть, открытая проблема?

(17 Дек '18 11:38) Казвертеночка

@falcao, на соседнем форуме написали кое-что интересное по этому поводу, но цитата в коммент не уместилась, придётся написать её в ответе на вопрос...

(17 Дек '18 11:57) Казвертеночка
10|600 символов нужно символов осталось
1

@falcao, на соседнем форуме написали, что:

«Среди первых 10 миллиардов членов последовательности не встретилось чисел 7525 7663 8901 10187 10740 13835 15050 15151 15326 17623 17661 17802 19573 19966 (и много ещё больших), два из которых, 13835 19966, не встретились и среди первых 100 миллиардов. Максимальный член последовательности при этом почти равен удвоенному количеству итераций (19999086352 и 199998599788 соответственно). С другой стороны, если не встретится число $%x$%, то не встретятся и бесконечное количество чисел вида $%x\cdot2^k$%, что маловероятно, уж наверняка какое-нибудь из них будет равно сумме другого встретившегося и натурального числа.»

Вот ссылка.

ссылка

отвечен 17 Дек '18 11:58

изменен 17 Дек '18 12:06

1

@Казвертеночка: да, интересно! Из "вероятностных" соображений положительный ответ звучит очень правдоподобно, и вычисления это косвенно подтверждают. Но доказать это, наверное, очень трудно. По внешнему виду -- не проще, чем для (3x+1)-проблемы. Фактически, здесь рассматриваются пары (n,s), и за один шаг пара переходит либо в (n/2,s), либо в (n+s,s+1) в зависимости от чётности. Начальная пара (1,1). Задачи такого типа бывают сложными даже для "траекторий" одного числа. Типа: f(x)=2x/3, если x кратно 3, и f(x)=round(4x/3) (до ближайшего целого), если не кратно. Для x=8 ответ неизвестен.

(17 Дек '18 21:45) falcao
1

Поясню последнее: мы имеем 8,11,15,10,13,17,...; стремится ли это дело к бесконечности, или входит в цикл? В обратную сторону траектория однозначно продолжается: ...,20,27,18,12,8 и так далее. "Сходятся" ли вместе эти две последовательности? Никто не знает. А для пар ещё сложнее (я знаю весьма трудные примеры таких систем).

(17 Дек '18 21:48) falcao
10|600 символов нужно символов осталось
Ваш ответ

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

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

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

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

отмечен:

×1,059
×120
×100
×24
×19

задан
17 Дек '18 3:12

показан
132 раза

обновлен
17 Дек '18 21:48

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

по почте:

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

по RSS:

Ответы

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

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