Гипотеза Коллатца. Первый шаг к доказательству

[Martynov_M]

Ende
Название темы изменено по просьбе топикстартера.

Аннотация
Доказательство гипотезы Коллатца. Поиск различных зависимостей между натуральными числами. Построение матрицы спуска. Проверка полученных результатов на компьютере. Ключевые слова: гипотеза Коллатца, рекурсия, матрица спуска.

§1. Введение
Гипотеза Коллатца - это одна из нерешенных проблем математики. Получила широкую известность благодаря простоте формулировки:
Берём любое натуральное число $n$; Если оно чётное, разделим его на 2, а если нечетное, то умножаем на 3 и прибавляем 1 (получаем $3n+1$); Над полученным числом выполняем те же самые действия, и так далее.
Какое бы начальное число $n$ мы ни взяли, рано или поздно мы получим единицу, - так гласит гипотеза. И надо это доказать.

Давайте посмотрим на последовательности в гипотезе Коллатца ($3n+1$):

3, 10, 5, 16, 8, 4, 2, 1
5, 16, 8, 4, 2, 1
7, 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1
9, 28, 14, 7, 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1
11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1
13, 40, 20, 10, 5, 16, 8, 4, 2, 1
15, 46, 23, 70, 35, 106, 53, 160, 80, 40, 20, 10, 5, 16, 8, 4, 2, 1
17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1
19, 58, 29, 88, 44, 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1
21, 64, 32, 16, 8, 4, 2, 1
23, 70, 35, 106, 53, 160, 80, 40, 20, 10, 5, 16, 8, 4, 2, 1
25, 76, 38, 19, 58, 29, 88, 44, 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1

§2. Таблица нечетных чисел



Вопрос. Можно ли по этой таблице спуститься к 1? Да, можно.
Это не просто таблица, это матрица спуска к единице.

Спуск выглядит следующим образом:



Для спуска к единице требуется всего два правила. Это "шаг назад" и правило $4x + 1.$

§3. Шаг назад

Шаг назад в гипотезе Коллатца выглядит следующим образом, пусть $n$ - нечетное число, тогда:
- Чтобы получить предыдущее мы должны умножить $n$*2.
- Предположим, перед $2n$ находится нечетное число $x$. Тогда справедливо равенство: $3x + 1 = 2n.$
- Получаем $x = \frac {2n-1}{3}$
- Результат $\frac{2n}{3} - \frac{1}{3}$ будет целым только в том случае, если $n \equiv 2 \pmod 3$.

Тогда для $n \equiv 1 \pmod 3$ удвоим количество четных чисел:
- Умножаем $n$ на 2, и снова на 2.
- Предположим, перед $4n$ находится нечетное число $x$. Тогда справедливо равенство: $3x + 1 = 4n.$
- Получаем $x = \frac {4n-1}{3}$
- Результат $\frac{4n}{3} - \frac{1}{3}$ всегда будет целый для $n \equiv 1 \pmod 3$.

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

$$n \equiv 1 \pmod 3 \quad \text{или} \quad n \equiv 2 \pmod 3 \quad \text{или} \quad n = 4x + 1.$$

Итак, в таблице:
$a(1)$ - это шаг назад,
$b(n)$ - это нечетное число,
$x$ - нечетное число для случая $b(n) = 4x+1.$
$a(m)$ - последовательность чисел, привязанная к $b(n)$.

§4. Правило 1/3 (одна треть)

Рассмотрим полученные формулы с другого ракурса: $\frac{2n}{3} - \frac{1}{3} \quad \text{и} \quad \frac{4n}{3} - \frac{1}{3}.$
Не будем обращать внимание на $\frac{1}{3}$, как пренебрежительно малое число, и сосредоточимся только на $\frac{2n}{3}$ и $\frac{4n}{3}$. Это ни что иное, как уменьшение/увеличение числа n на $\frac{1}{3}$. Такое уменьшение/увеличение будем называть "правилом 1/3".

§5. Особая связь ($4x + 1$)

Давайте посмотрим на последовательности для 7 и 29:



Чтобы подняться из числа 11 на шаг наверх, нам нужно решить равенство $3x+1=2n, \text{ где } n = 11$.
А что если мы хотим еще выше? Давайте решим его для $8n$:

$3x+1=2n, \; \; n= \frac {3x+1}{2}$

$3y+1=8n, \; \; n= \frac {3y+1}{8}$

$\frac {3x+1}{2} = \frac {3y+1}{8}$

$y=4x+1$

