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

Гипо́теза Ко́ллатца (3n+1 диле́мма, сираку́зская пробле́ма) — одна из нерешённых проблем математики.
Получила широкую известность благодаря простоте формулировки.
Названа по имени немецкого математика Лотара Коллатца, сформулировавшего эту задачу 1 июля 1932 года.

Формулировка 

Для объяснения сути гипотезы рассмотрим следующую последовательность чисел, называемую сираку́зской после́довательностью. Берём любое натуральное число n. Если оно чётное, то делим его на 2, а если нечётное, то умножаем на 3 и прибавляем 1 (получаем 3n + 1). Над полученным числом выполняем те же самые действия, и так далее.

Гипотеза Коллатца заключается в том, что какое бы начальное число n мы ни взяли, рано или поздно мы получим единицу.

Примеры 
Например, для числа 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 — нечётное.

Последовательность, начинающаяся числом 19, приходит к единице уже за двадцать шагов:
 19, 58, 29, 88, 44, 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1, …

Для числа 27 получаем:

 27, 82, 41, 124, 62, 31, 94, 47, 142, 71, 214, 107, 322, 161, 484, 242, 121, 364, 182, 91, 274, 137, 412, 206, 103, 310, 155, 466, 233, 700, 350, 175, 526, 263, 790, 395, 1186, 593, 1780, 890, 445, 1336, 668, 334, 167, 502, 251, 754, 377, 1132, 566, 283, 850, 425, 1276, 638, 319, 958, 479, 1438, 719, 2158, 1079, 3238, 1619, 4858, 2429, 7288, 3644, 1822, 911, 2734, 1367, 4102, 2051, 6154, 3077, 9232, 4616, 2308, 1154, 577, 1732, 866, 433, 1300, 650, 325, 976, 488, 244, 122, 61, 184, 92, 46, 23, 70, 35, 106, 53, 160, 80, 40, 20, 10, 5, 16, 8, 4, 2, 1

Жирным выделены нечётные числа.

Последовательность пришла к единице только через 111 шагов, достигнув в пи́ке значения 9232. 

Чи́сла-гра́дины — также распространённое название для совокупности рассмотренных последовательностей. Такое название возникло из-за того, что графики последовательностей (см. иллюстрацию) похожи на траектории движения градин в атмосфере.

Последовательность первых чисел

Проект «Collatz Conjecture» 
В августе 2009 года на платформе BOINC был запущен проект добровольных распределённых вычислений «Collatz Conjecture», целью которого является проверка гипотезы Коллатца на больших числах. Вычислительный модуль проекта может использовать вычислительные мощности современных видеокарт.

Кроме проекта Collatz Conjecture, с августа 2017 года поиском решения этой проблемы стал также заниматься проект распределённых вычислений yoyo@home.

По состоянию на июль 2023 года проверены все натуральные числа до 10¹⁰⁰ (десять в сотой степени), и каждое из них продемонстрировало соответствие гипотезе Коллатца.

Реализация на языках программирования 
Python:
maxnum = 0
num = int(input("Введите число: "))
while num != 1:
	if num % 2 == 0:
		num /= 2
	else:
		num = num*3 + 1
	print(num)
	maxnum = max(maxnum, num)
print("Пик:", maxnum)

C#
int n;
int i = 0;
Console.WriteLine("Введите число n: ");
n = int.Parse(Console.ReadLine());
while (n != 1) {
    if (n % 2 == 0) {
        n /= 2;
        i += 1;
    }
    else {
        n = 3 * n + 1;
        i += 1;
    }
}
Console.WriteLine($"{n} {i}");

C++:
#include <iostream>

int main() {
	int maxnum = 0;
	int num = 0;
	int count = 0;
	std::cin >> num;
	while (num != 1) {
		if (num % 2 == 0) {
			num = num / 2;
		} else {
			num = num * 3 + 1;
		}
		std::cout << num << std::endl;
		maxnum = std::max(maxnum, num);
		count++;
	}
	std::cout << "Пик: " << maxnum << std::endl;
	std::cout << "Шагов: " << count << std::endl;
}

См. также 
 Открытые математические проблемы
 BOINC
 FRACTRAN — эзотерический язык программирования, полный по Тьюрингу, со схожими инструкциями. Показывает, что подобные задачи не имеют алгоритмического решения.

Примечания

Литература

Ссылки 
 .
 
 Das Collatz-Problem интерактивные скрипты Юргена Денкерта для решения (3n+1)- и (3n−1)-задач, создаёт последовательность для чисел любой длины, также выдаёт статистику последовательности.
 Collatz Conjecture  — проект распределённых вычислений на платформе BOINC по проверке гипотезы Коллатца на больших числах.
 On the 3x + 1 problem  — проект распределённых вычислений, основанный Эриком Рузендалем (Eric Roosendaal), по проверке гипотезы Коллатца на больших числах.
 Аналитический подход к проблеме Коллатца .
 Реализация сиракузской последовательности на разных языках программирования  (на сайте ).
 Collatz conjecture A.A Durmagambetov, A. A Durmagambetova. https://www.researchgate.net/publication/359521315_Collatz_conjecture

Коллатца
Арифметика
Открытые математические проблемы