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

[dimkadimon]

Придумал интересную задачу, но не знаю как решить. Начнём с целого числа $k=2$. Если $k$ простое то заменим его на $k^2+9$. Иначе заменим его на $k/2$ (целое деление без остатка). Продолжаем пока не встретим старое число. Например вот первые значения:

2 (простое), 13 (простое), 178, 89 (простое), 7930, 3965, 1982, 991 (простое), ...

Вопрос: есть ли цикл в этой последовательности или она даёт новые значения бесконечно?

Интересно что если поменять 9 на другие числа (например от 1 до 8) то цикл возникает. С другой стороны, не могу найти цикл для 18, 19 и 22.


П.С. Простите если написал не в тот форум.

[dimkadimon]

Гмм... никто не пишет. Либо задача слишком скучная или слишком сложная?

А может я не в том форуме написал? Если так то админы пожалуйста передвиньте куда надо (может в Олимпиадные Задачи). Спасибо.

[dmd]

Мне тоже показалась интересной. Для 6 цикл тоже не прослеживается.
dd(a)=
{
k= 2^2+a;
while(1, if(ispseudoprime(k), print(k); k= k^2+a, k= k\2))
};

Последовательность длин циклов такая (начиная с a=1):

2,10,6,1,1,?,2,8,?,?,1,1,85,1,4,23,1,?,...

[dimkadimon]

dmd, хорошая работа - можно добавить в OEIS. Для а=6 и а=10 тоже есть циклы, но они длинные.

[Dmitriy40]

dmd в сообщении #1382889 писал(а):

Последовательность длин циклов такая (начиная с a=1):

2,10,6,1,1,?,2,8,?,?,1,1,85,1,4,23,1,?,...

Мне кажется тут неточности, у меня цифры получаются совершенно другими:

Используется синтаксис Text

? p=2;for(i=1,10,print1(p," ");if(ispseudoprime(p),p=p^2+1,p\=2))
2 <5 26 13 170 85 42 21 10> 5 - длина цикла 8
? p=2;for(i=1,102,print1(p," ");if(ispseudoprime(p),p=p^2+2,p\=2))
2 6 3 11 123 <61 3723 1861 3463323 1731661 865830 432915 216457 108228 54114 27057 13528 6764 3382 1691 845 422 211 44523 22261 11130 5565 2782 1391 695 347 120411 60205 30102 15051 7525 3762 1881 940 470 235 117 58 29 843 421 177243 88621 44310 22155 11077 5538 2769 1384 692 346 173 29931 14965 7482 3741 1870 935 467 218091 109045 54522 27261 13630 6815 3407 11607651 5803825 2901912 1450956 725478 362739 181369 90684 45342 22671 11335 5667 2833 8025891 4012945 2006472 1003236 501618 250809 125404 62702 31351 15675 7837 3918 1959 979 489 244 122> 61 - длина цикла 96
? p=2;for(i=1,47,print1(p," ");if(ispseudoprime(p),p=p^2+3,p\=2))
2 <7 52 26 13 172 86 43 1852 926 463 214372 107186 53593 2872209652 1436104826 718052413 359026206 179513103 89756551 44878275 22439137 11219568 5609784 2804892 1402446 701223 350611 175305 87652 43826 21913 10956 5478 2739 1369 684 342 171 85 42 21 10 5 28 14> 7 - длина цикла 45
? p=2;for(i=1,4,print1(p," ");if(ispseudoprime(p),p=p^2+4,p\=2))
<2 8 4> 2 - длина цикла 3
? p=2;for(i=1,4,print1(p," ");if(ispseudoprime(p),p=p^2+5,p\=2))
<2 9 4> 2 - длина цикла 3
? p=2;for(i=1,9,print1(p," ");if(ispseudoprime(p),p=p^2+7,p\=2))
<2 11 128 64 32 16 8 4> 2 - длина цикла 8
? p=2;for(i=1,43,print1(p," ");if(ispseudoprime(p),p=p^2+8,p\=2))
<2 12 6 3 17 297 148 74 37 1377 688 344 172 86 43 1857 928 464 232 116 58 29 849 424 212 106 53 2817 1408 704 352 176 88 44 22 11 129 64 32 16 8 4> 2 - длина цикла 42
? p=2;for(i=1,6,print1(p," ");if(ispseudoprime(p),p=p^2+11,p\=2))
2 <15 7 60 30> 15 - длина цикла 4
? p=2;for(i=1,150,print1(p," ");if(ispseudoprime(p),p=p^2+12,p\=2))
<2 16 8 4> 2 - длина цикла 4
? p=2;for(i=1,150,print1(p," ");if(ispseudoprime(p),p=p^2+14,p\=2))
<2 18 9 4> 2 - длина цикла 4
? p=2;for(i=1,107,print1(p," ");if(ispseudoprime(p),p=p^2+15,p\=2))
2 19 376 188 94 47 2224 1112 556 278 139 19336 9668 4834 2417 5841904 2920952 1460476 730238 365119 133311884176 66655942088 33327971044 16663985522 8331992761 4165996380 2082998190 1041499095 520749547 260374773 130187386 65093693 32546846 16273423 8136711 4068355 2034177 1017088 508544 254272 127136 63568 31784 15892 7946 3973 1986 993 496 248 124 62 31 976 488 244 <122 61 3736 1868 934 467 218104 109052 54526 27263 13631 6815 3407 11607664 5803832 2901916 1450958 725479 526319779456 263159889728 131579944864 65789972432 32894986216 16447493108 8223746554 4111873277 2055936638 1027968319 513984159 256992079 128496039 64248019 32124009 16062004 8031002 4015501 2007750 1003875 501937 250968 125484 62742 31371 15685 7842 3921 1960 980 490 245> 122 - длина цикла 50

