Меню
Эта первая статья из цикла "Доказательство гипотезы Коллатца", и на сегодняшний день единственная статья (в мире), раскрывающая истинную природу гипотезы Коллатца.
В этой статье автор подробно разбирает алгоритм гипотезы Коллатца, его структуру, свойства и особенности.
Все последующие статьи автора будут опираться на эту работу.
Ключевые слова: гипотеза Коллатца, алгоритм, рекурсия, шаг рекурсии, рекурсивный спуск, рекурсивный подъем.
§1. Постановка вопроса
Гипотеза Коллатца – это одна из нерешенных проблем математики. Получила широкую известность благодаря простоте формулировки:
Берём любое натуральное число [tex]n[/tex]; Если оно чётное, разделим его на 2, а если нечетное, то умножаем на 3 и прибавляем 1 (получаем 3n+1); Над полученным числом выполняем те же самые действия, и так далее.
Какое бы начальное число [tex]n[/tex] мы ни взяли, рано или поздно мы получим единицу, – так гласит гипотеза. И надо это доказать.
§2. Введение
В математических кругах уже давно ходят легенды о недоказуемости этой задачи. Так, например, американский математик J. Lagarias вспоминает:
"В 1960-м более месяца весь Йельский университет безрезультатно трудился над проблемой 3n+1. Это было что-то невероятное. Такая же участь постигла и исследователей Чикагского университета, когда я сообщил им об этой задаче. Ходила шутка, что 3n+1 – это заговор советских ученых против США, чтобы снизить научный потенциал Америки и замедлить наши исследования в других областях."
В 2007 г. математики S. Kurtz и J. Simon пришли к выводу, что в такой постановке вопроса задача 3n+1 не доказуема.
В 2010 г. Американское математическое сообщество выпустило сборник "Безграничный вызов для математики: 3x+1". Эта книга рассказывает о неудачных попытках найти решение для 3n+1.
Несмотря на всё это, автор, Михаил Мартынов, нашел в себе силы и раскрыл истинную суть гипотезы Коллатца. Поэтому данная статья является (на сегодняшний день) прорывом в области изучения [tex]3n+1[/tex] и показывает, что гипотеза Коллатца – это всего лишь часть алгоритма. Для доказательства гипотезы Коллатца нам нужно перейти к совсем другой задаче.
§3. Полная версия алгоритма
Гипотеза выполняет действия [tex]3n+1[/tex] и [tex]n/2[/tex], тогда обратные действия: [tex]\frac {n-1}{3}[/tex] и [tex]n[/tex]*2.
Сформулируем это так: Возьмем любое натуральное число [tex]n[/tex]; Если оно нечетное, тогда умножаем на 2. Если чётное, тогда отнимем из него единицу [tex](n-1)[/tex]; Если результат деления [tex]\frac {n-1}{3}[/tex] будет целый, тогда это будет следующее число; Если нет, то умножаем [tex]n[/tex] на 2; И вообще, всегда умножаем [tex]n[/tex] на 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. [tex]\frac {4-1}{3} = 1[/tex].
Число 4. Умножаем на 2. Получаем 8.
Выполним преобразование для 8:
Число 8. Умножаем на 2. Получаем 16.
Выполним преобразование для 16:
Число 16. [tex]\frac {16-1}{3} = 5[/tex].
Число 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, ...
На этом остановимся.
Алгоритм, который мы только что описали - это рекурсия. Алгоритм [tex]3n+1[/tex] воспроизводит действия [tex]\frac {n-1}{3}[/tex], но только в обратном порядке.
Таким образом, [tex]3n+1[/tex] - это развернутая в обратном направлении рекурсия от рекурсии [tex]\frac {n-1}{3}[/tex]. Именно этим и обусловлен тот факт, что [tex]3n+1[/tex], повторяя зеркальные действия [tex]\frac {n-1}{3}[/tex], спускается к единице.
Другими словами, рекурсия [tex]\frac {n-1}{3}[/tex] создала для нас дерево чисел. Рекурсия [tex]3n+1[/tex] еще не знает, что это за дерево, но шагая по нему обречена спуститься до 1.
§4. Первые выводы
Во-первых, такой вид рекурсии в математике называется возвратная рекурсия или рекурсия пробега (см. книгу С.Клини, Введение в метаматематику, [гл. IX, §46]).
Во-вторых, как очевидно, рекурсия начинается с 1. Единица - прародитель всех веток.
В-третьих, спуск к единице для каждого числа происходит по своей уникальной ветке.
В-четвертых, единица не может иметь другого прародителя, кроме самого себя, потому что [tex]\frac {n-1}{3}[/tex] и [tex]3n+1[/tex] дают для единицы - единицу (цикл 1, 4, 2, 1).
В-пятых, гипотеза Коллатца - это алгоритм, образованный от алгоритма [tex]\frac {n-1}{3}[/tex], и поэтому сохраняющий все его свойства.
§5. Чётные числа
Шаг рекурсии [tex]\frac {n-1}{3}[/tex] кажется нам невероятно сложным из-за наличия чётных чисел. Но влияют ли они на рекурсию?
Давайте посмотрим на шаг рекурсии:
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. Нечётные числа
Пусть [tex]n[/tex] - нечетное число, тогда, чтобы двигаться вперед по правилу [tex]\frac {n-1}{3}[/tex], мы должны:
- Умножить [tex]n[/tex]*2, потому что [tex]n[/tex] - нечетное число.
- Предположим, после [tex]2n[/tex] находится нечетное число [tex]x[/tex]. Тогда справедливо равенство: [tex]\frac {2n-1}{3} = x[/tex].
- Получаем [tex]x = \frac {2n-1}{3}[/tex]
- Результат [tex]\frac {2n}{3} - \frac {1}{3}[/tex] будет целым только в том случае, если [tex]n \equiv 2 \pmod 3[/tex].
Тогда для [tex]n \equiv 1 \pmod 3[/tex] удвоим количество чётных чисел:
- Умножаем [tex]n[/tex] на 2, и снова на 2.
- Предположим, после [tex]4n[/tex] находится нечетное число [tex]x[/tex]. Тогда справедливо равенство: [tex]\frac {4n-1}{3} = x[/tex].
- Получаем [tex]x = \frac {4n-1}{3}[/tex]
- Результат [tex]\frac {4n}{3} - \frac {1}{3}[/tex] всегда будет целый для [tex]n \equiv 1 \pmod 3[/tex].
§7. Хвост рекурсии
Обратим внимание, что получив на любом шаге нечетное число вида [tex]n \equiv 0 \pmod 3[/tex], мы не сможем продолжить генерацию чисел [tex]\frac {2n-1}{3}[/tex], или [tex]\frac {4n-1}{3}[/tex], или [tex]\frac {8n-1}{3}[/tex], или [tex]\frac {16n-1}{3},[/tex] или любой другой степени двойки [tex]2^k[/tex].
Потому что если [tex]n \equiv 0 \pmod 3[/tex], то решение уравнения [tex](\frac {2^kn}{3} - \frac {1}{3})[/tex] сводится к виду: [tex]2^kz - \frac {1}{3}[/tex]. Оно не имеет целочисленного решения.
Числа вида [tex]n \equiv 0 \pmod 3[/tex] мы будем называть хвостом рекурсии.
§8. Особая связь ([tex]4x + 1[/tex])
Алгоритм [tex]\frac {n-1}{3}[/tex] подразумевает постоянное умножение на 2.
Чтобы мы ни делали, мы всегда умножаем на 2. Именно в этом кроется ответ на вопрос, почему все нечетные числа в последовательностях Коллатца отделены друг от друга чётными.
В таком случае возникает ситуация, когда нечетное число может дать нам сразу две ветки нечетных чисел (как на рисунке выше). Т.е. нечетное число "раздваивается" на два нечетных числа.
Первый случай.
Как мы уже выяснили, если существует такое нечетное число [tex]n \equiv 2 \pmod 3[/tex], то из этого следует, что также существует нечетное число [tex]x = \frac {2n-1}{3}[/tex].
Но если мы умножим [tex]n[/tex] на 8, то обязательно будет существовать число: [tex]y = \frac {8n-1}{3}[/tex]. Потому что любое число [tex]n \equiv 2 \pmod 3[/tex] можно представить как [tex]3k-1[/tex], тогда уравнение [tex]y = \frac {8n-1}{3}[/tex] сводится к решению:
[tex]y = \frac{8(3k-1)-1}{3} = \frac{24k-9}{3}=8k-3[/tex], что, конечно, имеет целочисленное решение.
Есть ли связь между полученными таким образом числами: [tex]x[/tex] и [tex]y[/tex]?
[tex]\frac {2n-1}{3} = x, \; \; n = \frac {3x+1}{2}[/tex]
[tex]\frac {8n-1}{3} = y, \; \; n = \frac {3y+1}{8}[/tex]
[tex]\frac {3x+1}{2} = \frac {3y+1}{8}[/tex]
[tex]y=4x+1[/tex]
Да, связь есть.
Другими словами, из нечетного числа [tex]n \equiv 2 \pmod 3[/tex] мы можем получить сразу два числа: [tex]x = \frac {2n-1}{3}[/tex] и число [tex]y=4x+1.[/tex]
Второй случай.
Как мы уже выяснили, если существует такое нечетное число [tex]n \equiv 1 \pmod 3[/tex], то из этого следует, что также существует и нечетное число [tex]x = \frac {4n-1}{3}[/tex].
Но если мы умножим [tex]n[/tex] на 16, то обязательно будет существовать число: [tex]y = \frac {16n-1}{3}[/tex]. Потому что любое число [tex]n \equiv 1 \pmod 3[/tex] можно представить как [tex]3k-2[/tex], тогда уравнение [tex]y = \frac {16n-1}{3}[/tex] сводится к решению:
[tex]y = \frac{16(3k-2)-1}{3} = \frac{48k-33}{3}=16k-11[/tex], что, конечно, имеет целочисленное решение.
Есть ли связь между полученными таким образом числами: [tex]x[/tex] и [tex]y[/tex]?
[tex]\frac {4n-1}{3} = x, \; \; n = \frac {3x+1}{4}[/tex]
[tex]\frac {16n-1}{3} = y, \; \; n = \frac {3y+1}{16}[/tex]
[tex]\frac {3x+1}{4} = \frac {3y+1}{16}[/tex]
[tex]y=4x+1[/tex]
Да, связь есть.
Другими словами, из нечетного числа [tex]n \equiv 1 \pmod 3[/tex] мы можем получить сразу два числа: [tex]x = \frac {4n-1}{3}[/tex] и число [tex]y=4x+1.[/tex]
Таким образом мы установили шаг рекурсии между всеми нечетными числами:
[tex]\frac{2n-1}{3}[/tex] для случая [tex]n \equiv 2 \pmod 3[/tex],
[tex]\frac{4n-1}{3}[/tex] для случая [tex]n \equiv 1 \pmod 3[/tex],
[tex]n=n[/tex] для случая [tex]n \equiv 0 \pmod 3[/tex],
и постоянное применение к уже полученным числам [tex]4x+1[/tex].
§9. Новый алгоритм
Мы выкинули все чётные числа из рекурсии, и упростили алгоритм до применения всего лишь трех правил [tex]\frac{2n-1}{3}[/tex], [tex]\frac{4n-1}{3}[/tex] и [tex]4x+1[/tex]. Распишем всё это более подробно.
Итерация №1.
Число 1. [tex]n \equiv 1 \pmod 3[/tex], применяем [tex]\frac{4n-1}{3}, \quad \frac {4-1}{3} = 1.[/tex]
Число 1. [tex]4n+1=5.[/tex]
Итерация №2.
Число 5. [tex]n \equiv 2 \pmod 3[/tex], применяем [tex]\frac{2n-1}{3}, \quad \frac {10-1}{3} = 3.[/tex]
Число 5. [tex]4n+1=21.[/tex]
Итерация №3.
Число 3. [tex]n \equiv 0 \pmod 3[/tex], хвост рекурсии.
Число 3. [tex]4n+1=13.[/tex]
Итерация №4.
Число 13. [tex]n \equiv 1 \pmod 3[/tex], применяем [tex]\frac{4n-1}{3}, \quad \frac {52-1}{3} = 17.[/tex]
Число 13. [tex]4n+1=53.[/tex]
Итерация №5.
Число 17. [tex]n \equiv 2 \pmod 3[/tex], применяем [tex]\frac{2n-1}{3}, \quad \frac {34-1}{3} = 11.[/tex]
Число 17. [tex]4n+1=69.[/tex]
Итерация №6.
Число 11. [tex]n \equiv 2 \pmod 3[/tex], применяем [tex]\frac{2n-1}{3}, \quad \frac {22-1}{3} = 7.[/tex]
Число 11. [tex]4n+1=45.[/tex]
Итерация №7.
Число 7. [tex]n \equiv 1 \pmod 3[/tex], применяем [tex]\frac{4n-1}{3}, \quad \frac {28-1}{3} = 9.[/tex]
Число 7. [tex]4n+1=29.[/tex]
и т.д.
§10. Как получить число 27 ?
С точки зрения рекурсии [tex]\frac {n-1}{3}[/tex] ей без разницы какое число связано с каким.
С точки зрения человеков, они любят придумывать аномалии.
Для того чтобы получить число 27 нам нужно просто запустить рекурсию из единицы и прогуляться по следущей ветке:
1 [tex]\rightarrow[/tex] 5 [tex]\rightarrow[/tex] 3 [tex]\rightarrow[/tex] 13 [tex]\rightarrow[/tex] 53 [tex]\rightarrow[/tex] 35 [tex]\rightarrow[/tex] 23 [tex]\rightarrow[/tex] 15 [tex]\rightarrow[/tex] 61 [tex]\rightarrow[/tex] 81 [tex]\rightarrow[/tex] 325 [tex]\rightarrow[/tex] 433 [tex]\rightarrow[/tex] 577 [tex]\rightarrow[/tex] 769 [tex]\rightarrow[/tex] 3077 [tex]\rightarrow[/tex] 2051 [tex]\rightarrow[/tex] 1367 [tex]\rightarrow[/tex] 911 [tex]\rightarrow[/tex] 607 [tex]\rightarrow[/tex] 2429 [tex]\rightarrow[/tex] 1619 [tex]\rightarrow[/tex] 1079 [tex]\rightarrow[/tex] 719 [tex]\rightarrow[/tex] 479 [tex]\rightarrow[/tex] 319 [tex]\rightarrow[/tex] 425 [tex]\rightarrow[/tex] 283 [tex]\rightarrow[/tex] 377 [tex]\rightarrow[/tex] 251 [tex]\rightarrow[/tex] 167 [tex]\rightarrow[/tex] 111 [tex]\rightarrow[/tex] 445 [tex]\rightarrow[/tex] 593 [tex]\rightarrow[/tex] 395 [tex]\rightarrow[/tex] 263 [tex]\rightarrow[/tex] 175 [tex]\rightarrow[/tex] 233 [tex]\rightarrow[/tex] 155 [tex]\rightarrow[/tex] 103 [tex]\rightarrow[/tex] 137 [tex]\rightarrow[/tex] 91 [tex]\rightarrow[/tex] 121 [tex]\rightarrow[/tex] 161 [tex]\rightarrow[/tex] 107 [tex]\rightarrow[/tex] 71 [tex]\rightarrow[/tex] 47 [tex]\rightarrow[/tex] 31 [tex]\rightarrow[/tex] 41 [tex]\rightarrow[/tex] 27.
§11. Реализация рекурсии на компьютере
Рекурсия является простейшей, с точки зрения реализации. Для генерации новых чисел нужно рекурсивно выполнять следующий кусок кода, начиная с единицы:
- Код: Выделить всё
Процедура ПрименитьПравила(n)
Если (n % 3 = 1) Тогда
ПервоеЧисло = (4*n - 1)/3;
ВтороеЧисло = 4*n + 1;
КонецЕсли;
Если (n % 3 = 2) Тогда
ПервоеЧисло = (2*n - 1)/3;
ВтороеЧисло = 4*n + 1;
КонецЕсли;
Если (n % 3 = 0) Тогда
ПервоеЧисло = 0; // хвост рекурсии
ВтороеЧисло = 4*n + 1;
КонецЕсли;
ДобавитьНовоеЗначениеВТаблицу(ПервоеЧисло);
ДобавитьНовоеЗначениеВТаблицу(ВтороеЧисло);
КонецПроцедуры
Для покрытия интервала от [1 ... 100] требуется 500 итераций.
Для покрытия интервала от [1 ... 1000] требуется 25000 итераций.
Для покрытия интервала от [1 ... 10000] требуется 1 млн. итераций.
---
С уважением,
Автор статьи: Михаил Мартынов, Россия, Оренбург, программист.