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

Открытая задача о функциях 3x+1 и x/2.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

В обозначениях модульной арифметики определите функцию f следующим образом: $${\displaystyle 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 = fi ⁽ n ) ). $${\displaystyle a_{i}={\begin{cases}n&{\text{for }}i=0,\\f(a_{i-1})&{\text{for }}i>0\end{cases}}}$$ 

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

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

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

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

Поскольку 3 n + 1 четно, когда n нечетно, вместо этого можно использовать «сокращенную» форму функции Коллатца: это определение дает меньшие значения времени остановки и общего времени остановки без изменения общей динамики процесса. $${\displaystyle 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, 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, 319 , 958, 479 , 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]

меньше 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), представляют собой степени двойки , поскольку 2 ⁿ уменьшается вдвое n раз, чтобы достичь 1, и никогда не увеличивается.

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

• 
  Ориентированный граф, показывающий орбиты первых 1000 чисел.
• 
  Ось x представляет начальный номер, ось y представляет наибольшее число, достигнутое в ходе цепочки до 1. Этот график показывает ограниченную ось y : некоторые значения x дают промежуточные продукты такого высокого уровня, как2,7 × 10 ⁷ (для x = 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 ₀ , a ₁ , ..., a _q ) различных положительных целых чисел, где f ( a 0 ₎ = a ₁ , f ( a ₁ ) знак равно а ₂ , ... и ж ( а _q ) знак равно а ₀ . $${\displaystyle 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, то эта граница увеличится до ${\displaystyle 3\times 2^{69}}$217 976 794 617 (355 504 839 929 без сокращенного номера). ^{[20] [14]} Фактически, Элиаху (1993) доказал, что период p любого нетривиального цикла имеет форму , где a , b и c - неотрицательные целые числа, b ≥ 1 и ac = 0 . Этот результат основан на разложении ⁠ в непрерывную дробь . $${\displaystyle p=301994a+17087915b+85137581c}$$пер. 3/пер. 2⁠ . ^[14]

к-циклы

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

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

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

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

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

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

Когда отношение 3 n + 1 функции f заменяется обычным замещающим «сокращённым» отношением ⁠3 н + 1/2⁠ граф Коллатца определяется обратным соотношением: $${\displaystyle 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 (mod 2) тогда и только тогда, когда ⁠3 н + 1/2⁠ ≡ 2 (мод. 3) . Эквивалентно, ⁠2 п - 1/3⁠ ≡ 1 (mod 2) тогда и только тогда, когда n ≡ 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 ₁ , где каждый w _h представляет собой конечный и непрерывный фрагмент из представления ⁠1/3 ^часа⁠ . ^{[23] Таким образом} , представление n содержит повторы ⁠1/3 ^часа⁠ , где каждое повторение при необходимости вращается, а затем реплицируется до конечного числа битов. Это происходит только в двоичном формате. ^[24] Предположительно, каждая двоичная строка s , оканчивающаяся на «1», может быть получена с помощью представления этой формы (где мы можем добавлять или удалять ведущие «0» к  s ).

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

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

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

Пример

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

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

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

В этом разделе рассмотрим сокращенную форму функции Коллатца. $${\displaystyle 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 н + 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 — сколько увеличений произошло во время эта последовательность. Например, для 2 ⁵ a + 1 имеется 3 увеличения по мере того, как 1 повторяется до 2, 1, 2, 1 и, наконец, до 2, поэтому результат равен 3 ³ a + 2 ; для 2 ² 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 .

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

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

${\displaystyle 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 , б → а , c → ааа .

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

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

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

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

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

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

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

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

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

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

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

Например, цикл четности (1 0 1 1 0 0 1) имеет длину 7 и четыре нечетных члена с индексами 0, 2, 3 и 6. Он повторно генерируется дробью, поскольку последняя приводит к рациональному циклу. $${\displaystyle {\frac {3^{3}2^{0}+3^{2}2^{2}+3^{1}2^{3}+3^{0}2^{6}}{2^{7}-3^{4}}}={\frac {151}{47}}}$$ $${\displaystyle {\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) производится дробью $${\displaystyle {\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] функции Коллатца. $${\displaystyle 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] $${\displaystyle 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}}}$$ ${\displaystyle \mathbb {Z} _{2}}$

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

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

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

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

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

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

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

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

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

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

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

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

${\displaystyle {\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}}}$

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

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

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

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

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

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

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

Оптимизации

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

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

ж ^k (2 ^k а + б ) знак равно 3 ^{c ( б , k )} а + d ( б , k ) .

Значения c (или лучше 3 ^c ) и d могут быть предварительно вычислены для всех возможных k -битных чисел b , где d ( b , k ) является результатом применения функции f k раз к b , а c ( b , k ) — количество нечетных чисел, встретившихся на пути. ^[30] Например, если 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 }.

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

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

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

ж ^k (2 ^k а + б ) знак равно 3 ^{c ( б )} а + d ( б ) < 2 ^k а + б

выполняется для всех a , то первый контрпример, если он существует, не может быть b по модулю 2 ^k . ^[13] Например, первый контрпример должен быть нечетным, потому что f (2 n ) = n , меньше 2 n ; и это должно быть 3 по модулю 4, потому что f ² (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 ≥ 1 . Функция Сиракуз — это функция f из множества I положительных нечетных целых чисел в себя, для которой f ( k ) = k ’ (последовательность A075677 в OEIS ).

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

• Математический портал

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

Примечания

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

Рекомендации

1. Мэддукс, Клеборн Д.; Джонсон, Д. Ламонт (1997). Логотип: Ретроспектива . Нью-Йорк: Хаворт Пресс. п. 160. ИСБН 0-7890-0374-0. Эта проблема также известна под несколькими другими названиями, в том числе: гипотеза Улама, проблема Хейлстоуна, проблема Сиракуз, проблема Какутани, алгоритм Хассе и проблема Коллатца.
2. Лагариас, Джеффри К. (1985). «Задача 3 х + 1 и ее обобщения». Американский математический ежемесячник . 92 (1): 3–23. дои : 10.1080/00029890.1985.11971528. JSTOR  2322189.
3. Согласно Лагариасу (1985), ^[2] с. 4, название «Сиракузская проблема» было предложено Хассе в 1950-х годах во время визита в Сиракузский университет .
4. О'Коннор, Джей-Джей; Робертсон, Э.Ф. (2006). «Лотар Коллатц». Школа математики и статистики Университета Сент-Эндрюс, Шотландия.
5. Пиковер, Клиффорд А. (2001). Чудеса чисел . Оксфорд: Издательство Оксфордского университета. стр. 116–118. ISBN 0-19-513342-0.
6. Хофштадтер, Дуглас Р. (1979). Гёдель, Эшер, Бах . Нью-Йорк: Основные книги. стр. 400–2. ISBN 0-465-02685-0.
7. Гай, Ричард К. (2004). «»E16: Проблема 3x+1»». Нерешенные проблемы теории чисел (3-е изд.). Спрингер-Верлаг . стр. 330–6. ISBN 0-387-20860-7. Збл  1058.11001.
8. Лагариас, Джеффри С. , изд. (2010). Самая сложная задача: задача 3 x + 1 . Американское математическое общество . ISBN 978-0-8218-4940-8. Збл  1253.11003.
9. Тао, Теренс (2022). «Почти все орбиты карты Коллатца достигают почти ограниченных значений». Форум математики, Пи . 10 : е12. arXiv : 1909.03562 . дои : 10.1017/fmp.2022.8 . ISSN  2050-5086.
10. Ливенс, Гэри Т.; Вермюлен, Майк (декабрь 1992 г.). «3 х + 1 программа поиска». Компьютеры и математика с приложениями . 24 (11): 79–99. дои : 10.1016/0898-1221(92)90034-F.
11. Розендал, Эрик. «3x+1 запись задержки» . Проверено 14 марта 2020 г.(Примечание: «Записи задержки» — это записи общего времени остановки.)
12. Барина, Дэвид (2020). «Проверка сходимости задачи Коллатца». Журнал суперкомпьютеров . 77 (3): 2681–2688. дои : 10.1007/s11227-020-03368-x. S2CID  220294340.
13. Гарнер, Линн Э. (1981). «Об алгоритме Коллатца 3n + 1». Труды Американского математического общества . 82 (1): 19–22. дои : 10.1090/S0002-9939-1981-0603593-2 . JSTOR  2044308.
14. Элиаху, Шалом (1993). «Проблема 3x + 1: новые нижние оценки нетривиальных длин циклов». Дискретная математика . 118 (1): 45–56. дои : 10.1016/0012-365X(93)90052-U .
15. Саймонс, Дж.; де Вегер, Б. (2005). «Теоретические и вычислительные оценки m-циклов задачи 3n + 1» (PDF) . Акта Арифметика . 117 (1): 51–70. Бибкод : 2005AcAri.117...51S. дои : 10.4064/aa117-1-3 . Архивировано из оригинала 18 марта 2022 г. Проверено 28 марта 2023 г.{{cite journal}}: CS1 maint: bot: original URL status unknown (link)
16. Лагариас (1985), ^[2] раздел «Эвристический аргумент».
17. Террас, Рихо (1976). «Проблема времени остановки для положительных целых чисел» (PDF) . Акта Арифметика . 30 (3): 241–252. дои : 10.4064/aa-30-3-241-252 . МР  0568274.
18. Хартнетт, Кевин (11 декабря 2019 г.). «Математик доказал огромный результат в« опасной »задаче» . Журнал Кванта .
19. Красиков, Илья; Лагариас, Джеффри К. (2003). «Оценки задачи 3x + 1 с использованием разностных неравенств». Акта Арифметика . 109 (3): 237–258. arXiv : math/0205002 . Бибкод : 2003AcAri.109..237K. дои : 10.4064/aa109-3-4. MR  1980260. S2CID  18467460.
20. Герчер, К. (2023). «Не существует m-циклов Коллатца с m <= 91» (PDF) . Журнал целочисленных последовательностей . 26 (3): Статья 23.3.5.
21. Штайнер, Р.П. (1977). «Теорема о сиракузской проблеме». Материалы 7-й Манитобской конференции по числовой математике . стр. 553–9. МР  0535032.
22. Саймонс, Джон Л. (2005). «Об отсутствии 2-циклов в задаче 3х + 1». Математика. Комп . 74 : 1565–72. Бибкод : 2005MaCom..74.1565S. дои : 10.1090/s0025-5718-04-01728-4 . МР  2137019.
23. Колусси, Ливио (9 сентября 2011 г.). «Классы сходимости функции Коллатца». Теоретическая информатика . 412 (39): 5409–5419. дои : 10.1016/j.tcs.2011.05.056 .
24. Хью, Патрик Чисан (7 марта 2016 г.). «Работа в двоичном формате защищает повторения 1/3 часа: комментарий Колюсси «Классы сходимости функции Коллатца»». Теоретическая информатика . 618 : 135–141. дои : 10.1016/j.tcs.2015.12.033 .
25. Лагариас, Джеффри (1990). «Набор рациональных циклов для задачи 3x+1». Акта Арифметика . 56 (1): 33–53. дои : 10.4064/aa-56-1-33-53 . ISSN  0065-1036.
26. Белага, Эдвард Г.; Миньотт, Морис (1998). «Внедрение гипотезы 3x+1 в контекст 3x+d». Экспериментальная математика . 7 (2): 145–151. дои : 10.1080/10586458.1998.10504364. S2CID  17925995.
27. Бернштейн, Дэниел Дж.; Лагариас, Джеффри К. (1996). «Карта сопряженности 3x + 1». Канадский математический журнал . 48 (6): 1154–1169. дои : 10.4153/CJM-1996-060-x . ISSN  0008-414X.
28. Чемберленд, Марк (1996). «Непрерывное расширение задачи 3 x  + 1 на действительную линию». Динам. Продолжение. Дискретные импульсные системы . 2 (4): 495–509.
29. Летерман, Саймон; Шлейхер, Дирк; Вуд, Рег (1999). «(3 n  + 1)-задача и голоморфная динамика». Экспериментальная математика . 8 (3): 241–252. дои : 10.1080/10586458.1999.10504402.
30. Сколло, Джузеппе (2007). «Поиск записей классов в задаче 3x+1 с помощью грид-инфраструктуры COMETA» (PDF) . Дни открытых дверей Grid в Университете Палермо .
31. Лагариас (1985), ^[2] Теорема D.
32. Клей, Оливер Китинг. «Долгий поиск контрпримеров Коллатца». стр. 208–208 . Проверено 26 июля 2024 г.
33. Конвей, Джон Х. (1972). «Непредсказуемые итерации». Учеб. 1972 Конференция по теории чисел, Univ. Колорадо, Боулдер . стр. 49–52.
34. Курц, Стюарт А.; Саймон, Янош (2007). «Неразрешимость обобщенной проблемы Коллатца». В Кай, Ж.-Ю.; Купер, С.Б.; Чжу, Х. (ред.). Материалы 4-й Международной конференции по теории и приложениям моделей вычислений, TAMC 2007, состоявшейся в Шанхае, Китай, в мае 2007 года . стр. 542–553. дои : 10.1007/978-3-540-72504-6_49. ISBN 978-3-540-72503-9.В формате PDF
35. Бен-Амрам, Амир М. (2015). «Смертность итерированных кусочно-аффинных функций над целыми числами: разрешимость и сложность». Вычислимость . 1 (1): 19–56. дои : 10.3233/COM-150032.
36. Мишель, Паскаль (1993). «Оживленная конкуренция бобров и проблемы, подобные Коллатцу». Архив математической логики . 32 (5): 351–367.
37. «Твердость занятого бобра, значение BB (15)» .
38. Эммер, Мишель (2012). Представьте себе математику: между культурой и математикой . Издательство Спрингер . стр. 260–264. ISBN 978-8-847-02426-7.
39. Мазманян, Адам (19 мая 2011 г.). «ОБЗОР ФИЛЬМА: 'Пожары'». Вашингтон Таймс . Проверено 7 декабря 2019 г.

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

• Мэтьюз, Кейт. «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.
• Готовы ли компьютеры решить эту заведомо громоздкую математическую задачу?