Не так давно я наткнулся на гипотезу Коллатца, очень интересную математическую задачу, доказательство которой еще никто не нашел. Гипотеза Коллатца, также известная как проблема 3n+1, выглядит настолько простой, что у любого может возникнуть соблазн попытаться подойти к ней и найти доказательство.

Я слышал, что эта гипотеза в какой-то момент остановила прогресс в математике, потому что каждый математик работал над ней, пытаясь найти ее доказательство.

Так что же такое гипотеза Коллатца?

Гипотеза Коллатца — это гипотеза в математике, названная в честь Лотара Коллатца, и если обобщить ее: если взять любое натуральное число n, если оно хотя бы поделится на 2 (чтобы getn/2), если оно нечетное, умножьте его на 3 и прибавьте 1 (чтобы получить 3n+1) и если вы будете повторять этот процесс рекурсивно и бесконечно, то в конечном итоге вы достигнете 1.

Например, возьмем число 20, это последовательность, которую вы получите:

20, 10 (20/2), 5 (10/2), 16 (3*5+1), 8(16/2), 4(8/2), 2(4/2), 1(2/2)

Как видите, в итоге мы достигли 1. Это основы, и если вы хотите получить более подробную информацию, есть много информации в Интернете.

Эта статья о другой формулировке одной и той же гипотезы: обратной.

Обратное отношение

Первоначальная формулировка гласит, что все натуральные числа в конечном итоге приводят к единице. Используя обратное соотношение, мы можем поставить перед собой задачу доказать обратное, что 1 ведет ко всем натуральным числам.

Обратное соотношение несколько запутаннее и сложнее, чем исходное 3n+1, и требуется некоторое время, чтобы разобраться в этом. Он основан на Модульной арифметике, обратите внимание на символ конгруэнтности (≡):

Для любого целого числа n, n ≡ 1 (mod 2) если и только если 3n + 1 ≡ 4 (mod 6). Эквивалентно (n - 1)/3 ≡ 1 (mod 2) тогда и только тогда, когда n ≡ 4 (mod 6).

Для обратной гипотезы нам нужно подняться снизу вверх, 1. В этой формулировке меня интересует (n − 1)/3 ≡ 1 (mod 2) если и только если n ≡ 4 (mod 6) часть.

Так что же это нам дает? С помощью этой части мы можем «обнаружить» нечетные числа выше заданного числа, почему это полезно, потому что только иногда будут нечетные числа выше заданного числа и все время четные числа (см. рис. выше, 2n всегда присутствует).

Если n ≡ 4 (mod 6), то (n − 1)/3 ≡ 1 (mod 2)

Другими словами, слова JavaScript:

если (n-4)%6 = 0, то следующее число будет (n − 1)/3, а это число
((n − 1)/3)%2 = 1 (нечетное)

Давайте проверим это, начиная с 1:

(1–4)%6 != 0 означает, что в последовательности Коллатца нет нечетных чисел больше 1, но мы знаем, что четное (*2) число обязательно будет, поэтому число больше единицы будет 2.

Давайте продолжим со 2:

(2–4)%6 != 0 означает, что выше 2 нет нечетного числа, только четное: 2*2 = 4

Давайте продолжим с 4:

(4–4)%6 = 0, что означает, что выше 4 есть нечетное число, и это число равно (4–1)/3, что равно единице. Мы вернулись к тому, с чего начали, и это цикл, гипотеза Коларца «аномалия», что цикл 1 → 4 → 2 → 1. Сейчас нас это не волнует, поэтому нам нужно добавить еще одно условие для наших нечетных чисел:

Мы можем использовать нечетное число только в том случае, если оно не равно 1: (n-1)/3 != 1

Прямо сейчас мы можем просто проигнорировать нечетное число 1 и перейти к четному: 8

(8–4)%6 !=0, у нас есть только даже больше 8, что равно 16.

Пока у нас есть восходящая последовательность Коллатца: 1–2–4–8–16.

Посмотрим что будет дальше:

(16–4)%6 = 0 Существует нечетное число выше 16, и его (16–1)/3 = 5, как мы знаем, всегда будет также четное число,

Прямо сейчас мы знаем, что есть 2 числа выше 16: 5 и 32, здесь мы можем видеть формирование дерева:

И когда мы повторим тот же процесс для 32 и 5, мы увидим, как будет расти это дерево.

Теперь, когда мы немного разобрались с арифметикой обратной формулировки гипотезы Коллатца, мы, наконец, можем начать что-то кодировать. Как вы уже знаете, языком, который я выбрал для реализации игровой площадки, является JavaScript, учитывая, что я буду использовать только функции родного языка без каких-либо осложнений.

Простые уровни без ссылок

Первая простая вещь, которую мы можем сделать, это заполнить массив массивов, каждый подмассив будет соответствовать числам на определенном уровне дерева:

Бинарное дерево

Как вы могли заметить, результаты вычислений образуют несбалансированное бинарное дерево или даже, возможно, бинарное дерево поиска, путем замены условий больше чем и меньше чем с простыми нечетными и четными. Я не буду здесь создавать пользовательскую структуру данных бинарного дерева, она заслуживает отдельной статьи, но, эй, мы знаем, что мы можем представить бинарное дерево как неявную структуру данных, используя нативные массивы:

В этом компактном расположении, если узел имеет индекс i, его потомки находятся с индексами 2i+1 (для левого потомка) и 2i+2 (для правого), а его родитель (если есть) находится с индексом ( i-1)/2 (при условии, что корень имеет нулевой индекс).

Как видите, это была действительно плохая идея и абсолютно не эффективное решение для последовательности Коллатца. Я думаю, что могут быть способы оптимизации, но они определенно выходят за рамки этой статьи.

Вывод

Самая сложная часть обратной гипотезы Коллатца — это вычисление лежащей в ее основе математики, после чего вы можете выполнять свои собственные решения по реализации, хранению и вычислениям, как вы видели в моих двух примерах выше. Все зависит от того, над каким подходом вы работаете и для чего вам нужны данные, анализ, визуализация или что-то еще.

И просто в качестве отказа от ответственности, но если вы читаете эту статью, вы, вероятно, уже знаете, что однопоточный JavaScript, привязанный к процессору, не подходит для реальных тяжелых вычислений и анализа. Причина, по которой я играл с ним, — будущая визуализация результатов, рисование красивых графиков и деревьев, здесь мы просто охватываем базовую арифметику.