Приветствую Вас, уважаемые Читатели! Сегодня продолжаю цикл материалов, посвященных нерешенным математическим задачам. Может показаться, что такие неподдающиеся решению задачи должны пугать каждого обывателя сложность формулировок, но это не тот случай. Фабула гипотезы Коллатца настолько простая, что её без труда поймет даже пятиклассник, только-только освоивший основные математические операции. Поехали!
Формулировка
Впервые на эту задачу обратили внимание в 1932 году. Для понимания её сути необходимо рассмотреть последовательность чисел, называемую "сиракузской последовательностью". Алгоритм её формирования следующий:
- Взять натуральное число n.
- Если оно четное, поделить его на 2, а если нет - умножить на три и прибавить один.
- Повторить шаг 2.
Гипотеза Коллатца заключается в том, что для любого числа n всё закончится на единице! Т.к. число, получаемое на втором шаге из нечетного равно 3n+1, эта задача имеет еще одно название - "дилемма 3n+1".
Пример
Давайте для примера возьмем какое-нибудь число, например, 13:
- 13 - нечетное - 13*3+1 = 40;
- 40 - четное - 40/2 = 20;
- 20 - четное - 20/2 = 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. Расчет окончен за 9 шагов. Если считать дальше, то получится бесконечный цикл 1-4-2-1...
Особенности задачи
Элементарная задача. я же говорил! Главная трудность, впрочем, в нахождении общего решения, например, формулы, которая для каждого натурального числа даёт количество шагов, после которого оно придет к единице.
Также ясно, что существуют некие "фатальные петли". из которым числам уже не вырваться. На приведенном выше примере - это числа 40, 20, 10, 5, 16, 8, 4 и 2. Еще можно заметить, что такой "петлей" для любых чисел будут степени двойки, тогда после ряда делений, всё вернется к единице.
Может показаться. что с увеличением n количество шагов и максимальное значение последовательности очень быстро растут, но это не так. Число 27 - скорее аномальный выброс. Самый длинный путь из первых ста тысяч чисел - 350 шагов, что всего лишь 3 раза больше.
Максимальные значения тоже пляшут, как им заблагорассудится: они вроде бы и не случайны, но внятной трактовки себе дать не позволяют.
По состоянию на апрель 2019 года различными командами, проводящими распределенные вычисления, проверены все числа до 1 152 921 504 606 846 976. Гипотеза Коллатца может не подтвердиться, если для хотя бы одного числа возникнет замкнутый цикл. Если Вы думаете, что такого быть не может, почитайте мою статью про число 196: там тоже ничего не предвещало беды.