Гипотеза Коллатца, часть 2 / forpes.ru

02.05.2023 20:58

Martynov_M 74 2600 Источник

Аннотация

Это вторая статья из цикла "Доказательство гипотезы Коллатца".
Первая часть находится здесь.
Данная статья отвечает на самый главный вопрос гипотезы Коллатца, почему в 3n+1 нет циклов, зацикливания и повторов.

§1. Постановка вопроса

Как известно, гипотеза Коллатца может быть легко опровергнута в том случае, если существует такое число , которое зацикливается или уходит в бесконечность.
На сегодняшний день проверены все числа до 10 000 000 000 000 000 000 000 включительно ( $2^{73}$ ), и все они соответствуют гипотезе Коллатца.

В первой части публикации мы совершили прорыв в области изучения 3n+1 и смогли установить шаг рекурсии. Теперь мы доказываем, почему в 3n+1 нет повторов.

§2. Пример цикла

Гипотеза Коллатца ярко выделяется на фоне других аналогичных задач. Так, например, всего лишь изменив одно условие 3n+1 на 5n+1 мы почти сразу же получаем цикл:

5 $\rightarrow$ 26 $\rightarrow$ 13 $\rightarrow$ 66 $\rightarrow$ 33 $\rightarrow$ 166 $\rightarrow$ 83 $\rightarrow$ 416 $\rightarrow$ 208 $\rightarrow$ 104 $\rightarrow$ 52 $\rightarrow$ 26 $\rightarrow$ 13.

Этот цикл можно представить как: 5 $\rightarrow$ 13 $\rightarrow$ 33 $\rightarrow$ 83 $\rightarrow$ 13.
Что означает, что преобразование для 5 и 83 дает повтор – 13.

§3. Может ли такое быть в гипотезе Коллатца?

Как мы уже выяснили, 3n+1 – это алгоритм, образованный от алгоритма $\frac {n-1}{3}$ . Полная версия алгоритма основана на шаге рекурсии:

$\frac{2n-1}{3}$ для случая n ≡ 2 mod(3),

$\frac{4n-1}{3}$ для случая n ≡ 1 mod(3),

для случая n ≡ 0 mod(3),
и постоянное применение к уже полученным числам

Чётные числа являются ширмой в гипотезе Коллатца и ни на что не влияют (см. предыдущую работу). Таким образом, для образования циклов в гипотезе Коллатца необходимо следующее условие:

a $\rightarrow$ c (cycle) $\rightarrow$ ... ... ... $\rightarrow$ $\rightarrow$ c (cycle) ... ... ... $\rightarrow$ $\rightarrow$ c (cycle),
где все числа а, b, c – это нечетные числа.

Первый случай

Предположим, что есть такое число a, к которому мы применили шаг рекурсии $\frac{2n-1}{3}$ , и есть такое число b, к которому мы применили $\frac{4n-1}{3}$ . И в обоих случаях мы получили число c. Тогда справедливо равенство:

$\frac{2a-1}{3} = \frac{4b-1}{3}.$

Но это невозможно, потому что и не могут быть чётными числами.

Второй случай

Предположим, что есть такое число a, к которому мы применили шаг рекурсии $\frac{2n-1}{3}$ , и есть такое число b, к которому мы применили . И в обоих случаях мы получили число c. Тогда справедливо равенство:

$\frac{2a-1}{3} = 4b+1.$

Но это невозможно, потому что и не могут быть чётными числами.

Третий случай

Предположим, что есть такое число a, к которому мы применили шаг рекурсии $\frac{4n-1}{3}$ , и есть такое число b, к которому мы применили . И в обоих случаях мы получили число c. Тогда справедливо равенство:

$\frac{4a-1}{3} = 4b+1.$

Но это невозможно, потому что и не могут быть чётными числами.

§4. Окончательный вывод

Отсутствие циклов позволяет нам наконец-то поставить точку в гипотезе Коллатца. Подытожим (на основании первой и второй публикации):

