Гипотеза Коллатца

Нерешенная задача по математике :

• Для четных чисел разделите их на 2;
• Для нечетных чисел умножьте на 3 и прибавьте 1.

При достаточном повторении все ли положительные целые числа сходятся к 1?

(еще нерешенные задачи по математике)

Ориентированный график , показывающий орбиты малых чисел по карте Коллатца, пропуская четные числа. Гипотеза Коллатца утверждает, что все пути в конечном итоге ведут к 1.

Коллатца Гипотеза — одна из самых известных нерешённых задач математики . Гипотеза спрашивает, приведет ли повторение двух простых арифметических операций в конечном итоге к преобразованию каждого положительного целого числа в 1. Она касается последовательностей целых чисел , в которых каждый член получается из предыдущего члена следующим образом: если предыдущий член четный , следующий член равен половине предыдущий срок. Если предыдущий член нечетный, следующий член в 3 раза больше предыдущего плюс 1. Предполагается, что эти последовательности всегда достигают 1, независимо от того, какое положительное целое число выбрано для начала последовательности. Было показано, что гипотеза верна для всех натуральных чисел до 2,95 × 10. ²⁰ , но общего доказательства не найдено.

Он назван в честь математика Лотара Коллатца , который выдвинул эту идею в 1937 году, через два года после получения докторской степени. Используемую последовательность чисел иногда называют последовательностью градины, числами градины или цифрами градины (поскольку значения обычно подвержены множественным спускам и подъемам, как градины в облаке). или как чудесные числа.

Пол Эрдеш сказал о гипотезе Коллатца: «Математика, возможно, не готова к таким проблемам». Джеффри Лагариас заявил в 2010 году, что гипотеза Коллатца «является чрезвычайно сложной проблемой, совершенно недоступной современной математике». Однако, хотя сама гипотеза Коллатца остается открытой, попытки решить проблему привели к новым методам и множеству частичных результатов.

Постановка задачи

Числа от 1 до 9999 и соответствующее им общее время остановки.

Гистограмма общего времени остановки для чисел от 1 до 10 ⁸ . Общее время остановки отложено по оси X , частота — по Y. оси

Гистограмма общего времени остановки для чисел от 1 до 10 ⁹ . Общее время остановки отложено по оси X , частота — по Y. оси

Время итерации для входов от 2 до 10 ⁷ .

Общее время остановки чисел до 250, 1000, 4000, 20000, 100000, 500000

Рассмотрим следующую операцию над произвольным положительным целым числом :

• Если число четное, разделите его на два.
• Если число нечетное, утройте его и прибавьте единицу.

В модульной арифметики обозначениях определите функцию f следующим образом: $$f(n)={\begin{cases}n/2&{\text{if }}n\equiv 0{\pmod {2}},\\[4px]3n+1&{\text{if }}n\equiv 1{\pmod {2}}.\end{cases}}$$

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

В обозначениях: $$a_{i}={\begin{cases}n&{\text{for }}i=0,\\f(a_{i-1})&{\text{for }}i>0\end{cases}}$$ (то есть: a _i — значение f, примененное к n рекурсивно i раз; a _i = f  ^я ( н ) ).

Гипотеза Коллатца такова: этот процесс в конечном итоге достигнет числа 1, независимо от того, какое положительное целое число выбрано изначально. То есть для каждого $n$, есть некоторые $i$ с $a_{i}=1$.

Если гипотеза ложна, то это может быть только потому, что существует некое начальное число, которое порождает последовательность, не содержащую 1. Такая последовательность либо войдет в повторяющийся цикл, исключающий 1, либо будет неограниченно возрастать. Такой последовательности не обнаружено.

Наименьшее i такое, что a _i < a _0, временем остановки n называется . Аналогично, наименьшее k такое, что a _k = 1, общим временем остановки n называется . Если один из индексов i или k не существует, мы говорим, что время остановки или полное время остановки соответственно бесконечно.

Гипотеза Коллатца утверждает, что общее время остановки каждого n конечно. Это также эквивалентно утверждению, что каждое n ≥ 2 имеет конечное время остановки.

Поскольку 3 n + 1 четно, когда n нечетно, вместо этого можно использовать «сокращенную» форму функции Коллатца: $$f(n)={\begin{cases}{\frac {n}{2}}&{\text{if }}n\equiv 0{\pmod {2}},\\[4px]{\frac {3n+1}{2}}&{\text{if }}n\equiv 1{\pmod {2}}.\end{cases}}$$ Это определение дает меньшие значения времени остановки и общего времени остановки без изменения общей динамики процесса.

Эмпирические данные

Например, начиная с n = 12 и применяя функцию f без «ярлыка», можно получить последовательность 12, 6, 3, 10, 5, 16, 8, 4, 2, 1.

Числу n = 19 требуется больше времени, чтобы достичь 1: 19, 58, 29, 88, 44, 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2. , 1.

Последовательность для n = 27 , указанная и изображенная на графике ниже, занимает 111 шагов (41 шаг через нечетные числа, выделены жирным шрифтом), поднимаясь до 9232, а затем опускаясь до 1.

