Гипотеза Коллатца утверждает: если начать с положительного целого числа и повторять правила «чётное разделить на 2, нечётное умножить на 3 и прибавить 1», последовательность в конце концов достигнет 1. Это именно гипотеза, а не доказанное для всех чисел правило.
Например, для 7 получается 7 → 22 → 11 → 34 → 17 → 52 → 26 → 13 → 40 → 20 → 10 → 5 → 16 → 8 → 4 → 2 → 1. После единицы повторяется цикл 1 → 4 → 2 → 1. Проверить отдельную цепочку можно, но это ещё не доказательство для всех положительных целых чисел.
Решена ли гипотеза Коллатца?
Нет. На дату обновления статьи общепринятого доказательства или опровержения гипотезы Коллатца нет. Проверка огромного количества отдельных чисел подтверждает гипотезу только для проверенного диапазона. Математическое доказательство должно охватывать сразу все натуральные числа, которых бесконечно много.
| Что известно | Что пока не доказано |
|---|---|
| Для каждого проверенного компьютером начального числа цепочка пришла к 1 | Что так произойдёт для любого натурального числа без исключений |
| Для многих классов чисел получены частичные результаты | Что не существует неизвестной бесконечной цепочки или другого цикла |
Пример последовательности для числа 6
6 → 3 → 10 → 5 → 16 → 8 → 4 → 2 → 1. Для чётных чисел применяем деление на 2, для нечётных — 3n + 1. Через восемь переходов получаем единицу.
Для опровержения хватило бы одного положительного целого числа, чья цепочка никогда не достигнет 1. Но долгое вычисление само по себе не докажет, что такого достижения не будет позже. Чтобы опровергнуть гипотезу, нужно обосновать иной цикл или бесконечное поведение, а не просто дождаться конца времени работы программы.
Два правила вычисления
На каждом шаге проверяют чётность положительного целого числа n и выбирают одно из двух действий:
- чётное → делим на 2 (n ÷ 2);
- нечётное → умножаем на 3 и прибавляем 1 (3·n + 1).
Для начала можно сравнить цепочки небольших положительных целых чисел. Возьмём 6: оно чётное, делим — 3. Тройка нечётная: 3·3+1 = 10. Дальше 10 → 5 → 16 → 8 → 4 → 2 → 1. Восемь шагов — и пришли к единице. У вычисленных цепочек бывают разные длины пути; сравнение примеров помогает заметить, насколько непохожими бывают траектории соседних чисел, но не доказывает гипотезу для всех начал.
Почему эти числа называют «градинами»
Если изобразить значения последовательности на графике, часто видны подъёмы и спады: нечётный шаг увеличивает число, а чётный уменьшает. Отсюда название hailstone sequence, «последовательность градин»: рисунок напоминает движение градины вверх и вниз в облаке. Аналогия помогает запомнить вид вычисленной цепочки, но не доказывает достижение единицы. У конкретного примера конец можно проверить вычислением; утверждение обо всех возможных началах остаётся открытым.
Соседние начальные числа могут давать очень разные вычисленные цепочки. Для 27 максимальное значение до первой единицы равно 9232, а число переходов — 111. Для 28 достаточно 18 переходов. Простая общая формула времени достижения единицы для произвольного положительного целого начала неизвестна. Это не доказательство невозможности такой формулы: прежде всего остаётся нерешённым вопрос, всегда ли это время конечно.
Три взгляда на одну загадку
Как последовательность
Самый простой взгляд: мы строим цепочку чисел, где каждое следующее получено из предыдущего. Цепочка обрывается, как только мы попадаем в 1.
Как петля
После 1 алгоритм продолжает работать: 3·1+1=4, затем 4 → 2 → 1. Гипотеза утверждает, что каждая последовательность с положительным целым началом попадёт в этот цикл. Одной проверки отсутствия других циклов недостаточно: отдельно нужно исключить последовательности, которые никогда не входят в цикл и не достигают единицы.
Как дерево
Можно повернуть задачу наоборот: начать с 1 и спрашивать, какие числа в неё ведут. Тогда из единицы вырастает гигантское ветвящееся дерево, и гипотеза Коллатца говорит, что на этом дереве рано или поздно окажется каждое натуральное число — ни одно не потеряется.
Зачем это взрослым: цена «простых» программ
В программе достаточно повторять правило, пока n не станет равным 1. Для отдельного входа завершение подтверждается полученной цепочкой. Но доказательство завершения этого цикла для всех положительных целых входов фактически решило бы гипотезу Коллатца. Здесь полезно различать два вопроса. Для произвольных программ не существует универсального алгоритма, решающего проблему остановки. Из этого, однако, не следует, что именно гипотеза Коллатца недоказуема: отсутствие доказательства сейчас не равно доказательству невозможности решить задачу.
Как учебное упражнение цепочка позволяет потренировать цикл, проверку чётности, счётчик шагов и хранение максимального значения. Практическая программа должна ограничивать число шагов и контролировать переполнение выбранного числового типа. Сообщение «лимит шагов исчерпан» означает только, что вычисление остановлено по техническому ограничению. Нельзя выдавать его за найденное опровержение или обещать, что программа мгновенно обработает любое введённое число.
Задачи для самопроверки
Задача 1. Постройте путь числа 11. За сколько шагов оно дойдёт до 1?
Показать решение
11 → 34 → 17 → 52 → 26 → 13 → 40 → 20 → 10 → 5 → 16 → 8 → 4 → 2 → 1. Получилось 14 шагов.
Задача 2. Какое из чисел дойдёт до 1 быстрее: 8 или 16?
Показать решение
16 → 8 → 4 → 2 → 1 — это 4 шага. 8 → 4 → 2 → 1 — 3 шага. Быстрее доходит 8. Вообще степени двойки (2, 4, 8, 16, 32…) — самые «спокойные» числа: они просто делятся пополам до самой единицы без единого взлёта.
Задача 3. Цепочка достигла 16. Можно ли теперь гарантировать достижение 1? А доказано ли, что каждая цепочка когда-нибудь достигнет степени двойки?
Показать решение
После 16 ответ известен: 16 → 8 → 4 → 2 → 1. Вообще после 2ᵏ, где k — неотрицательное целое, остаётся k делений на 2. Но достижение какой-нибудь степени двойки для любого положительного целого начала не доказано. Именно здесь заканчивается проверенный частный случай и начинается общее утверждение гипотезы.
Немного истории
Задача связана с немецким математиком Лотаром Коллатцем и обычно датируется 1937 годом. В литературе встречаются названия «проблема 3n+1» и «сиракузская проблема». Разные названия относятся к одной основной идее, но алгоритмы подсчёта шагов могут отличаться. Например, иногда нечётный шаг 3n+1 сразу объединяют с последующим делением на 2. Поэтому при сравнении таблиц важно сначала уточнить, что автор считает одним переходом.
Компьютерная проверка подтверждает достижение единицы только для явно указанного конечного диапазона. За его пределами остаётся бесконечно много положительных целых чисел. Если программа проверила все начала от 1 до N, это сильный результат о данном диапазоне, но не об N+1 и не обо всех числах сразу. Проверка примеров ищет контрпример и уточняет картину; доказательство должно объяснить, почему исключений не бывает.
Частичный результат Тао: что значит «почти все»
В работе 2019 года Теренс Тао доказал частичный результат: если выбрать любую функцию f(n), стремящуюся к бесконечности, то для «почти всех» начальных n последовательность когда-нибудь опустится ниже f(n). Здесь «почти все» понимается в специальном смысле логарифмической плотности. Граница f(n) зависит от начального числа: теорема не говорит, что все цепочки дойдут до 1 или до одной фиксированной маленькой константы.
Чтобы почувствовать разницу, сравните три утверждения: «мой пример дошёл до 1», «все числа до заданной границы дошли до 1» и «любое положительное целое число дойдёт до 1». Первые два можно подтвердить конечным вычислением. Третье требует общего доказательства. Эта граница между наблюдением и доказательством — главный вывод задачи, даже если вы исследовали только несколько небольших начальных чисел.
Частые вопросы
Гипотеза Коллатца доказана или нет?
Нет, общепринятого доказательства или опровержения нет. Компьютерные проверки охватывают большие конечные диапазоны, но не заменяют доказательства для бесконечного множества положительных целых начал. Частичные теоремы тоже не утверждают завершение каждой цепочки.
Почему её называют задачей 3n+1?
Из-за главного правила: для нечётного числа мы вычисляем 3·n + 1. Именно этот шаг «подбрасывает» числа вверх и делает поведение последовательности таким непредсказуемым.
Что будет, если использовать 5n+1 вместо 3n+1?
Уже появляется проверяемый цикл без единицы: 13 → 66 → 33 → 166 → 83 → 416 → 208 → 104 → 52 → 26 → 13. Для нечётных здесь использовано 5n+1, для чётных — деление на 2. Повторение 13 доказывает, что именно эта цепочка не придёт к 1. Это контрпример для изменённого правила, а не для гипотезы 3n+1.
Можно ли получить приз за решение?
Математическое решение и получение премии — разные вещи. Выплата возможна только по условиям конкретного конкурса; из самой формулировки гипотезы никакое денежное вознаграждение не следует. Поэтому обещание приза требует отдельного объявления организатора, а не только ссылки на известность задачи.
Что будет считаться доказательством гипотезы?
Доказательство должно охватывать все положительные целые начала и исключать другие циклы и цепочки, не достигающие 1. Большая таблица примеров или ограниченный компьютерный перебор этих требований не заменяют. Для опровержения, напротив, достаточно одного строго установленного контрпримера.
Есть ли практическая польза от этой задачи?
Прямой пользы немного, но она стала классическим примером в теории чисел и информатике — особенно при изучении проблемы остановки, рекурсии и непредсказуемости простых алгоритмов. Главная её ценность — в том, как она показывает границы наших знаний.
Читайте также
- Треугольник Паскаля: правило, формулы и где он встречается
- Бесконечность в математике: что это такое и почему бывает разного размера
- Фракталы: что это, примеры в природе и формула красоты
- Парадокс дня рождения: почему 23 человек хватит для совпадения
- Магический квадрат — что это такое, виды и как составить