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

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

Для объяснения сути гипотезы рассмотрим следующую последовательность чисел, называемую сираку́зской после́довательностью . Берём любое натуральное число n . Если оно чётное, то делим его на 2, а если нечётное, то умножаем на 3 и прибавляем 1 (получаем 3 n + 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¹⁰⁰ (десять в сотой степени) ^{[ источник не указан 141 день ]} , и каждое из них продемонстрировало соответствие гипотезе Коллатца.

Реализация на языках программирования

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 — эзотерический язык программирования, полный по Тьюрингу, со схожими инструкциями. Показывает, что подобные задачи не имеют алгоритмического решения.

Примечания

Литература

• Хэйес, Брайан. // В мире науки (Scientific American, издание на русском языке). — 1984. — № 3 . — С. 102—107 .
• Стюарт, Иэн. Величайшие математические задачи. — М. : Альпина нон-фикшн, 2015. — 460 с. — ISBN 978-5-91671-318-3 .
• Jeff Lagarias. (англ.) // American Mathematical Monthly . — 1985. — Vol. 92 . — P. 3—23 .

Ссылки

• последовательность в OEIS .
• (рус.) (Видео). www.youtube.com . Дата обращения: 2 ноября 2022. 2 ноября 2022 года.
• интерактивные скрипты Юргена Денкерта для решения (3n+1)- и (3n−1)-задач, создаёт последовательность для чисел любой длины, также выдаёт статистику последовательности.
• от 4 декабря 2017 на Wayback Machine — проект распределённых вычислений на платформе BOINC по проверке гипотезы Коллатца на больших числах.
• от 14 декабря 2013 на Wayback Machine — проект распределённых вычислений , основанный Эриком Рузендалем ( Eric Roosendaal ), по проверке гипотезы Коллатца на больших числах.
• от 20 марта 2013 на Wayback Machine . (англ.)
• от 4 апреля 2018 на Wayback Machine (на сайте ).
• Collatz conjecture A.A Durmagambetov, A. A Durmagambetova.