Да, всё сходится: $n = 11, \; x = 7, \; y = 29 \; (4x+1).$
Но давайте возьмем другой пример:



Чтобы подняться из числа 7 на два шага наверх, нам нужно решить равенство $3x+1=4n, \text{ где } n = 7$.
А что если мы хотим еще выше? Давайте решим его для $16n$:

$3x+1=4n, \; \; n= \frac{3x+1}{4}$

$3y+1=16n, \; n= \frac{3y+1}{16}$

$\frac{3x+1}{4} = \frac{3y+1}{16}$

$y=4x+1$

Да, всё верно: $n = 7, \; x = 9, \; y = 37 \; (4x+1).$

Заметьте, мы специально взяли два примера (7 и 11), которые дают нам разный остаток от деления на три, но получили одну и ту же зависимость.
Сформулируем её так: Если число $n$ связано с другим числом $x$ по правилу 1/3, то число $n$ также будет связано с его производным $y$ по правилу $y=4x+1$.

Другими словами, нечетные числа $x$ и $y$ спускаются к единице по той же последовательности, что и число $n$.

Важно понимать, что применяя правило $4n+1$ мы заменяем одно нечетное число на другое, но спуск к единице не меняется.



§6. Матрица спуска

Мы проверили нашу матрицу спуска для чисел от 1 до 1000000000 на компьютере.
Все числа гарантированно спускаются к единице по заданным в матрице правилам (1/3 и $4n+1$). Каких-либо других правил, связывающих нечетные числа, мы не обнаружили.

Это означает, что мы можем убрать все чётные числа в последовательностях Коллатца, и оперировать только лишь правилами 1/3 и $4n+1$.

§7. Лучший пример - число 27

Давайте сформируем настоящую (истинную) последовательность для 27, используя только лишь правила 1/3 и $4n+1$:

27 $\rightarrow$ 41 $\rightarrow$ 31 $\rightarrow$ 47 $\rightarrow$ 71 $\rightarrow$ 107 $\rightarrow$ 161 $\rightarrow$ 121 $\rightarrow$ 91 $\rightarrow$ 137 $\rightarrow$ 103 $\rightarrow$ 155 $\rightarrow$ 233 $\rightarrow$ 175 $\rightarrow$ 263 $\rightarrow$ 395 $\rightarrow$ 593 $\rightarrow$ 445 $\rightarrow$ 111 $\rightarrow$ 167 $\rightarrow$ 251 $\rightarrow$ 377 $\rightarrow$ 283 $\rightarrow$ 425 $\rightarrow$ 319 $\rightarrow$ 479 $\rightarrow$ 719 $\rightarrow$ 1079 $\rightarrow$ 1619 $\rightarrow$ 2429 $\rightarrow$ 607 $\rightarrow$ 911 $\rightarrow$ 1367 $\rightarrow$ 2051 $\rightarrow$ 3077 $\rightarrow$ 769 $\rightarrow$ 577 $\rightarrow$ 433 $\rightarrow$ 325 $\rightarrow$ 81 $\rightarrow$ 61 $\rightarrow$ 15 $\rightarrow$ 23 $\rightarrow$ 35 $\rightarrow$ 53 $\rightarrow$ 13 $\rightarrow$ 3 $\rightarrow$ 5 $\rightarrow$ 1.

Для чисел 3077, 2429, 445, 325, 61, 53, 13, 5 - мы воспользовались правилом $4n+1$, в остальных случаях 1/3. Мы получили точно такую же последовательность спуска к единице, но все чётные исчезли.

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

Гипотеза выполняет действия $3n+1$ и $n/2$, тогда обратные действия: $\frac {n-1}{3}$ и $n$*2.
Сформулируем это так: Возьмем любое натуральное число $n$; Отнимем из него единицу $(n-1)$; Если результат деления $\frac {n-1}{3}$ будет целый, тогда это будет следующее число; Если нет, то умножаем $n$ на 2; И вообще, всегда умножаем $n$ на 2 для порождения всё новых и новых веток.

Посмотрим на последовательности по данной схеме:

1, 2, 4, 1
1, 2, 4, 8, 16, 5
1, 2, 4, 8, 16, 5, 10, 3
1, 2, 4, 8, 16, 5, 10, 20, 40, 13
1, 2, 4, 8, 16, 5, 10, 20, 40, 13, 26, 52, 17
1, 2, 4, 8, 16, 5, 10, 20, 40, 13, 26, 52, 17, 34, 11
1, 2, 4, 8, 16, 5, 10, 20, 40, 13, 26, 52, 17, 34, 11, 22, 7
1, 2, 4, 8, 16, 5, 10, 20, 40, 13, 26, 52, 17, 34, 11, 22, 7, 14, 28, 9
1, 2, 4, 8, 16, 5, 10, 20, 40, 13, 26, 52, 17, 34, 11, 22, 44, 88, 29, 58, 19

