Гипотеза Коллатца

Гипотеза Коллатца

Сообщение Martynov_M » Чт фев 16, 2023 5:44 pm

Гипотеза Коллатца
Это одна из нерешенных проблем математики. Получила широкую известность благодаря простоте формулировки:
- Берём любое натуральное число 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

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

Изображение

Обратим внимание, что первая строка таблицы - это ни что иное, как последовательность A002450: 1, 5, 21, 85, 341, 1365...
Справочник OEIS предлагает нам следующую формулу: a(m+1) = 4*a(m) + 1.

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

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

Таким образом мы установили зависимость одного нечетного числа от другого.

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

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

Примечание
Конечно, "правило 1/3" - это просто шаг назад в гипотезе Коллатца, и оно дано нам по условию самой задачи. Но именно такое название передает всю суть гипотезы – многократное увеличение/уменьшение числа n на 1/3, пока оно не скатится до единицы.

Вопрос. Можно ли по этой таблице спуститься к 1?
Да, можно. Это не просто таблица, это матрица спуска к единице. Спуск выглядит следующим образом:

Изображение

На рисунке выше для чисел 3, 9, 15, 21 мы изобразили только 1 переход. Это связано с тем, что эти числа особенные, они делятся на 3. В конце статьи мы расскажем про них более подробно.

Особая связь (4n + 1)
Давайте посмотрим на последовательности для 7 и 29.

Изображение

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

[tex]3x+1=2n , \ n = \frac {3x+1} {2}[/tex]

[tex]3y+1=8n , \ n = \frac {3y+1} {8}[/tex]

[tex]\frac {3x+1} {2} = \frac {3y+1} {8}[/tex]

[tex]y = 4x+1[/tex]

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

Изображение

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

[tex]3x+1=4n , \ n = \frac {3x+1} {4}[/tex]

[tex]3y+1=16n , \ n = \frac {3y+1} {16}[/tex]

[tex]\frac {3x+1} {4} = \frac {3y+1} {16}[/tex]

[tex]y = 4x+1[/tex]

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

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

Если взять наш пример, то мы увидим:
37, 112, 56, 28… - это всего лишь производная ветка от 9, 28...
29, 88, 44, 22… - это всего лишь производная ветка от 7, 22...
Расстояние между 9 и 37 два чётных числа. Расстояние между 7 и 29 тоже два чётных числа.

Таким образом, мы установили, что для правила 4n+1 нечетные числа отделены друг от друга двумя чётными. Как нам уже известно, в правиле 1/3 расстояние между нечетными тоже не более двух чётных (2n, 4n).
Никаких других закономерностей мы не нашли. И забегая вперед, скажем, что их нет.

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

Из этого следует:
- Если в последовательности Коллатца встречается более двух подряд идущих чётных чисел, то их можно разложить на комбинацию нечетных. При этом спуск до единицы не изменится (см. рисунок).

Изображение

С учетом того, что никаких правил кроме 1/3 и 4n+1 в гипотезе Коллатца не существует, повторимся, это означает, что все чётные числа - это порождение формул 1/3 и 4n+1.

Таким образом, главный наш вывод:
- Мы можем убрать все чётные числа в последовательностях Коллатца, и оперировать только лишь правилами 1/3 и 4n+1.
- Любая последовательность Коллатца – это всего лишь последовательность нечетных чисел, следующих друг за другом по правилам 1/3 и 4n+1.

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

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

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

Окончательный вывод
Постулат №1. Все последовательности Коллатца строятся только на связях между нечетными числами.

Постулат №2. Любое нечетное число привязано к двум другим нечетным числам на расстоянии 1/3, либо по формуле (4n+1).

Постулат №3. Нечетное число не может бесконечно возрастать на 1/3, потому что оно ограничено самим правилом 1/3. Применение правила 1/3 несколько раз подряд всегда дает разный остаток от деления на 3. Другими словами, нет такого числа, которое бы бесконечно возрастало на 1/3 по правилу 1/3.

Постулат №4. Единица, в виде известной нам последовательности A002450, разбросана на множестве натуральных чисел бесконечно много раз:

Изображение

Постулат №5. Для каждого числа соприкасающегося с A002450 происходит спуск к единице (не требует доказательства).

Вывод:
- Из-за конечности выбираемого нечетного числа и с учетом бесконечности A002450 следует, что гипотеза Коллатца верна.

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

3 -> 5
9 -> 7
15 -> 23
21 -> 5 (4n+1)
27 -> 41
33 -> 25
39 -> 59
45 -> 11 (4n+1)
51 -> 77
57 -> 43
63 -> 95
69 -> 17 (4n+1)

Здесь прослеживается аналогия с чётными числами. Поэтому сделаем вывод:
- Множество натуральных чисел от 1 до N (с точки зрения гипотезы Коллатца) можно разделить на фальшивые и истинные числа. Фальшивыми мы будем называть те числа, которые имеют только одну связь с нечетным числом. Например, все чётные числа - это фальшивые, потому что они всегда приведут нас только к одному нечетному числу. Числа кратные трем тоже фальшивые, они всегда приведут нас только к одному нечетному числу. Такого рода числа не меняют сути доказательства. Спуск к единице для фальшивых чисел аналогичен спуску к единице для истинного числа. Наше доказательство учитывает все истинные числа.
Т.о. гипотеза Коллатца верна. Что и требовалось доказать.

Матрица спуска

Мы проверили матрицу спуска для чисел от 1 до 1000000000 на компьютере. Все числа гарантированно спускаются к единице по заданным в матрице правилам (1/3 и 4n+1).
Каких-либо других правил, связывающих нечетные числа, мы не обнаружили.
Martynov_M
 
Сообщения: 3
Зарегистрирован: Вс фев 12, 2023 9:08 pm

Вернуться в Высшая математика



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей и гости: 1

cron