02.08.2018 19:01
Eponesh 9 2700 Источник
Меня привлекают такие задачи, как проблема Коллатца. Они просты в формулировке и отлично тренируют голову, в особенности алгоритмического мышления, что очень полезно программисту.

Формулируется задача довольно просто:
Берём любое натуральное число 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 ]

Комментарии (9)


  1. maslyaev
    02.08.2018 22:08
    #18952429

    while (number < 1) {
    while (number > 1) {


  1. zzzmmtt
    03.08.2018 09:08
    #18953227

    «Никаких истинных шагов делать не нужно, простым делением все сведется к единице.
    Зная это, можно отбросить из таблицы все числа, кратные двум.»
    Не все числа кратные 2 (это просто четные), а числа являющиеся двойкой в какой-либо степени, по вашей же формуле, которую можно записать как P(0,k)=2^(k+1).
    Вы убрали 10 из столбца с 1 истинным шагом, да оно кратно двум, но 1 истинный шаг всё равно требуется для него (равно как и для 20). И подобным образом вы теряете часть чётных, для которых нужно сделать 1 и более истинных шагов.
    В вашем же примере вы получаете " 3, 6, 13, 26, 113", потеряв 12, 24, 48 и т.д., да они сведутся к 3, далее 1 истинный шаг до 1, но последовательность неполна.


    1. Eponesh Автор
      03.08.2018 10:01
      #18953383

      Да, верно, идея статьи показать как образуется эта последовательность, отбросив четные, я как раз хотел показать их родителей, так же как отбрасывая степени альфа, например 13, 53 у тройки, можно показать, что множество нечетных порождается множеством нечетных своего же шага, то есть 3, 113… а вот они уже порождены только предыдущим шагом.
      А вот в конце статьи наоборот формула восстанавливающая всю последовательность. Та же самая тройка создает нечетных потомков, которые в свою очередь включая тройку создают бесчисленное множество четных чисел.


  1. stalinets
    03.08.2018 10:22
    #18953435

    Раньше был (и, вероятно, есть сейчас) проект распределённых вычислений «Collatz Conjecture», причём расчёты, в отличие от многих других GRID-проектов на BOINC и пр., велись на видеокартах, что давало на то время бешеную производительность. Это потом уже все начали считать биткоины. Сейчас считать на средних видюхах биткоин давно невыгодно, так что можно подключиться. В Вики написано, что есть и новый проект: «yoyo@Home».


  1. orion76
    03.08.2018 10:57
    #18953561

    т.к. к «единице» нас ведет операция «деления на 2», а чтобы достичь «единицы» делением на 2 делимое должно быть равно 2^n, то условие сводится к тому чтобы доказать, что данный алгоритм «движения к единице» должен достичь числа a
    где a = 2^b
    и a=3c+1 (если исходное число не равно 2^b)

    причем a >= 16, а следовательно b >= 4 (если исходное число не равно 2^b)


    1. Eponesh Автор
      03.08.2018 11:50
      #18953767

      Верно, как только мы достигаем числа, равного 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.


  1. oleg-x2001
    03.08.2018 19:43
    #18955687

    Пустое множество — ?, реализация на JavaScript-е…


  1. orion76
    04.08.2018 12:06
    #18956947

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


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


    Например
    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 что-то таблицы как-то странно маркдауном рисуются


  1. Milliard
    05.08.2018 12:37
    #18958963

    Интересно, что если расширить область значений с натуральных до целых чисел, то помимо зацикленной последовательности 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.
    Особенно интересна последняя последовательность, т.к. она довольно длинная и включает в себя большие по абсолютной величине значения.