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

Простейшее правило, которое не может одолеть вся современная математика: дели или умножай — и всё придёт к единице.

Гипотеза Коллатца — утверждение, что для любого натурального числа последовательность «чётное делим на 2, нечётное умножаем на 3 и прибавляем 1» всегда достигает единицы.

Правило формулируется в одну строку, его поймёт школьник. Но Пауль Эрдёш, один из величайших математиков XX века, сказал: «Математика ещё не созрела для таких задач». Гипотеза проверена для чисел до $2^{68}$ и для всех держится — но доказательства нет.

Правило Коллатца

Стартуем с числа $n$ и применяем функцию

$$f(n) = \begin{cases} n/2, & n \text{ чётное}, \\ 3n + 1, & n \text{ нечётное}. \end{cases}$$

Например, для $n = 6$: $6 \to 3 \to 10 \to 5 \to 16 \to 8 \to 4 \to 2 \to 1$ — восемь шагов. Длину пути до единицы называют временем остановки. Поведение этого времени совершенно непредсказуемо: близкие числа могут давать совсем разную длину.

Симулируем траектории

def collatz_steps(n):
    steps = 0
    peak = n
    while n != 1:
        n = n // 2 if n % 2 == 0 else 3 * n + 1
        peak = max(peak, n)
        steps += 1
    return steps, peak

for start in [6, 7, 27, 97]:
    steps, peak = collatz_steps(start)
    print(f"n={start:>3}: шагов до 1 = {steps:>3}, максимум в пути = {peak}")

Вывод:

n=  6: шагов до 1 =   8, максимум в пути = 16
n=  7: шагов до 1 =  16, максимум в пути = 52
n= 27: шагов до 1 = 111, максимум в пути = 9232
n= 97: шагов до 1 = 118, максимум в пути = 9232

Как работает под капотом

Посмотрите на строку с числом 27: невинное двузначное число делает 111 шагов и взлетает до 9232, прежде чем смиренно прийти к единице! Это и есть знаменитая непредсказуемость Коллатца. Чётные шаги уменьшают число вдвое, нечётные — увеличивают примерно втрое, но за каждым нечётным шагом обязательно идёт чётный (ведь $3n+1$ чётно при нечётном $n$). В среднем спуск перевешивает подъём, и потому числа «обычно» падают к единице — но строгого доказательства, что так будет всегда и не возникнет бесконечного цикла или убегания, нет.

Частые ошибки

Не путайте время остановки (число шагов) с максимумом траектории — это разные вещи: у 27 шагов 111, а пик 9232. Не думайте, что монотонность есть: число то растёт, то падает. И главное — помните, что это гипотеза: проверка для триллионов чисел не есть доказательство для всех.

Итог

• Правило: чётное делим на 2, нечётное превращаем в $3n+1$.
• Гипотеза: любое число в итоге приходит к 1.
• Время остановки крайне нерегулярно (27 даёт 111 шагов и пик 9232).
• Гипотеза проверена для огромных диапазонов, но не доказана.