2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Эта тема закрыта, вы не можете редактировать и оставлять сообщения в ней.
 
 Гипотеза Коллатца
Сообщение16.02.2023, 17:08 
Аватара пользователя


12/02/23
69
Гипотеза Коллатца
Это одна из нерешенных проблем математики. Получила широкую известность благодаря простоте формулировки:
- Берём любое натуральное число 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 \cdot a(m) + 1. $

Связь таблицы с гипотезой
Шаг назад в гипотезе Коллатца выглядит следующим образом, пусть 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 $.

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

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

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

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

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

Изображение

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

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

Изображение

Чтобы подняться из числа 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). $
Но давайте возьмем другой пример:

Изображение

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

Заметьте, мы специально взяли два примера, которые дают нам разный остаток от деления на три, но получили одну и ту же зависимость.
Сформулируем её так:
- Если число n связано с другим числом x по правилу 1/3, то число n также будет связано с его производным y по правилу $ y = 4x+1. $
Другими словами, нечетные числа 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).
Каких-либо других правил, связывающих нечетные числа, мы не обнаружили.

 Профиль  
                  
 
 Re: Гипотеза Коллатца
Сообщение16.02.2023, 18:48 


12/02/23
3
Martynov_M
Круто, но можно было просто на компьютере проверить гипотезу Коллатца для чисел от 1 до 1000000000, я так эту гипотезу уже давно доказал, так что опоздали вы

 Профиль  
                  
 
 Re: Гипотеза Коллатца
Сообщение16.02.2023, 18:59 
Аватара пользователя


11/06/12
10390
стихия.вздох.мюсли
vitaliidemid, не желаете поделиться доказательством с общественностью?

 Профиль  
                  
 
 Re: Гипотеза Коллатца
Сообщение16.02.2023, 21:09 
Админ форума


02/02/19
1994
 !  Martynov_M
Даже самые простые формулы должны быть оформлены с помощью $\TeX$: не "n = 7", а $n = 7$. На первый раз в Карантин не понесу, в следующий раз - обязательно.

 Профиль  
                  
 
 Re: Гипотеза Коллатца
Сообщение17.02.2023, 00:36 
Заслуженный участник
Аватара пользователя


15/10/08
11536
Martynov_M
В некоторых местах Вашего Magnum Opus я обнаружил попытки посчитать прообраз отображения Коллатца. Вам это удалось? Если да, то приведите, пожалуйста, результат.

 Профиль  
                  
 
 Re: Гипотеза Коллатца
Сообщение18.02.2023, 18:22 


12/02/23
3
Aritaborian
Нет, я доказал гипотезу, но быть посмешищем не хочу, поэтому доказательства публиковать не буду

 Профиль  
                  
 
 Re: Гипотеза Коллатца
Сообщение18.02.2023, 20:26 
Аватара пользователя


12/02/23
69
Утундрий,
Такой задачи не ставил. Но вы правы. Экспериментально я проверил это на компьютере. Прогнал все последовательности Коллатца от 1 до 1000000000 с условием, что каждому нечетному числу соответствует комбинация:
- два чётных (2n, 4n) для правила 4n+1.
- два чётных (2n, 4n) для правила 1/3, где $ n \equiv 1 \pmod 3 $.
- одно чётное (2n) для правила 1/3, где $ n \equiv 2 \pmod 3 $.

Компьютер сказал, что, да, это так. Других соответствий нет.

 Профиль  
                  
 
 Re: Гипотеза Коллатца
Сообщение18.02.2023, 21:22 
Аватара пользователя


17/02/23
1
Martynov_M в сообщении #1581862 писал(а):
Постулат №1. Все последовательности Коллатца строятся только на связях между нечетными числами.
Взяв наугад некоторую последовательность Коллатца и произвольное нечетное число в ней, мы, конечно, можем вычислить следующее нечетное число (3n+1), но предыдущее не можем. Так что связь односторонняя.

Martynov_M в сообщении #1581862 писал(а):
Вывод:
- Из-за конечности выбираемого нечетного числа и с учетом бесконечности A002450 следует, что гипотеза Коллатца верна.
Нет. Из бесконечности A002450 не следует, что в нее обязательно попадет какой-нибудь элемент из последовательности Коллатца.

 Профиль  
                  
 
 Re: Гипотеза Коллатца
Сообщение18.02.2023, 21:47 
Аватара пользователя


12/02/23
69
mathforum1 в сообщении #1582249 писал(а):
Взяв наугад некоторую последовательность Коллатца и произвольное нечетное число в ней, мы, конечно, можем вычислить следующее нечетное число (3n+1), но предыдущее не можем. Так что связь односторонняя.
Можем. Я публиковал статью на эту тему. Гипотеза Коллатца – это частный случай движения от N до 1. Более полный вариант, безусловно, вы правы, – это движение в сторону от 1 до N (со всеми возможными ответвлениями):

http://mathhelpplanet.com/viewtopic.php?f=51&t=77286

mathforum1 в сообщении #1582249 писал(а):
Из бесконечности A002450 не следует, что в нее обязательно попадет какой-нибудь элемент из последовательности Коллатца.
Это происходит из-за того, что все нечетные числа рекурсивно связаны между собой (см. матрицу спуска), каждое число цепляет другое, и т.д., таким образом все числа цепляют друг друга. Хоть что выбирай, а спуск до единицы уже предрешен.

В упомянутой статье, я как раз пишу об этом:
- Все числа рождаются из единицы, и поэтому их спуск до единицы уже предрешен. Мы можем двигаться как от 1 до N, так и от N до 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, 2, 4, 8, 16, 5, 10, 20, 40, 13, 26, 52, 17, 34, 11, 22, 44, 88, 29, 58, 19, 38, 76, 25
1, 2, 4, 8, 16, 5, 10, 20, 40, 80, 160, 53, 106, 35, 70, 23, 46, 15

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

