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

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

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

Гипотеза названа в честь Лотара Коллатца , который представил эту идею в 1937 году, через два года после получения докторской степени. ^[1] Известно также , как 3 п + 1 задачи , то 3 п + 1 гипотеза , то гипотеза Улама (после Станиславом Уламом ), проблема Какутани (после того, как Шизуо Какутани ), то гипотеза Туэйтс (после сэра Брайана Туэйтса ), Хассе алгоритм (по Гельмуту Хассе ), или проблема Сиракуз . ^{[2] [4]} Используемая последовательность чисел иногда называется последовательностью градин или числами градин (потому что значения обычно подвержены многократным спускам и подъемам, как град в облаке), ^{[5] [6]} или чудесными числами . ^[7]

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

Постановка проблемы [ править ]

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

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

В модульной арифметической нотации определите функцию f следующим образом:

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

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

В обозначениях:

${\displaystyle 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 ⁱ ( n ) ).

Гипотеза Коллатца такова: этот процесс в конечном итоге достигнет числа 1, независимо от того, какое положительное целое число выбрано изначально.

Это наименьшее я такое , что _я = 1 называется общее время остановки по п . ^[3] Гипотеза утверждает, что у каждого n есть строго определенное общее время остановки. Если для некоторого n такое i не существует, мы говорим, что n имеет бесконечное общее время остановки, и гипотеза неверна.

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

Примеры [ править ]

Например, начиная с n = 12 , получается последовательность 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 )

Количество шагов по п достичь 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 шага, ^[11]

менее 10 ¹¹ это75 128 138 247 , в котором 1228 ступеней,

менее 10 ¹² это989 345 275 647 , что имеет 1348 ступеней,

менее 10 ¹³ это7 887 663 552 367 , что имеет 1563 ступеньки,

менее 10 ¹⁴ это80 867 137 596 217 , что имеет 1662 ступеньки,

менее 10 ¹⁵ составляет942 488 749 153 153 , что имеет 1862 ступеньки,

менее 10 ¹⁶ есть7 579 309 213 675 935 , с 1958 ступенями,

менее 10 ¹⁷ составляет+93 +571 393 692 802 302 , который имеет 2091 шагов и

менее 10 ¹⁸ это931 386 509 544 713 451 , что составляет 2283 ступени. ^[12]

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

Степень двойки быстро сходится к единице, потому что 2 ⁿ уменьшается вдвое n раз до 1 и никогда не увеличивается.

Визуализации [ править ]

• Направленный график, показывающий орбиты первых 1000 чисел.

• Х ось представляет стартовый номер, то у ось представляет наибольшее число , достигнутое в ходе цепи до 1. Этот график показывает , ограниченный у оси: некоторые х значения дают промежуточные продукты так высоко , как2,7 × 10 ⁷ (для x = 9663 )

• Дерево всех чисел, имеющее менее 20 шагов (щелкните, чтобы увеличить) .

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

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

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

По состоянию на 2020 год ^[update]гипотеза проверена на компьютере для всех начальных значений до 2 ⁶⁸ ≈ 2,95 × 10 ²⁰ . ^[13] Все начальные значения, протестированные до сих пор, в конечном итоге заканчиваются повторяющимся циклом (4; 2; 1) , который состоит только из трех членов. Из этой нижней границы начального значения можно также получить нижнюю границу для количества членов, которые должен иметь повторяющийся цикл, кроме (4; 2; 1) . ^[14] Когда это соотношение было установлено в 1981 году, формула давала нижнюю границу35 400 терминов. ^[14]

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

Вероятностная эвристика [ править ]

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

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

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

Строгие границы [ править ]

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

Циклы [ править ]

В этой части рассмотрим "сокращенную" форму функции Коллатца.

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

Цикл представляет собой последовательность ( ₀ ; ₁ ; ...; _д ) из различных натуральных чисел , где Т ( ₀ ) = а ₁ , Т ( ₁ ) = а ₂ , ..., и T ( A _д ) = а ₀ .

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

Продолжительность цикла [ править ]

Известно, что длина нетривиального цикла не меньше 17 087 915 . ^[19] Фактически, Элиаху (1993) доказал, что период p любого нетривиального цикла имеет вид

${\displaystyle p=301994a+17087915b+85137581c}$

где a , b и c - неотрицательные целые числа, b ≥ 1 и ac = 0 . Этот результат основан на расширении непрерывной фракциипер 3/пер. 2.

Аналогичное рассуждение, которое объясняет недавнюю проверку гипотезы до 2 ^68, приводит к улучшенной нижней оценке114 208 327 604 (или186 265 759 595 без «ярлыка»). Эта нижняя оценка согласуется с приведенным выше результатом, поскольку .${\displaystyle 114208327604=17087915\times 361+85137581\times 1269}$

k -циклы [ править ]

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

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

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

В обратном [ править ]

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

${\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 (mod 2) тогда и только тогда, когда 3 n + 1 ≡ 4 (mod 6) . Эквивалентно,п - 1/3≡ 1 (mod 2) тогда и только тогда, когда n 4 (mod 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 нап '/H ( п ')где n ′ = 3 n + 1 и H ( n ′) - наибольшая степень двойки, которая делит n ′ (без остатка ). Результирующая функция f преобразует нечетные числа в нечетные. Теперь предположим, что для некоторого нечетного числа n применение этой операции k раз дает число 1 (то есть f ^k ( n ) = 1 ). Тогда в двоичном формате число n можно записать как конкатенацию строк w _k w _{k −1} … w _1, где каждый w _h является конечным и непрерывным извлечением из представления1/3 ^ч. ^[23] Представление п , следовательно , удерживает repetends из1/3 ^ч, где каждый повторяющийся фрагмент необязательно вращается, а затем реплицируется до конечного числа битов. Это происходит только в двоичном формате. ^[24] Предположительно, каждая двоичная строка s, которая заканчивается на «1», может быть достигнута с помощью представления этой формы (где мы можем добавлять или удалять ведущие «0» к  s ).

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

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

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

Пример [ править ]

Начальное число 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}}.}$

