i |
Ende Название темы изменено по просьбе топикстартера. |
АннотацияДоказательство гипотезы Коллатца. Поиск различных зависимостей между натуральными числами. Построение матрицы спуска. Проверка полученных результатов на компьютере. Ключевые слова: гипотеза Коллатца, рекурсия, матрица спуска.
§1. ВведениеГипотеза Коллатца - это одна из нерешенных проблем математики. Получила широкую известность благодаря простоте формулировки:
Берём любое натуральное число
![$n$ $n$](https://dxdy-02.korotkov.co.uk/f/5/5/a/55a049b8f161ae7cfeb0197d75aff96782.png)
; Если оно чётное, разделим его на 2, а если нечетное, то умножаем на 3 и прибавляем 1 (получаем
![$3n+1$ $3n+1$](https://dxdy-02.korotkov.co.uk/f/9/3/f/93f5f9a7e819a127ffcbbaa1c137009382.png)
); Над полученным числом выполняем те же самые действия, и так далее.
Какое бы начальное число
![$n$ $n$](https://dxdy-02.korotkov.co.uk/f/5/5/a/55a049b8f161ae7cfeb0197d75aff96782.png)
мы ни взяли, рано или поздно мы получим единицу, - так гласит гипотеза. И надо это доказать.
Давайте посмотрим на последовательности в гипотезе Коллатца (
![$3n+1$ $3n+1$](https://dxdy-02.korotkov.co.uk/f/9/3/f/93f5f9a7e819a127ffcbbaa1c137009382.png)
):
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. Таблица нечетных чисел![Изображение](https://i.imgur.com/Rhr5mVPl.png)
Вопрос. Можно ли по этой таблице спуститься к 1? Да, можно.
Это не просто таблица, это матрица спуска к единице.
Спуск выглядит следующим образом:
![Изображение](https://i.imgur.com/c0Tj3IX.png)
Для спуска к единице требуется всего два правила. Это "шаг назад" и правило
§3. Шаг назадШаг назад в гипотезе Коллатца выглядит следующим образом, пусть
![$n$ $n$](https://dxdy-02.korotkov.co.uk/f/5/5/a/55a049b8f161ae7cfeb0197d75aff96782.png)
- нечетное число, тогда:
- Чтобы получить предыдущее мы должны умножить
![$n$ $n$](https://dxdy-02.korotkov.co.uk/f/5/5/a/55a049b8f161ae7cfeb0197d75aff96782.png)
*2.
- Предположим, перед
![$2n$ $2n$](https://dxdy-01.korotkov.co.uk/f/4/7/c/47c124971e1327d1d3882a141f95face82.png)
находится нечетное число
![$x$ $x$](https://dxdy-04.korotkov.co.uk/f/3/3/2/332cc365a4987aacce0ead01b8bdcc0b82.png)
. Тогда справедливо равенство:
![$3x + 1 = 2n.$ $3x + 1 = 2n.$](https://dxdy-01.korotkov.co.uk/f/c/e/a/ceadd91e6c62a48dc7d77a07f96bb9a182.png)
- Получаем
![$x = \frac {2n-1}{3}$ $x = \frac {2n-1}{3}$](https://dxdy-01.korotkov.co.uk/f/4/4/4/4449a40677240fe4932fa75edafc0a8182.png)
- Результат
![$\frac{2n}{3} - \frac{1}{3}$ $\frac{2n}{3} - \frac{1}{3}$](https://dxdy-03.korotkov.co.uk/f/6/7/d/67d4a97f1528c400ded7da8e5e4ade5182.png)
будет целым только в том случае, если
![$n \equiv 2 \pmod 3$ $n \equiv 2 \pmod 3$](https://dxdy-01.korotkov.co.uk/f/0/f/0/0f065e6931084118f36907503b71e18d82.png)
.
Тогда для
![$n \equiv 1 \pmod 3$ $n \equiv 1 \pmod 3$](https://dxdy-04.korotkov.co.uk/f/b/f/7/bf7414f7c97388c618a0c531bc9a710482.png)
удвоим количество четных чисел:
- Умножаем
![$n$ $n$](https://dxdy-02.korotkov.co.uk/f/5/5/a/55a049b8f161ae7cfeb0197d75aff96782.png)
на 2, и снова на 2.
- Предположим, перед
![$4n$ $4n$](https://dxdy-04.korotkov.co.uk/f/3/2/b/32b9ce449a8a3151ecebc40e1e56224182.png)
находится нечетное число
![$x$ $x$](https://dxdy-04.korotkov.co.uk/f/3/3/2/332cc365a4987aacce0ead01b8bdcc0b82.png)
. Тогда справедливо равенство:
![$3x + 1 = 4n.$ $3x + 1 = 4n.$](https://dxdy-01.korotkov.co.uk/f/0/6/4/0644a494411f0d88a781ffb1bb2bdbd982.png)
- Получаем
![$x = \frac {4n-1}{3}$ $x = \frac {4n-1}{3}$](https://dxdy-02.korotkov.co.uk/f/5/5/b/55b2ea6f64abdf207030b19b6538663482.png)
- Результат
![$\frac{4n}{3} - \frac{1}{3}$ $\frac{4n}{3} - \frac{1}{3}$](https://dxdy-02.korotkov.co.uk/f/1/3/2/132e1887f80af6f9ee0fb1e29a814c8582.png)
всегда будет целый для
![$n \equiv 1 \pmod 3$ $n \equiv 1 \pmod 3$](https://dxdy-04.korotkov.co.uk/f/b/f/7/bf7414f7c97388c618a0c531bc9a710482.png)
.
Таким образом мы установили зависимость одного нечетного числа от другого.
Эта зависимость не простая. Она рекурсивная. Каждое нечетное число цепляет другое пока выполняется условие (шаг рекурсии):
![$$n \equiv 1 \pmod 3 \quad \text{или} \quad n \equiv 2 \pmod 3 \quad \text{или} \quad n = 4x + 1.$$ $$n \equiv 1 \pmod 3 \quad \text{или} \quad n \equiv 2 \pmod 3 \quad \text{или} \quad n = 4x + 1.$$](https://dxdy-03.korotkov.co.uk/f/a/5/e/a5e6aa7bc4cc087f55b35fee38efb61982.png)
Итак, в таблице:
![$a(1)$ $a(1)$](https://dxdy-03.korotkov.co.uk/f/6/a/e/6ae58d0a2803e6533d8769754a79118d82.png)
- это шаг назад,
![$b(n)$ $b(n)$](https://dxdy-02.korotkov.co.uk/f/1/4/6/14619328ba0e9a59db400bd29792af8082.png)
- это нечетное число,
![$x$ $x$](https://dxdy-04.korotkov.co.uk/f/3/3/2/332cc365a4987aacce0ead01b8bdcc0b82.png)
- нечетное число для случая
![$b(n) = 4x+1.$ $b(n) = 4x+1.$](https://dxdy-01.korotkov.co.uk/f/4/7/b/47baf76db9b8e08244e48b2e5922ed6a82.png)
![$a(m)$ $a(m)$](https://dxdy-04.korotkov.co.uk/f/7/0/b/70b99dd43bd96f3fe6cdfd3f3eaf345d82.png)
- последовательность чисел, привязанная к
![$b(n)$ $b(n)$](https://dxdy-02.korotkov.co.uk/f/1/4/6/14619328ba0e9a59db400bd29792af8082.png)
.
§4. Правило 1/3 (одна треть)Рассмотрим полученные формулы с другого ракурса:
![$\frac{2n}{3} - \frac{1}{3} \quad \text{и} \quad \frac{4n}{3} - \frac{1}{3}.$ $\frac{2n}{3} - \frac{1}{3} \quad \text{и} \quad \frac{4n}{3} - \frac{1}{3}.$](https://dxdy-03.korotkov.co.uk/f/2/f/c/2fcd39d3c77a05651afce9979874737d82.png)
Не будем обращать внимание на
![$\frac{1}{3}$ $\frac{1}{3}$](https://dxdy-01.korotkov.co.uk/f/4/8/6/4866e384d04d2b473e19a2850b073f5082.png)
, как пренебрежительно малое число, и сосредоточимся только на
![$\frac{2n}{3}$ $\frac{2n}{3}$](https://dxdy-03.korotkov.co.uk/f/2/f/1/2f183c735c91abe56973d9d31290d04282.png)
и
![$\frac{4n}{3}$ $\frac{4n}{3}$](https://dxdy-01.korotkov.co.uk/f/4/a/a/4aa33c1c6cacf8f6e72b5769248f46f382.png)
. Это ни что иное, как уменьшение/увеличение числа n на
![$\frac{1}{3}$ $\frac{1}{3}$](https://dxdy-01.korotkov.co.uk/f/4/8/6/4866e384d04d2b473e19a2850b073f5082.png)
. Такое уменьшение/увеличение будем называть "правилом 1/3".
§5. Особая связь (
)Давайте посмотрим на последовательности для 7 и 29:
![Изображение](https://i.imgur.com/ic6EYJX.png)
Чтобы подняться из числа 11 на шаг наверх, нам нужно решить равенство
![$3x+1=2n, \text{ где } n = 11$ $3x+1=2n, \text{ где } n = 11$](https://dxdy-04.korotkov.co.uk/f/f/f/6/ff66c28650efae6511635921014e477382.png)
.
А что если мы хотим еще выше? Давайте решим его для
![$8n$ $8n$](https://dxdy-02.korotkov.co.uk/f/d/6/1/d612c2a8a5d700585a5ecb6d421709a782.png)
:
![$3x+1=2n, \; \; n= \frac {3x+1}{2}$ $3x+1=2n, \; \; n= \frac {3x+1}{2}$](https://dxdy-03.korotkov.co.uk/f/2/1/5/2153829989abc26b997a4862f269db0882.png)
![$3y+1=8n, \; \; n= \frac {3y+1}{8}$ $3y+1=8n, \; \; n= \frac {3y+1}{8}$](https://dxdy-04.korotkov.co.uk/f/b/a/3/ba341a37dbea60293382b8ea1e9429cc82.png)
![$\frac {3x+1}{2} = \frac {3y+1}{8}$ $\frac {3x+1}{2} = \frac {3y+1}{8}$](https://dxdy-04.korotkov.co.uk/f/f/b/b/fbba8373eb3c7312c1c120932f6267f782.png)
![$y=4x+1$ $y=4x+1$](https://dxdy-02.korotkov.co.uk/f/d/b/1/db1a0e2e2fef1b8417636da28d05345a82.png)
Да, всё сходится:
![$n = 11, \; x = 7, \; y = 29 \; (4x+1).$ $n = 11, \; x = 7, \; y = 29 \; (4x+1).$](https://dxdy-02.korotkov.co.uk/f/1/5/6/15631707f5cf31ce8fc95826ac31f7ff82.png)
Но давайте возьмем другой пример:
![Изображение](https://i.imgur.com/EmCjviL.png)
Чтобы подняться из числа 7 на два шага наверх, нам нужно решить равенство
![$3x+1=4n, \text{ где } n = 7$ $3x+1=4n, \text{ где } n = 7$](https://dxdy-02.korotkov.co.uk/f/1/f/a/1fa77dae84b8672503f1edb167f8b70182.png)
.
А что если мы хотим еще выше? Давайте решим его для
![$16n$ $16n$](https://dxdy-04.korotkov.co.uk/f/7/8/4/784c17efedfe2ce13ee19cfd84d30b9182.png)
:
![$3x+1=4n, \; \; n= \frac{3x+1}{4}$ $3x+1=4n, \; \; n= \frac{3x+1}{4}$](https://dxdy-01.korotkov.co.uk/f/0/c/3/0c386e9ea547d5eb9e288e9d6b210f4582.png)
![$3y+1=16n, \; n= \frac{3y+1}{16}$ $3y+1=16n, \; n= \frac{3y+1}{16}$](https://dxdy-04.korotkov.co.uk/f/f/0/8/f0848df62bc4cd595e6e55fea2f9f34d82.png)
![$\frac{3x+1}{4} = \frac{3y+1}{16}$ $\frac{3x+1}{4} = \frac{3y+1}{16}$](https://dxdy-03.korotkov.co.uk/f/6/2/f/62f6685d9b08e131b1e118c0d4c58e9982.png)
![$y=4x+1$ $y=4x+1$](https://dxdy-02.korotkov.co.uk/f/d/b/1/db1a0e2e2fef1b8417636da28d05345a82.png)
Да, всё верно:
![$n = 7, \; x = 9, \; y = 37 \; (4x+1).$ $n = 7, \; x = 9, \; y = 37 \; (4x+1).$](https://dxdy-03.korotkov.co.uk/f/2/a/c/2ac1e8c92651800eb4c5b48d1536d3fc82.png)
Заметьте, мы специально взяли два примера (7 и 11), которые дают нам разный остаток от деления на три, но получили одну и ту же зависимость.
Сформулируем её так: Если число
![$n$ $n$](https://dxdy-02.korotkov.co.uk/f/5/5/a/55a049b8f161ae7cfeb0197d75aff96782.png)
связано с другим числом
![$x$ $x$](https://dxdy-04.korotkov.co.uk/f/3/3/2/332cc365a4987aacce0ead01b8bdcc0b82.png)
по правилу 1/3, то число
![$n$ $n$](https://dxdy-02.korotkov.co.uk/f/5/5/a/55a049b8f161ae7cfeb0197d75aff96782.png)
также будет связано с его производным
![$y$ $y$](https://dxdy-02.korotkov.co.uk/f/d/e/c/deceeaf6940a8c7a5a02373728002b0f82.png)
по правилу
![$y=4x+1$ $y=4x+1$](https://dxdy-02.korotkov.co.uk/f/d/b/1/db1a0e2e2fef1b8417636da28d05345a82.png)
.
Другими словами, нечетные числа
![$x$ $x$](https://dxdy-04.korotkov.co.uk/f/3/3/2/332cc365a4987aacce0ead01b8bdcc0b82.png)
и
![$y$ $y$](https://dxdy-02.korotkov.co.uk/f/d/e/c/deceeaf6940a8c7a5a02373728002b0f82.png)
спускаются к единице по той же последовательности, что и число
![$n$ $n$](https://dxdy-02.korotkov.co.uk/f/5/5/a/55a049b8f161ae7cfeb0197d75aff96782.png)
.
Важно понимать, что применяя правило
![$4n+1$ $4n+1$](https://dxdy-01.korotkov.co.uk/f/8/3/9/83908d7bc1098c423296b00fabc8821482.png)
мы заменяем одно нечетное число на другое, но спуск к единице не меняется.
§6. Матрица спускаМы проверили нашу матрицу спуска для чисел от 1 до 1000000000 на компьютере.
Все числа гарантированно спускаются к единице по заданным в матрице правилам (1/3 и
![$4n+1$ $4n+1$](https://dxdy-01.korotkov.co.uk/f/8/3/9/83908d7bc1098c423296b00fabc8821482.png)
). Каких-либо других правил, связывающих нечетные числа, мы не обнаружили.
Это означает, что мы можем убрать все чётные числа в последовательностях Коллатца, и оперировать только лишь правилами 1/3 и
![$4n+1$ $4n+1$](https://dxdy-01.korotkov.co.uk/f/8/3/9/83908d7bc1098c423296b00fabc8821482.png)
.
§7. Лучший пример - число 27Давайте сформируем настоящую (истинную) последовательность для 27, используя только лишь правила 1/3 и
![$4n+1$ $4n+1$](https://dxdy-01.korotkov.co.uk/f/8/3/9/83908d7bc1098c423296b00fabc8821482.png)
:
27
![$\rightarrow$ $\rightarrow$](https://dxdy-03.korotkov.co.uk/f/e/5/d/e5d134f35dc4949fab12ec64d186248a82.png)
41
![$\rightarrow$ $\rightarrow$](https://dxdy-03.korotkov.co.uk/f/e/5/d/e5d134f35dc4949fab12ec64d186248a82.png)
31
![$\rightarrow$ $\rightarrow$](https://dxdy-03.korotkov.co.uk/f/e/5/d/e5d134f35dc4949fab12ec64d186248a82.png)
47
![$\rightarrow$ $\rightarrow$](https://dxdy-03.korotkov.co.uk/f/e/5/d/e5d134f35dc4949fab12ec64d186248a82.png)
71
![$\rightarrow$ $\rightarrow$](https://dxdy-03.korotkov.co.uk/f/e/5/d/e5d134f35dc4949fab12ec64d186248a82.png)
107
![$\rightarrow$ $\rightarrow$](https://dxdy-03.korotkov.co.uk/f/e/5/d/e5d134f35dc4949fab12ec64d186248a82.png)
161
![$\rightarrow$ $\rightarrow$](https://dxdy-03.korotkov.co.uk/f/e/5/d/e5d134f35dc4949fab12ec64d186248a82.png)
121
![$\rightarrow$ $\rightarrow$](https://dxdy-03.korotkov.co.uk/f/e/5/d/e5d134f35dc4949fab12ec64d186248a82.png)
91
![$\rightarrow$ $\rightarrow$](https://dxdy-03.korotkov.co.uk/f/e/5/d/e5d134f35dc4949fab12ec64d186248a82.png)
137
![$\rightarrow$ $\rightarrow$](https://dxdy-03.korotkov.co.uk/f/e/5/d/e5d134f35dc4949fab12ec64d186248a82.png)
103
![$\rightarrow$ $\rightarrow$](https://dxdy-03.korotkov.co.uk/f/e/5/d/e5d134f35dc4949fab12ec64d186248a82.png)
155
![$\rightarrow$ $\rightarrow$](https://dxdy-03.korotkov.co.uk/f/e/5/d/e5d134f35dc4949fab12ec64d186248a82.png)
233
![$\rightarrow$ $\rightarrow$](https://dxdy-03.korotkov.co.uk/f/e/5/d/e5d134f35dc4949fab12ec64d186248a82.png)
175
![$\rightarrow$ $\rightarrow$](https://dxdy-03.korotkov.co.uk/f/e/5/d/e5d134f35dc4949fab12ec64d186248a82.png)
263
![$\rightarrow$ $\rightarrow$](https://dxdy-03.korotkov.co.uk/f/e/5/d/e5d134f35dc4949fab12ec64d186248a82.png)
395
![$\rightarrow$ $\rightarrow$](https://dxdy-03.korotkov.co.uk/f/e/5/d/e5d134f35dc4949fab12ec64d186248a82.png)
593
![$\rightarrow$ $\rightarrow$](https://dxdy-03.korotkov.co.uk/f/e/5/d/e5d134f35dc4949fab12ec64d186248a82.png)
445
![$\rightarrow$ $\rightarrow$](https://dxdy-03.korotkov.co.uk/f/e/5/d/e5d134f35dc4949fab12ec64d186248a82.png)
111
![$\rightarrow$ $\rightarrow$](https://dxdy-03.korotkov.co.uk/f/e/5/d/e5d134f35dc4949fab12ec64d186248a82.png)
167
![$\rightarrow$ $\rightarrow$](https://dxdy-03.korotkov.co.uk/f/e/5/d/e5d134f35dc4949fab12ec64d186248a82.png)
251
![$\rightarrow$ $\rightarrow$](https://dxdy-03.korotkov.co.uk/f/e/5/d/e5d134f35dc4949fab12ec64d186248a82.png)
377
![$\rightarrow$ $\rightarrow$](https://dxdy-03.korotkov.co.uk/f/e/5/d/e5d134f35dc4949fab12ec64d186248a82.png)
283
![$\rightarrow$ $\rightarrow$](https://dxdy-03.korotkov.co.uk/f/e/5/d/e5d134f35dc4949fab12ec64d186248a82.png)
425
![$\rightarrow$ $\rightarrow$](https://dxdy-03.korotkov.co.uk/f/e/5/d/e5d134f35dc4949fab12ec64d186248a82.png)
319
![$\rightarrow$ $\rightarrow$](https://dxdy-03.korotkov.co.uk/f/e/5/d/e5d134f35dc4949fab12ec64d186248a82.png)
479
![$\rightarrow$ $\rightarrow$](https://dxdy-03.korotkov.co.uk/f/e/5/d/e5d134f35dc4949fab12ec64d186248a82.png)
719
![$\rightarrow$ $\rightarrow$](https://dxdy-03.korotkov.co.uk/f/e/5/d/e5d134f35dc4949fab12ec64d186248a82.png)
1079
![$\rightarrow$ $\rightarrow$](https://dxdy-03.korotkov.co.uk/f/e/5/d/e5d134f35dc4949fab12ec64d186248a82.png)
1619
![$\rightarrow$ $\rightarrow$](https://dxdy-03.korotkov.co.uk/f/e/5/d/e5d134f35dc4949fab12ec64d186248a82.png)
2429
![$\rightarrow$ $\rightarrow$](https://dxdy-03.korotkov.co.uk/f/e/5/d/e5d134f35dc4949fab12ec64d186248a82.png)
607
![$\rightarrow$ $\rightarrow$](https://dxdy-03.korotkov.co.uk/f/e/5/d/e5d134f35dc4949fab12ec64d186248a82.png)
911
![$\rightarrow$ $\rightarrow$](https://dxdy-03.korotkov.co.uk/f/e/5/d/e5d134f35dc4949fab12ec64d186248a82.png)
1367
![$\rightarrow$ $\rightarrow$](https://dxdy-03.korotkov.co.uk/f/e/5/d/e5d134f35dc4949fab12ec64d186248a82.png)
2051
![$\rightarrow$ $\rightarrow$](https://dxdy-03.korotkov.co.uk/f/e/5/d/e5d134f35dc4949fab12ec64d186248a82.png)
3077
![$\rightarrow$ $\rightarrow$](https://dxdy-03.korotkov.co.uk/f/e/5/d/e5d134f35dc4949fab12ec64d186248a82.png)
769
![$\rightarrow$ $\rightarrow$](https://dxdy-03.korotkov.co.uk/f/e/5/d/e5d134f35dc4949fab12ec64d186248a82.png)
577
![$\rightarrow$ $\rightarrow$](https://dxdy-03.korotkov.co.uk/f/e/5/d/e5d134f35dc4949fab12ec64d186248a82.png)
433
![$\rightarrow$ $\rightarrow$](https://dxdy-03.korotkov.co.uk/f/e/5/d/e5d134f35dc4949fab12ec64d186248a82.png)
325
![$\rightarrow$ $\rightarrow$](https://dxdy-03.korotkov.co.uk/f/e/5/d/e5d134f35dc4949fab12ec64d186248a82.png)
81
![$\rightarrow$ $\rightarrow$](https://dxdy-03.korotkov.co.uk/f/e/5/d/e5d134f35dc4949fab12ec64d186248a82.png)
61
![$\rightarrow$ $\rightarrow$](https://dxdy-03.korotkov.co.uk/f/e/5/d/e5d134f35dc4949fab12ec64d186248a82.png)
15
![$\rightarrow$ $\rightarrow$](https://dxdy-03.korotkov.co.uk/f/e/5/d/e5d134f35dc4949fab12ec64d186248a82.png)
23
![$\rightarrow$ $\rightarrow$](https://dxdy-03.korotkov.co.uk/f/e/5/d/e5d134f35dc4949fab12ec64d186248a82.png)
35
![$\rightarrow$ $\rightarrow$](https://dxdy-03.korotkov.co.uk/f/e/5/d/e5d134f35dc4949fab12ec64d186248a82.png)
53
![$\rightarrow$ $\rightarrow$](https://dxdy-03.korotkov.co.uk/f/e/5/d/e5d134f35dc4949fab12ec64d186248a82.png)
13
![$\rightarrow$ $\rightarrow$](https://dxdy-03.korotkov.co.uk/f/e/5/d/e5d134f35dc4949fab12ec64d186248a82.png)
3
![$\rightarrow$ $\rightarrow$](https://dxdy-03.korotkov.co.uk/f/e/5/d/e5d134f35dc4949fab12ec64d186248a82.png)
5
![$\rightarrow$ $\rightarrow$](https://dxdy-03.korotkov.co.uk/f/e/5/d/e5d134f35dc4949fab12ec64d186248a82.png)
1.
Для чисел 3077, 2429, 445, 325, 61, 53, 13, 5 - мы воспользовались правилом
![$4n+1$ $4n+1$](https://dxdy-01.korotkov.co.uk/f/8/3/9/83908d7bc1098c423296b00fabc8821482.png)
, в остальных случаях 1/3. Мы получили точно такую же последовательность спуска к единице, но все чётные исчезли.
§8. Доказательство гипотезы КоллатцаГипотеза выполняет действия
![$3n+1$ $3n+1$](https://dxdy-02.korotkov.co.uk/f/9/3/f/93f5f9a7e819a127ffcbbaa1c137009382.png)
и
![$n/2$ $n/2$](https://dxdy-02.korotkov.co.uk/f/d/6/d/d6d54860f3796e33548482099695dec582.png)
, тогда обратные действия:
![$\frac {n-1}{3}$ $\frac {n-1}{3}$](https://dxdy-01.korotkov.co.uk/f/4/b/b/4bb1f9867b5829bdb4563db22494283782.png)
и
![$n$ $n$](https://dxdy-02.korotkov.co.uk/f/5/5/a/55a049b8f161ae7cfeb0197d75aff96782.png)
*2.
Сформулируем это так: Возьмем любое натуральное число
![$n$ $n$](https://dxdy-02.korotkov.co.uk/f/5/5/a/55a049b8f161ae7cfeb0197d75aff96782.png)
; Отнимем из него единицу
![$(n-1)$ $(n-1)$](https://dxdy-01.korotkov.co.uk/f/0/d/1/0d1f34c830dc60d4f09b8b49b25af89f82.png)
; Если результат деления
![$\frac {n-1}{3}$ $\frac {n-1}{3}$](https://dxdy-01.korotkov.co.uk/f/4/b/b/4bb1f9867b5829bdb4563db22494283782.png)
будет целый, тогда это будет следующее число; Если нет, то умножаем
![$n$ $n$](https://dxdy-02.korotkov.co.uk/f/5/5/a/55a049b8f161ae7cfeb0197d75aff96782.png)
на 2; И вообще, всегда умножаем
![$n$ $n$](https://dxdy-02.korotkov.co.uk/f/5/5/a/55a049b8f161ae7cfeb0197d75aff96782.png)
на 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$ $\frac {4-1}{3} = 1$](https://dxdy-03.korotkov.co.uk/f/2/8/c/28cd4496c4062a05f14b2bbb36f91d3782.png)
.
Число 4. Умножаем на 2. Получаем 8.
Выполним преобразование для 8:
Число 8. Умножаем на 2. Получаем 16.
Выполним преобразование для 16:
Число 16.
![$\frac {16-1}{3} = 5$ $\frac {16-1}{3} = 5$](https://dxdy-04.korotkov.co.uk/f/f/e/5/fe5145c5f00b8e4d44a3b1e9c4e607bd82.png)
.
Число 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, и продолжим каждую последовательность:
![Изображение](https://i.imgur.com/8xZxSMhl.png)
Таким образом, мы приходим к выводу, что выбирая любое натуральное число
![$n$ $n$](https://dxdy-02.korotkov.co.uk/f/5/5/a/55a049b8f161ae7cfeb0197d75aff96782.png)
в гипотезе Коллатца, мы на самом деле выбираем элемент из этого множества. Потому что каждое нечетное число в этом множестве - это шаг рекурсии:
![$$n \equiv 1 \pmod 3 \quad \text{или} \quad n \equiv 2 \pmod 3 \quad \text{или} \quad n = 4x + 1.$$ $$n \equiv 1 \pmod 3 \quad \text{или} \quad n \equiv 2 \pmod 3 \quad \text{или} \quad n = 4x + 1.$$](https://dxdy-03.korotkov.co.uk/f/a/5/e/a5e6aa7bc4cc087f55b35fee38efb61982.png)
А каждое чётное число образовано от нечетного простым умножением на 2.
Таким образом, гипотеза Коллатца - это развернутая в обратном направлении рекурсия.
Для доказательства гипотезы Коллатца нам потребуется:
- Построить множество всех вариантов последовательностей Коллатца, что мы и сделали.
- Показать, как все последовательности Коллатца начинаются с единицы, что мы и сделали.
- Ответить на вопрос, есть ли числа, которые попадают в
![$3n+1$ $3n+1$](https://dxdy-02.korotkov.co.uk/f/9/3/f/93f5f9a7e819a127ffcbbaa1c137009382.png)
, но не попадают в
![$\frac {n-1}{3}$ $\frac {n-1}{3}$](https://dxdy-01.korotkov.co.uk/f/4/b/b/4bb1f9867b5829bdb4563db22494283782.png)
?
Таких чисел нет, потому что рекурсивное правило
![$\frac {n-1}{3}$ $\frac {n-1}{3}$](https://dxdy-01.korotkov.co.uk/f/4/b/b/4bb1f9867b5829bdb4563db22494283782.png)
это зеркальная копия
![$3n+1$ $3n+1$](https://dxdy-02.korotkov.co.uk/f/9/3/f/93f5f9a7e819a127ffcbbaa1c137009382.png)
.
![$k=3n+1, \; \; n = \frac {k-1}{3}$ $k=3n+1, \; \; n = \frac {k-1}{3}$](https://dxdy-01.korotkov.co.uk/f/8/a/b/8abc0b13e575ba1a4b0d77cffc51607282.png)
.
Это одна и та же рекурсия, просто развернутая в разные стороны. Выполняя одни и те же действия, нельзя сойти с одного и того же пути. Если рекурсия начинается с единицы, то она всегда в неё возвращается (см. книгу С.Клини, Введение в метаматематику, [гл. IX, §46]).
Все последовательности зеркальны, идентичны и обладают одинаковыми свойствами. И мы можем это легко проверить.
§9. Шаг впередПусть
![$n$ $n$](https://dxdy-02.korotkov.co.uk/f/5/5/a/55a049b8f161ae7cfeb0197d75aff96782.png)
- нечетное число, тогда чтобы двигаться вперед по правилу
![$\frac {n-1}{3}$ $\frac {n-1}{3}$](https://dxdy-01.korotkov.co.uk/f/4/b/b/4bb1f9867b5829bdb4563db22494283782.png)
мы должны:
- Отнять от
![$n$ $n$](https://dxdy-02.korotkov.co.uk/f/5/5/a/55a049b8f161ae7cfeb0197d75aff96782.png)
единицу
![$(n-1)$ $(n-1)$](https://dxdy-01.korotkov.co.uk/f/0/d/1/0d1f34c830dc60d4f09b8b49b25af89f82.png)
и разделить на три. Но если мы отнимем от нечетного числа единицу, то мы получим чётное. Четное не делится на три.
- Тогда у нас остается только один вариант, умножить
![$n$ $n$](https://dxdy-02.korotkov.co.uk/f/5/5/a/55a049b8f161ae7cfeb0197d75aff96782.png)
*2.
- Предположим, после
![$2n$ $2n$](https://dxdy-01.korotkov.co.uk/f/4/7/c/47c124971e1327d1d3882a141f95face82.png)
находится нечетное число
![$x$ $x$](https://dxdy-04.korotkov.co.uk/f/3/3/2/332cc365a4987aacce0ead01b8bdcc0b82.png)
. Тогда справедливо равенство:
![$\frac {2n-1}{3} = x$ $\frac {2n-1}{3} = x$](https://dxdy-04.korotkov.co.uk/f/f/9/f/f9f91f104017e7e62f5ac93b0286ebd382.png)
.
- Получаем
![$x = \frac {2n-1}{3}$ $x = \frac {2n-1}{3}$](https://dxdy-01.korotkov.co.uk/f/4/4/4/4449a40677240fe4932fa75edafc0a8182.png)
- Результат
![$\frac {2n}{3} - \frac {1}{3}$ $\frac {2n}{3} - \frac {1}{3}$](https://dxdy-01.korotkov.co.uk/f/0/6/5/065d36c59edc0a74b71b6067645c55e682.png)
будет целым только в том случае, если
![$n \equiv 2 \pmod 3$ $n \equiv 2 \pmod 3$](https://dxdy-01.korotkov.co.uk/f/0/f/0/0f065e6931084118f36907503b71e18d82.png)
.
Тогда для
![$n \equiv 1 \pmod 3$ $n \equiv 1 \pmod 3$](https://dxdy-04.korotkov.co.uk/f/b/f/7/bf7414f7c97388c618a0c531bc9a710482.png)
удвоим количество четных чисел:
- Умножаем
![$n$ $n$](https://dxdy-02.korotkov.co.uk/f/5/5/a/55a049b8f161ae7cfeb0197d75aff96782.png)
на 2, и снова на 2.
- Предположим, после
![$4n$ $4n$](https://dxdy-04.korotkov.co.uk/f/3/2/b/32b9ce449a8a3151ecebc40e1e56224182.png)
находится нечетное число
![$x$ $x$](https://dxdy-04.korotkov.co.uk/f/3/3/2/332cc365a4987aacce0ead01b8bdcc0b82.png)
. Тогда справедливо равенство:
![$\frac {4n-1}{3} = x$ $\frac {4n-1}{3} = x$](https://dxdy-01.korotkov.co.uk/f/8/a/f/8afbae6b6e078125f2ad3f8aa2243e7182.png)
.
- Получаем
![$x = \frac {4n-1}{3}$ $x = \frac {4n-1}{3}$](https://dxdy-02.korotkov.co.uk/f/5/5/b/55b2ea6f64abdf207030b19b6538663482.png)
- Результат
![$\frac {4n}{3} - \frac {1}{3}$ $\frac {4n}{3} - \frac {1}{3}$](https://dxdy-03.korotkov.co.uk/f/2/4/2/242a8ec0c02e8d526409362d5a9821c182.png)
всегда будет целый для
![$n \equiv 1 \pmod 3$ $n \equiv 1 \pmod 3$](https://dxdy-04.korotkov.co.uk/f/b/f/7/bf7414f7c97388c618a0c531bc9a710482.png)
.
Тоже самое и с правилом
![$4n+1$ $4n+1$](https://dxdy-01.korotkov.co.uk/f/8/3/9/83908d7bc1098c423296b00fabc8821482.png)
:
![Изображение](https://i.imgur.com/pG0MbEi.png)
Число 11 порождает две ветки. Зайдем в первую ветку
![$2n$ $2n$](https://dxdy-01.korotkov.co.uk/f/4/7/c/47c124971e1327d1d3882a141f95face82.png)
:
![$\frac {2n-1}{3} = x, \; \; n = \frac {3x+1}{2}$ $\frac {2n-1}{3} = x, \; \; n = \frac {3x+1}{2}$](https://dxdy-01.korotkov.co.uk/f/8/5/e/85ea092aec0774124d1222077156b3c882.png)
Зайдем во вторую ветку
![$8n$ $8n$](https://dxdy-02.korotkov.co.uk/f/d/6/1/d612c2a8a5d700585a5ecb6d421709a782.png)
:
![$\frac {8n-1}{3} = y, \; \; n = \frac {3y+1}{8}$ $\frac {8n-1}{3} = y, \; \; n = \frac {3y+1}{8}$](https://dxdy-03.korotkov.co.uk/f/a/b/2/ab2bd0c6c85b8253a029888b514882fd82.png)
![$\frac {3x+1}{2} = \frac {3y+1}{8}$ $\frac {3x+1}{2} = \frac {3y+1}{8}$](https://dxdy-04.korotkov.co.uk/f/f/b/b/fbba8373eb3c7312c1c120932f6267f782.png)
![$y=4x+1$ $y=4x+1$](https://dxdy-02.korotkov.co.uk/f/d/b/1/db1a0e2e2fef1b8417636da28d05345a82.png)
Да, всё верно:
![$n = 11, \; x = 7, \; y = 29 \; (4x+1).$ $n = 11, \; x = 7, \; y = 29 \; (4x+1).$](https://dxdy-02.korotkov.co.uk/f/1/5/6/15631707f5cf31ce8fc95826ac31f7ff82.png)
Теперь мы понимаем, почему в гипотезе Коллатца можно заменить нечетное число вида
![$4n+1$ $4n+1$](https://dxdy-01.korotkov.co.uk/f/8/3/9/83908d7bc1098c423296b00fabc8821482.png)
на его производное и спуск до единицы не изменится. Потому что это раздвоенная ветка одного и того же числа.
Обратим внимание и на цикл «1, 2, 4, 1». Он рождается в обеих схемах, что служит прекрасным доказательством тождественности правил.
Отвечая на вопрос, является ли правило
![$3n+1$ $3n+1$](https://dxdy-02.korotkov.co.uk/f/9/3/f/93f5f9a7e819a127ffcbbaa1c137009382.png)
развернутой в обратном направлении рекурсией
![$\frac {n-1}{3}$ $\frac {n-1}{3}$](https://dxdy-01.korotkov.co.uk/f/4/b/b/4bb1f9867b5829bdb4563db22494283782.png)
? Мы говорим, однозначно, да.
§10. Последний вопросИ последний вопрос, который мы обязаны задать: Есть ли такое число, которое не входит в рекурсию
![$\frac {n-1}{3}$ $\frac {n-1}{3}$](https://dxdy-01.korotkov.co.uk/f/4/b/b/4bb1f9867b5829bdb4563db22494283782.png)
?
Предположим, что есть. Но тогда из этого следует, что его нельзя подставить в
![$3n+1$ $3n+1$](https://dxdy-02.korotkov.co.uk/f/9/3/f/93f5f9a7e819a127ffcbbaa1c137009382.png)
. Потому что
![$3n+1$ $3n+1$](https://dxdy-02.korotkov.co.uk/f/9/3/f/93f5f9a7e819a127ffcbbaa1c137009382.png)
- это уже сформированная рекурсия от
![$\frac {n-1}{3}$ $\frac {n-1}{3}$](https://dxdy-01.korotkov.co.uk/f/4/b/b/4bb1f9867b5829bdb4563db22494283782.png)
.
Таким образом, мы приходим к выводу, что все числа рекурсивно связаны между собой, а правило
![$\frac {n-1}{3}$ $\frac {n-1}{3}$](https://dxdy-01.korotkov.co.uk/f/4/b/b/4bb1f9867b5829bdb4563db22494283782.png)
перебирает бесконечное количество веток с бесконечным количеством вариантов по mod(3) и умножением на 2. И каждая такая ветка обречена спуститься к единице. Ч.т.д.
---
С уважением,
Автор статьи: Михаил Мартынов, Россия, Оренбург, программист.