Гипотеза Коллатца. Доказательство

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

§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 (нажмите для просмотра)

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

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

Рисунок 2 (нажмите для просмотра)

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

§3. Шаг назад

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

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

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

$n ≡ 1 \; mod(3) \quad или \quad n ≡ 2 \; mod(3) \quad или \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 и \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:

Рисунок 3 (нажмите для просмотра)

Чтобы подняться из числа 11 на шаг наверх, нам нужно решить равенство $3x+1=2n$, где $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).$
Но давайте возьмем другой пример:

Рисунок 4 (нажмите для просмотра)

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

$3x+1=4n, \quad 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$ мы заменяем одно нечетное число на другое, но спуск к единице не меняется.

Рисунок 5 (нажмите для просмотра)

§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, и продолжим каждую последовательность:

Рисунок 6 (нажмите для просмотра)

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

$n ≡ 1 \; mod(3) \quad или \quad n ≡ 2 \; mod(3) \quad или \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 ≡ 2 mod(3).

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

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

Рисунок 7 (нажмите для просмотра)

Число 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. И каждая такая ветка обречена спуститься к единице. Ч.т.д.

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

Цитата
martynov-m
Пусть $n$ - нечетное число, тогда чтобы двигаться вперед по правилу $\frac {n–1}{3}$ мы должны:
- Отнять от $n$ единицу $(n–1)$ и разделить на три. Но если мы отнимем от нечетного числа единицу, то мы получим чётное. Четное не делится на три.

Еще раз

Цитата
martynov-m
Четное не делится на три.

))

Цитата
alexx223344
Не мучайтесь, до бесконечности ни одна ветка не достигает непрерывно.

2^n
достигает бесконечности, но по условию она исключена, так как четная

2^n - 1
достигает только до N степени

остальные нечетные
не достигают и до N степени

Вся гипотеза в этой матрице

https://postimg.cc/YjytYN9W
как вертикаль так и горизонталь бесконечный ---
то что автор еле создает таблицами и хочет осмыслить (доказать
то не может ) ,то показано мной строго по правилам и языке выс.
математики .

Ценность характеристического многочлена в том, что собственные значения матрицы являются его корнями.

Наши оппоненты то не понимают их и вряд ли поймут---
составлять как не знают читать тем более --они только грамматику или опечатку могут заметит .



Редактировалось 1 раз(а). Последний 19.03.2023 14:18.