О формировании последовательностей в гипотезе Коллатца ( 3n+1 )03.08.2018 10:03

Меня привлекают такие задачи, как проблема Коллатца. Они просты в формулировке и отлично тренируют голову, в особенности алгоритмического мышления, что очень полезно программисту.

Формулируется задача довольно просто:

Берём любое натуральное число n. Если оно чётное, то делим его на 2, а если нечётное, то умножаем на 3 и прибавляем 1 (получаем 3n + 1). Над полученным числом выполняем те же самые действия, и так далее.


Гипотеза Коллатца заключается в том, что какое бы начальное число n мы ни взяли, рано или поздно мы получим единицу.

Алгоритмически это выглядит так: 

while (number > 1) {
        if (number % 2 === 0) number = number / 2;
        else number = 3 * number +1;
}


К примеру, возьмем n=5. Оно нечетное, значит выполним действие над нечетным, то есть 3n+1 => 16. 16 — четное, значит выполним действие над четным, то есть n / 2 => 8 => 4 => 2 => 1.
Последовательность, образованная при n = 5: 16, 8, 4,2, 1.

Я прошу простить меня за мою математику, дайте знать, если где-то ошибусь.

Давайте выделим общее количество сведений к единице и истинное количество сведений к единице. Обозначим это за шаги.

Рассмотрим последовательность для n = 7:

22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1.

Всего шагов 16. А истинных шагов, которые на самом деле перебрасывают в другое числовое множество — их 5:

7, 11, 17, 13, 5.

Истинным шагом Sa (n) будем называть количество операций 3n+1 над числом, необходимых, чтобы достичь единицы.

Идея наглядно демонстрируется на примере таблицы:

Sn (0) Sn (1) Sn (2) Sn (3) Sn (4) Sn (5) Sn (6) Sn (7) Sn (8) Sn (9) Sn (10) Sn (11) Sn (12)
2 5 3 17 11 7 9 25 33 43 57 39 105
4 10 6 34 22 14 18 49 65 86 59 78 203
8 20 12 35 23 15 19 50 66 87 114 79 209
16 21 13 68 44 28 36 51 67 89 115 153 210
32 40 24 69 45 29 37 98 130 182 118 156 211
64 42 26 70 46 30 38 99 131 173 119 157 406
128 80 48 75 88 56 72 100 132 174 228 158 407
256 84 52 136 90 58 74 101 133 177 229 305 409
512 85 53 138 92 60 77 102 134 178 230 306 418


В такой таблице уже проглядывается порядок, своя закономерность.
Как видно степень двойки никогда четной не станет, поэтому все сводится к простому делению.
Образуется последовательность от Sa (0) всего 1 формулой.

$P(0,k)= 2*2^k.$


Никаких истинных шагов делать не нужно, простым делением все сведется к единице.
Зная это, можно отбросить из таблицы все числа, кратные двум.

Sn (0) Sn (1) Sn (2) Sn (3) Sn (4) Sn (5) Sn (6) Sn (7) Sn (8) Sn (9) Sn (10) Sn (11) Sn (12)
5 3 17 11 7 9 25 33 43 57 39 105
21 13 35 23 15 19 49 65 87 59 79 203
85 53 69 45 29 37 51 67 89 115 153 209
341 113 75 93 61 77 99 131 173 119 157 211
1365 213 141 181 117 81 101 133 177 229 305 407


Сейчас уже сложнее уловить закономерность, однако она есть. Сейчас самое интересное — образование последовательностей. Не просто так следующей цифрой после 5 стоит 21, а после неё 85.
На самом деле Sa (1) — это последовательность A002450 (0, 1, 5, 21, 85, 341, 1365, 5461, 21845, 87381…). Она образуется формулой:

$P(k)={4^k- 1\over 3}.$


Эту же последовательность можно описать рекурсивной формулой:

$P(k)= 4k_0+1,при \ k_0=1.$


