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

[Ktina]

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

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

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

[Dmitriy40]

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

[Ktina]

Dmitriy40
Тем не менее, проблема остаётся открытой, насколько я понимаю.

[grizzly]

Ktina в сообщении #1361858 писал(а):

Тем не менее, проблема остаётся открытой, насколько я понимаю.

Я бы поспорил, что при нашей жизни она не закроется. Правда, спор какой-то невыгодный получился бы из-за асимметричности, но риски тоже небольшие :)

По ассоциации отступлю немного в интересный офтоп, чтоб не плодить зря бесполезную тему. Есть такая последовательность:
$p_1=2, p_2=3$, $p_{k+1}$ -- наименьший простой делитель числа $p_1p_2\cdots p_k+1$. Совпадает ли множество значений этой последовательности с множеством простых чисел? Это давно известная и тоже беспросветно открытая проблема.

[Ktina]

grizzly в сообщении #1362056 писал(а):

Есть такая последовательность:
$p_1=2, p_2=3$, $p_{k+1}$ -- наименьший простой делитель числа $p_1p_2\cdots p_k+1$. Совпадает ли множество значений этой последовательности с множеством простых чисел? Это давно известная и тоже беспросветно открытая проблема.

Это, случайно, не "проблема 196"?

[grizzly]

Нет, конечно.

[Dmitriy40]

Ради интереса запустил перебор дальше, число 19966 встретилось между 240 и 250 млрд итерациями, а вот число 13835 продержалось до 2'355'483'842'842 итерации.
После 5'000'000'000'000 итераций 5 наименьших не встреченных числа: 35749 61616 71498 76195 87483.
Число 35749 встретилось на 19'780'805'300'961 итерации. 5 наименьших не встреченных на 20 трлн итерацию: 61616 76195 87483 120256 123232.
Число 61616 встретилось на 88'805'718'863'570 месте. 5 наименьших не встреченных: 76195 152390 190909 299663 304780.
Число 76195 встретилось на 149'849'331'459'571 месте. 5 наименьших не встреченных на 500 трлн итерацию: 190909 299663 334299 381818 460597.

[Dmitriy40]

Если изменить условие и добавлять не следующее натуральное число, а следующее по порядку простое число, получим последовательность

1 3 6 3 8 4 2 1 8 4 2 1 12 6 3 16 8 4 2 1 18 9 28 ...

Список наименьших 10-ти не встреченных чисел при длине последовательности:

1: 2 3 4 5 6 7 8 9 10 11
7: 5 7 9 10 11 12 13 14 15 16
71: 13 17 19 25 26 27 32 33 34 36
345: 25 27 32 36 49 50 54 60 64 67
1154: 27 36 54 60 72 75 79 84 97 107
161336: 36 60 72 97 107 115 120 127 144 157

36 держится очень долго, среди первых пятидесяти миллиардов членов его нет ...