Доказательство гипотезы Коллатца

Продолжу начатую предыдущим постом тему доказательством гипотезы Коллатца.

В чём заключается эта гипотеза? Возьмём любое натуральное число $$. Если оно чётное, то делим его на $$, а если нечётное, то умножаем на $$ и прибавляем $$ (получаем $$). Над полученным числом выполняем те же самые действия, и так далее. Гипотеза Коллатца заключается в том, что какое бы начальное число $$ мы ни взяли, рано или поздно мы получим единицу.

Доказательство гипотезы Коллатца

Переформулируем гипотезу следующим образом: возьмём любое натуральное число $$. Если оно чётное, то делим его на $$ пока оно не потеряет свойство чётности, а потом переводим в систему счисления по основанию $$ и прибавляем $$ до тех пор, пока основание системы счисления не станет обратным $$, на каждом шаге умножая $$ на $$, где $$ — номер текущего шага. Гипотеза Коллатца в такой формулировке заключается в том, что какое бы начальное число $$ мы ни взяли, рано или поздно это произойдёт, то есть в том, что уравнение

$$

где $$ — число нечётных шагов, $$ — общее число шагов, имеет решение при любом натуральном $$, что очевидно так.

Доказано.

Но ничего не понятно, особенно почему я переформулировал гипотезу именно так и откуда в ней взялось число шагов. Может быть я не прав? Проверим на конкретных примерах со страницы в Википедии.

Для числа $$ получаем

$$

решением является $$, то есть число $$ можно преобразовать в $$ за три нечётных шага, а всего для этого потребуется $$ шагов. Верно.
Для числа $$ получаем

$$

решением является $$, то есть число $$ можно преобразовать в $$ за семь нечётных шага, а всего для этого потребуется $$ шагов. Тоже верно, но всё равно ничего не ясно. Ответ ниже.

Внимание! Слабонервным и испорченным российским математическим образованием просьба дальше не читать!

Некоторые основные понятия теории энтропии

Система — неопределимое понятие, на основании которого строятся недоказуемые определения:
Энтропия — информационная ёмкость системы.
Экстропия — величина, противоположная энтропии.
Фазовый переход — уменьшение энтропии на один порядок, происходящий при накоплении достаточного и необходимого объёма знаний.

Эволюция маленькой n

Рассмотрим на конкретном примере: возьмём из формулировки гипотезы n и превратим его в $$. Как этого достичь? Уменьшая незнание, то есть задавая вопросы на которые возможен только однозначный ответ «да» или «нет». Поехали:
1. n — самолёт? Нет. Этот ответ уменьшил наше незнание о n на знание «n — не самолёт», но не сообщил нам ничего о свойствах n, то есть он уменьшил энтропию, но не увеличил экстропию.
2. n — математический объект? Да. Этот ответ увеличил экстропию, теперь мы знаем, что n — математический объект, следовательно обладает всеми свойствами математического объекта, в частности является переменной либо константой.
3. n — константа? Нет. Этот ответ снова снизил энтропию и произвёл фазовый переход. Количество накопленной информации «n — математический объект» и «n — не константа» перешло в её качество — вывод «$$ — переменная» и теперь позволяет нам уменьшить энтропию данных выше определений.

Энтропия (в математике) — неотъемлемое свойство математического объекта, мера нашего незнания о нём как о системе, величина измеряемая в битах энтропии. Неформально: ответ «нет» на вопрос.
Экстропия (в математике) — величина, противоположная энтропии (в математике), мера нашего знания о математическом объекте как о системе, величина измеряемая в битах экстропии. Неформально: ответ «да» на вопрос.
Фазовый переход (в математике) — уменьшение энтропии (в математике) на один бит энтропии, происходящий при накоплении достаточного и необходимого объёма знаний.

Немного магии теории энтропии

Так как же всё-таки я получил свой эквивалент гипотезы Коллатца? Допустим, что изначально $$ имело вид $$, то есть содержало $$ бита экстропии: ответы «да» на вопросы «делится ли $$ на $$ соответственно?» и некоторое количество бит энтропии, определяемое переменной $$. Операцией деления на $$ мы трижды экстропию понизили, в итоге она стала равна нолю, энтропия же осталась неизменной и равной $$, где $$ — число разрядов в двоичной записи числа $$. Переводом в систему счисления с дробным основанием мы каждый раз совершали фазовый переход (в математике), так как получали знание «$$ делится на $$«, то есть, выражаясь понятным программистам языком, совершали битовый сдвиг влево и заменяли ноль в крайнем правом разряде на единицу. В итоге за $$ сдвигов у нас из полностью неопределённого числа получилось числа с $$ разрядами, все цифры в котором ноли, то есть число полностью определённое. Прибавив к нолям единицу мы и получили искомое.

P.S. Вдумчивый читатель наверняка обратил внимание на то, что важнейшим следствием из доказательства гипотезы служит тот факт, что $$ число всегда составное при любом $$. Это важнейшее открытие, ключ к экспоненциальному снижению вычислительной сложности компьютерной задачи факторизации больших чисел. Я обязательно разовью эту тему в следующем посте, который, видимо, из-за моей отрицательной кармы, увидит свет только через неделю.