27 , 82 , 41 , 124, 62, 31 , 94, 47 , 142, 107 71, 214, , 322, 161 , 484, 242, 121 , 364, 182, 91 , 274, 137 , 412, 206, 1 03 , 310, 155 , 466, 233 , 700, 350, 175 , 526, 263 , 790, 395 , 1186, 593 , 1780, 890, 445 , 1336, 668, 334, 167 , 502, 251 , 754, 377 , 1132, 566, 283 , 850, 425 , 1276, 638, 479 319, 958, , 1438, 719 , 2158, 1079, 3238 , 1619, 4858 , 2429, 7288 , 3644, 1822 , , 2734, 1367 , 4102, 2051 , 6154, 3077 , 9232, 4616, 2308, 1154, 577 , 1732, 866, 433 , 1300, 650, 325 , 976, 488, 244, 122, 61 , 184, 92, 46, 23 , 70 , 35 , 106, 53 , 160, 80, 40, 20, 10, 5 , 16, 8, 4, 2, 1 (последовательность A008884 в OEIS )

Числа, общее время остановки которых больше, чем у любого меньшего начального значения, образуют последовательность, начинающуюся с:

1, 2, 3, 6, 7, 9, 18, 25, 27, 54, 73, 97, 129, 171, 231, 313, 327, 649, 703, 871, 1161, 2223, 2463, 2919, 3711, 6171, ... (последовательность A006877 в OEIS ).

Стартовые значения, максимальная точка траектории которых больше, чем у любого меньшего стартового значения, следующие:

1, 2, 3, 7, 15, 27, 255, 447, 639, 703, 1819, 4255, 4591, 9663, 20895, 26623, 31911, 60975, 77671, 113383, 138367, 159487, 270271, 665215, 704511, ... (последовательность A006884 в OEIS )

Число шагов, необходимых для того, чтобы n достигло 1, равно

0, 1, 7, 2, 5, 8, 16, 3, 19, 6, 14, 9, 9, 17, 17, 4, 12, 20, 20, 7, 7, 15, 15, 10, 23, 10, 111, 18, 18, 18, 106, 5, 26, 13, 13, 21, 21, 21, 34, 8, 109, 8, 29, 16, 16, 16, 104, 11, 24, 24, ... (последовательность A006577 в OEIS )

Начальное значение, имеющее наибольшее общее время остановки, будучи

меньше 10 равно 9, имеющему 19 ступеней,

меньше 100 — это 97, что имеет 118 ступеней,

меньше 1000 — это 871, что имеет 178 шагов,

менее 10 ⁴ это 6171, что имеет 261 ступень,

менее 10 ⁵ составляет 77 031 , что имеет 350 шагов,

менее 10 ⁶ равно 837 799 , что имеет 524 шага,

менее 10 ⁷ равен 8 400 511 , что имеет 685 шагов,

менее 10 ⁸ равен 63 728 127 , что имеет 949 шагов,

менее 10 ⁹ равен 670 617 279 , что имеет 986 шагов,

менее 10 ¹⁰ равен 9 780 657 630 , что имеет 1132 шага,

менее 10 ¹¹ равно 75 128 138 247 , что имеет 1228 шагов,

менее 10 ¹² равен 989 345 275 647 , что имеет 1348 шагов. (последовательность A284668 в OEIS )

Эти числа являются наименьшими при указанном количестве шагов, но не обязательно единственными, которые ниже заданного предела. Например, 9 780 657 631 имеет 1132 шага, как и 9 780 657 630 .

Начальные значения, имеющие наименьшее общее время остановки по отношению к количеству цифр (в базе 2), представляют собой степени двойки, поскольку 2 ^н уменьшается вдвое n раз, чтобы достичь 1, и никогда не увеличивается.

Визуализации

• 
  Ориентированный граф, показывающий орбиты первых 1000 чисел.
• 
  Ось x представляет начальный номер, ось y представляет наибольшее число, достигнутое в ходе цепочки до 1. На этом графике показана ограниченная ось y : некоторые значения x дают промежуточные продукты размером до 2,7 × 10. ⁷ (для х = 9663 )
• 
  Тот же график, что и предыдущий, но в логарифмическом масштабе, поэтому y показаны все значения . Первая толстая линия ближе к середине графика соответствует вершине на отметке 27, которая достигает максимума на отметке 9232.
• 
  Дерево всех чисел, имеющих менее 20 ступеней.
• 
  Число итераций, необходимое для получения одной из первых 100 миллионов чисел.

Поддерживающие аргументы

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

Экспериментальные доказательства

Гипотеза проверена компьютером для всех начальных значений до 2. ⁶⁸ ≈ 2.95 × 10 ²⁰ . Все проверенные значения сходятся к 1.

Это компьютерное свидетельство все еще не является строгим доказательством того, что гипотеза верна для всех начальных значений, поскольку контрпримеры могут быть найдены при рассмотрении очень больших (или, возможно, огромных) положительных целых чисел, как в случае с опровергнутой гипотезой Полиа и гипотезой Мертенса .

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