$P(1) = 4*1+1 = 5;$
$P(5) = 4*5+1 = 21;$
$P(21) = 4*21+1 = 85;$
И так далее…

Ряд первого шага построен, хотя он может продолжаться до бесконечности. Перейдем к шагу два. Формулу перехода к шагу 2 можно выразить из нечетной формулы.
Зная, что мы собираемся делить результат $3n+1$ несколько раз, можно это записать как $2^{2\alpha}$, где $\alpha$— количество делений.

$P(k)={3n+1\over2^{2\alpha}};\\ 2^{2\alpha}P(k)=3n+1;\\ 3n= 2^{2\alpha}P(k)-1;$


Итоговая формула принимает вид:

$n(P(k),\alpha)={2^{2\alpha}P(k)-1\over3};$


Так же введем поправку на $\beta$, как $2^{2\alpha+\beta}$, чтобы не случилось варианта деления числа не кратного 3 на 3.

$n(P(k),\alpha,\beta)={2^{2\alpha+\beta}P(k)-1\over3};$


Давайте проверим формулу, так как альфа неизвестная, проверим для подряд идущих 5 альф:

$n(5,\alpha,\beta)={2^{2\alpha+\beta}*5-1\over3};$


$n(5,0,1)=(2^{0+1}*5-1)/3=3.$
$n(5,1,1)=(2^{2+1}*5-1) /3=13.$
$n(5,2,1)=(2^5*5-1)/3=53.$
$n(5,3,1)=(2^7*5-1)/3=213.$
$n(5,4,1)=(2^9*5-1)/3=853.$

Тем самым начинает образовываться последовательность второго шага. Однако, можно заметить, что 113 нет в последовательности, важно помнить, что формула рассчитывалась от 5.

n = 113 на самом деле:
$n(85,0,2)=(2^{0+2}*85-1)/3=113.$

Подытожим:

Множество от $Sa(n+1)$ порождается функцией $n(P(k),\alpha,\beta)$ от каждого элемента множества от $Sa(n)$.

Тогда зная это — можно еще сократить таблицу, убрав все порождения кратные альфа.

Sn (0) Sn (1) Sn (2) Sn (3) Sn (4) Sn (5) Sn (6) Sn (7) …
5 3 17 11 7 9 …
113 75 201 267 715 …
227 151 401 1073 1425 …


Чтобы было понятно, вот пример того, как элементы множества от $Sa(2)$ порождают элементы множества от $Sa(3)$ для альфа от 0 до 4.

P (k)=3 P (k)=113 P (k)=227
3 от α=0 порождает:
Ничего

13 от α=1 порождает:
17
69
277
1109
4437

53 от α=2 порождает:
35
141
565
2261
9045

213 от α=3 порождает:
Ничего

853 от α=4 порождает:
1137
4549
18197
72789
291157

 113 от α=0 порождает:
75
301
1205
4821
19285

453 от α=1 порождает:
Ничего

1813 от α=2 порождает:
2417
9669
38677
154709
618837

7253 от α=3 порождает:
4835
19341
77365
309461
1237845

29013 от α=4 порождает:
Ничего

 227 от α=0 порождает:
151
605
2421
9685
38741

909 от α=1 порождает:
Ничего

3637 от α=2 порождает:
4849
19397
77589
310357
1241429

14549 от α=3 порождает:
9699
38797
155189
620757
2483029

58197 от α=4 порождает:
Ничего


Объединив эти множества, получим множество от Sa (3):

17, 35, 69, 75, 141, 151, 277, 301, 565, 605, 1109, 1137, 1205, 2261, 2275, 2417, 2421, 4437, 4549, 4821, 4835, 4849, 9045, 9101, 9669, 9685, 9699, 17749, 18197, 19285, 19341, 19397, 19417…

Причем убрав степени $\alpha>0$» />, получим: <br /></p> <blockquote> <p>17, 75, 151…</p> </blockquote><p> То есть все сводится к: </p> <p><img src=

