Сценарий: Джейкоб ДеНельски, Шриранг Карандикар.

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

В этой статье я исследую две гипотезы:

  • Проявляют ли разные основания одинаковое поведение Коллатца — каждая последовательность заканчивается на 1?
  • Имеют ли множители для базисов с поведением, подобным Коллатцу, то же свойство нечастотности, что и 3 в исходной гипотезе?

В исходной гипотезе Коллатца основание равно 2, а множитель равен 3. Я видел данные, в которых рассматриваются различные множители, используемые в гипотезе Коллатца, но мне было интересно, как будут выглядеть результаты, если вместо этого будут исследоваться другие основания. Для основания 2, 3 и его кратные встречаются нечасто. Если гипотеза является обобщенной, являются ли кратные всех множителей такими же редкими, как и в исходной гипотезе?

Ключевой момент заключается в том, чтобы помнить, что в стандартной гипотезе Коллатца, если число четное, оно делится на два. Если число нечетное, оно умножается на 3 и прибавляется 1. Функция Коллатца гарантирует, что если текущее число нечетное, следующее будет четным. Гипотеза Коллатца на самом деле представляет собой две операции, «борющиеся» друг с другом: одна толкает текущее число к бесконечности, а другая — к 1. Однако все числа в конце концов, кажется, заканчиваются на 1.

Что, если это мышление распространится на основание из пяти, а не на основание из двух, как в исходной гипотезе? Если значение делится на пять, то разделите на пять. Если это не так, то следование логике гипотезы Коллатца означало бы умножение этого числа и добавление смещения, чтобы оно делилось на пять. В зависимости от значения n%5, где n — текущее значение, следующей операцией будет 5n+4, 5n+3, 5n+2 или 5n+1.

Точно так же, что, если выбрано основание 7? Если число делится на 7, разделите на 7. В противном случае, в зависимости от значения n%7, вычислите 7n+6, 7n+5, 7n+4, 7n+3, 7n+2 или 7n+1 так, чтобы следующее число гарантированно будет делиться на 7.

Первое, что я хотел проверить, это то, будет ли модифицированная последовательность Коллатца работать для всех оснований. Я использовал приведенный ниже блок try/catch, чтобы найти все базы, которые работают между 2 и 100 для этого подхода. Я использовал максимальную итерацию 10 000, так как после такого количества итераций почти гарантирована бесконечная рекурсия.

Когда у меня был список всех работающих баз, пришло время протестировать эту пользовательскую функцию «Collatz». Я обнаружил, что использование основания 3, например, приводит к тому, что последовательности выходят из-под контроля и никогда не достигают 1. В приведенном ниже коде показано, как я впервые реализовал эту функцию. Это сработало, но эта конкретная реализация будет работать только для основания 3, а три оператора if будут проверять, равно ли n%3 2, 1 или 0. Проблема с этим подходом заключается в том, что для основания k, k-1 if операторы должны быть добавлены, чтобы изменить функцию для этой базы.

Пересмотренная функция, представленная ниже, устраняет эти недостатки. Функция рекурсивно возвращает n // base в случае, если n % base равно 0. Если n % base не равно 0, последняя строка гарантирует, что на следующей итерации n% base станет 0, а n будет разделено по основанию : поведение, демонстрируемое функцией Коллатца!

Первоначально я думал, что, возможно, будут работать только базисы, являющиеся простыми числами, но оказалось, что числа, которые работали как базисы, были довольно равномерно распределены. Ниже приведены гистограммы для времени остановки для различных оснований с начальными значениями от 1 до 2000. Первый график, основание 2, показывает время остановки для того, что фактически является исходной гипотезой Коллатца. Другие базы показывают, что происходит для других базисов, используя обобщенную гипотезу. Я также сгенерировал гораздо больший график, показывающий гистограммы для всех рабочих оснований ниже 100, который можно посмотреть здесь.

На приведенной ниже гистограмме показаны последовательности Коллатца от 1 до 2000 и время остановки для каждой последовательности Коллатца. Синий график показывает стандартную последовательность Коллатца с основанием 2, а оранжевый график показывает обобщенную функцию Коллатца с основанием 7. Точно так же вторая гистограмма показывает тот же график с основанием 2 и основанием 98. В то время как графики для оснований 7 и 98 смещены, они оба имеют четкие дискретные полосы.

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

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

На приведенном ниже графике показано распределение кратных первых десяти кратных 8. Значения 1 представляют собой начальные номера последовательностей «Коллаца», которые содержат конкретное кратное 8. Например, 8 встречается в трех из первых 1000 последовательностей этого « Collatz», а число 80 встречается в виде двух.

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

В процессе написания этих трех статей, хотя я, конечно, многое узнал о проблеме Коллатца, это также было отличным упражнением в C, Python и визуализации данных с помощью gnuplot и matplotlib. Визуализация нечастостей кратных и других интересных свойств дала мне гораздо больше понимания этой неразгаданной математической тайны. Есть еще много разных путей, которые можно исследовать в рамках этой проблемы: например, есть ли шаблон для оснований, которые работают с обобщенной функцией, множители, отличные от основания + 1, частотные шаблоны чисел, кроме множителя и его кратных, и многое другое.