Вероятностная эвристика

Если рассматривать только нечетные числа в последовательности, генерируемой процессом Коллатца, то каждое нечетное число в среднем ⁠ 3/4 ​ предыдущего ⁠ . (Точнее, среднее геометрическое отношений исходов равно ⁠ 3 / 4 ⁠ .) Это дает эвристический аргумент в пользу того, что каждая последовательность Хейлстоуна должна уменьшаться в долгосрочной перспективе, хотя это не является свидетельством против других циклов, а только против дивергенции. Этот аргумент не является доказательством, поскольку предполагает, что последовательности Хейлстоуна собираются из некоррелированных вероятностных событий. (Он строго устанавливает, что 2-адическое расширение процесса Коллатца имеет два шага деления для каждого шага умножения почти для всех 2-адических начальных значений.)

Время остановки

Как доказал Рихо Террас , почти каждое положительное целое число имеет конечное время остановки. Другими словами, почти каждая последовательность Коллатца достигает точки, которая находится строго ниже ее начального значения. Доказательство основано на распределении векторов четности и использует центральную предельную теорему .

В 2019 году Теренс Тао улучшил этот результат, показав с помощью логарифмической плотности , что почти все (в смысле логарифмической плотности) орбиты Коллатца спускаются ниже любой заданной функции начальной точки при условии, что эта функция расходится к бесконечности, как бы то ни было. медленно. Отвечая на эту работу, журнал Quanta Magazine написал, что Тао «пришёл к одному из самых значительных результатов по гипотезе Коллатца за последние десятилетия».

Нижние границы

В компьютерном доказательстве Красиков и Лагариас показали, что количество целых чисел в интервале [1, x ] , которые в конечном итоге достигают 1, по крайней мере равно x ^0.84 для всех достаточно больших x .

Циклы

