Меню
Доказательство гипотезы Коллатца. Поиск различных зависимостей между натуральными числами. Построение матрицы спуска. Проверка полученных результатов на компьютере. Ключевые слова: гипотеза Коллатца, рекурсия, матрица спуска.
§1. Введение
Гипотеза Коллатца - это одна из нерешенных проблем математики. Получила широкую известность благодаря простоте формулировки:
Берём любое натуральное число [tex]n[/tex]; Если оно чётное, разделим его на 2, а если нечетное, то умножаем на 3 и прибавляем 1 (получаем [tex]3n+1[/tex]); Над полученным числом выполняем те же самые действия, и так далее.
Какое бы начальное число [tex]n[/tex] мы ни взяли, рано или поздно мы получим единицу, - так гласит гипотеза. И надо это доказать.
Давайте посмотрим на последовательности в гипотезе Коллатца ([tex]3n+1[/tex]):
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? Да, можно.
Это не просто таблица, это матрица спуска к единице.
Спуск выглядит следующим образом:
Для спуска к единице требуется всего два правила. Это "шаг назад" и правило [tex]4x + 1.[/tex]
§3. Шаг назад
Шаг назад в гипотезе Коллатца выглядит следующим образом, пусть [tex]n[/tex] - нечетное число, тогда:
- Чтобы получить предыдущее мы должны умножить [tex]n[/tex]*2.
- Предположим, перед [tex]2n[/tex] находится нечетное число [tex]x[/tex]. Тогда справедливо равенство: [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) удвоим количество четных чисел:
- Умножаем [tex]n[/tex] на 2, и снова на 2.
- Предположим, перед [tex]4n[/tex] находится нечетное число [tex]x[/tex]. Тогда справедливо равенство: [tex]3x + 1 = 4n.[/tex]
- Получаем [tex]x = \frac {4n-1}{3}[/tex]
- Результат [tex]\frac{4n}{3} - \frac{1}{3}[/tex] всегда будет целый для n ≡ 1 mod(3).
Таким образом мы установили зависимость одного нечетного числа от другого.
Эта зависимость не простая. Она рекурсивная. Каждое нечетное число цепляет другое пока выполняется условие (шаг рекурсии):
[tex]n \equiv 1 \pmod 3 \quad \text{или} \quad n \equiv 2 \pmod 3 \quad \text{или} \quad n = 4x + 1.[/tex]
Итак, в таблице:
[tex]a(1)[/tex] - это шаг назад,
[tex]b(n)[/tex] - это нечетное число,
[tex]x[/tex] - нечетное число для случая [tex]b(n) = 4x+1.[/tex]
[tex]a(m)[/tex] - последовательность чисел, привязанная к [tex]b(n)[/tex].
§4. Правило 1/3 (одна треть)
Рассмотрим полученные формулы с другого ракурса: [tex]\frac{2n}{3} - \frac{1}{3} \quad \text{и} \quad \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".
§5. Особая связь ([tex]4x + 1[/tex])
Давайте посмотрим на последовательности для 7 и 29:
Чтобы подняться из числа 11 на шаг наверх, нам нужно решить равенство [tex]3x+1=2n, \text{ где } n = 11[/tex].
А что если мы хотим еще выше? Давайте решим его для [tex]8n[/tex]:
[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]
Да, всё сходится: [tex]n = 11, \; x = 7, \; y = 29 \; (4x+1).[/tex]
Но давайте возьмем другой пример:
Чтобы подняться из числа 7 на два шага наверх, нам нужно решить равенство [tex]3x+1=4n, \text{ где } n = 7[/tex].
А что если мы хотим еще выше? Давайте решим его для [tex]16n[/tex]:
[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]
Да, всё верно: [tex]n = 7, \; x = 9, \; y = 37 \; (4x+1).[/tex]
Заметьте, мы специально взяли два примера (7 и 11), которые дают нам разный остаток от деления на три, но получили одну и ту же зависимость.
Сформулируем её так: Если число [tex]n[/tex] связано с другим числом [tex]x[/tex] по правилу 1/3, то число [tex]n[/tex] также будет связано с его производным [tex]y[/tex] по правилу [tex]y=4x+1[/tex].
Другими словами, нечетные числа [tex]x[/tex] и [tex]y[/tex] спускаются к единице по той же последовательности, что и число [tex]n[/tex].
Важно понимать, что применяя правило [tex]4n+1[/tex] мы заменяем одно нечетное число на другое, но спуск к единице не меняется.
§6. Матрица спуска
Мы проверили нашу матрицу спуска для чисел от 1 до 1000000000 на компьютере.
Все числа гарантированно спускаются к единице по заданным в матрице правилам (1/3 и [tex]4n+1[/tex]). Каких-либо других правил, связывающих нечетные числа, мы не обнаружили.
Это означает, что мы можем убрать все чётные числа в последовательностях Коллатца, и оперировать только лишь правилами 1/3 и [tex]4n+1[/tex].
§7. Лучший пример - число 27
Давайте сформируем настоящую (истинную) последовательность для 27, используя только лишь правила 1/3 и [tex]4n+1[/tex]:
27 [tex]\rightarrow[/tex] 41 [tex]\rightarrow[/tex] 31 [tex]\rightarrow[/tex] 47 [tex]\rightarrow[/tex] 71 [tex]\rightarrow[/tex] 107 [tex]\rightarrow[/tex] 161 [tex]\rightarrow[/tex] 121 [tex]\rightarrow[/tex] 91 [tex]\rightarrow[/tex] 137 [tex]\rightarrow[/tex] 103 [tex]\rightarrow[/tex] 155 [tex]\rightarrow[/tex] 233 [tex]\rightarrow[/tex] 175 [tex]\rightarrow[/tex] 263 [tex]\rightarrow[/tex] 395 [tex]\rightarrow[/tex] 593 [tex]\rightarrow[/tex] 445 [tex]\rightarrow[/tex] 111 [tex]\rightarrow[/tex] 167 [tex]\rightarrow[/tex] 251 [tex]\rightarrow[/tex] 377 [tex]\rightarrow[/tex] 283 [tex]\rightarrow[/tex] 425 [tex]\rightarrow[/tex] 319 [tex]\rightarrow[/tex] 479 [tex]\rightarrow[/tex] 719 [tex]\rightarrow[/tex] 1079 [tex]\rightarrow[/tex] 1619 [tex]\rightarrow[/tex] 2429 [tex]\rightarrow[/tex] 607 [tex]\rightarrow[/tex] 911 [tex]\rightarrow[/tex] 1367 [tex]\rightarrow[/tex] 2051 [tex]\rightarrow[/tex] 3077 [tex]\rightarrow[/tex] 769 [tex]\rightarrow[/tex] 577 [tex]\rightarrow[/tex] 433 [tex]\rightarrow[/tex] 325 [tex]\rightarrow[/tex] 81 [tex]\rightarrow[/tex] 61 [tex]\rightarrow[/tex] 15 [tex]\rightarrow[/tex] 23 [tex]\rightarrow[/tex] 35 [tex]\rightarrow[/tex] 53 [tex]\rightarrow[/tex] 13 [tex]\rightarrow[/tex] 3 [tex]\rightarrow[/tex] 5 [tex]\rightarrow[/tex] 1.
Для чисел 3077, 2429, 445, 325, 61, 53, 13, 5 - мы воспользовались правилом [tex]4n+1[/tex], в остальных случаях 1/3. Мы получили точно такую же последовательность спуска к единице, но все чётные исчезли.
§8. Доказательство гипотезы Коллатца
Гипотеза выполняет действия [tex]3n+1[/tex] и [tex]n/2[/tex], тогда обратные действия: [tex]\frac {n-1}{3}[/tex] и [tex]n[/tex]*2.
Сформулируем это так: Возьмем любое натуральное число [tex]n[/tex]; Отнимем из него единицу [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, ...
На этом остановимся.
Далее мы рассмотрим множество следующего вида:
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, и продолжим каждую последовательность:
Таким образом, мы приходим к выводу, что выбирая любое натуральное число [tex]n[/tex] в гипотезе Коллатца, мы на самом деле выбираем элемент из этого множества. Потому что каждое нечетное число в этом множестве - это шаг рекурсии:
[tex]n \equiv 1 \pmod 3 \quad \text{или} \quad n \equiv 2 \pmod 3 \quad \text{или} \quad n = 4x + 1.[/tex]
А каждое чётное число образовано от нечетного простым умножением на 2.
Таким образом, гипотеза Коллатца - это развернутая в обратном направлении рекурсия.
Для доказательства гипотезы Коллатца нам потребуется:
- Построить множество всех вариантов последовательностей Коллатца, что мы и сделали.
- Показать, как все последовательности Коллатца начинаются с единицы, что мы и сделали.
- Ответить на вопрос, есть ли числа, которые попадают в [tex]3n+1[/tex], но не попадают в [tex]\frac {n-1}{3}[/tex]?
Таких чисел нет, потому что рекурсивное правило [tex]\frac {n-1}{3}[/tex] это зеркальная копия [tex]3n+1[/tex].
[tex]k=3n+1, \; \; n = \frac {k-1}{3}[/tex].
Это одна и та же рекурсия, просто развернутая в разные стороны. Выполняя одни и те же действия, нельзя сойти с одного и того же пути. Если рекурсия начинается с единицы, то она всегда в неё возвращается (см. книгу С.Клини, Введение в метаматематику, [гл. IX, §46]).
Все последовательности зеркальны, идентичны и обладают одинаковыми свойствами. И мы можем это легко проверить.
§9. Шаг вперед
Пусть [tex]n[/tex] - нечетное число, тогда чтобы двигаться вперед по правилу [tex]\frac {n-1}{3}[/tex] мы должны:
- Отнять от [tex]n[/tex] единицу [tex](n-1)[/tex] и разделить на три. Но если мы отнимем от нечетного числа единицу, то мы получим чётное. Четное не делится на три.
- Тогда у нас остается только один вариант, умножить [tex]n[/tex]*2.
- Предположим, после [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] будет целым только в том случае, если n ≡ 2 mod(3).
Тогда для n ≡ 1 mod(3) удвоим количество четных чисел:
- Умножаем [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] всегда будет целый для n ≡ 1 mod(3).
Тоже самое и с правилом [tex]4n+1[/tex]:
Число 11 порождает две ветки. Зайдем в первую ветку [tex]2n[/tex]:
[tex]\frac {2n-1}{3} = x, \; \; n = \frac {3x+1}{2}[/tex]
Зайдем во вторую ветку [tex]8n[/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 = 11, \; x = 7, \; y = 29 \; (4x+1).[/tex]
Теперь мы понимаем, почему в гипотезе Коллатца можно заменить нечетное число вида [tex]4n+1[/tex] на его производное и спуск до единицы не изменится. Потому что это раздвоенная ветка одного и того же числа.
Обратим внимание и на цикл «1, 2, 4, 1». Он рождается в обеих схемах, что служит прекрасным доказательством тождественности правил.
Отвечая на вопрос, является ли правило [tex]3n+1[/tex] развернутой в обратном направлении рекурсией [tex]\frac {n-1}{3}[/tex] ? Мы говорим, однозначно, да.
§10. Последний вопрос
И последний вопрос, который мы обязаны задать: Есть ли такое число, которое не входит в рекурсию [tex]\frac {n-1}{3}[/tex] ?
Предположим, что есть. Но тогда из этого следует, что его нельзя подставить в [tex]3n+1[/tex]. Потому что [tex]3n+1[/tex] - это уже сформированная рекурсия от [tex]\frac {n-1}{3}[/tex].
Таким образом, мы приходим к выводу, что все числа рекурсивно связаны между собой, а правило [tex]\frac {n-1}{3}[/tex] перебирает бесконечное количество веток с бесконечным количеством вариантов по mod(3) и умножением на 2. И каждая такая ветка обречена спуститься к единице. Ч.т.д.
---
С уважением,
Автор статьи: Михаил Мартынов, Россия, Оренбург, программист.
