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

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

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

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

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

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

Она названа в честь математика Лотара Коллатца , который представил эту идею в 1937 году, через два года после получения докторской степени. ^[4] Последовательность задействованных чисел иногда называют последовательностью градин, числами градин или числами градин (потому что значения обычно подвержены многократным падениям и подъемам, как градины в облаке), ^[5] или чудесными числами. ^[6]

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

Постановка проблемы

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

Гистограмма общего времени остановок для чисел от 1 до 10 ^8. Общее время остановок отложено по оси $x$ , частота — по оси $y$ .

Гистограмма общего времени остановок для чисел от 1 до 10 ^9. Общее время остановок отложено по оси $x$ , частота — по оси $y$ .

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

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

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

В модульной арифметической нотации определим функцию $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$ — это значение $f,$ примененное к $n$ рекурсивно $i$ раз; $a$ $i$ $=$ $f$ $i$ $($ $n$ $)$ ). $a_{i}={\begin{cases}n&{\text{for }}i=0,\\f(a_{i-1})&{\text{for }}i>0\end{cases}}$

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

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

Наименьшее $i,$ $такое$ что $a i < a 0,$ называется временем остановки n . Аналогично, наименьшее $k$ , такое что $a$ $k$ $= 1,$ называется общим временем остановки n . ^[2] Если один из индексов $i$ или $k не существует, мы говорим$ $,$ что время остановки или общее время остановки, соответственно, бесконечно.

Гипотеза Коллатца утверждает, что общее время остановки каждого $n$ конечно. Это также эквивалентно утверждению, что каждое $n \geq 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, 71 , 214, 107 , 322, 161 , 484, 242, 121 , 364, 182, 91 , 274, 137 , 412, 206, 103 , 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, 319 , 958, 479 , 1438, 719 , 2158, 1079 , 3238, 1619 , 4858, 2429 , 7288, 3644, 1822, 911 , 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]

меньше 10 ¹¹75 128 138 247 , который имеет 1228 ступеней,

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

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

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

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

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

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

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

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

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

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

Однако такие проверки могут иметь и другие последствия. Определенные ограничения на любой нетривиальный цикл, такие как нижние границы длины цикла, могут быть доказаны на основе значения самого низкого члена в цикле. Поэтому компьютерный поиск для исключения циклов с небольшим самым низким членом может усилить эти ограничения. ^[13]^[14]^[15]

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

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

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

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

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

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

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

Циклы

В этой части рассмотрим сокращенную форму функции Коллатца. Цикл — это последовательность $($ $a$ $0$ $,$ $a$ $1$ $, ...,$ $a$ $q$ $)$ различных положительных целых чисел, где $f$ $($ $a$ $0$ $) =$ $a$ $1$ , $f$ $($ $a$ $1$ $) =$ $a$ $2$ , ..., и $f$ $($ $a$ $q$ $) =$ $a$ $0$ . $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}}$

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

Длина цикла

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

к-циклы

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

Steiner (1977) доказал, что не существует 1-цикла, кроме тривиального $(1; 2)$ . ^[21] Simons (2005) использовал метод Steiner, чтобы доказать, что не существует 2-цикла. ^{[22] Simons и de Weger (2005) расширили это доказательство до 68-циклов;} $k$ -цикла нет вплоть до $k = 68.$ [ ^15] Hercher расширил метод еще больше и доказал, что не существует k -цикла с $k \leq 91.$ [ ^20] Поскольку исчерпывающие компьютерные поиски продолжаются, большие значения $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 \equiv 1 (mod 2)$ тогда и только тогда, когда $3 n + 1 \equiv 4 (mod 6)$ . Эквивалентно, $⁠$ $н - 1 / 3 ⁠ \equiv 1 (mod 2)$ тогда и только тогда, когда $n \equiv 4 (mod 6)$ . Предположительно, это обратное отношение образует дерево, за исключением цикла 1–2–4 (обратного цикла 4–2–1 неизмененной функции $f,$ определенной в разделе «Постановка задачи» этой статьи).

Когда отношение $3 n + 1$ функции $f$ заменяется общим заменяющим «сокращенным» отношением $⁠$ $3 н + 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 \equiv 1 (mod 2)$ тогда и только тогда, когда $⁠$ $3 н + 1 / 2 ⁠ \equiv 2 (mod 3)$ . Эквивалентно, $⁠$ $2 н - 1 / 3 ⁠ \equiv 1 (mod 2)$ тогда и только тогда, когда $n \equiv 2 (mod 3)$ . Предположительно, это обратное отношение образует дерево, за исключением цикла 1–2 (обратного цикла 1–2 функции f(n), пересмотренного, как указано выше).

