Форум мехмата МГУ по высшей математике
| Пользователям: | Аксиома — это истина, на которую не хватило доказательств. |
Форумы > Математика > Высшая математика > Тема |
Объявления | Последний пост | |
---|---|---|
Работодателям и кадровым агентствам: Размещение вакансий | 26.03.2008 03:07 | |
Правила и принципы форума «Высшая математика» | 28.10.2009 15:17 | |
Книги по математике и экономике в добрые руки! | 10.08.2023 09:45 |
18.03.2023 08:11 Дата регистрации: 1 год назад Посты: 94 | Гипотеза Коллатца. Доказательство Аннотация Доказательство гипотезы Коллатца. Поиск различных зависимостей между натуральными числами. Построение матрицы спуска. Проверка полученных результатов на компьютере. Ключевые слова: гипотеза Коллатца, рекурсия, матрица спуска. §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. И каждая такая ветка обречена спуститься к единице. Ч.т.д. --- С уважением, Автор статьи: Михаил Мартынов, Россия, Оренбург, программист. |
18.03.2023 09:07 Дата регистрации: 6 лет назад Посты: 5 176 | Малая теорема Ферма Сколько писанины без смысла -главное нет общей формулы всех 4n+1 т.е ничего не доказали . А до 1000000 или более и так проверенно до вас. Для первой вашей таблицы есть общая формула которую я составил т.е до вас .уже видели те таблицы и доказали . Общая формула гипотезы Коллатца составленная мной 2022г. т.е полностью доказано одной всего формулой в течение 30мин после исследования. Формулу все же пока не показываю . https://postimg.cc/YjytYN9W Редактировалось 3 раз(а). Последний 18.03.2023 10:10. |
19.03.2023 12:40 Дата регистрации: 13 лет назад Посты: 1 126 | .
Еще раз
)) |
19.03.2023 13:12 Дата регистрации: 3 года назад Посты: 2 475 | 2^n - 1 Не мучайтесь, до бесконечности ни одна ветка не достигает непрерывно. 2^n достигает бесконечности, но по условию она исключена, так как четная 2^n - 1 достигает только до N степени остальные нечетные не достигают и до N степени |
19.03.2023 14:14 Дата регистрации: 6 лет назад Посты: 5 176 | -1/12
Вся гипотеза в этой матрице https://postimg.cc/YjytYN9W как вертикаль так и горизонталь бесконечный --- то что автор еле создает таблицами и хочет осмыслить (доказать то не может ) ,то показано мной строго по правилам и языке выс. математики . Ценность характеристического многочлена в том, что собственные значения матрицы являются его корнями. Наши оппоненты то не понимают их и вряд ли поймут--- составлять как не знают читать тем более --они только грамматику или опечатку могут заметит . Редактировалось 1 раз(а). Последний 19.03.2023 14:18. |
Copyright © 2000−2023 MathForum.Ru & MMOnline.Ru Разработка, поддержка и дизайн — MMForce.Net |