В этой части рассмотрим сокращенную форму функции Коллатца. $$f(n)={\begin{cases}{\frac {n}{2}}&{\text{if }}n\equiv 0{\pmod {2}},\\[4px]{\frac {3n+1}{2}}&{\text{if }}n\equiv 1{\pmod {2}}.\end{cases}}$$ Цикл f — это последовательность ( a ₀ , a ₁ , ..., a _q ) различных натуральных чисел, где ( a 0 ₎ = a ₁ , f ( a ₁ ) = a ₂ , ... и f ( a _q ) знак равно а ₀ .

Единственный известный цикл — это (1,2) периода 2, называемый тривиальным циклом.

Длина цикла

Известно, что длина нетривиального цикла не менее 114 208 327 604 (или 186 265 759 595 без сокращения). Если можно показать, что для всех натуральных чисел меньше $3\times 2^{69}$ последовательности Коллатца достигают 1, тогда эта граница увеличится до 217 976 794 617 ( 355 504 839 929 без сокращения). Фактически, Элиаху (1993) доказал, что период p любого нетривиального цикла имеет вид $$p=301994a+17087915b+85137581c$$ где a , b и c — неотрицательные целые числа, b ≥ 1 и ac = 0 . Этот результат основан на непрерывном дробном разложении ⁠ пер 3 / пер 2 ⁠ .

k -циклы

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

Штайнер (1977) доказал, что не существует 1-цикла, кроме тривиального (1; 2) . Саймонс (2005) использовал метод Штайнера, чтобы доказать отсутствие 2-цикла. Саймонс и де Вегер (2005) расширили это доказательство до 68 циклов; нет k до k = 68 -цикла . Герчер расширил метод и доказал, что не существует k -цикла с k ≤91 . Поскольку исчерпывающие компьютерные поиски продолжаются, большие значения k могут быть исключены. Чтобы сформулировать аргумент более интуитивно; нам не нужно искать циклы, имеющие менее 92 подпоследовательностей, где каждая подпоследовательность состоит из последовательных взлетов, за которыми следуют последовательные падения.

Другие формулировки гипотезы

В обратном порядке

Первый 21 уровень Коллатца графа генерируется восходящим способом. Граф включает в себя все числа с длиной орбиты 21 или меньше.

Существует еще один подход к доказательству гипотезы, который рассматривает восходящий метод. метод выращивания так называемого графа Коллатца . Граф Коллатца — это граф , определяемый обратным соотношением $$R(n)={\begin{cases}\{2n\}&{\text{if }}n\equiv 0,1,2,3,5\\[4px]\left\{2n,{\frac {n-1}{3}}\right\}&{\text{if }}n\equiv 4\end{cases}}{\pmod {6}}.$$

Итак, вместо того, чтобы доказывать, что все положительные целые числа в конечном итоге приводят к 1, мы можем попытаться доказать, что 1 ведет в обратном направлении ко всем положительным целым числам. Для любого целого числа n n ≡ 1 (по модулю 2) тогда и только тогда, когда 3 n + 1 ≡ 4 (по модулю 6) . Эквивалентно, ⁠ n - 1/3 ⁠ ≡ ≡ 1 (по модулю 2) тогда и только тогда, когда n 4 (по модулю 6) . Предположительно, это обратное отношение образует дерево, за исключением цикла 1–2–4 (обратного цикла 4–2–1 неизмененной функции f, определенной в разделе «Постановка задачи» этой статьи).

Когда отношение 3 n + 1 функции f заменяется обычным замещающим «сокращенным» отношением ⁠ 3 n + 1/2 ⁠ , граф Коллатца определяется обратным соотношением, $$R(n)={\begin{cases}\{2n\}&{\text{if }}n\equiv 0,1\\[4px]\left\{2n,{\frac {2n-1}{3}}\right\}&{\text{if }}n\equiv 2\end{cases}}{\pmod {3}}.$$

Для любого целого числа n n ≡ 1 (по модулю 2) тогда и только тогда, когда ⁠ 3 n + 1/2 ≡ 2 (мод . ⁠ 3) . Эквивалентно, ⁠ 2 n - 1 / 3 ⁠ ≡ 1 (mod 2) тогда и только тогда, когда n ≡ 2 (mod 3) . Предположительно, это обратное соотношение образует дерево, за исключением цикла 1–2 (обратного цикла 1–2 функции f(n), измененного, как указано выше).

Альтернативно замените 3 n + 1 на ⁠ n ′ / H ( n ′ ) ⁠ где n ′ = 3 n + 1 и H ( n ′ ) — высшая степень 2 , которая делит n ′ (без остатка ). Результирующая функция f отображает нечетные числа в нечетные числа. Теперь предположим, что для некоторого нечетного числа n применение этой операции k раз дает число 1 (т. е. f ^к ( п ) знак равно 1 ). Тогда в двоичном формате число n можно записать как объединение строк w _k w _{k −1} ... w ₁ , где каждый w _h представляет собой конечный и непрерывный фрагмент из представления ⁠ 1 / 3 ^час ⁠ . представление n содержит повторы Таким образом , ⁠ 1 / 3 ^час ⁠ , где каждое повторение при необходимости вращается, а затем реплицируется до конечного числа битов. Это происходит только в двоичном формате. Предположительно, каждая двоичная строка s , оканчивающаяся на «1», может быть получена с помощью представления этой формы (где мы можем добавлять или удалять ведущие «0» к s ).

Как абстрактная машина, вычисляющая по основанию два

Повторяющиеся применения функции Коллатца можно представить как абстрактную машину обрабатывающую строки битов , . Машина выполнит следующие три шага с любым нечетным числом, пока не останется только один. 1 осталось:

1. Добавить 1 в (правом) конце числа в двоичном формате (что дает 2 n + 1 );
2. Добавьте это к исходному числу путем двоичного сложения (получив 2 n + 1 + n = 3 n + 1 );
3. Удалить все конечные 0 с (то есть многократно делить на 2, пока результат не станет нечетным).

Пример

Начальное число 7 записывается по второй базе как 111 . Результирующая последовательность Коллатца:

         111
        1111
       10110
      10111
     100010
    100011
    110100
   11011
  101000
 1011
10000

Как последовательность четности

В этом разделе рассмотрим сокращенную форму функции Коллатца. $$f(n)={\begin{cases}{\frac {n}{2}}&{\text{if }}n\equiv 0\\[4px]{\frac {3n+1}{2}}&{\text{if }}n\equiv 1\end{cases}}{\pmod {2}}.$$

Если P(...) — это четность числа, то есть P(2 n ) = 0 и P(2 n + 1) = 1 , то мы можем определить последовательность четности Коллатца (или вектор четности) для числа п как п _я знак равно P( а _я ) , где а ₀ знак равно п и а _{я +1} знак равно ж ( а _я ) .

Какая операция выполняется, ⁠ 3 n + 1/2 ⁠ или ​ ⁠ n / 2 ⁠ , зависит от четности. Последовательность четности такая же, как и последовательность операций.

Используя эту форму для f ( n ) , можно показать, что последовательности четности для двух чисел m и n будут согласовываться в первых k терминах тогда и только тогда, когда m и n эквивалентны по модулю 2. ^к . Это означает, что каждое число однозначно идентифицируется своей последовательностью четности, и, более того, если существует несколько циклов Хейлстоуна, то соответствующие им циклы четности должны быть разными.

Применяя f функцию k раз к числу n = 2 ^к a + b даст результат 3 ^с a + d , где d — результат применения f функции k раз к b , а c — сколько увеличений произошло во время этой последовательности. Например, за 2 ⁵ a + 1, есть 3 увеличения, поскольку 1 повторяется до 2, 1, 2, 1 и, наконец, до 2, поэтому результат равен 3 ³ а + 2 ; для 2 ² a + 1 есть только 1 увеличение, поскольку 1 повышается до 2 и падает до 1, поэтому результат равен 3 a + 1 . Когда b равно 2 ^к − 1 , то будет k подъемов и результат будет 3 ^к а + 3 ^к − 1 . Степень 3 умножения a не зависит от значения a ; это зависит только от поведения b . Это позволяет предсказать, что определенные формы чисел всегда будут приводить к меньшему числу после определенного количества итераций: например, 4 a + 1 становится 3 a + 1 после двух применений f , а 16 a + 3 становится 9 a + 2 после четырех применений f . Однако продолжаются ли эти меньшие числа до 1, зависит от значения a .

Как система тегов

Для функции Коллатца в сокращенной форме

$f(n)={\begin{cases}{\frac {n}{2}}&{\text{if }}n\equiv 0\\[4px]{\frac {3n+1}{2}}&{\text{if }}n\equiv 1.\end{cases}}{\pmod {2}}$

Последовательности града могут быть рассчитаны с помощью системы с двумя тегами с использованием правил производства.

а → bc , b → а , c → ааа

В этой системе положительное целое число n представлено строкой из n копий a , и итерация операции тега останавливается на любом слове длиной меньше 2. (Адаптировано из De Mol.)

Гипотеза Коллатца эквивалентно утверждает, что эта система тегов с произвольной конечной строкой a в качестве начального слова в конечном итоге останавливается (см. Систему тегов для рабочего примера).

Расширения для более крупных доменов

Итерация по всем целым числам

Расширение гипотезы Коллатца включает в себя все целые числа, а не только положительные целые числа. Если оставить в стороне цикл 0 → 0, в который нельзя войти извне, то всего существует четыре известных цикла, в которые, похоже, все ненулевые целые числа в конечном итоге попадают при итерации f . Эти циклы перечислены здесь, начиная с хорошо известного цикла для положительных n :

Нечетные значения выделены крупным жирным шрифтом. В списке каждого цикла первым указывается член с наименьшим абсолютным значением (который всегда нечетный).

Цикл	Длина цикла нечетных значений	Полная длина цикла
1 → 4 → 2 → 1 ...	1	3
−1 → −2 → −1 ...	1	2
−5 → −14 → −7 → −20 → −10 → −5 ...	2	5
−17 → −50 → −25 → −74 → −37 → −110 → −55 → −164 → −82 → −41 → −122 → −61 → −182 → −91 → −272 → −136 → −68 → −34 → −17 ...	7	18

Обобщенная гипотеза Коллатца — это утверждение, что каждое целое число при итерации по f в конечном итоге попадает в один из четырех циклов, указанных выше, или в цикл 0 → 0. (Цикл 0 → 0 включен только для полноты.)

Итерация рациональных чисел с нечетными знаменателями

Карта Коллатца может быть расширена до (положительных или отрицательных) рациональных чисел, которые имеют нечетный знаменатель при записи в наименьших терминах. Число считается «нечетным» или «четным» в зависимости от того, является ли его числитель нечетным или четным. Тогда формула для карты точно такая же, как и в случае, когда областью определения являются целые числа: такое «четное» рациональное число делится на 2; «нечетное» такое рациональное число умножается на 3, а затем добавляется 1. Тесно связанный факт состоит в том, что отображение Коллатца расширяется до кольца 2-адических целых чисел , которое содержит в качестве подкольца кольцо рациональных чисел с нечетными знаменателями.

При использовании «сокращенного» определения карты Коллатца известно, что любая периодическая последовательность четности порождается ровно одним рациональным числом. И наоборот, предполагается, что каждое рациональное число с нечетным знаменателем имеет в конечном итоге циклическую последовательность четности (гипотеза периодичности). ).