В качестве альтернативы замените $3 n + 1$ на $⁠$ $н' / Н (н') ⁠$ где $n' = 3 n + 1$ и $H (n')$ является наибольшей степенью числа 2 , которая делит $n'$ (без остатка ). Результирующая функция $f$ отображает нечетные числа в нечетные числа. Теперь предположим, что для некоторого нечетного числа $n$ применение этой операции $k$ раз дает число 1 (то есть $f k (n) = 1$ ). Тогда в двоичной системе число $n$ можно записать как конкатенацию строк $w k w k -1 ... w 1$ , где каждое $w h$ является конечным и непрерывным извлечением из представления $⁠$ $1 / 3 ч. ⁠$ .^{[23] Следовательно} $,$ представление $n$ содержит повторения ⁠ $1 / 3 ч. ⁠$ , где каждый повтор опционально вращается и затем реплицируется до конечного числа бит. Это происходит только в двоичном коде.^[24] Предположительно, каждая двоичная строка $s$ , которая заканчивается на «1», может быть достигнута представлением этой формы (где мы можем добавлять или удалять ведущие «0» к $s$ ).

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

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

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

Пример

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

 111 111 1 1011 0  1011 1 10001 0  10001 1 1101 00  1101 1 101 000  101 1
1 0000

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

В этом разделе рассмотрим сокращенную форму функции Коллатца $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$ , то мы можем определить последовательность четности Коллатца (или вектор четности) для числа $n$ как $p i = P(a i)$ , где $a 0 = n$ , а $a i +1 = f (a i)$ .

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

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

Применение функции $f$ $k$ раз к числу $n = 2 k a + b$ даст результат $3 c a + d$ , где $d$ — результат применения функции $f$ $k$ раз к $b$ , а $c$ — количество увеличений, произошедших в этой последовательности. Например, для $25 a + 1$ происходит 3 увеличения, поскольку 1 увеличивается до 2, 1, 2, 1 и, наконец, до 2 , поэтому результат равен $33 a + 2$ ; для $22 a + 1$ происходит только 1 увеличение, поскольку 1 увеличивается до 2 и уменьшается до 1 , поэтому результат равен $3 a + 1$ . Когда $b$ равно $2 k - 1$ , то будет $k$ увеличений, и результат будет равен $3 k a + 3 k - 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}}$

Последовательности градин можно вычислить с помощью 2-теговой системы с правилами производства

а \to bc

б \to а

c \to ааа

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

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

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

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

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

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

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

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

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

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

Если цикл четности имеет длину $n$ и включает нечетные числа ровно $m$ раз в индексах $k 0 < \dots < k 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$ » ^[26] функции Коллатца $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-адическое расширение

Функция хорошо определена на кольце 2 -адических целых чисел , где она непрерывна и сохраняет меру относительно 2-адической меры. Более того, ее динамика, как известно, эргодична . ^[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}$

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

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

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

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

Карту Коллатца можно расширить до вещественной линии , выбрав любую функцию, которая вычисляется как , когда — четное целое число, и как или (для «сокращенной» версии), когда — нечетное целое число. Это называется интерполирующей функцией. Простой способ сделать это — выбрать две функции и , где: $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)

Одним из таких выборов является и . Итерации этого отображения приводят к динамической системе , дополнительно исследованной Марком Чемберлендом. ^[28] Он показал, что гипотеза не верна для положительных действительных чисел, поскольку существует бесконечно много неподвижных точек , а также орбит, монотонно уходящих в бесконечность. Функция имеет два притягивающих цикла периода : и . Более того, предполагается, что множество неограниченных орбит имеет меру . $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$

