Гипотеза Коллатца — самый крутой математический фокус всех времён
В сети и в развлекательной литературе нередко можно встретить разные математические фокусы: вас просят задумать какое-то число, затем выполнить с ним ряд арифметических действий. После этого собеседник точно называет получившееся у вас число. Большинство этих фокусов основано на том, что исходное число в ходе преобразований незаметно подменяется другим, а затем за несколько шагов сводится к известному ответу. Такие фокусы, например, можно встретить в книгах Якова Перельмана.
Визуализация гипотезы Коллатца с сайта www.algoritmarte.com
Гипотеза Коллатца оставляет все подобные фокусы позади. На первый взгляд может показаться, что это тоже какой-то фокус с подвохом. Однако при внимательном рассмотрении оказывается, что никакого подвоха нет. Вы загадываете число и несколько раз повторяете для него одно из двух арифметических действий. Удивительно, что результат этих действий будет всегда одним и тем же. Или не всегда? Этого пока наверняка никто не знает, но получить что-то другое пока никому не удалось.
Давайте попробуем. Итак, загадайте любое целое положительное число. Дальше следуйте простому алгоритму:
1. Если число чётное, разделите его на 2. Иначе умножьте его на 3 и прибавьте 1.
2. Повторите шаг 1 с полученным числом.
Как вы думаете, что мы получим в итоге, если будем много раз выполнять шаги 1 и 2?
Немецкий математик Лотар Коллатц считает, что для любого целого положительного числа мы рано или поздно получим сначала 4, потом закономерно — 2, а потом 1. И после этого мы будем ходить по кругу, вновь и вновь получая цепочку 4–2–1. Самое удивительное в том, что мы придём к такому результату, с какого бы числа мы ни начали.
Лотар Коллатц / Wikimedia Commons
Не верите? Это не сложно проверить, тем более, что условия задачи очень просты. Пожалуй, на данный момент это простейшая формулировка нерешённой математической задачи — умножать и складывать умеет каждый. Справедливости ради стоит заметить, что для некоторых исходных чисел считать придётся долго. Так что для загадывания в дружеской компании этот «фокус» если и подойдёт, то только для небольших исходных чисел. Но мы всегда можем написать маленькую программку — куда уж проще: цикл с одним условием. Вот мой вариант простейшей программы на любимом Delphi:
program collatz;
{$APPTYPE CONSOLE}
uses
SysUtils, Classes;
var
s: string;
num, steps, max: integer;
begin
readln(s);
num:=strtoint(s); // Исходное число
steps:=0; // Счётчик шагов
max:=num; // Максимальное промежуточное число
while (num<>1) do
begin
if odd(num) then num:=num*3+1 // Число нечётно
else num:=num div 2; // Число чётно
if num>max then max:=num;
inc(steps);
writeln(inttostr(num));
end;
writeln('Steps - '+inttostr(steps));
writeln('Max - '+inttostr(max));
end.При желании попробуйте сами немного поэкспериментировать с этой гипотезой. Кстати, в сети можно найти много интересных визуализаций, показывающих распределение решений и шагов для разных исходных данных. А ещё есть сайт, который содержит варианты реализации этой задачи для множества языков программирования.
Фрактал Коллатца — визуализация с сайта soulofmathematics.com
Знаете, что ещё интересно? Утверждение Коллатца не зря называется гипотезой — пока никто так и не смог придумать её логическое доказательство. Лотар Коллатц сформулировал свою гипотезу ещё в 30-х годах 20 века и с тех пор предпринимались многочисленные попытки доказать или опровергнуть это утверждение с помощью строгой математической логики. Но всё, чего смогли добиться математики, — это просто проверить гипотезу экспериментально. В этой задаче программный поиск решения по сути ничем не ограничен, кроме вычислительных мощностей. Пока гипотеза не опровергнута — даже для огромных исходных чисел рано или поздно алгоритм достигает 1. Для решения этой задачи даже был организован проект добровольных распределённых вычислений. Но для классической математики этого недостаточно. Числа иногда бывают очень коварны. Где-то среди неимоверно огромных исходных чисел может скрываться такое исходное число, для которого гипотеза не подтвердится.
Кстати, у гипотезы Коллатца есть ещё несколько менее известных названий:
— дилемма 3n+1 — это вариант шага для нечётных чисел;
— гипотеза градины — графики последовательностей чем-то напоминают траектории движения града в атмосфере;
— гипотеза Улама — по имени польского математика Станислава Улама;
— проблема Какутани — по имени японского математика Сидзуо Какутани;
— гипотеза Туэйтса — по имени английского математика Брайна Туэйта;
— алгоритм Хассе — по имени немецкого математика Хельмута Хассе;
— сиракузская проблема.
По количеству разнообразных наименований видно, что математиков всерьёз заинтересовала эта проблема. Однако оказалось, что это одна из тех «вредных» задач, которые очень легко формулируются, но чрезвычайно тяжело решаются. Прямо как Великая теорема Ферма.
Числа в этой задаче ведут себя крайне странно: в некоторых случаях вычисления доходят до единицы очень быстро, а иногда промежуточный итог добирается до довольно большого числа, а затем быстро «срывается» вниз — до самой единицы. Например, для начального числа 27 промежуточный итог достигает 9232, а затем за несколько шагов быстро спускается до 1. В итоге количество шагов для 27 равно 111. И это при том, что для 26 оно равно 10 (максимальное промежуточное число — 40), а для 28 — 18 (максимальное промежуточное число — 52).
Хоть математикам и не удалось полностью логически подтвердить или опровергнуть гипотезу, они всё же кое-чего достигли. Как это часто бывает, учёные подбираются к решению постепенно. Совсем недавно, 8 сентября 2019, математик из Калифорнийского университета Теренс Тао опубликовал доказательство, где показано, что гипотеза Коллатца, по меньшей мере, «почти» верна «почти» для всех чисел. История того, как математики штурмовали эту проблему и о том, чего удалось достичь Теренсу Тао подробно описана в этой статье.
В журналах и в сети уже неоднократно появлялись варианты доказательства гипотезы Коллатца. Однако, к большому сожалению, все они либо содержали ошибки, либо были неполными. Так что гипотеза пока остаётся гипотезой, а ещё — крутым и красивым математическим фокусом.
Статья была впервые опубликована на другом ресурсе 10 марта 2021.
