Приветствую Вас, уважаемые Читатели! Сегодня продолжаю цикл материалов, посвященных нерешенным математическим задачам. Может показаться, что такие неподдающиеся решению задачи должны пугать каждого обывателя сложность формулировок, но это не тот случай. Фабула гипотезы Коллатца настолько простая, что её без труда поймет даже пятиклассник, только-только освоивший основные математические операции. Поехали!
Немецкий математик Лотар Коллатц. Источник: https://everipedia-storage.s3.amazonaws.com/ProfilePicture/en/Lothar_Collatz__6a5b5d/Lothar_Collatz.jpg__74854.jpeg
Формулировка
Впервые на эту задачу обратили внимание в 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…
Спираль, на которой отмечено количество шагов до 1. Источни: https://p7.hiclipart.com/preview/933/793/73/collatz-conjecture-mathematics-theorem-sequence-looking-up.jpg
Особенности задачи
Элементарная задача. я же говорил! Главная трудность, впрочем, в нахождении общего решения, например, формулы, которая для каждого натурального числа даёт количество шагов, после которого оно придет к единице.
Также ясно, что существуют некие "фатальные петли". из которым числам уже не вырваться. На приведенном выше примере — это числа 40, 20, 10, 5, 16, 8, 4 и 2. Еще можно заметить, что такой "петлей" для любых чисел будут степени двойки, тогда после ряда делений, всё вернется к единице.
График последовательности для числа 27. Потребовалось 111 шагов! Источник: http://www.ega-math.narod.ru/Nquant/IMG/Collatz1.gif
Может показаться. что с увеличением n количество шагов и максимальное значение последовательности очень быстро растут, но это не так. Число 27 — скорее аномальный выброс. Самый длинный путь из первых ста тысяч чисел — 350 шагов, что всего лишь 3 раза больше.
Максимальные значения тоже пляшут, как им заблагорассудится: они вроде бы и не случайны, но внятной трактовки себе дать не позволяют.
Источник: http://www.ega-math.narod.ru/Nquant/Collatz.htm
По состоянию на апрель 2019 года различными командами, проводящими распределенные вычисления, проверены все числа до 1 152 921 504 606 846 976. Гипотеза Коллатца может не подтвердиться, если для хотя бы одного числа возникнет замкнутый цикл. Если Вы думаете, что такого быть не может, почитайте мою статью про число 196: там тоже ничего не предвещало беды.
Читайте также:
- TELEGRAM и Facebook — там я публикую не только интересные статьи, но и математический юмор и многое другое.
