Гипотеза Коллатца, часть 3

Аннотация

Это третья статья из цикла «Доказательство гипотезы Коллатца».
Первая часть находится здесь.
Вторая часть здесь.

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

Как известно, гипотеза Коллатца может оказаться неверна только лишь в том случае, если существует такое число n, которое зацикливается или уходит в бесконечность. В противном случае, число n всегда достигает единицы.

В первой части публикации мы выяснили, почему вообще гипотеза Коллатца начинается с единицы. Во второй части мы доказали, что в 3n+1 не существует циклов и повторов. Сейчас же мы покажем, почему сиракузские последовательности не могут уйти в бесконечность и слева, и справа. Бесконечность для них только одна, она начинается с единицы.

§2. Терминология

Гипотеза Коллатца – это алгоритм.
Что такое алгоритм? Это совокупность точно заданных правил (набор инструкций).

Если развернуть 3n+1 в обратную сторону $\frac {n-1}{3}$ , то это тоже алгоритм? – спросите вы.
– Да, это тоже алгоритм. Но другой, – отвечу я.

Пример последовательности 3n+1:
13, 40, 20, 10, 5, 16, 8, 4, 2, 1.

Пример последовательности $\frac {n-1}{3}:$
1, 2, 4, 8, 16, 5, 10, 20, 40, 13 …

§3. Разговор двух программистов

1 мая 2022 года, время полночь:
– Бро, как охватить все последовательности Коллатца?
– Нужно изменить алгоритм $\frac {n-1}{3}$ .
– Как?
– Добавить в него новую инструкцию.
– Какую?
– На разветвление.
– Но это будет другая задача!
– Да. Именно! Она и строит все последовательности Коллатца.
– Допустим, ты прав. Но как это поможет нам с доказательством?
– Что первичнее? Полная версия алгоритма или обрубок?
– Конечно, полная! Обрубок 3n+1 вообще ничего не умеет, только спускаться к 1… Постой, подожди. На что ты намекаешь? Ты хочешь сказать, что математики на протяжении 100 лет решали не ту задачу?
– Вот именно.
– Я в шоке! Что дальше?
– Мы выкинем все чётные числа из алгоритма.
– Так нееееельзя! Это издевательство над математиками!
– Мы творцы алгоритмов и делаем с ними всё что хотим.
– К чему ты клонишь?
– У меня есть подозрение, что программисты подсунули математикам «кота в мешке». Алгоритм $\frac {n-1}{3}$ и вся гипотеза Коллатца – это порождение другой сущности…, – сказал один приятель другому, и в это время небо в Оренбурге заволокло тучами.

Раздался гром. Два русских мужика из сельской глубинки на границе Казахстана, перекрестились, опрокинули стакан водки, и произнесли тост за упокой «Великой недосягаемой гипотезы Коллатца».

§4. Рекурсия

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

Но что вообще из себя представляет эта «обратная схема»? Ведь мы замахнулись на охват сразу всех последовательностей Коллатца. Мы строим всё дерево целиком!

Сделав одно открытие, мы даже не заметили, как перешли к другому. Прошел год с момента публикации. Этого достаточно, чтобы всё осмыслить.

§5. Что такое рекурсия?

Рекурсия – это описание какого-либо объекта через самого себя.

С точки зрения натуральных чисел, все числа – это порождение других чисел. Все числа имеют уникальные рекурсивные связи. Все числа имеют родителя и потомков. Все числа рекурсивно связаны друг с другом. Единица, однажды породив число, уже никогда не сможет остановиться, – гласит вселенская истина. Всё это и есть рекурсия.

Словами Наполеона Бонапарта: «Рекурсия породила миф о гипотезе Коллатца, рекурсия его и убила!»

Для осознания рекурсии программисты часто используют конструкцию:
рекурсия $\rightarrow$ см. рекурсия $\rightarrow$ см. рекурсия $\rightarrow$ см. рекурсия $\rightarrow$ …

Как известно, сила рекурсии – в её способности описать бесконечное число операций c бесконечным числом элементов только через саму себя, как сущность, не прибегая при этом ни к каким другим понятиям. Рекурсия – Бог алгоритмов.

§6. Рекурсия в рекурсии, вот где собака зарыта!

На строгом математическом языке рекурсию $\frac {n-1}{3}$ можно классифицировать как классическую взаимную рекурсию, когда одно нечетное число расщепляется на два других. И этот процесс зацикливается сам на себе (уходит в бесконечность):

Стоит отметить, что в прикладных задачах всегда есть ограничение на количество «саженцев». Но в гипотезе Коллатца таких ограничений нет, и мы можем расщеплять число бесконечно долго.

