Гіпотеза Коллатца — також відома як задача 3n+1 — одна з найвідоміших нерозв'язаних проблем математики. Починаючи з будь-якого натурального числа, ви багаторазово застосовуєте просте правило: якщо число парне, ділите його на 2; якщо непарне, множите на 3 і додаєте 1. Отримана послідовність, яку називають градоподібною (hailstone), завжди, здається, зрештою досягає 1, але ніхто ніколи не довів цього для кожного натурального числа. Цей візуалізатор дозволяє простежувати окремі градоподібні шляхи, порівнювати часи зупинки для сотень чисел за допомогою теплової карти й досліджувати дерево збіжності, що показує, які числа ведуть до 1.
Гіпотезу вперше досліджував Лотар Коллатц приблизно 1937 року, і відтоді вона привертала увагу багатьох провідних математиків, зокрема Пола Ердеша, який, за переказами, сказав: «Математика ще не готова для таких проблем». Попри оманливо просте формулювання, гіпотеза Коллатца торкається глибоких ідей теорії чисел, динамічних систем і обчислювальної складності.
Гіпотеза Коллатца стверджує, що для будь-якого натурального числа n багаторазове застосування правила n/2 (якщо n парне) або 3n+1 (якщо n непарне) зрештою дасть значення 1. Послідовність чисел, що виникає при цьому, називають градоподібною послідовністю, бо значення хаотично зростають і спадають, перш ніж обвалитися до 1. Попри те, що гіпотезу перевірено обчисленнями для всіх чисел приблизно до двох у степені шістдесят вісім, у загальному вигляді вона залишається недоведеною.
Введіть початкове число в поле або перетягніть повзунок, а потім спостерігайте, як вкладка «Послідовність» простежує повний градоподібний шлях на графіку в логарифмічному масштабі. Скористайтеся кнопкою «Анімація», щоб покроково пройти шлях кадр за кадром. Перейдіть на вкладку «Теплова карта», щоб побачити часи зупинки для всіх чисел до обраного діапазону, зафарбовані від синього (короткий) до червоного (довгий). Вкладка «Дерево» показує зворотне дерево Коллатца, розкриваючи, як числа сходяться до 1 — блакитні ребра підсвічують шлях вашого поточного початкового числа.
Починаючи з 27, послідовність досягає піку 9232, перш ніж зрештою опуститися до 1 за 111 кроків — драматичний виліт для такого малого початкового числа. Це відбувається тому, що правило 3n+1, застосоване до непарних чисел, може тимчасово підсилювати значення далеко за межі початкового вхідного числа, тоді як ділення n/2 повільно повертає їх назад униз. Відношення максимального значення до початкового числа для n=27 становить близько 342, що робить цей приклад одним із найяскравіших у діапазоні малих чисел.
Час зупинки (також званий повним часом зупинки) числа n — це кількість ітерацій правила Коллатца, потрібних, перш ніж послідовність вперше досягне 1. Дослідження часів зупинки виявляє фракталоподібну структуру: сусідні цілі числа можуть мати надзвичайно різні часи зупинки, як видно на тепловій карті. Математики аналізують часи зупинки статистично — середній час зупинки зростає приблизно як логарифм n, але окремі значення коливаються надзвичайно сильно. Розуміння розподілів часів зупинки — один із напрямів, який дослідники використовують, щоб з'ясувати, чи можна довести гіпотезу за допомогою ймовірнісних аргументів.
Станом на 2026 рік гіпотеза Коллатца залишається недоведеною. У 2019 році Теренс Тао опублікував знакову статтю, яка показала, що «майже всі» послідовності Коллатца справді зрештою досягають 1 у точному ймовірнісному сенсі, але повного доведення для кожного натурального числа досі немає. Жодного контрприкладу так і не знайдено, попри вичерпні комп'ютерні пошуки, що охоплюють числа до двох у степені шістдесят вісім. Цю проблему вважають однією з найвідоміших відкритих задач математики саме тому, що її формулювання настільки просте, тоді як розв'язання, схоже, вимагає принципово нових математичних ідей.
Поширена помилка полягає в тому, що оскільки гіпотезу перевірено для трильйонів чисел, вона неодмінно правдива і потребує лише рутинного доведення. Насправді в теорії чисел є багато гіпотез, які справджуються для величезних діапазонів випадків, але зрештою не виконуються для якогось надзвичайно великого числа. Складність із гіпотезою Коллатца в тому, що поведінка послідовності здається справді хаотичною — немає очевидного патерну чи алгебраїчної структури, яка дозволила б довести її методом індукції чи прямим аналізом. Сама лише величезна кількість перевірених випадків не замінює математичного доведення.
Лотару Коллатцу, німецькому математику, приписують першу постановку цієї проблеми приблизно 1937 року, хоча він міг розглядати її вже 1932-го. Гіпотеза поширювалася математичними колами здебільшого з вуст в уста і стала широко відомою після обговорень на міжнародних конференціях у 1950-х і 1960-х роках. Відтоді вона з'являлася під багатьма назвами: проблема Сіракуз, проблема Какутані, проблема Улама та алгоритм Гассе, що відображає те, наскільки незалежно її переоткривали різні дослідники. Назва «гіпотеза Коллатца» стала стандартною лише поступово.
Гіпотеза Коллатца пов'язана з вивченням ітерованих відображень і динамічних систем на цілих числах. Дерево Коллатца, показане в цьому візуалізаторі, — приклад структури бінарного дерева, де кожен вузол має унікального попередника за правилом «парне» (2n) і, можливо, другого попередника за правилом «непарне». До споріднених проблем належать узагальнені гіпотези 3n+k і складніша задача 5n+1, для якої насправді відомі контрприклади (розбіжні послідовності), що ілюструє, наскільки чутливі ці проблеми до точно обраного правила. Також досліджувалися зв'язки з теорією автоматних послідовностей і p-адичних чисел.
Сама проблема Коллатца не застосовується в практичних технологіях, але має значні зв'язки з теоретичною інформатикою. Це один із перших прикладів, з якими стикаються студенти, — алгоритм, завершення якого неможливо довести лише за його специфікацією, що безпосередньо стосується теорії обчислюваності та проблеми зупинки. Функцію Коллатца також вивчали як тест для арифметики довільної точності, оскільки числа-рекордсмени (як-от 837 799) породжують послідовності з дуже великими проміжними значеннями. Деякі криптографічні хеш-функції та генератори псевдовипадкових чисел були натхненні властивостями перемішування хаотичних цілочислових відображень, подібних до Коллатца.
До актуальних напрямів досліджень належить ймовірнісний підхід Тао (2019), який довів, що для будь-якої функції, що прямує до нескінченності, майже всі орбіти Коллатца набувають значень, нижчих за цю функцію — найближче, наскільки хтось наблизився до повного доведення. Інші дослідники вивчають зв'язки з ергодичною теорією, тропічною геометрією та теорією аперіодичних мозаїк. Обчислювальні зусилля з використанням розподілених обчислень (як-от проєкт Collatz@Home) продовжують підвищувати перевірений діапазон. Деякі математики підозрюють, що гіпотеза може бути невирішуваною в межах стандартних аксіоматичних систем, тобто може бути істинною, але недоведеною, що поміщає її в ту саму категорію, що й деякі твердження, досліджувані в основах математики.