Рекурсия 3n+1 – это развернутая в обратном направлении рекурсия от рекурсии прародителя $\frac {n-1}{3}$ .
Рекурсия $\frac {n-1}{3}$ начинается из единицы и уходит в бесконечность.
Рекурсия 3n+1, как производная форма от $\frac {n-1}{3}$ , может спускаться только к единице.
В обоих алгоритмах исключены повторы, циклы и зацикливания.
Чётные числа не влияют на шаг рекурсии.
Нет такого нечетного числа, которое бы рекурсивно не цепляло другое. Потому что шаг рекурсии $\frac {n-1}{3}$ включает в себя все комбинации по модулю 3, n ≡ 0 mod(3), n ≡ 1 mod(3), n ≡ 2 mod(3). Другими словами, невозможно подобрать такое нечетное число, которое нельзя было бы подставить в рекурсию, и оно при этом не цепляло бы другое нечетное число.
Всё это означает, что все переходы между нечетными числами уникальны и ведут либо к единице, либо в бесконечность, в зависимости от направления рекурсии, которое мы выбираем 3n+1 или $\frac {n-1}{3}$ .

§5. Хвост рекурсии или последнее слово математика

На протяжении 100 лет математики «вязли в болоте» Коллатца только лишь потому, что не могли описать задачу через элементарную теорию алгоритмов. Мешал им в этом пресловутый хвост рекурсии.

Так, например, 5 лет назад на самом популярном математическом форуме в России dxdy.ru пользователь с ником «Soul Friend» прогнал гипотезу Коллатца на компьютере и экспериментально получил шаг рекурсии $\frac {n-1}{3}$ , такой же шаг как в этой работе. К сожалению, он забросил свое исследование и не получил какой-либо поддержки от других математиков.

Алгоритм $\frac {n-1}{3}$ и гипотеза Коллатца настолько просты, что сейчас уже сложно кому-то объяснить, почему на эту задачу были потрачены миллионы человеко-часов, сняты фильмы и написаны книги. Но по личной истории, я могу констатировать, что вся загвоздка с 3n+1 упиралась только в хвост рекурсии.

Как сейчас уже очевидно, возрастание с единицы до бесконечности по алгоритму $\frac {n-1}{3}$ , основано только лишь на одном правиле 4x+1. Применение же формул $\frac{2n-1}{3},$ $\frac{4n-1}{3}$ – это просто ветка дерева "вправо-влево", которая ни на что не влияет, потому что каждая такая ветка всегда заканчивается хвостом рекурсии n ≡ 0 mod(3).

К сожалению, всё это скрыто от взгляда стороннего наблюдателя, если он двигается в ограниченной системе координат 3n+1. И отчетливо видно, если он переходит к полной версии алгоритма $\frac {n-1}{3}$ .

Вычислив полный шаг рекурсии в гипотезе Коллатца, в начале этого года я отправил его в:

Журнал «Математический сборник» (РАН),
«Журнал целочисленных последовательностей» (OEIS),
Кафедру прикладной математики Оренбургского Государственного Университета,
В исследовательский портал https://arxiv.org/,
На рассмотрение модераторов Википедии в статью «Гипотеза Коллатца».

Во всех организациях я получил отказ от публикации. К тому же на форуме dxdy.ru я получил бан с формулировкой: «Мы не видим никакой связи между Вашим шагом рекурсии и какой-либо возможностью доказать гипотезу Коллатца».

Во всех случаях, камнем преткновения для меня стал хвост рекурсии n ≡ 0 mod(3). Я получил сотни вопросов от математиков, почему рекурсия на этом месте заканчивается, а дерево не зацикливается? И что вообще из себя представляет рекурсия на языке математики? В итоге пришлось проделать путь в несколько недель, чтобы самому ответить на все эти вопросы. «Болото» Коллатца оказалось не болотом, а ручейком.

С уважением,
Автор статьи: Михаил Мартынов.

Гипотеза Коллатца, часть 2 -12

Комментарии (74)