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

Гипотеза Ко́ллатца — одна из нерешённых проблем математики: верно ли, что последовательность чисел, строящаяся от произвольного натурального ${\displaystyle n_{0}}$, каждое ${\displaystyle (i+1)}$-е число в которой равно ${\displaystyle 3n_{i}+1}$, если ${\displaystyle n_{i}}$ — нечётное, и ${\displaystyle n_{i}/2}$, если ${\displaystyle n_{i}}$ — чётное, рано или поздно вырождается в единицу. Такие последовательности называются сиракузскими, а гипотеза иногда фигурирует как под наименованием «сираку́зская проблема».

Последовательности для всех нечётных чисел от 1 до 49 включительно (кроме чисел 27, 31, 41, 47). Чётные числа в последовательности опущены

Названа по имени немецкого математика Лотара Коллатца, сформулировавшего похожую задачу 1 июля 1932 года^[1].

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

1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16
1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16
	1	10	2	16	3	22	4	28	5	34	6	40	7	46	8
		5	1	8	10	11	2	14	16	17	3	20	22	23	4
		16		4	5	34	1	7	8	52	10	10	11	70	2
		8		2	16	17		22	4	26	5	5	34	35	1
		4		1	8	52		11	2	13	16	16	17	106
		2			4	26		34	1	40	8	8	52	53
		1			2	13		17		20	4	4	26	160
					1	40		52		10	2	2	13	80
						20		26		5	1	1	40	40
						10		13		16			20	20
						5		40		8			10	10
						16		20		4			5	5
						8		10		2			16	16
						4		5		1			8	8
						2		16					4	4
						1		8					2	2
								4					1	1
								2
								1

График последовательности для числа 27

При ${\displaystyle n=27}$ последовательность состоит из 111 членов до первой единицы, достигая в пике значения 9232.

Благодаря элементарности формулировки проблема снискала широкую известность, фигурировала во множестве научно-популярных публикаций, создано множество визуализаций для умозрительного поиска закономерностей. Запущено несколько проектов добровольных вычислений по проверке гипотезы: в августе 2009 года — на платформе BOINC^[2] (с поддержкой GPGPU), в августе 2017 года — в рамках проекта «yoyo@home»^[3].

В последние годы^{[уточнить]} проверены все натуральные числа до 3×10²⁰, и каждое из них продемонстрировало соответствие гипотезе Коллатца.

Визуализации

• 
  Направленный график, показывающий орбиты первых 1000 чисел.
• 
  Ось ${\displaystyle x}$ представляет начальное число, ось ${\displaystyle y}$ — наибольшее число, достигнутое в цепочке до 1. Этот график показывает ограниченность оси y: некоторые значения ${\displaystyle x}$ дают промежуточные значения, достигающие 2,7e7 (для ${\displaystyle x=9663}$)
• 
  График в логарифмическом масштабе; первая жирная линия в середине графика соответствует вершине в точке 27, которая достигает максимума в точке 9232.
• 
  Дерево всех чисел, имеющих меньше 20 шагов.
• 
  Количество итераций, необходимое для достижения единицы для первых 100 миллионов чисел.
• 
  Пути по гипотезе Коллатца для 5000 случайных начальных точек меньше 1 миллиона.