Обратим внимание, что это обычная последовательность Коллатца, только она развернута в обратном направлении и учитывает все числа, все ветки и все ответвления. Распишем это более подробно.

Выполним преобразование для 1:
Число 1. Умножаем на 2. Получаем 2.

Выполним преобразование для 2:
Число 2. Умножаем на 2. Получаем 4.

Выполним преобразование для 4:
Число 4. $\frac {4-1}{3} = 1$.
Число 4. Умножаем на 2. Получаем 8.

Выполним преобразование для 8:
Число 8. Умножаем на 2. Получаем 16.

Выполним преобразование для 16:
Число 16. $\frac {16-1}{3} = 5$.
Число 16. Умножаем на 2. Получаем 32.

Итак, мы на пороге первой развилки! 1, 2, 4, 8, 16 - здесь у нас развилка на 5 и 32.

Зайдем на развилку 5:
1, 2, 4, 8, 16, 5, 10 - здесь у нас снова развилка на 3 и 20.
1, 2, 4, 8, 16, 5, 10, 3, ...
1, 2, 4, 8, 16, 5, 10, 20, ...

Вернемся к числу 32:
1, 2, 4, 8, 16, 32, 64 - здесь у нас снова развилка на 21 и 128.
1, 2, 4, 8, 16, 32, 64, 21, ...
1, 2, 4, 8, 16, 32, 64, 128, ...

На этом остановимся.
Далее мы рассмотрим множество следующего вида:

1
1, 2
1, 2, 4
1, 2, 4, 1
1, 2, 4, 8, 16
1, 2, 4, 8, 16, 5
1, 2, 4, 8, 16, 32
1, 2, 4, 8, 16, 5, 10
1, 2, 4, 8, 16, 5, 10, 3
1, 2, 4, 8, 16, 5, 10, 20, 40
1, 2, 4, 8, 16, 5, 10, 20, 40, 13
...

Каждый элемент этого множества - это последовательность, образованная очередным шагом по обратной схеме.
Применим к этому множеству бесконечное умножение на 2, и продолжим каждую последовательность:



Таким образом, мы приходим к выводу, что выбирая любое натуральное число $n$ в гипотезе Коллатца, мы на самом деле выбираем элемент из этого множества. Потому что каждое нечетное число в этом множестве - это шаг рекурсии:

$$n \equiv 1 \pmod 3 \quad \text{или} \quad n \equiv 2 \pmod 3 \quad \text{или} \quad n = 4x + 1.$$

А каждое чётное число образовано от нечетного простым умножением на 2.
Таким образом, гипотеза Коллатца - это развернутая в обратном направлении рекурсия.

Для доказательства гипотезы Коллатца нам потребуется:
- Построить множество всех вариантов последовательностей Коллатца, что мы и сделали.
- Показать, как все последовательности Коллатца начинаются с единицы, что мы и сделали.
- Ответить на вопрос, есть ли числа, которые попадают в $3n+1$, но не попадают в $\frac {n-1}{3}$?

Таких чисел нет, потому что рекурсивное правило $\frac {n-1}{3}$ это зеркальная копия $3n+1$.

$k=3n+1, \; \; n = \frac {k-1}{3}$.

Это одна и та же рекурсия, просто развернутая в разные стороны. Выполняя одни и те же действия, нельзя сойти с одного и того же пути. Если рекурсия начинается с единицы, то она всегда в неё возвращается (см. книгу С.Клини, Введение в метаматематику, [гл. IX, §46]).

Все последовательности зеркальны, идентичны и обладают одинаковыми свойствами. И мы можем это легко проверить.

§9. Шаг вперед

Пусть $n$ - нечетное число, тогда чтобы двигаться вперед по правилу $\frac {n-1}{3}$ мы должны:
- Отнять от $n$ единицу $(n-1)$ и разделить на три. Но если мы отнимем от нечетного числа единицу, то мы получим чётное. Четное не делится на три.
- Тогда у нас остается только один вариант, умножить $n$*2.
- Предположим, после $2n$ находится нечетное число $x$. Тогда справедливо равенство: $\frac {2n-1}{3} = x$.
- Получаем $x = \frac {2n-1}{3}$
- Результат $\frac {2n}{3} - \frac {1}{3}$ будет целым только в том случае, если $n \equiv 2 \pmod 3$.