Почему где-то $\beta=2$, а где-то $\beta=1$?

Вернемся снова к последовательности A002450. Есть интересная зависимость:

$P(m)=(4^3m- 1)/3$ — не производит дочерних последовательностей.
$P(m)=(4^{3m+1}- 1)/3$ — производит дочерние последовательности при $\beta=2$.
$P(m)=(4^{3m+2}- 1)/3$ — производит дочерние последовательности при $\beta=1$.

Есть всего 3 потенциальных дочерних множества у числа.
Если применить к рекурсивной формуле, то:

Функция $n(\gamma,\alpha,\beta)$, где $\gamma$ — любое число кратное 3, образует пустое множество ⨂.

$A(n(\gamma),\alpha,\beta)=⨂.$

Функция $n(\lambda,\alpha,\beta)$, где $\lambda$ — любое число порожденное $\gamma$, при $\beta=2$ образует множество чисел K принадлежащих множеству натуральных чисел N.

$K(n(P(\gamma),\alpha,2))⊆ N.$

Функция $n(P(\lambda),\alpha,\beta)$, при $\beta=1$ образует множество чисел L принадлежащих множеству натуральных чисел N.

$L(n(P(\lambda),\alpha,1))⊆ N.$


Очевидно, что это каким-то образом можно свести к более строгой и доказательной формулировке.

Собственно, так и образуются последовательности в гипотезе Коллатца.
Осталась одна деталь. Необходимо из полученных нами множеств восстановить полноценные множества от абсолютных шагов.

Формула для нечетных:

$n(P(k),\alpha,\beta)={2^{2\alpha+\beta}P(k)-1\over3};$


Помимо нечетных, нужно восстановить множество четных. Для этого вспомним формулу:

$P(0,k)= 2*2^k.$


Осталось только соотнести все вместе:

$n(P(k),\alpha,\beta,\epsilon)={2^{2\alpha+\beta}P(k)-1\over3}*2^\epsilon.$


Окончательный вариант:

$n(k,\alpha,\beta,\epsilon)=2^\epsilon{2^{2\alpha+\beta}(4k+1)-1\over3};$


Тем самым любая k может породить последовательность.

Справедливо ли обратное, что любое из натуральных чисел определенно принадлежит к какой-либо последовательности от $n(k)$?

Если так, то вполне возможно, что Коллатц был прав.

Под финал пример реализации функции на javascript: 

function collatsSequence(
    number,
    sequenceLength,
    alpha,
    epsilon
) {

    // Массив множества от истинного шага,
    // определяемого number
    let set = [];

    // Сводим к нечетному
    while (number % 2 === 0) number /= 2;

    // Для каждого элемента последовательности, 
    // образованной от number, ограничиваясь sequenceLength
    for (let k = 0; k < sequenceLength; k++) {

        // Для каждой степени alpha
        for (let a = 0; a < alpha; a++) {

            // Пустое множество, пропускаем
            if (number % 3 === 0) break;

            // Рассчитываем для beta = 1
            let numWithBeta = (number * 2 ** (2 * a + 1) - 1) / 3;

            // Если число не делится на 3 при beta === 1
            // тогда точно делится на 3 при beta === 2
            if (Math.floor(numWithBeta) !== numWithBeta)

                // Рассчитываем для beta = 2
                numWithBeta = (number * 2 ** (2 * a + 2) - 1) / 3;

            // Заполняем множество четными до предела epsilon
            for (let e = 0; e < epsilon; e++)
                set.push(numWithBeta * 2 ** e);

        }

        // Переходим к следующему элементу последовательности
        number = number * 4 + 1;
    }

    return set;

}

console.log(
    collatsSequence(5, 5, 2, 2)
);

// [ 3, 6, 13, 26, 113, 226, 453, 906, 227, 454, 909, 1818 ]

© Habrahabr.ru