Такой вид рекурсии, как известно, образует двоичное дерево в Теории графов:

§7. Шаг рекурсии

Строго говоря, такого термина как «шаг рекурсии» в математике нет. Он используется только в программировании. И только в случае, когда взаимная рекурсия упрощается до прямой рекурсии, что мы и сделали в первой части работы.

Но в математике с этим дела обстоят еще хуже.

Взаимная рекурсия – это абстракция абстракций, её нельзя записать формулой. Всё, что мы можем сделать, это использовать функцию F для фиксации каждого нашего действия, каждого нашего перехода по дереву, каждой генерации сиракузской последовательности, каждого разветвления нечетного числа:

$F = [f_{1}(n), f_{2}(n)],$
где

$f_{1}(n) = \begin{cases} \frac{2n-1}{3}, & n ≡ 2 \; mod \; (3) \\ \frac{4n-1}{3}, & n ≡ 1 \; mod \; (3) \\ 0, & otherwise \end{cases}$

$f_{2}(n) = 4n+1.$

Такая запись эквивалентна понятию «шаг рекурсии», на который мы ссылались в предыдущих работах. Но функция F не имеет для нас никакого практического смысла. Она лишь служит доказательством, что такой вид рекурсии – тоже рекурсия. Проверили. Доказали. Идем дальше.

§8. Ряд нечетных чисел

Переходим к бесконечности. Все нечетные числа по модулю 3 равномерно рассредоточены в ряду нечетных чисел: 3k, 3k-1, 3k-2.

Сдвигая любое нечетное число по правилу $\frac{2n-1}{3},$ $\frac{4n-1}{3}$ с позиции 3k-1, 3k-2 мы всегда получаем число 3k. Для каждого числа n количество сдвигов разное. Но все они упираются в 3k, «хвост рекурсии». Почему так происходит?

Как показано в этой статье, это происходит из-за того, что среди нечетных чисел есть такие числа, которые «привязаны» к числу 3k. Мы будем называть их маркерами. Как только последовательность $\frac {n-1}{3}$ доходит до такого маркера, она сразу же упирается в 3k. Выглядит это следующим образом:

Не пугайтесь. Всё просто:

Числа вида 3k-1, 3k-2 порождают друг друга через правила $\frac{2n-1}{3},$ $\frac{4n-1}{3}$ .
Они делают это до тех пор, пока не поймают свой маркер.
Маркеры – это те же числа 3k-1, 3k-2, но только «привязанные» к 3k.
Маркеры всегда раздваиваются. Одна ветка уходит на 3k, другая на 4x+1.
Маркеры «А» – особенные, они могут порождать сразу два хвоста рекурсии 3k.
Маркеры «Б» так не умеют.
Числа вида 3k-1 могут порождать число 3k через правило 4x+1.
Числа 3k-2 так не умеют.
Любой выход из блока (применение правила 4x+1) означает создание нового блока.
Новый блок всегда начинается с 3k-1, 3k-2.

Пример.

Число 111:
… 111 $\rightarrow$ 445 $\rightarrow$ 593 $\rightarrow$ 395 $\rightarrow$ 263 $\rightarrow$ 175 $\rightarrow$ 233 $\rightarrow$ 155 $\rightarrow$ 103 $\rightarrow$ 137 $\rightarrow$ 91 $\rightarrow$ 121 $\rightarrow$ 161 $\rightarrow$ 107 $\rightarrow$ 71 $\rightarrow$ 47 $\rightarrow$ 31 $\rightarrow$ 41 $\rightarrow$ 27.

Как мы видим, 111 – это хвост рекурсии (3k), он принадлежит другому блоку. Применяем к нему правило 4x+1. Получаем новый блок. Стартовое число 445. Применяем к нему правила $\frac{2n-1}{3},$ $\frac{4n-1}{3}$ . Натыкаемся на маркер 41.

Маркер не простой. Он особенный. Принадлежит классу «А». Этот маркер порождает сразу два хвоста (27, 165). Наш блок отработал. Но в процессе он сгенерировал 20 новых чисел. Применяем к каждому из них 4x+1 и получаем еще 20 новых блоков. Это и есть рекурсия. Бесконечное разветвление чисел.

§9. Математическое обоснование

Мы проверили триллионы последовательностей Коллатца на компьютере, и все они оказались блоками рекурсии по схеме описанной выше.

Как уже было сказано, существование маркеров было доказано нами в этой статье. Поэтому сейчас мы рассмотрим только переходы по правилу 4x+1:

имеет целочисленное решение. Это означает, что числа 3k-1 могут порождать 3k через правило 4x+1.

не имеет решения.

