Молодым математикам сразу советуют не браться за эту задачу, считая попытки её решения пустой тратой времени. Простую на вид гипотезу не смогли доказать лучшие умы человечества. Пол Эрдёш однажды заметил: «Математика ещё не созрела для таких вопросов».
Суть гипотезы
Выберите любое положительное целое число. Действуем по двум правилам:
- Нечётное число умножаем на 3 и добавляем 1. Например, 3 × 7 = 21 + 1 = 22.
- Чётное число делим на 2. Например, 22 ÷ 2 = 11.
Повторяем действия. Рассмотрим пример с числом 11:
11 → 34 → 17 → 52 → 26 → 13 → 40 → 20 → 10 → 5 → 16 → 8 → 4 → 2 → 1 → 4 → 2 → 1
Получается цикл 4, 2, 1 с минимальным значением 1.
Гипотеза утверждает: любое положительное целое число, следуя алгоритму, обязательно попадает в цикл 4, 2, 1. Её автор — Лотар Коллатц, немецкий математик (предположительно, 1930-е годы). Гипотеза также известна как гипотеза Улама, теорема Катанака, гипотеза Туэ, алгоритм Хассе, 3n+1 последовательность.
Сложность гипотезы
Гипотеза получила сомнительную славу в профессиональной среде. Работа над ней считается признаком непрофессионализма.
Числа, получаемые в процессе преобразования 3n + 1, ведут себя хаотично: значения то возрастают, то убывают. Однако рано или поздно все стремятся к единице — по крайней мере, так кажется. Представим числа как высоту над землёй. Число 26 находится на высоте 26 м. При применении 3x + 1, оно сначала поднимется до 40, а затем за 10 шагов опустится до единицы (время остановки). Соседнее число 27, наоборот, достигнет 9232 (выше Эвереста), но и оно, пройдя 111 шагов, достигнет единицы и цикла 4, 2, 1.
Такая непредсказуемость затрудняет доказательство. Многие математики считали задачу неразрешимой. Один из ведущих специалистов по этой проблеме предостерегал: «Не занимайтесь этим, если хотите сделать карьеру. Сначала займитесь нормальной математикой».
Поиск закономерностей и статистический анализ
Некоторые математики, например, Алекс Канторович и Яков Синай, искали закономерности в поведении чисел. Путь случайно выбранного большого числа сначала демонстрирует резкий рост, затем — стремительное падение. В колебаниях прослеживается нисходящий тренд, подобный обвалу на рынке акций. Это пример геометрического броуновского движения: логарифм колебаний случаен. Поведение 3x + 1 похоже на случайные скачки на бирже, но в отличие от рынков акций, 3x + 1 в долгосрочной перспективе падает.
Анализ старшего разряда чисел, представленный в виде гистограммы, показывает, что с увеличением количества данных, соотношение частоты цифр упорядочивается. Для миллиарда последовательностей, единица встречается в начале почти в 30% случаев; двойка — в 17,5%; тройка — в 12%; частота остальных цифр уменьшается. Это распределение соответствует закону Бенфорда, используемому, например, для обнаружения мошенничества. Закон Бенфорда работает лучше всего при большом разбросе значений, как в случае 3x + 1, но не подтверждает гипотезу Коллатца.
Странно, что 3x + 1 приводит все числа к единице, учитывая, что нечётные числа возрастают более чем в три раза, а чётные — уменьшаются вдвое. Однако каждое умножение нечётного числа на три и прибавление единицы приводит к чётному числу, которое делится на два. В итоге нечётные числа умножаются примерно на 3/2. Для больших чисел можно игнорировать «+1». Среднее геометрическое показывает, что в среднем для перехода от одного нечётного числа к другому, нужно умножить на 3/4, что меньше единицы. Статистически, последовательности 3x + 1 уменьшаются чаще, чем растут.
Визуализация путей чисел в виде ориентированного графа, напоминающего дерево или множество ручьёв, показывает, что если гипотеза верна, бесконечное количество «ручьёв» сходятся в цикле 1. Модификация графа с поворотом на каждом шаге создаёт интересные фрактальные структуры.
Гипотеза окажется неверной, если будет найдено число, дающее бесконечную последовательность, или последовательность, образующая собственный замкнутый цикл. Пока ничего подобного не найдено.
Проверка и попытки доказательства
Перебором проверены все числа до 268 (около 300 квинтиллионов), все они приводят к единице. На основе этих данных рассчитано, что другой цикл, если он существует, должен состоять как минимум из 186 миллиардов чисел.
Попытки подтверждения гипотезы включали построение диаграммы рассеяния. Если доказать, что в любой последовательности 3x + 1 есть число меньше исходного, гипотеза будет подтверждена. Доказать это не удалось. Рихард Террас показал, что почти все последовательности включают значение ниже исходного x7. Позже степень уточнили до x0.869. «Почти все» означает, что при x, стремящемся к бесконечности, доля значений x последовательности, в которых есть число меньше значения ограничивающей функции, стремится к единице.
Тери Тау доказал, что 3x + 1 подчиняется ещё более строгим ограничениям: почти все числа будут меньше значения любой функции f(x), стремящейся к бесконечности при x, стремящемся к бесконечности. Это впечатляющее достижение, но не полное доказательство.
Почему гипотеза не подтверждена?
Возможно, потому что гипотеза неверна? Поиск контрпримеров важен. Число 27 достигает 9232. Не доказано, что другое число не может устремиться в бесконечность. Для опровержения достаточно одного такого числа или цикла, отличного от 4, 2, 1.
Среди отрицательных чисел существуют три независимых цикла (-1, -5, -17). Если циклы возможны среди отрицательных чисел, почему их не может быть среди положительных?
Доказательство Тау о том, что почти все числа имеют в своих последовательностях сколь угодно малые значения, — убедительный аргумент, но «почти все» не значит «все».
Аналогия с полными квадратами показывает, что доля полных квадратов стремится к нулю при увеличении диапазона, хотя их бесконечно много. Перебор до 268 не исключает существование контрпримера.
Гипотеза Эрдёша о разложении чисел на нечётное количество простых множителей была опровергнута контрпримером 1.45 × 10361.
Задача может быть представлена как программа на машине Тьюринга. Проверка до 268 не гарантирует поведения для всех чисел. Поиск контрпримера перебором невозможен из-за бесконечности множества чисел.
Возможно, гипотеза неразрешима. Джон Конвей доказал, что обобщение задачи 3x + 1 (машина «транс») полна по Тьюрингу и подвержена проблеме остановки. На основе имеющихся данных, подтвердить или опровергнуть гипотезу Коллатца, возможно, невозможно.