Правда ли, что «любое число в конце концов сводится к 1»? ── Играем с гипотезой Коллатца

Всем привет! Я kenji.

Вдруг возник вопрос: если вам скажут о «правиле, по которому любое число в конечном итоге становится равным 1», разве это не покажется немного странным?

Например, 19, или 87, или даже 1000000. Если вы будете изменять число в соответствии с определенным правилом, оно по какой-то причине в конечном итоге сойдется к «1».

Такая история, похожая на сон, называется гипотезой Коллатца (Collatz Conjecture).

Что же такое гипотеза Коллатца?

Сначала давайте познакомимся с правилами.

Старт: выберите любое положительное целое число
Операция:
- Если четное → разделить пополам (n → n / 2)
- Если нечетное → умножить на 3 и прибавить 1 (n → 3n + 1)

Если повторять это снова и снова, суть гипотезы заключается в том, что любое число в конечном итоге достигнет 1.

Например, если начать с 6:

1
6 → 3 → 10 → 5 → 16 → 8 → 4 → 2 → 1

Оно действительно стало «1». С возвращением!

Давайте проверим в коде: Коллатц на Python

Итак, в таких случаях быстрее всего проверить это с помощью кода! Давайте выведем «последовательность Коллатца» на Python.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
def collatz(n):
    steps = [n]
    while n != 1:
        if n % 2 == 0:
            n = n // 2
        else:
            n = 3 * n + 1
        steps.append(n)
    return steps

# Пример: начнем с 19
print(collatz(19))

Результат выполнения:

1
[19, 58, 29, 88, 44, 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1]

Оно прекрасно достигает 1. Несмотря на то, что пришлось немного поплутать, в конце концов — успешный финиш!

Кстати, если начать с 27, оно также достигнет 1.

1
print(collatz(27))

Результат выполнения

1
2
3
4
5
6
7
8
[27, 82, 41, 124, 62, 31, 94, 47, 142, 71, 214, 107, 322, 161, 484, 242,
121, 364, 182, 91, 274, 137, 412, 206, 103, 310, 155, 466, 233, 700, 350,
175, 526, 263, 790, 395, 1186, 593, 1780, 890, 445, 1336, 668, 334, 167,
502, 251, 754, 377, 1132, 566, 283, 850, 425, 1276, 638, 319, 958, 479,
1438, 719, 2158, 1079, 3238, 1619, 4858, 2429, 7288, 3644, 1822, 911,
2734, 1367, 4102, 2051, 6154, 3077, 9232, 4616, 2308, 1154, 577, 1732,
866, 433, 1300, 650, 325, 976, 488, 244, 122, 61, 184, 92, 46, 23, 70, 35,
106, 53, 160, 80, 40, 20, 10, 5, 16, 8, 4, 2, 1]

Ого, это занимает целых 111 шагов!

Более того, по пути есть моменты, когда значение раздувается до более чем 9000. Это тот самый сценарий, когда вы очень долго плутаете перед тем, как достичь цели.

И что же в этом такого удивительного?

Что удивительного в этой гипотезе, так это то, что:

Хотя это и не доказано, кажется, что какое бы число вы ни взяли, оно превратится в 1

Вот в чем дело.

А? А как насчет 1 триллиона или 10 квадриллионов…?

Те, кто так подумал, обладают острым умом. На самом деле, с помощью компьютеров это было проверено вплоть до «2 в 68 степени», и все они достигают 1. Невероятно…

Но теоретически не было доказано, что «так будет со всеми числами». В мире математики это называется «нерешенной проблемой».

Почему оно становится «1»? Подход с точки зрения теории вероятностей (математический контекст)

То, что любое число в конечном итоге становится 1, кажется магией, но с вероятностной точки зрения существует рациональное объяснение из разряда «ну, так и должно было быть».

Если применить 3n + 1 к нечетному числу $n$, ответ всегда будет четным. Следовательно, на следующем шаге оно обязательно разделится на 2, фактически становясь $\frac{3n + 1}{2} \approx 1.5n$.

Затем вероятность того, что это число снова окажется четным, составляет $\frac{1}{2}$. Если оно четное, оно снова делится на 2, становясь $0.75n$, что меньше исходного числа.

Хотя это и не является математически строгим доказательством, известно, что если взять среднее геометрическое «множителей» при переходе от одного нечетного числа к следующему нечетному числу, оно составит примерно $\frac{3}{4}$ (эвристическая вероятностная модель). Другими словами, поскольку значения имеют тенденцию уменьшаться в среднем, они в конечном итоге падают, словно затягиваемые в 1.