Т.е. последовательность длин циклов a(n=1..15): 8,96,45,3,3,*,8,42,*,*,4,4,*,4,50.

-- 20.03.2019, 02:24 --

А, Вы учитывали лишь простые, по ним тогда да. Но это не цикл последовательности, это нечто чуточку другое.

[dimkadimon]

Для а<=50 не нашёл циклы для а=9, 18, 19, 22, 26, 27, 45, 46. Для а=6 нужно было 295000+ терминов чтобы вернуться к началу (точную длину цикла не знаю) и числа достигали 12551 цифр!

[dimkadimon]

Для а=10 нужно было 39000+ терминов.

[dmd]

Придумал такую программку, чтоб точно посчитать величину цикла

dd(a)=
{
 d= [];
 k= 2^2+a;
 while(1,
  if(ispseudoprime(k),
   d= concat(d, [k]);
\\   print(k);
   k= k^2+a;
   p= #d\2;
   if(p>1,
    for(i=1, p, d1= d2= []; 
     for(j=1, i,
      d1= concat(d1, [d[#d+1-j]]);
      d2= concat(d2, [d[#d-i+1-j]])
     ); \\print(d1);print(d2);
     if(d1==d2, print("\na = ",a,"    period = ",#d1); break(2))
    )
   )
  ,
   k= k\2
  )
 )
};

Но как-то не складно она выглядит.

[Dmitriy40]

Я тоже думал автоматизировать этот процесс, но ничего умнее двойного прохода в голову не приходит: на первом проходе идём и все числа складываем в сортированный вектор с предварительной проверкой что их там ещё нет, как только находим повтор, то инициализируем счётчик и просто идём дальше и считаем когда это же число снова появится, уже без вектора.
Логичнее было бы складывать в несортированный массив, но по нему vecsearch работает неправильно. Хотя можно складывать в два массива, сортированный для проверки цикла и в несортированный для определения точки начала и длины цикла, как-то так:

default(parisizemax,10^9);
{for(a=1,20,
   s=[]; n=[]; p=2; f=0;
   while(f==0 && #s<10^4,
      s=Set(concat(s,p)); n=concat(n,p);
      if(ispseudoprime(p), p=p*p+a, p\=2);
      f=setsearch(s,p);
   );
   if(f>0,
      f=0; for(k=1,#n, if(n[k]==p, f=k; break));
      printf("%d:%d+%d\n", a,f,#n-f+1);
   );
);}
1:2+8
2:6+96
3:2+45
4:1+3
5:1+3
7:1+8
8:1+42
11:2+4
12:1+4
13:1+6587
14:1+4
15:57+50
16:5283+366
17:2+4
20:33+50

Вывод: второе слагаемое : начало цикла + длина цикла.

[Someone]

У Д. Кнута мне попадался такой алгоритм поиска длины периода последовательности, задаваемой формулой $a_{n+1}=f(a_n)$: задаём начальное значение $b\leftarrow a\leftarrow a_0$, затем в каждом цикле считаем $a\leftarrow f(a)$ и $b\leftarrow f(f(b))$ и ищем совпадения $a$ и $b$.
Но начало цикла потом придётся искать отдельно.

[Dmitriy40]

dimkadimon в сообщении #1383040 писал(а):

Для а=10 нужно было 39000+ терминов.

Для a=10 цикл длиной 355 начиная с 39389.

-- 20.03.2019, 17:33 --

Someone
Да, но я посчитал что операции над не слишком большими массивами/векторами (добавление к простому и вставка в отсортированный) дешевле двойного вычисления $f()$ (и чем сортировка простого массива).

[dmd]

Dmitriy40 в сообщении #1383145 писал(а):

dimkadimon в сообщении #1383040 писал(а):

Для а=10 нужно было 39000+ терминов.

Для a=10 цикл длиной 355 начиная с 39389.

Получается ещё интереснее! Тоже заметил, что некоторые циклы начинаются не с первого элемента. Но чтоб так далеко от первого - неожиданно.

[mihaild]

Dmitriy40 в сообщении #1383145 писал(а):

Для a=10 цикл длиной 355 начиная с 39389.

Причем первый элемент - всего $40$.

Т.к. почти всё время занимает проверка на простоту, то выгоднее сохранять позиции, и даже не особо важно, как именно.

[dimkadimon]

Dmitriy40
Я так и сделал - использую set и list одновременно. Ищу замыкание цикла через set, а потом нахожу его длину через list. Вот мои результаты для всех а<=30, начиная с 2:

a, количество разных элементов, длина цикла, длина наибольшего числа
1 9 8 3
2 101 96 8
3 46 45 10
4 3 3 1
5 3 3 1
6 295581? ? 12551?
7 8 8 3
8 42 42 4
9 ?
10 39391? 355 3874?
11 5 4 2
12 4 4 2
13 6587 6587 218
14 4 4 2
15 106 50 12
16 5648 366 332
17 5 4 2
18 ?
19 ?
20 82 50 12
21 3082 3080 297
22 ?
23 14 14 3
24 798 798 71
25 73 18 10
26 ?
27 ?
28 5 5 2
29 5 5 2
30 148 104 14

Самое интересное что некоторые а имеют несколько циклов разной длины. Например а=3 имеет циклы длиной 3, 45 и 279. а=4 имеет цикл длиной 3 и возможно бесконечный цикл тоже!

[mihaild]

$$\begin{tabular}{|c|c|c|c|c|} \hline a & первый простой элемент цикла & длина & число простых внутри & стартовая позиция \\ \hline 1 & 5 & 8 & 2 & 2 \\ \hline 2 & 61 & 96 & 10 & 6 \\ \hline 3 & 7 & 45 & 6 & 2 \\ \hline 4 & 2 & 3 & 1 & 1 \\ \hline 5 & 2 & 3 & 1 & 1 \\ \hline 6 & 5 & 295579 & 154 & 3 \\ \hline 10 & 5 & 355 & 11 & 39392 \\ \hline \end{tabular}$$