Если цикл четности имеет длину n и включает в себя нечетные числа ровно m раз с индексами k ₀ < ⋯ < k _{m −1} , то единственным рациональным числом, которое немедленно и периодически порождает этот цикл четности, является

${\frac {3^{m-1}2^{k_{0}}+\cdots +3^{0}2^{k_{m-1}}}{2^{n}-3^{m}}}.$ ( 1 )

Например, цикл четности (1 0 1 1 0 0 1) имеет длину 7 и четыре нечетных члена с индексами 0, 2, 3 и 6. Он повторно генерируется дробью $${\frac {3^{3}2^{0}+3^{2}2^{2}+3^{1}2^{3}+3^{0}2^{6}}{2^{7}-3^{4}}}={\frac {151}{47}}$$ поскольку последнее приводит к рациональному циклу $${\frac {151}{47}}\rightarrow {\frac {250}{47}}\rightarrow {\frac {125}{47}}\rightarrow {\frac {211}{47}}\rightarrow {\frac {340}{47}}\rightarrow {\frac {170}{47}}\rightarrow {\frac {85}{47}}\rightarrow {\frac {151}{47}}.$$

Любая циклическая перестановка (1 0 1 1 0 0 1) связана с одной из вышеуказанных дробей. Например, цикл (0 1 1 0 0 1 1) производится дробью $${\frac {3^{3}2^{1}+3^{2}2^{2}+3^{1}2^{5}+3^{0}2^{6}}{2^{7}-3^{4}}}={\frac {250}{47}}.$$

