“Действительно ли любое число в конце концов становится 1?” ── Играем с гипотезой Коллатца

Всем привет! Это Кенджи.

Внезапный вопрос: когда вы слышите о “правиле, по которому любое число в итоге превращается в 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. Пришлось сделать немало крюков, но в итоге мы на финише!

Кстати, даже если мы начнем с 29, оно достигнет 1 таким же образом.

1
pythonprint(collatz(29))

При запуске:

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

Вот в чем крутизна.

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

Если вы подумали об этом, то вы очень проницательны. На самом деле, с помощью компьютеров это было проверено вплоть до “2 в 68-й степени”, и все они достигают 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”.

Вывод: Этот мир действительно странный

Итак, это гипотеза Коллатца.

Хотя она очень проста
Никто не может ее доказать
Это огромная проблема в математическом мире

Она оказалась чем-то вроде сгустка тайн.

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

Гипотеза Коллатца