Эта проблема названа в честь Лотара Коллатца, предложившего ее впервые в 1937 году. Она имеет много других названий, в частности, числа-градины, сиракузская последовательность, проблема 3n+1 и др.). Задача эта имеет очень простую и доступную формулировку, однако до сих пор считается нерешенной.
Для объяснения сути гипотезы берём любое натуральное число n. Если оно чётное, то делим его на 2, а если нечётное, то умножаем на 3 и прибавляем 1 (получаем 3n + 1). Над полученным числом выполняем те же самые действия, и так далее.
Возникающую последовательность чисел еще называют последовательностью градин или просто градинами (поскольку ее числа резко возрастают и падают как градины во время грозы и шторма) или еще «блуждающими числами».
Гипотеза Коллатца заключается в том, что какое бы начальное число мы ни взяли, рано или поздно мы получим единицу.
Например, для числа 3 получаем:
3 — нечётное, 3×3 + 1 = 10 10 — чётное, 10:2 = 5 5 — нечётное, 5×3 + 1 = 16 16 — чётное, 16:2 = 8 8 — чётное, 8:2 = 4 4 — чётное, 4:2 = 2 2 — чётное, 2:2 = 1 1 — нечётное, 1×3 + 1 = 4
Для проверки гипотезы Коллатца на больших числах было запущено несколько проектов распределенных вычислений. По состоянию на 2019 год проверены все натуральные числа меньше чем 1 152 921 504 606 846 976 и каждое из них за конечное количество шагов соответствовало условиям Гипотезы Коллатца.