Для взаимно однозначного соответствия цикл четности должен быть несократимым , то есть не разбиваемым на одинаковые подциклы. В качестве иллюстрации этого цикл четности (1 1 0 0 1 1 0 0) и его подцикл (1 1 0 0) связаны с одной и той же дробью. ⁠ 5 / 7 ⁠ при сокращении до самых низких условий.

В этом контексте предположение о справедливости гипотезы Коллатца означает, что (1 0) и (0 1) — единственные циклы четности, порожденные положительными целыми числами (1 и 2 соответственно).

Если нечетный знаменатель d рационального числа не кратен 3, то все итерации имеют одинаковый знаменатель, и последовательность числителей можно получить, применив обобщение « 3 n + d ». функции Коллатца $$T_{d}(x)={\begin{cases}{\frac {x}{2}}&{\text{if }}x\equiv 0{\pmod {2}},\\[4px]{\frac {3x+d}{2}}&{\text{if }}x\equiv 1{\pmod {2}}.\end{cases}}$$

2-адическое расширение

Функция $$T(x)={\begin{cases}{\frac {x}{2}}&{\text{if }}x\equiv 0{\pmod {2}}\\[4px]{\frac {3x+1}{2}}&{\text{if }}x\equiv 1{\pmod {2}}\end{cases}}$$ четко выражен на кольце $\mathbb {Z} _{2}$ , 2-адических целых чисел где оно непрерывно и сохраняет меру относительно 2-адической меры. При этом ее динамика, как известно, эргодична .

Определим четности векторную функцию Q, действующую на $\mathbb {Z} _{2}$ как $$Q(x)=\sum _{k=0}^{\infty }\left(T^{k}(x)\mod 2\right)2^{k}.$$

Функция Q является 2-адической изометрией . Следовательно, каждая бесконечная последовательность четности встречается ровно для одного 2-адического целого числа, так что почти все траектории ацикличны в $\mathbb {Z} _{2}$.

Эквивалентная формулировка гипотезы Коллатца состоит в том, что $$Q\left(\mathbb {Z} ^{+}\right)\subset {\tfrac {1}{3}}\mathbb {Z} .$$

Итерация по действительным или комплексным числам

Паутинка орбиты 10 → 5 → 8 → 4 → 2 → 1 → ... в расширении отображения Коллатца до вещественной линии.

Отображение Коллатца можно расширить до действительной линии , выбрав любую функцию, результат которой равен $x/2$ когда $x$ является четным целым числом, и либо $3x+1$ или $(3x+1)/2$ (для «ярлыковой» версии), когда $x$ является нечетным целым числом. Это называется интерполирующей функцией. Простой способ сделать это — выбрать две функции $g_{1}$ и $g_{2}$, где:

$g_{1}(n)={\begin{cases}1,&n{\text{ is even,}}\\0,&n{\text{ is odd,}}\end{cases}}$

$g_{2}(n)={\begin{cases}0,&n{\text{ is even,}}\\1,&n{\text{ is odd,}}\end{cases}}$

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

$f(x)\triangleq {\frac {x}{2}}\cdot g_{1}(x)\,+\,{\frac {3x+1}{2}}\cdot g_{2}(x)$.

Одним из таких вариантов является $g_{1}(x)\triangleq \cos ^{2}\left({\tfrac {\pi }{2}}x\right)$ и $g_{2}(x)\triangleq \sin ^{2}\left({\tfrac {\pi }{2}}x\right)$. Итерации , которую этой карты приводят к динамической системе далее исследовал Марк Чемберланд. Он показал, что гипотеза не верна для положительных действительных чисел, поскольку существует бесконечно много неподвижных точек , а также орбит, уходящих монотонно в бесконечность. Функция $f$ имеет два притягивающих цикла периода $2$: $(1;\,2)$ и $(1.1925...;\,2.1386...)$. Более того, предполагается, что множество неограниченных орбит имеет меру $0$.

Летерман, Шлейхер и Вуд распространили исследование на комплексную плоскость . Они использовали функцию Чемберленда для комплексного синуса и косинуса и добавили дополнительный член ${\tfrac {1}{\pi }}\left({\tfrac {1}{2}}-\cos(\pi z)\right)\sin(\pi z)\,+$ $h(z)\sin ^{2}(\pi z)$, где $h(z)$ это любая целая функция . Поскольку это выражение имеет нулевое значение для действительных целых чисел, расширенная функция

${\begin{aligned}f(z)\triangleq \;&{\frac {z}{2}}\cos ^{2}\left({\frac {\pi }{2}}z\right)+{\frac {3z+1}{2}}\sin ^{2}\left({\frac {\pi }{2}}z\right)\,+\\&{\frac {1}{\pi }}\left({\frac {1}{2}}-\cos(\pi z)\right)\sin(\pi z)+h(z)\sin ^{2}(\pi z)\end{aligned}}$

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

Коллатца Фрактал с центром в начале координат и действительными частями от -5 до 5.

