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

Возьмем целое число. Если оно четное, разделим на 2. Если нечетное, домножим на 3 и прибавим 1. Повторим эту операцию бесконечное число раз. Что произойдет?

К примеру, можно начать с числа 12. Получим следующую последовательность:

12 ? 6 ? 3 ? 10 ? 5 ? 16 ? 8 ? 4 ? 2 ? 1,

после чего последовательность 4 ? 2 ? 1 ? 4 ? 2 ? 1 будет повторяться бесконечно. Гипотеза Коллатца утверждает, что конечный результат будет одним и тем же, с какого бы числа мы ни начали. Гипотеза названа в честь Лотара Коллатца, предложившего ее в 1937 г., но имеет и множество других названий: гипотеза 3n + 1, гипотеза градины, гипотеза Улама, проблема Какутани, гипотеза Туэйтса, алгоритм Хассе или сиракузская проблема.

Что делает эту задачу такой сложной, так это то, что нередко числа буквально взрываются. Так, если начать с 27, последовательность поднимется до 9232, но при этом все равно через 111 шагов сойдется к 1. Компьютерное моделирование подтверждает гипотезу для всех первоначальных чисел вплоть до 5,764 ? 10¹⁸. Доказано, что не существует циклов, за исключением 4 ? 2 ? 1, в которых было бы меньше 35 400 шагов. Возможность того, что некоторое начальное число дает последовательность, содержащую все более крупные числа, разделенные более мелкими, не исключена. Илья Красиков и Джеффри Лагариас доказали, что для начальных величин вплоть до n по крайней мере n0,84 из них со временем сходится к 1. Так что исключения, если они существуют, встречаются редко.