Тогда для $n \equiv 1 \pmod 3$ удвоим количество четных чисел:
- Умножаем $n$ на 2, и снова на 2.
- Предположим, после $4n$ находится нечетное число $x$. Тогда справедливо равенство: $\frac {4n-1}{3} = x$.
- Получаем $x = \frac {4n-1}{3}$
- Результат $\frac {4n}{3} - \frac {1}{3}$ всегда будет целый для $n \equiv 1 \pmod 3$.

Тоже самое и с правилом $4n+1$:



Число 11 порождает две ветки. Зайдем в первую ветку $2n$:

$\frac {2n-1}{3} = x, \; \; n = \frac {3x+1}{2}$

Зайдем во вторую ветку $8n$:

$\frac {8n-1}{3} = y, \; \; n = \frac {3y+1}{8}$

$\frac {3x+1}{2} = \frac {3y+1}{8}$

$y=4x+1$

Да, всё верно: $n = 11, \; x = 7, \; y = 29 \; (4x+1).$

Теперь мы понимаем, почему в гипотезе Коллатца можно заменить нечетное число вида $4n+1$ на его производное и спуск до единицы не изменится. Потому что это раздвоенная ветка одного и того же числа.
Обратим внимание и на цикл «1, 2, 4, 1». Он рождается в обеих схемах, что служит прекрасным доказательством тождественности правил.
Отвечая на вопрос, является ли правило $3n+1$ развернутой в обратном направлении рекурсией $\frac {n-1}{3}$ ? Мы говорим, однозначно, да.

§10. Последний вопрос

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

---
С уважением,
Автор статьи: Михаил Мартынов, Россия, Оренбург, программист.

[Ende]

Martynov_M
Что Вы изменили по сравнению с темой «Гипотеза Коллатца»?

[Martynov_M]

Ende
Спасибо за вопрос.
1. Изменилась суть публикации.
2. Переработан весь текст.
3. Добавлены новые графики (рисунки).
4. Добавлен раздел §8. "Доказательство."
5. В таком виде статья является научной публикацией.
6. Предыдущая статья - дилетантская.

[Ende]

Раз так, я закрыл предыдущую тему и оставил там ссылку на эту тему. Не надо заводить на форуме несколько тем, посвященных одному и тому же.

[tolstopuz]

Применимо ли аналогичное доказательство к проблеме $5n+1$?

-- Сб мар 18, 2023 12:27:48 --

Martynov_M в сообщении #1585833 писал(а):

Но если мы отнимем от нечетного числа единицу, то мы получим чётное. Четное не делится на три.

Браво!

[Martynov_M]

tolstopuz в сообщении #1585843 писал(а):

Браво!

Да, действительно, забавно вышло! :)
Придется внести уточнения:

Гипотеза выполняет действия $3n+1$ и $n/2$, тогда обратные действия: $\frac {n-1}{3}$ и $n$*2.

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

-- 18.03.2023, 13:50 --

tolstopuz в сообщении #1585843 писал(а):

Применимо ли аналогичное доказательство к проблеме $5n+1$?

Раз вы задали такой вопрос, тогда, с вашего позволения, дам более обширный ответ. Проблема гипотезы Коллатца, мне кажется, – это проблема в математиках, как людях, которые отрицают рекурсивную природу этой задачи. Это мое мнение, конечно.

Но основатели теории алгоритмов (Тьюринг, Пост, Чёрч, Клини) 100 лет назад показали нам, что не все математические задачи могут быть решены через формулы. Поэтому они ввели такое понятие, как рекурсия. Иногда рекурсия может быть настолько сложной, что её не сразу видно. Такой тип рекурсии называется возвратная рекурсия, или рекурсия пробега. Гипотеза Коллатца – это классическая возвратная рекурсия. Как только математики признают (своим консенсусом) рекурсивную природу этой задачи, обсуждение будет закрыто.

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

Про задачу $5n+1$ я не знаю. Надо смотреть какой там шаг итерации.

[tolstopuz]

Martynov_M в сообщении #1585824 писал(а):

Потому что каждое нечетное число в этом множестве - это шаг рекурсии:

$$n \equiv 1 \pmod 3 \quad \text{или} \quad n \equiv 2 \pmod 3 \quad \text{или} \quad n = 4x + 1.$$

К какому из этих случаев относится число $15$?

[Martynov_M]

tolstopuz в сообщении #1585849 писал(а):

