Conjecture 1: For any positive integer, the sequence generated by repeating the following rules
x → x / (k - 1) (if x ≡ 0 mod k - 1)
x → x / (k - 2) (if x ≡ 0 mod k - 2)
...
x → x / 3 (if x ≡ 0 mod 3)
x → x / 2 (if x ≡ 0 mod 2)
x → kx + 1 (for odd k, x)
will always reach the number 1. The appropriate transformation rule is selected per cycle in a top-down priority.
This is a generalization of the Collatz Conjecture.
I applied these algorithms to a range of integers from 1 to 1,000,000
3x + 1: pass (possibly breaks, cuz 9, 27, ... break)
5x + 1: pass (possibly never breaks, 25, 625 don't break)
7x + 1: pass (possibly breaks)
9x + 1: break at 13
11x + 1: break at 17
13x + 1: break at 19
15x + 1: break at 23
17x + 1: break at 43
19x + 1: break at 46063
21x + 1: break at 29
23x + 1: break at 179
25x + 1: pass
27x + 1: break at 433
29x + 1: pass
31x + 1: break at 67
33x + 1: break at 37
35x + 1: break at 43
37x + 1: break at 2173
39x + 1: break at 127
41x + 1: pass (possibly breaks)
43x + 1: break at 174569
45x + 1: break at 53
47x + 1: break at 859
49x + 1: break at 223
51x + 1: break at 67
53x + 1: break at 19559
55x + 1: break at 59
57x + 1: break at 67
59x + 1: break at 73
61x + 1: break at 97
63x + 1: break at 71
65x + 1: break at 239
67x + 1: break at 181
69x + 1: break at 109
71x + 1: break at 306511
...
125x + 1: break at 359
...
625x + 1: pass (25 * 25, 25 also pass)
...
841x + 1: pass (29 * 29, 29 also pass)
...
1681x + 1: break at 15749 (41 * 41, 41 pass) (41 possibly breaks too)
...
24389x + 1: possibly pass (29 * 29 * 29, 29 pass)
when it breaks at 13 on 9x + 1 it goes in a loop:
13n 118n 59n 532n 76n 19n 172n 43n 388n 97n 874n 437n 3934n 562n 281n 2530n 506n 253n 2278n 1139n 10252n 2563n 23068n 5767n 51904n 6488n 811n 7300n 1460n 292n 73n 658n 94n 47n 424n 53n 478n 239n 2152n 269n 2422n 346n 173n 1558n 779n 7012n 1753n 15778n 2254n 322n 46n 23n 208n 26n 13n
Next it breaks at 19 and goes in a loop:
19n 172n 43n 388n 97n 874n 437n 3934n 562n 281n 2530n 506n 253n 2278n 1139n 10252n 2563n 23068n 5767n 51904n 6488n 811n 7300n 1460n 292n 73n 658n 94n 47n 424n 53n 478n 239n 2152n 269n 2422n 346n 173n 1558n 779n 7012n 1753n 15778n 2254n 322n 46n 23n 208n 26n 13n 118n 59n 532n 76n 19n
Web need to figure out what kind of loop it is and why algoritms, that pass, don't have it
The sequence enters a loop at the prime number.
An even number is treated as one type of entity, while an odd number is another. These can be visualized as two different colored circles. The system containing these entities tends to form pairs based on the principle of "even with even" and "odd with odd." Such a pair results in an even number and is considered stable. Within this model, the fact that all entities eventually form pairs is analogous to the sequence converging to 1.
Уточненный расчет «полного шага»
В вашей системе проверка идет по цепочке: сначала делим на 4, если нет — на 3, если нет — на 2. Если число не делится ни на что из этого, оно обязательно нечетное.
-
Случай «Спад» (число четное или делится на 3): Делится на 4 (P = 1/4): коэффициент 1/4. Делится на 3, но не на 4 (P = 1/4): коэффициент 1/3. Делится на 2, но не на 4 или 3 (P = 1/4): коэффициент 1/2
-
Случай «Рост + Спад» (число нечетное и не делится на 3) Это происходит в оставшихся 25% случаев. Когда мы делаем 5x + 1 для такого числа, результат гарантированно четный. Но на что именно он поделится дальше? Если y делится на 4: Итоговый коэффициент (5/4) Если y делится на 3 (но не на 4): Итоговый коэффициент (5/3) Если y делится на 2 (но не на 4 или 3): Итоговый коэффициент (5/2)
Примечание: Вероятности деления результата 5x + 1 на 2, 3 или 4 распределены так же, как и для обычного числа.
рост = (1/4 * 1/3 * 1/2 * (5/4^1/4 * 5/3^1/4 * 5/2^1/4))^1/4 средний спад (75% времени) (1/41/31/2)^(1/3) = 0.346 средний рост со спуском (25% времени) (5/45/35/2)^(1/3) = 1.73
Итоговый средний множитель за один акт принятия решения: K = (1/4)^1/4*(1/3)^1/4*(1/2)^1/4*(1.73)^1/4 = 0.83
Даже с учетом гарантированного деления после роста, ваша функция имеет средний коэффициент ~0,83. Это меньше 1, а значит, математически ваша последовательность должна стремиться к локальным циклам или единице, как и классический Коллатц. Она убывает даже быстрее, чем оригинал (у Коллатца 0,866)
node index.js