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

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

    Формулируется задача довольно просто:
    Берём любое натуральное число 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$, получим:
    17, 75, 151 …
    То есть все сводится к:

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



    Почему где-то $\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 ]
    

    Только зарегистрированные пользователи могут участвовать в опросе. Войдите, пожалуйста.

    Как считаете, верна ли гипотеза Коллатца?
    Поделиться публикацией
    Комментарии 10
      0
      while (number < 1) {
      while (number > 1) {
        0
        «Никаких истинных шагов делать не нужно, простым делением все сведется к единице.
        Зная это, можно отбросить из таблицы все числа, кратные двум.»
        Не все числа кратные 2 (это просто четные), а числа являющиеся двойкой в какой-либо степени, по вашей же формуле, которую можно записать как P(0,k)=2^(k+1).
        Вы убрали 10 из столбца с 1 истинным шагом, да оно кратно двум, но 1 истинный шаг всё равно требуется для него (равно как и для 20). И подобным образом вы теряете часть чётных, для которых нужно сделать 1 и более истинных шагов.
        В вашем же примере вы получаете " 3, 6, 13, 26, 113", потеряв 12, 24, 48 и т.д., да они сведутся к 3, далее 1 истинный шаг до 1, но последовательность неполна.
          0
          Да, верно, идея статьи показать как образуется эта последовательность, отбросив четные, я как раз хотел показать их родителей, так же как отбрасывая степени альфа, например 13, 53 у тройки, можно показать, что множество нечетных порождается множеством нечетных своего же шага, то есть 3, 113… а вот они уже порождены только предыдущим шагом.
          А вот в конце статьи наоборот формула восстанавливающая всю последовательность. Та же самая тройка создает нечетных потомков, которые в свою очередь включая тройку создают бесчисленное множество четных чисел.
          0
          Раньше был (и, вероятно, есть сейчас) проект распределённых вычислений «Collatz Conjecture», причём расчёты, в отличие от многих других GRID-проектов на BOINC и пр., велись на видеокартах, что давало на то время бешеную производительность. Это потом уже все начали считать биткоины. Сейчас считать на средних видюхах биткоин давно невыгодно, так что можно подключиться. В Вики написано, что есть и новый проект: «yoyo@Home».
            +1
            т.к. к «единице» нас ведет операция «деления на 2», а чтобы достичь «единицы» делением на 2 делимое должно быть равно 2^n, то условие сводится к тому чтобы доказать, что данный алгоритм «движения к единице» должен достичь числа a
            где a = 2^b
            и a=3c+1 (если исходное число не равно 2^b)

            причем a >= 16, а следовательно b >= 4 (если исходное число не равно 2^b)
              0
              Верно, как только мы достигаем числа, равного 2^n, останется только делить, чтобы достичь единицы. В табличке множество порожденное 2^n — это множество от Sa(0) — шаг 0, то есть только деление.

              Операция 3n+1 не отдаляет число от единицы, а наоборот приближает его.
              Над абсолютно любым числом множества Sa(1) {5, 10, 20, 21...} (с учетом сведения этого числа сначала к нечетному) операцией 3n+1, мы совершим инъекцию в множество от Sa(0), то есть получим 2^n.

              Так же как любое число множества Sa(2) {3,6,12,13...} сведенное к нечетному, операцией 3n+1 инъектируется в множество от Sa(1) а оно уже в множество от Sa(0).
              An( Sa(n) ) ->… -> A2( Sa(2) ) -> A1( Sa(1) ) -> A0( Sa(0) ).

              Так что в этом смысле операция 3n+1 стремится свести число в множество чисел 2^n.
              А операция n / 2, так скажем не то что стремится свести число к единице, она лишь стремится свести любое четное число к его родителю (4 -> 1, 10 -> 5, 24 -> 3...). А родитель чисел 2^n множества A0 всего один — «единица», ровно как во множестве A1 родитель только один — «5». Из формулы: P(0)=1, P(1)=5.
              0
              Пустое множество — ⨂, реализация на JavaScript-е…
                0

                В глубокой молодости любил голову подобными головоломками поломать.
                Сейчас тоже приходиться, но головоломками из более "практической" сферы-)


                Любопытная закономерность данного алгоритма.
                Некоторым простым числам и предшествующим им четным числам для достижения единицы необходимо одинаковое кол-во шагов.
                Причем последовательность результатов шагов сходиться для обоих случаев (и четного, и последующего простого числа) на одном и том же шаге к одному и тому же числу, а далее шаги(последовательность результатов шагов) полностью идентичны.


                Например
                N
                чет
                прост


                0
                12
                13

                1
                6
                40

                2
                3
                20

                3
                10
                10



                N
                чет
                прост


                0
                28
                29

                1
                14
                88

                2
                7
                44

                3
                22
                22



                N
                чет
                прост


                0
                100
                101

                1
                50
                304

                2
                25
                152

                3
                76
                76



                PS что-то таблицы как-то странно маркдауном рисуются

                  0
                  Интересно, что если расширить область значений с натуральных до целых чисел, то помимо зацикленной последовательности 4, 2, 1, к которой приходят (предположительно) все положительные целые, появятся несколько последовательностей для отрицательных целых:
                  -2,-1;
                  -20,-10,-5,-14,-7;
                  -272,-136,-68,-34,-17,-50,-25, -74,-37,-110,-55,-164,-82,-41,-122,-61,-182,-91.
                  Особенно интересна последняя последовательность, т.к. она довольно длинная и включает в себя большие по абсолютной величине значения.
                    0
                    Вернемся снова к последовательности A002450. Есть интересная зависимость:...

                    полагаю, здесь опечатка.

                    Должно быть
                    P(m)=(4^(3m)- 1)/3
                    (TeX notation)

                    Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

                    Самое читаемое