Это можно сделать, потому что, когда n нечетно, 3 n + 1 всегда четно.

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

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

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

Применение функции 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 повышений, и результат будет 2 × 3 ^k a - 1 . Коэффициент 3 при умножении a не зависит от значения a ; это зависит только от поведения b . Это позволяет предсказать, что определенные формы чисел всегда будут приводить к меньшему числу после определенного количества итераций, например, 4 a + 1 становится 3 a + 1.после двух приложений f и 16 a + 3 становится 9 a + 2 после 4 приложений 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}}}$

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

a → bc , b → a , c → aaa .

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

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

Расширения на более крупные домены [ править ]

Итерации по всем целым числам [ править ]

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

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

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

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

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

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

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

${\displaystyle {\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. Он многократно генерируется дробью

${\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 " функции Коллатца.

${\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-адическое расширение [ править ]

Функция

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

хорошо определенно на кольцо ℤ ₂ из 2-адических целых чисел , где она непрерывна и сохраняющее меру по отношению к 2-адической мере. Более того, его динамика, как известно, эргодична . ^[3]

Определим вектор- функцию четности Q, действующую на ℤ _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} .}$

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

Карту Коллатца можно рассматривать как ограничение на целые числа гладкой карты.

${\displaystyle f(z)={\frac {1}{2}}z\cos ^{2}\left({\frac {\pi }{2}}z\right)+(3z+1)\sin ^{2}\left({\frac {\pi }{2}}z\right).}$

Точка зрения итерации на действительной прямой была исследована Чемберлендом (1996), ^[28] . Он показал, что гипотеза не верна для действительных чисел, поскольку существует бесконечно много неподвижных точек, а также орбит, монотонно уходящих в бесконечность. Он также показал, что существует по крайней мере еще один цикл притяжения: 1,1925 → 2,1386.

На комплексной плоскости это было исследовано Летерманом, Шлейхером и Вудом (1999). ^[29] Большинство точек плоскости расходятся до бесконечности, как показано синим цветом на рисунке ниже. Граница между расходящимися и нерасходящимися областями представляет собой фрактальный узор, называемый «фракталом Коллатца».

Оптимизация [ править ]

Компромисс времени и пространства [ править ]

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

f ^k (2 ^k a + b ) = 3 ^{c ( b )} a + d ( b ) .

С (или лучше 3 ^с ) и д массивы предварительно вычислены для всех возможного K чисел -разр б , где д ( б ) является результатом применения F функции K раза , чтобы Ь и с ( б ) это число нечетного числа встречающиеся на пути. ^[30] Например, если k = 5 , на каждой итерации можно перейти на 5 шагов вперед, выделив 5 младших битов числа и используя:

c (0 ... 31) = {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) = {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 Предвычислений и хранения , чтобы ускорить полученный расчет на коэффициенте K , в пространственно-временном компромиссе .

Модульные ограничения [ править ]

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

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

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

Функция Сиракузы [ править ]

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

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

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

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

Неразрешимые обобщения [ править ]

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

В частности, он рассматривал функции вида

${\displaystyle {g(n)=a_{i}n+b_{i}}\;\;,{\text{where}}\;{n\equiv i{\pmod {P}}}}$

и a ₀ , b ₀ , ..., a _{P - 1} , b _{P - 1} - рациональные числа, которые выбраны так, чтобы g ( n ) всегда было целым числом.

Стандартная функция Коллатца задается формулой P = 2 , a ₀ =1/2, b ₀ = 0 , a ₁ = 3 , b ₁ = 1 . Конвей доказал, что проблема:

Достигает ли последовательность повторений g ^k ( n ) 1 при заданных g и n ?

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

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

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

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

В популярной культуре [ править ]

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

См. Также [ править ]

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

Дальнейшее чтение [ править ]

• Окончательный вызов: задача 3 x + 1 :

Этот том ^[37] отредактированный Джеффри Лагариасом и опубликованный Американским математическим обществом , представляет собой сборник информации о гипотезе Коллатца, методах ее приближения и обобщениях. Он включает в себя две обзорные статьи редактора и пять других авторов, касающиеся истории проблемы, обобщений, статистических подходов и результатов теории вычислений . Он также включает оттиски ранних работ по этой теме (включая запись Лотара Коллатца).

Ссылки [ править ]

Внешние ссылки [ править ]

•  Страница Кита Мэтьюза 3 x + 1: Обзор прогресса плюс различные программы .
• Проект распределенных вычислений ( BOINC ), который проверяет гипотезу Коллатца для больших значений.
• Текущий проект распределенных вычислений Эрика Розендаала проверяет гипотезу Коллатца для все больших и больших значений.
• Другой продолжающийся проект распределенных вычислений Томаса Оливейры и Силвы продолжает проверять гипотезу Коллатца (с меньшим количеством статистических данных, чем на странице Эрика Розендаала, но с дальнейшим прогрессом).
• Вайсштейн, Эрик В. "Проблема Коллатца" . MathWorld .
• Задача Коллатца в PlanetMath ..
• Ночелла, Джесси. «Пути Коллатца» . Демонстрационный проект Вольфрама .
• Математики так близки к разгадке этой загадки 82-летней давности