Большинство точек имеют орбиты, расходящиеся в бесконечность. Раскрашивание этих точек в зависимости от того, насколько быстро они расходятся, дает изображение слева, например $h(z)\triangleq 0$. Внутренние черные области и внешняя область — это компоненты Фату , а граница между ними — множество Жюлиа . $f$, который образует фрактальный узор, иногда называемый «фракталом Коллатца».

Набор Юлии экспоненциальной интерполяции.

Существует много других способов определения сложной интерполирующей функции, например использование комплексной экспоненты вместо синуса и косинуса:

$f(z)\triangleq {\frac {z}{2}}+{\frac {1}{4}}(2z+1)\left(1-e^{i\pi z}\right)$,

которые демонстрируют разную динамику. В этом случае, например, если $\operatorname {Im} (z)\gg 1$, затем $f(z)\approx z+{\tfrac {1}{4}}$. Соответствующее множество Жюлиа, показанное справа, состоит из бесчисленного множества кривых, называемых волосками , или лучами .

Оптимизации

Компромисс время-пространство

В разделе «Как последовательность четности» выше можно ускорить моделирование последовательности. Чтобы перейти на k шагов вперед на каждой итерации (используя функцию f из этого раздела), разбейте текущее число на две части: b ( k младших битов, интерпретируемых как целое число) и a (остальные биты как целое число). Результат прыжка вперед k определяется выражением

ж ^к (2 ^к а + б ) = 3 ^{в ( б , к )} а + d ( б , k ) .

Значения c (а лучше 3 ^с ) и d может быть предварительно вычислено для всех возможных k -битных чисел b , где d ( b , k ) — результат применения f функции k раз к b , а c ( b , k ) — количество нечетных чисел, встречающихся на путь. Например, если k = 5 , можно перейти на 5 шагов вперед на каждой итерации, отделив 5 младших битов числа и используя

c (0...31, 5) = { 0, 3, 2, 2, 2, 2, 2, 4, 1, 4, 1, 3, 2, 2, 3, 4, 1, 2, 3, 3, 1, 1, 3, 3, 2, 3, 2, 4, 3, 3, 4, 5 },

d (0...31, 5) = { 0, 2, 1, 1, 2, 2, 2, 20, 1, 26, 1, 10, 4, 4, 13, 40, 2, 5, 17, 17, 2, 2, 20, 20, 8, 22, 8, 71, 26, 26, 80, 242 }.

Для этого требуется 2 ^к предварительные вычисления и сохранение для ускорения итогового расчета в k раз , что является компромиссом между пространством и временем .

Модульные ограничения

Для специальной цели поиска контрпримера к гипотезе Коллатца это предварительное вычисление приводит к еще более важному ускорению, которое использовал Томас Оливейра и Силва в своих вычислительных подтверждениях гипотезы Коллатца до больших значений n . Если для некоторых заданных b и k неравенство

ж ^к (2 ^к а + б ) = 3 ^{в ( б )} а + d ( б ) < 2 ^к а + б

выполняется для всех a , то первый контрпример, если он существует, не может быть b по модулю 2 ^к . Например, первый контрпример должен быть нечетным, поскольку f (2 n ) = n меньше 2 n ; и это должно быть 3 по модулю 4, потому что f ² (4 n + 1) = 3 n + 1 , меньше 4 n + 1 . Для каждого начального значения a, которое не является контрпримером к гипотезе Коллатца, существует k , для которого выполняется такое неравенство, поэтому проверка гипотезы Коллатца для одного начального значения так же эффективна, как проверка всего класса конгруэнтности. По мере увеличения k при поиске необходимо проверять только те остатки b , которые не исключаются при более низких значениях k . Выживает лишь экспоненциально малая часть остатков. Например, единственными сохранившимися остатками mod 32 являются 7, 15, 27 и 31.

Целые числа, делящиеся на 3, не могут образовывать цикл, поэтому эти целые числа не нужно проверять в качестве встречных примеров.

Сиракузская функция

Если k — нечетное целое число, то 3 k + 1 — четное, поэтому 3 k + 1 = 2. ^а k ′ с k ′ нечетным и a ≥ 1 . Функция Сиракуз — это функция f из множества I положительных нечетных целых чисел в себя, для которой f ( k ) = k ’ (последовательность A075677 в OEIS ).

Некоторые свойства функции Сиракуз:

• Для всех ∈ I f k ( 4 k + 1) знак равно f ( k ) . (Потому что 3( 4k + 1) + 1 = 12k + 4 = 4(3k + 1) .)
• В более общем плане: для всех p ≥ 1 нечетных h f и ^{п - 1} (2 ^п ч - 1) = 2 × 3 ^{п - 1} час - 1 . (Здесь f ^{п - 1} это обозначение итерации функции .)
• Для всех нечетных f h ( 2 h − 1) ⩽ ⁠ 3 h − 1 / 2 ⁠

Гипотеза Коллатца эквивалентна утверждению, что для всех k из I существует целое число n ≥ 1 такое, что f ^н ( k ) знак равно 1 .