Летерман, Шлейхер и Вуд расширили исследование до комплексной плоскости . ^[29] Они использовали функцию Чемберленда для комплексного синуса и косинуса и добавили дополнительный член , где — любая целая функция . Поскольку это выражение вычисляется как ноль для действительных целых чисел, расширенная функция ${\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$

Большинство точек имеют орбиты, которые расходятся к бесконечности. Раскрашивание этих точек в зависимости от того, насколько быстро они расходятся, дает изображение слева, для . Внутренние черные области и внешняя область являются компонентами Фату , а граница между ними — множество Жюлиа , которое образует фрактальный узор, иногда называемый «фракталом Коллатца». $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$ определяется как

f k (2 k a + b) = 3 c (b, k) a + d (b, k)

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

с

(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 },

д

(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 }.

Это требует $2k$ предварительных вычислений $и$ хранения для ускорения результирующего вычисления в $k$ раз , компромисс между пространством и временем .

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

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

f k (2 k a + b) = 3 c (b) a + d (b) < 2 k a + b

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

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

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

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

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

Для всех $k \in I$ , $f (4 k + 1) = f (k)$ . (Поскольку $3(4 k + 1) + 1 = 12 k + 4 = 4(3 k + 1)$ .)
В более общем виде: для всех $p \geq 1$ и нечетных $h$ , $f p - 1 (2 p h - 1) = 2 \times 3 p - 1 h - 1$ . (Здесь $f p - 1$ — это обозначение итерации функции .)
Для всех нечетных $h$ , $f (2 h - 1) \leq ⁠ 3 ч - 1 / 2 ⁠$

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

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

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

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

При заданных

g

n

достигает ли последовательность итераций

g k (n)

1

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

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

При заданном

g

достигает ли последовательность итераций

g k (n)

1

для всех

n > 0

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

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

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

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

Смотрите также

На Викискладе есть медиафайлы по теме «Гипотеза Коллатца» .

Примечания

^ Она также известна как проблема (или гипотеза ) $3 n + 1$ , проблема (или гипотеза ) $3$ $x$ $+ 1$ , гипотеза Улама (в честь Станислава Улама ), проблема Какутани (в честь Сидзуо Какутани ), гипотеза Туэйтса (в честь Брайана Туэйтса ), алгоритм Хассе (в честь Хельмута Хассе ) или Сиракузская проблема (в честь Сиракузского университета ). ^[1]^[3]

Ссылки

^ Maddux, Cleborne D.; Johnson, D. Lamont (1997). Логотип: Ретроспектива . Нью-Йорк: Haworth Press. стр. 160. ISBN 0-7890-0374-0. Проблема также известна под несколькими другими названиями, включая: гипотеза Улама, проблема Хейлстоуна, проблема Сиракуз, проблема Какутани, алгоритм Хассе и проблема Коллатца.
^ abcdefg Lagarias, Jeffrey C. (1985). «Проблема 3 x + 1 и ее обобщения». The American Mathematical Monthly . 92 (1): 3–23. doi :10.1080/00029890.1985.11971528. JSTOR 2322189.
^ Согласно Лагариасу (1985), ^[2] стр. 4, название «Сиракузская проблема» было предложено Хассе в 1950-х годах во время визита в Сиракузский университет .
^ О'Коннор, Дж. Дж.; Робертсон, Э. Ф. (2006). «Лотар Коллатц». Школа математики и статистики Университета Сент-Эндрюс, Шотландия.
^ Пиковер, Клиффорд А. (2001). Чудеса чисел . Оксфорд: Oxford University Press. С. 116–118. ISBN 0-19-513342-0.
^ Хофштадтер, Дуглас Р. (1979). Гёдель, Эшер, Бах . Нью-Йорк: Basic Books. стр. 400–2. ISBN 0-465-02685-0.
^ Гай, Ричард К. (2004). ""E16: Проблема 3x+1"". Нерешенные проблемы теории чисел (3-е изд.). Springer-Verlag . С. 330–6. ISBN 0-387-20860-7. Збл 1058.11001.
^ ab Lagarias, Jeffrey C. , ред. (2010). The Ultimate Challenge: The 3 x + 1 Problem . Американское математическое общество . ISBN 978-0-8218-4940-8. Збл 1253.11003.
^ ab Tao, Terence (2022). «Почти все орбиты отображения Коллатца достигают почти ограниченных значений». Forum of Mathematics, Pi . 10 : e12. arXiv : 1909.03562 . doi : 10.1017/fmp.2022.8 . ISSN 2050-5086.
^ Ливенс, Гэри Т.; Вермейлен, Майк (декабрь 1992 г.). «3 x + 1 поисковые программы». Компьютеры и математика с приложениями . 24 (11): 79–99. doi :10.1016/0898-1221(92)90034-F.
^ Розендал, Эрик. «3x+1 запись задержки» . Проверено 14 марта 2020 г.(Примечание: «Записи о задержках» представляют собой записи общего времени остановок.)
^ Барина, Дэвид (2020). «Проверка сходимости проблемы Коллатца». Журнал суперкомпьютеров . 77 (3): 2681–2688. doi :10.1007/s11227-020-03368-x. S2CID 220294340.
^ ab Garner, Lynn E. (1981). «Об алгоритме Коллатца 3n + 1». Труды Американского математического общества . 82 (1): 19–22. doi : 10.1090/S0002-9939-1981-0603593-2 . JSTOR 2044308.
^ abc Элиаху, Шалом (1993). «Проблема 3x + 1: новые нижние границы нетривиальных длин циклов». Дискретная математика . 118 (1): 45–56. doi : 10.1016/0012-365X(93)90052-U .
^ abc Simons, J.; de Weger, B. (2005). "Теоретические и вычислительные границы для m-циклов проблемы 3n + 1" (PDF) . Acta Arithmetica . 117 (1): 51–70. Bibcode :2005AcAri.117...51S. doi : 10.4064/aa117-1-3 . Архивировано из оригинала 2022-03-18 . Получено 2023-03-28 .{{cite journal}}: CS1 maint: bot: original URL status unknown (link)
^ Лагариас (1985), ^[2] раздел «Эвристический аргумент».
^ ab Terras, Riho (1976). «Проблема времени остановки для положительных целых чисел» (PDF) . Acta Arithmetica . 30 (3): 241–252. doi : 10.4064/aa-30-3-241-252 . MR 0568274.
^ Хартнетт, Кевин (11 декабря 2019 г.). «Математик доказывает огромный результат в решении «опасной» проблемы». Журнал Quanta .
^ Красиков, Илья; Лагариас, Джеффри К. (2003). «Оценки задачи 3x + 1 с использованием разностных неравенств». Акта Арифметика . 109 (3): 237–258. arXiv : математика/0205002 . Бибкод : 2003AcAri.109..237K. дои : 10.4064/aa109-3-4. MR 1980260. S2CID 18467460.
^ ab Hercher, C. (2023). "Нет m-циклов Коллатца с m <= 91" (PDF) . Журнал целочисленных последовательностей . 26 (3): Статья 23.3.5.
^ Штайнер, РП (1977). «Теорема о сиракузской проблеме». Труды 7-й Манитобской конференции по численной математике . С. 553–9. MR 0535032.
^ Саймонс, Джон Л. (2005). «О несуществовании 2-циклов для проблемы 3x + 1». Math. Comp . 74 : 1565–72. Bibcode :2005MaCom..74.1565S. doi : 10.1090/s0025-5718-04-01728-4 . MR 2137019.
^ Колусси, Ливио (9 сентября 2011 г.). «Классы сходимости функции Коллатца». Теоретическая информатика . 412 (39): 5409–5419. doi : 10.1016/j.tcs.2011.05.056 .
↑ Хью, Патрик Чисан (7 марта 2016 г.). «Работа в двоичном коде защищает повторения 1/3h: комментарий к работе Колусси «Классы сходимости функции Коллатца». Теоретическая информатика . 618 : 135–141. doi : 10.1016/j.tcs.2015.12.033 .
^ Лагариас, Джеффри (1990). «Набор рациональных циклов для задачи 3x+1». Акта Арифметика . 56 (1): 33–53. дои : 10.4064/aa-56-1-33-53 . ISSN 0065-1036.
^ Белага, Эдвард Г.; Миньотт, Морис (1998). «Вложение гипотезы 3x+1 в контекст 3x+d». Экспериментальная математика . 7 (2): 145–151. doi :10.1080/10586458.1998.10504364. S2CID 17925995.
^ Бернштейн, Дэниел Дж.; Лагариас, Джеффри К. (1996). «Карта сопряженности 3x + 1». Канадский математический журнал . 48 (6): 1154–1169. дои : 10.4153/CJM-1996-060-x . ISSN 0008-414X.
^ Чемберленд, Марк (1996). «Непрерывное расширение проблемы 3 x + 1 на действительную прямую». Dynam. Contin. Discrete Impuls Systems . 2 (4): 495–509.
^ Летерман, Саймон; Шлейхер, Дирк; Вуд, Рег (1999). «Проблема (3 n + 1) и голоморфная динамика». Экспериментальная математика . 8 (3): 241–252. doi :10.1080/10586458.1999.10504402.
^ Сколло, Джузеппе (2007). «Поиск записей классов в задаче 3x + 1 с помощью инфраструктуры сетки COMETA» (PDF) . Дни открытых дверей сетки в Университете Палермо .
^ Лагариас (1985), ^[2] Теорема D.
^ Клей, Оливер Китинг. «Долгий поиск контрпримеров Коллатца». стр. 208. Получено 26 июля 2024 г.
^ Конвей, Джон Х. (1972). «Непредсказуемые итерации». Труды Конференции по теории чисел 1972 г., Университет Колорадо, Боулдер . С. 49–52.
^ Курц, Стюарт А.; Саймон, Янос (2007). «Неразрешимость обобщенной проблемы Коллатца». В Cai, J.-Y.; Cooper, SB; Zhu, H. (ред.). Труды 4-й Международной конференции по теории и применению моделей вычислений, TAMC 2007, состоявшейся в Шанхае, Китай , в мае 2007 г. стр. 542–553. doi :10.1007/978-3-540-72504-6_49. ISBN 978-3-540-72503-9.В формате PDF
^ Бен-Амрам, Амир М. (2015). «Смертность итерированных кусочно-аффинных функций над целыми числами: разрешимость и сложность». Вычислимость . 1 (1): 19–56. doi :10.3233/COM-150032.
^ Мишель, Паскаль (1993). «Соревнование занятых бобров и проблемы типа Коллатца». Архив для Mathematical Logic . 32 (5): 351–367. doi :10.1007/BF01409968.
^ "Твёрдость делового бобра BB(15)".

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

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