Гипотеза Коллатца

Теорема.

Для любого натурального числа n при его пошаговом изменении в соответствии с алгоритмом:

если n – нечётное, то умножаем его на 3 и к произведению добавляем 1;

если n – чётное, то делим его на 2;

неизбежно получится последовательность 4; 2; 1.

Доказательство.

Утверждение теоремы будет верным только в том случае, если в процессе преобразований любого натурального числа n по данному алгоритму на очередном шаге мы при умножении нечётного числа k на 3 и добавлении к произведению 1 получим чётное число 4m, где m – натуральное число. Дальнейшая серия делений на 2 приведёт к конечной последовательности.

Так как k – нечётное число, то его можно представить в виде k=2t+1, где t – натуральное число. Тогда преобразование числа n на рассматриваемом шаге можно представить в виде равенства 3(2t+1)+1=4mили 6t+4=4m

Если данное равенство будет верным при множестве произвольных значений t и m, то теорема верна.

Преобразуем 6t+4=4m. Отсюда 4m-4=22m-22=(2m-2)(2m+2)=6t.

Далее 4(2m-1-1)(2m-1+1)=6t. Тогда 2(2m-1-1)(2m-1+1)=3t.

У нас имеется последовательность следующих друг за другом трёх натуральных чисел: (2m-1-1); (2m-1); (2m-1+1). Значит, одно из них обязательно делится на 3. Но это не (2m-1), так как данное число имеет простые делители только 2. Значит, (2m-1-1) или (2m-1+1) обязательно делится на 3.

Таким образом, левая часть последнего уравнения делится на 3, что соответствует условию правой части данного уравнения.

Значит, данное уравнение будет верным при множестве произвольных значений t и m. Поэтому теорема верна.