И тут дилемма... Что появилось раньше: курица или яйцо? Это единица рождает все наши числа, или это все числа спускаются к 1?
Неожиданно, да? :)

Но если мы с вами дошли до такого, значит, мы уже доказали гипотезу. Потому что такая постановка вопроса означает, что мы понимаем, с чем имеем дело.

Да, да, да. Вот именно. Это рекурсивная связь всех чисел со всеми. И матрица спуска это прекрасно демонстрирует. Какое бы число n вы не взяли, оно уже зацепилось за матрицу (за рекурсию) и спуск до единицы предрешен.

Почему? Почему? Почему? – снова предвкушаю я ваши вопросы. :)

Да, потому что по условию самой задачи (!) нам уже дана рекурсивная зависимость всех чисел со всеми. Вы не ослышались. Вот именно. Правило 1/3 – это бесконечная рекурсия нечетных чисел по отношению друг к другу. И если мы с вами хоть раз начали с единицы, то развернув рекурсию в обратную сторону, мы вернемся к 1.

С вашего позволения, я подытожу. Гипотеза Коллатца – это частный случай спуска от N до 1 по рекурсии, которая уже была образована до этого от 1 до N.

Пришло время переименовать эту задачу в «Задачу о рекурсивном возрастании с 1 до N и рекурсивном спуске с N до 1», – вот в такой постановке она была бы решена еще в 1932 г.
И все вопросы сводились бы:
- А как, ты разве не знал, что имеешь дело с рекурсией (которая начинается с единицы)? Ты что серьезно не понимаешь, что такое рекурсия, и почему она снова возвращается в 1?

И какой-нибудь первоклассник во Франкфурте вышел бы к доске в 1932 г. и гордо произнес:
- Я доказал гипотезу Коллатца! Потому что спуск к 1 - это всего лишь развернутая в обратном направлении рекурсия.

И спустя 100 лет, какой-нибудь нобелевский лауреат подошел бы к нему в 2023 г. и спросил:
- Слушай дедушка, а как же ты доказал? Вот не пойму, я. Хоть убей.

И дедушка ответил:

- Правило 1/3 (шаг назад) «равно» правилу 3n+1? Так? Да.

- Почему?

- Потому что это правила одной закономерности. Они одинаковы (зеркальны), идентичны. Они рекурсивно привязаны к mod 3. Они одно целое, их нельзя рассматривать отдельно друг от друга.

- Ок, дедушка! Я всё понял! Но если мы начинаем двигаться с единицы (по правилу 1/3), разве сможем ли мы по 3n+1 вернуться в единицу?

- Да, черт возьми, да! Потому что это одна и та же рекурсия! Выполняя одни и те же действия, нельзя сойти с этого пути.

Доказательство гипотезы Коллатца сводится лишь к одному слову: РЕКУРСИЯ.

 Профиль  
                  
 
 Posted automatically
Сообщение18.02.2023, 21:58 
Админ форума


02/02/19
1994
 i  Тема перемещена из форума «Дискуссионные темы (М)» в форум «Карантин»
по следующим причинам:

- неинформативный заголовок;
- неправильно набраны формулы (краткие инструкции: «Краткий FAQ по тегу [math]» и видеоролик Как записывать формулы);

Исправьте все Ваши ошибки и сообщите об этом в теме Сообщение в карантине исправлено.
Настоятельно рекомендуется ознакомиться с темами Что такое карантин и что нужно делать, чтобы там оказаться и Правила научного форума.

 Профиль  
                  
 
 Posted automatically
Сообщение18.02.2023, 23:35 
Админ форума


02/02/19
1994
 i  Тема перемещена из форума «Карантин» в форум «Дискуссионные темы (М)»
Причина переноса: не указана.

 Профиль  
                  
 
 Re: Гипотеза Коллатца
Сообщение28.02.2023, 21:13 
Аватара пользователя


12/10/16
637
Almaty, Kazakhstan

(Оффтоп)

Вспомнил свое давно забытое старое :

Soul Friend в сообщении #1345553 писал(а):
может кто в этой матрице найдёт доказательство для пункта 3 или 4 предыдущего поста:
Soul Friend в сообщении #1344434 писал(а):
Код:
M=matrix(100, 20)
for(m=1, 20, for(n=1, 100, if(Mod(2*n-1,3)==1, M[n,m]=((2^(2*m)*(2*n-1))-1)/3, if(Mod(2*n-1,3)==2, M[n,m]=((2^(2*m-1)*(2*n-1))-1)/3, M[n,m]=0))))

Эта матрица нечётных чисел, предшествующих перед числами $2n-1$ в последовательности, строющуюся по условиям гипотезы Коллатца.
Изображение

взаимосвязанные последовательности в гипотезе Коллатца:

Изображение


ниже некоторые свойства этой матрицы:


Изображение

В этой матрице числа не повторяются. А вот является ли какое либо число $a$ предшественником числа $b$ которая является предшественником числа $a$ ? Вот в чём вопрос.

 Профиль  
                  
 
 Re: Гипотеза Коллатца
Сообщение18.03.2023, 11:38 
Админ форума


02/02/19
1994
 i  Эта тема закрыта в связи с тем, что ТС полностью переработал свои тезисы. Новую версию можно найти в теме «Гипотеза Коллатца. Доказательство»

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Эта тема закрыта, вы не можете редактировать и оставлять сообщения в ней.  [ Сообщений: 13 ] 

Модераторы: Модераторы Математики, Супермодераторы



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

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


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group