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

В виде отображения правило гипотезы Коллатца записывается так:

Полёт идёт от $n$ через $f(n)$, $f(f(n))$ и так далее и заканчивается при достижении 1: дальше он лишь повторял бы цикл 1 → 4 → 2 → 1. Гипотеза утверждает, что туда приходит любое положительное целое число. Здесь можно запускать числа в полёт по одному или группой, даже если в них сотни цифр. Можно сравнить их с приближённым рассуждением, которое делает гипотезу столь правдоподобной, и увидеть, почему это рассуждение не является доказательством.

По горизонтали отложено число шагов, по вертикали — значение на логарифмической шкале. Если выбрать Значение, получится привычная картина градин. Каждое число группы — цветная линия, поэтому участок, по которому проходит много чисел, окрашен сильнее: светлее на тёмном фоне и темнее на светлом. Рассматриваемое число выделено, а красная точка отмечает его текущее положение. Полёты трудно предсказать: 27 поднимается до 9 232 и достигает 1 за 111 шагов, а 28 — за 18.

Почему в неё верят? Шаг с нечётным числом всегда даёт чётное, поэтому объединим его со следующим делением пополам в один сокращённый шаг. Теперь предположим, что чётности этих шагов ведут себя как независимые броски честной монеты. В половине случаев $n$ умножается примерно на 3/2, а в другой половине — на 1/2. Значит, в среднем один сокращённый шаг изменяет $\ln n$ на

Тогда числа должны уменьшаться, обычно до 3/4 прежнего значения за каждые два сокращённых шага. На логарифмической оси этот дрейф показан пунктирной линией, которую рисуют для группы Близкие по величине из 100 чисел или более. Линия не учитывает приземление: числа, достигшие 1, остаются внизу, поэтому ближе к концу средняя высота группы на этой оси снижается медленнее линии.

Броски монеты — лишь модель среднего поведения чисел. Гипотеза же говорит о каждом положительном целом числе: единственный полёт, никогда не достигающий 1, опроверг бы её.

Отрицательные числа показывают, что упускает рассуждение. То же правило образует на них циклы; известны три, например −5 → −14 → −7 → −20 → −10 → −5. Модель с монетой предсказывает уменьшение и здесь, но полный обход любого цикла изменяет $\log|n|$ ровно на 0. Средний дрейф вниз не исключает цикл, в том числе среди положительных чисел.

Коралл разворачивает полёты: при росте назад от 1 пути группы образуют дерево. Каждое ребро поворачивается относительно предыдущего на $+\alpha$, если новое число чётное, и на $-\alpha \log_2 3$, если нечётное; α задаётся параметром Изгиб. При движении назад от 1 чётный шаг удваивает число и увеличивает его $\log_2$ на 1, а нечётный уменьшает его чуть больше чем на $\log_2 3$. Поэтому ребро, приходящее в n, в сумме повёрнуто от вертикали вверх на $\alpha \log_2 n$, плюс небольшая добавка за каждый нечётный шаг: его поворот записывает величину n. Вдоль ветви направление поднимается и опускается вместе с числами одного полёта, так что каждая ветвь — свёрнутый полёт. Ветви сливаются там, где встречаются полёты. На этом языке гипотеза утверждает, что дерево, выросшее из 1, содержит каждое положительное целое число.

Задачу обычно связывают с Лотаром Коллатцем, который ставил подобные вопросы в 1930-х годах. Коралл основан на «Collatz seaweed» Эдмунда Харрисса (2016).