К какому из этих случаев относится число $15$?

$n \equiv 2 \pmod 3$.

Вы шагаете из единицы. Доходите до числа 23. Следующий ваш шаг - число 15. Получили 15? Отлично! Рекурсия в этой ветки отработала. Переходите к другим веткам.

[tolstopuz]

Martynov_M в сообщении #1585824 писал(а):

$\rightarrow$ 61 $\rightarrow$ 15 $\rightarrow$ 23 $\rightarrow$ 35 $\rightarrow$ 53 $\rightarrow$ 13 $\rightarrow$ 3 $\rightarrow$ 5 $\rightarrow$ 1.

А как же я, шагая из единицы, получу $61$, если после $15$ перейду к другим веткам?

[Martynov_M]

Я знал, что вы зададите этот вопрос. :)
Спасибо вам очень большое за ваши вопросы!
Да, всё верно. После 15 рекурсия идет на 61. Т.к. это прописано в самой рекурсии. Шаг итерации:

$$n \equiv 1 \pmod 3 \quad \text{или} \quad n \equiv 2 \pmod 3 \quad \text{или} \quad n = 4x + 1.$$

После того, как мы получили $15, n \equiv 0 \pmod 3$, мы всё равно продолжаем эту ветку, потому что есть еще число $61, n = 4x + 1.$

[lek]

Martynov_M в сообщении #1585824 писал(а):

Мы проверили нашу матрицу спуска для чисел от 1 до 1000000000 на компьютере.
Все числа гарантированно спускаются к единице по заданным в матрице правилам (1/3 и $4n+1$). Каких-либо других правил, связывающих нечетные числа, мы не обнаружили.

Обычно такая таблица строится с помощью функции обратной к функции Сиракуз $f:a_m\to b=(3a_m+1)/2^p$, где $a_m$ и $b$ - нечетные натуральные числа. В этом случае ваше правило $4n+1$ выполняется автоматически, поскольку тогда $b'=(3(4a_m+1)+1)/2^p'=(3a_m+1)/2^{p'-2}=b$, где $p'=p+2$.

Martynov_M в сообщении #1585824 писал(а):

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

Общеизвестно, что гипотеза Коллатца эквивалентна утверждению, что существует $n$-я итерация функции Сиракуз такая, что $f^n(k)=1$ для любого нечетного натурального $k$. Как это утверждение следует из вашей конструкции, непонятно.

[Martynov_M]

lek в сообщении #1585880 писал(а):

Как это утверждение следует из вашей конструкции, непонятно.

Lek
Я не математик. Поэтому прошу снисхождения, если что-то я не понимаю и спрашиваю у вас.
Но первое, на что мы должны обратить внимание, что гипотеза Коллатца – это развернутая в обратном направлении рекурсия. В таком случае мы переходим к исходной рекурсии.

Исходная рекурсия начинается с единицы. Это и есть причина, по которой все последовательности Коллатца заканчиваются на единице.

[tolstopuz]

Martynov_M в сообщении #1585878 писал(а):

$$n \equiv 1 \pmod 3 \quad \text{или} \quad n \equiv 2 \pmod 3 \quad \text{или} \quad n = 4x + 1.$$

После того, как мы получили $15, n \equiv 0 \pmod 3$, мы всё равно продолжаем эту ветку, потому что есть еще число $61, n = 4x + 1.$

То есть условие на шаг итерации написано для красоты, потому что мы не смотрим на него, а все равно продолжаем, в результате чего в настоящей (истинной) последовательности появляются не только числа, удовлетворяющие вышепроцитированному условию, но и прочие нечетные числа.

Замечательно. Это означает, что параграфы 1-7 излишни и доказательство можно сильно сократить, начав сразу с параграфа 8. Согласны?

[Martynov_M]

tolstopuz в сообщении #1585886 писал(а):

Это означает, что параграфы 1-7 излишни и доказательство можно сильно сократить, начав сразу с параграфа 8. Согласны?

Да, безусловно.

[tolstopuz]

Martynov_M в сообщении #1585883 писал(а):

Исходная рекурсия начинается с единицы. Это и есть причина, по которой все последовательности Коллатца заканчиваются на единице.

Например, в проблеме $5n+1$ существует цикл $13, 66, 33, 166, 83, 416, 208, 104, 52, 26, 13...$, то есть рекурсия, начинающаяся с единицы, никогда не дойдет до этих чисел. Где в вашем рассуждении доказательство, что аналогичного цикла не существует в проблеме $3n+1$?