Последнее равенство можно интерпретировать так: «Хвост никогда не сможет породить еще один хвост, потому что он хвост».

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

§10. «Золотое сечение»

Мы подсчитали процент маркеров и получили цифру 22.22%. Это огромный удельный вес для оставшихся 44.44% чисел.

Даже если по каким-то причинам числа 3k-1, 3k-2 избежали первой встречи с маркером, они всё равно обречены наткнуться на него. Это обусловлено равномерностью их распределения.

Другими словами, «золотое сечение» в гипотезе Коллатца (охват всех чисел) достигается:
– Во-первых, пропорциональностью всех классов 3k, 3k-1, 3k-2 по отношению друг к другу.
– Во-вторых, отсутствием циклов (см. предыдущую работу).
– В-третьих, правилом 4x+1.

§11. Правило: 4x+1.

Начиная с единицы, рекурсия соединяет все блоки между собой правилом 4x+1. Это означает, что двигаясь в обратном направлении (по схеме 3n+1) можно разложить любое нечетное число на эти же самые блоки и снова получить единицу.

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

«Фальшивость» 3n+1 сделала из этой задачи настоящую головоломку века, а в совокупности с нетерпимостью математиков к рекурсиям, сформировала легенду.

«Нет такого математика, которой бы не потерпел крах в гипотезе Коллатца», – говорится в различной литературе, и добавляется: «Наука бессильна! Даже не пытайтесь её доказать!»

Но вот перед нами обычная последовательность Коллатца:
53 $\rightarrow$ 160 $\rightarrow$ 80 $\rightarrow$ 40 $\rightarrow$ 20 $\rightarrow$ 10 $\rightarrow$ 5 $\rightarrow$ 16 $\rightarrow$ 8 $\rightarrow$ 4 $\rightarrow$ 2 $\rightarrow$ 1.

Теперь сравним её с нашей рекурсивной моделью:
53 $\rightarrow$ 13 $\rightarrow$ 3 $\rightarrow$ 5 $\rightarrow$ 1.

Как мы видим, в последовательности Коллатца отсутствуют числа 13 и 3. Куда они делись?
– Их там не должно быть, – скажите вы, – Потому что (53*3 + 1) = 160, 160/2 = 80…
– Нет, – скажу я вам, – Вы не правы. Они там есть.
– Но где? Мы вам не верим, покажите!
– Но тогда вопрос уже к Вам. Что, по-вашему, означает то самое правило 4x+1 в контексте нашей рекурсии?
– Оно означает, что любое нечетное число можно разложить на определенное количество блоков, вплоть до единицы. Потому что эти блоки образованы из единицы. Это элементарно, Ватсон! Вы же сами сказали.
– Вот именно! Тогда зачем Вы ломаете блок? Почему не применяете 4x+1?
– Но как?
– Замените 53 на 13, 13 на 3, и вы получите рекурсию в том виде, в котором она и была.

Один из контр-примеров к моим работам обычно звучал так: – А ну-ка объясни:
1365, 4096, 2048, 1024, 512, 256, 128, 64, 32, 16, 8, 4, 2, 1.

Действительно, без математической модели не было смысла идти к математикам. Но теперь всё встало на свои места. Любое число вида «4x+1» – это ограничитель. Это блок. Нельзя пренебрегать им.

Становится очевидным, что любая сиракузская последовательность «фальшива» по своей сути, по своему определению, потому что она не учитывает переходы 4x+1.

– Но что будет, если мы будем учитывать все переходы 4x+1? – спросите вы.
– Тогда вы получите рекурсию в том виде, в котором она и была. Вы получите набор блоков, связанных между собой правилом 4x+1.

§12. Но что если маркера нет? Тогда ваша мат. модель не работает?

Рассмотрим такое число n, которое бесконечно долго прыгает по правилам $\frac{2n-1}{3},$ $\frac{4n-1}{3}$ и никак не может найти свой маркер.

Случай 1. Правило $\frac{2n-1}{3}$ преобладает над числом, и оно спускается к единице.
Но спуск к единице возможен только лишь по тем числам, которые уже и так находятся рядом с единицей. Это означает образование цикла в гипотезе Коллатца. Например, 3 -> 13, n -> 13. Но мы доказали, что циклов нет. Получаем противоречие. Отсюда следует, что такого числа нет.

Случай 2. Правило $\frac{4n-1}{3}$ преобладает над числом, и оно уходит в бесконечность.
Но мы и так движемся из единицы в бесконечность. Здесь нет противоречий.

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

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

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

ссылка на оригинал статьи https://habr.com/ru/articles/738260/

Гипотеза Коллатца, часть 3

Комментарии

Добавить комментарий Отменить ответ