Интересная последовательность

[dimkadimon]

mihaild
Отличные результаты! Вы говорили что цикл для а=10 начинается с 40? А в таблице 5

[mihaild]

Да, плохо написал. Это на самом деле первое простое число в цикле (и его позиция).

[Dmitriy40]

Вот цикл для a=10 у меня: ... 1281, 640, 320, 160, 80, <40, 20, 10, 5, 35, 17, 299, ..., 10401, 5200, 2600, 1300, 650, 325, 162, 81>, 40, 20, 10, 5, 35, ...
И цикл начинается с позиции 39389, в которой стоит число 40.
Наибольшее число было из 3873 цифр.

Давайте уже договоримся что именно считать последовательностью: все числа или только простые среди них. В начальном сообщении темы указано считать все, вы же оба иногда учитываете только простые, как например в начальной позиции цикла для a=10 выше. Бардак.

[dimkadimon]

Dmitriy40
Я предлагаю считать все числа.

[mihaild]

https://github.com/mihaild/dxdy/tree/master/seq - код подсчета и последовательности простых для некоторых чисел
Число простых среди первых членов последовательности для $a = 6$:

[dimkadimon]

mihaild, спасибо за код и результаты. Мои результаты совпадают с вашими. Я не знал что в Python можно использовать такие огромные числа - это очень удобно.

Получился очень интересный график для а=6. Интересно почему много простых в начале и в конце? Подозреваю что это все маленькие простые, которых больше шансов случайно встретить, а в середине редкие большие простые.

Что будем дальше делать? Хорошо бы отправить в OEIS, но в каком виде? Еще появились новые вопросы:

1. Как доказать что будет бесконечный цикл?
2. Можно ли ускорить подсчет элементов? Например если у нас число вида $a*2^b$ то можно перейти до $a$.
3. Какой самый длинный подъем - цепочка простых подряд?
4. Какой самый длинный спуск - цепочка составных подряд?
5. Сколько разных циклов возможно для одного а и разных стартовых значений? Пока больше 3 не видел.
6. Почему последовательность имеет такое хаотичное поведение? Соседние а могут вести себя совсем по разному. Что у нее общего с последовательностью Коллатза?

[SergeCpp]

Someone в сообщении #1383144 писал(а):

У Д. Кнута мне попадался такой алгоритм поиска длины периода последовательности, задаваемой формулой $a_{n+1}=f(a_n)$...

В книге Уоррена Алгоритмические трюки для программистов (в конце главы 5, с.95-97 русского издания 2003 года) описан алгоритм Госпера (также со ссылкой на том 2 Кнута), который лучше. Там объёмно, вот, в интернете есть:

Cycle detection писал(а):

Gosper's algorithm

R. W. Gosper's algorithm[10][11] finds the period but not the starting point of the first cycle. Its main feature is that it never backs up to reevaluate the generator function, and is economical in both space and time. For example, if it is known a priori that the generator function has a period of $2^{32}$ then 33 words is sufficient.

10: http://www.hackersdelight.org/hdcodetxt/loopdet.c.txt
11: http://www.inwap.com/pdp10/hbaker/hakmem/flows.html -- ITEM 132 (Gosper): LOOP DETECTOR

[dmd]

Не очень понятно, как получаются разные циклы для одного значения $a$. Мне думается, в таком виде в OEIS не примут. Если это особенность того, что Вы считаете цикл из не простых чисел, то - надо всё-таки считать цикл из простых чисел, который вроде должен быть однозначен (однозначно безконечен).

[dimkadimon]

dmd, для одной а, но разных стартовых значений получаются разные циклы. В этих циклах отличается длина и составные числа.

[mihaild]

Переписал на плюсы и распараллелил: https://github.com/mihaild/dxdy/blob/ma ... rallel.cpp
Для $a = 9$ цикла среди первых 324000 элементов нет, а самое длинное встреченное там число состоит из 38155 десятичных цифр.
Для $a = 18$ цикла среди первых 196988 элементов (125 простых) нет, самое длинное число до этого момента из 38763 цифр.

Не думаю, что этой последовательности место в OEIS - слишком она странная, да и деление пополам нацело - не особо интересная операция.

Список простых для $a = 6$ (вместе с номером в последовательности; по списку простых вся последовательность восстанавливается элементарно) - https://github.com/mihaild/dxdy/blob/master/seq/logs/6

[dimkadimon]

Carlos Rivera опубликовал задачу на своем сайте:

https://www.primepuzzles.net/puzzles/puzz_949.htm

[dimkadimon]

Вышли результаты с сайта Rivera. Для оригинальной задачи никто цикл не нашел, хотя нашли цикл для других стартовых чисел как например 3251 и его множители.