Впервые на эту задачу обратили внимание в 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
Особенности задачи
Элементарная задача. я же говорил! Главная трудность, впрочем, в нахождении общего решения, например, формулы, которая для каждого натурального числа даёт количество шагов, после которого оно придет к единице.
Пошаговое объяснение:
Здесь информация