Неразрешимые обобщения

Основная статья: ФРАКТРАН

В 1972 году Джон Хортон Конвей доказал, что естественное обобщение проблемы Коллатца алгоритмически неразрешимо .

В частности, он рассматривал функции вида $${g(n)=a_{i}n+b_{i}}{\text{ when }}{n\equiv i{\pmod {P}}},$$ где a ₀ , b ₀ , ..., a _{P − 1} , b _{P − 1} — рациональные числа, выбранные таким образом, что g ( n ) всегда является целым числом. Стандартная функция Коллатца имеет вид P = 2 , a ₀ = ⁠ 1 / 2 ⁠ , б ₀ знак равно 0 , а _{1 знак} равно 3 , б ₁ знак равно 1 . Конвей доказал, что проблема

Учитывая g и n , последовательность итераций g ^к ( n ) достичь 1 ?

неразрешима, представляя проблему остановки таким образом.

Ближе к проблеме Коллатца стоит следующая универсальная количественная проблема:

Учитывая g , выполняет ли последовательность итераций g ^к ( n ) достигает 1 для всех n > 0 ?

Изменение условия таким образом может усложнить или облегчить решение проблемы (интуитивно, труднее обосновать положительный ответ, но может быть легче обосновать отрицательный). Курц и Саймон доказал, что универсальная квантифицированная проблема на самом деле неразрешима и находится даже выше в арифметической иерархии ; в частности, это Π ⁰
_2- полный. Этот результат о твердости сохраняется, даже если ограничить класс функций g , зафиксировав модуль P равным 6480.

Итерации в упрощенной версии этой формы со всеми $b_{i}$ равные нулю, формализуются на эзотерическом языке программирования под названием FRACTRAN .

По вычислительной сложности

Коллатц и связанные с ним гипотезы часто используются при изучении сложности вычислений. Соединение осуществляется через функцию Busy Beaver , где BB(n) — максимальное количество шагов, сделанных любой машиной Тьюринга остановившейся с n состояниями. Существует машина Тьюринга с 15 состояниями, которая останавливается тогда и только тогда, когда гипотеза Пола Эрдеша (тесно связанная с гипотезой Коллатца) ложна. Следовательно, если бы BB(15) было известно и эта машина не остановилась за такое количество шагов, было бы известно, что она будет работать вечно, и, следовательно, не существует никаких контрпримеров (что доказывает, что гипотеза верна). Это совершенно непрактичный способ разрешить эту гипотезу; вместо этого оно используется для предположения, что BB(15) будет очень сложно вычислить, по крайней мере так же сложно, как и разрешить эту гипотезу, подобную Коллатцу.

В популярной культуре

В фильме «Пламя» аспирант кафедры чистой математики объясняет гипотезу Коллатца группе студентов. Она на время откладывает учебу, чтобы ответить на некоторые нерешенные вопросы о прошлом своей семьи. В конце фильма оказывается, что гипотеза Коллатца предвещает тревожное и трудное открытие, которое она делает о своей семье.

См. также

• 3 х + 1 полугруппа
• Арифметическая динамика
• Модульная арифметика
• Аффинная группа по классу вычета

Внешние ссылки

• Мэтьюз, Кейт. « 3 х + 1 страница» .
• Текущий волонтерский вычислительный проект, заархивированный 30 августа 2021 г. в Wayback Machine Дэвидом Баржиной, проверяет сходимость гипотезы Коллатца для больших значений. (дальний прогресс на данный момент)
• ( BOINC ) волонтерский вычислительный проект. Архивировано 4 декабря 2017 г. на Wayback Machine , который проверяет гипотезу Коллатца для больших значений.
• Текущий волонтерский вычислительный проект Эрика Розендаала подтверждает гипотезу Коллатца для все больших и больших значений.
• Другой текущий волонтерский компьютерный проект Томаса Оливейры и Силвы продолжает проверять гипотезу Коллатца (с меньшим количеством статистики, чем на странице Эрика Розендаала, но с дальнейшим прогрессом).
• Вайсштейн, Эрик В. «Проблема Коллатца» . Математический мир .
• Задача Коллатца в PlanetMath ..
• Ночелла, Джесси. «Тропы Коллатца» . Демонстрационный проект Wolfram .
• Айзенбуд, Д. (8 августа 2016 г.). Невзламываемый? Гипотеза Коллатца (короткое видео). Числофил. Архивировано из оригинала 11 декабря 2021 г. – на YouTube.
• Эйзенбуд, Д. (9 августа 2016 г.). Невзламываемый? Гипотеза Коллатца (дополнительные кадры). Числофил. Архивировано из оригинала 11 декабря 2021 г. – на YouTube.
• Алекс Конторович (в роли) (30 июля 2021 г.). Простейшая математическая задача, которую никто не может решить (короткое видео). Веритасиум – через YouTube.
• Готовы ли компьютеры решить эту заведомо громоздкую математическую задачу?