Что будет, если немного изменить правила? (Сравнение с другими гипотезами)

Возникает естественный вопрос: «А что, если вместо умножения на 3 мы будем умножать на 5?». На самом деле, это известно как проблема $5n + 1$, и в этом случае не все числа сходятся к 1.

В случае $5n + 1$ было подтверждено существование нескольких различных циклов (петель), и также указывается на возможность существования чисел, которые будут бесконечно увеличиваться (расходимость). Кроме того, в случае проблемы $3n - 1$, помимо цикла «$1 \to 2 \to 1$», существует другой цикл, такой как «$5 \to 14 \to 7 \to 20 \to 10 \to 5$».

Из этого видно, насколько тонко сбалансировано свойство гипотезы Коллатца «всё сходится к 1 (цикл $4 \to 2 \to 1$)».

Достижения человечества ①: Пределы компьютерного перебора

В настоящее время математики и энтузиасты компьютерных наук по всему миру продолжают вычислять гипотезу Коллатца, используя распределенные вычисления (проекты, объединяющие вычислительные мощности ПК по всему миру) и графические процессоры (GPU).

По состоянию на 2020 год компьютеры подтвердили, что гипотеза Коллатца верна (в конечном итоге становится 1) для всех начальных значений, равных или меньших поразительного $2^{68}$ (около 295 квинтиллионов).

Однако в мире математики нельзя сказать: «Мы проверили до 295 квинтиллионов, поэтому всё верно». В море чисел, которое продолжается бесконечно, даже $2^{68}$ — это всего лишь «первая капля».

Достижения человечества ②: Неразрешимость и прорыв Теренса Тао

В ответ на вопрос: «Почему никто не может это доказать?», британский гений математики Джон Конвей доказал в 1972 году, что слегка расширенная версия гипотезы Коллатца «неразрешима» (Тьюринг-полна). Это ужасающий факт, затрагивающий саму суть информатики: в зависимости от правил «в принципе не существует алгоритма для определения того, будет ли достигнута 1». Существует даже вероятность того, что сама гипотеза Коллатца является недоказуемым утверждением в рамках современной математики.

Однако в 2019 году наконец-то произошел крупный прорыв. Один из величайших гениев математики современности, Теренс Тао (Terence Tao), используя методы дифференциальных уравнений в частных производных и теории вероятностей, доказал, что «(хотя строго нельзя сказать, что для всех) почти для всех начальных значений последовательность Коллатца в конечном итоге достигает значения, которое намного меньше исходного числа».

Хотя это и не полное доказательство того, что «всё становится 1», оно вызвало переполох в математическом мире всего мира, как исторический рубеж, на котором человечество ближе всего подошло к истине гипотезы Коллатца.

Кто такой мистер Коллатц?

Итак, дочитав до этого момента, вы наверняка подумали: «А кто вообще такой этот Коллатц?». Я должным образом представлю его!

Имя: Лотар Коллатц (Lothar Collatz)
Гражданство: Германия
Годы жизни: 1910 — 1990
Профессия: Математик (работал в области функционального анализа и теории чисел)

Он предложил эту гипотезу в 1937 году, и с тех пор, на протяжении более 80 лет, никто не смог ни доказать, ни опровергнуть ее.

Кстати, эта проблема настолько проста, но в то же время настолько глубока, что даже знаменитый Пал Эрдёш (супер-известный математик) сказал:

«Математика еще не созрела для решения проблем Коллатца»

Другими словами, существует теория, что математика человечества еще не доросла до этой загадки…

«Сложные формулы» не нужны

Прелесть гипотезы Коллатца в том, что играть с ней может каждый.

Вам понадобятся только бумага и ручка. Если вы напишете код на Python, то сможете проверять ее автоматически. И при всем этом передовые математики бросают ей серьезный вызов.

Разве это не захватывающе?

Бонус: Код для пакетной проверки

Я также оставлю код для тестирования множества различных чисел сразу.

1
2
3
for n in range(1, 21):
    steps = collatz(n)
    print(f"{n}: {steps} (Количество шагов: {len(steps)-1})")

Это сразу же выдаст последовательности Коллатца от «1 до 20».

Заключение: Этот мир все-таки удивителен

Вот вам и гипотеза Коллатца.

Несмотря на ее огромную простоту
Никто не может ее доказать
И это огромная проблема в математическом мире

Это было похоже на сгусток тайн.

Даже новички в программировании могут попробовать ее, так что обязательно поиграйте с ней!

Что такое гипотеза Коллатца? Проверка на Python нерешенной математической задачи, где любое число в итоге становится 1