Гипотеза Коллатца - Collatz conjecture

Нерешенная проблема в математике: Достигает ли последовательность Коллатца 1 для всех положительных целых начальных значений? (больше нерешенных задач по математике)

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

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

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

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

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

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

Гистограмма общего времени остановки для чисел от 1 до 10⁸. Общее время остановки указано на Икс ось, частота на у ось.

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

Время остановки: график 250, 1000, 4000, 20000, 100000, 500000

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

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

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

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

(то есть: а_я это ценность ж применительно к п рекурсивно я раз; а_я = ж^я(п)).

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

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

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

Примеры

Например, начиная с п = 12, получается последовательность 12, 6, 3, 10, 5, 16, 8, 4, 2, 1.

п = 19, например, для достижения 1:19, 58, 29, 88, 44, 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1.

Последовательность для п = 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⁵ является 77031, имеющий 350 ступеней,

менее 10⁶ является 837799, имеющий 524 ступени,

менее 10⁷ является 8400511, который имеет 685 ступеней,

менее 10⁸ является 63728127, который имеет 949 шагов,

менее 10⁹ является 670617279, который имеет 986 шагов,

менее 10¹⁰ является 9780657630, который имеет 1132 ступени,^[11]

менее 10¹¹ является 75128138247, в котором 1228 ступеней,

менее 10¹² является 989345275647, который имеет 1348 ступеней,

менее 10¹³ является 7887663552367, который имеет 1563 ступени,

менее 10¹⁴ является 80867137596217, имеющий 1662 ступени,

менее 10¹⁵ является 942488749153153, имеющий 1862 ступеньки,

менее 10¹⁶ является 7579309213675935, имеющий 1958 ступеней, и

менее 10¹⁷ является 93571393692802302, который имеет 2091 шаг.^[12]

Эти числа являются самыми низкими с указанным количеством шагов, но не обязательно единственными ниже заданного предела. В качестве примера, 9780657631 имеет 1132 шага, как и 9780657630.

В силы двух сходятся к одному быстро, потому что 2^п делится вдвое п раз до 1 и никогда не увеличивается.

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

• 

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

• 

  В Икс ось представляет начальный номер, у ось представляет наибольшее число, достигнутое в течение цепочки до 1. Этот график показывает ограниченное у ось: некоторые Икс ценности производят промежуточные звенья до 2.7×10⁷ (за Икс = 9663)

• 

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

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

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

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

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

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

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

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

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

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

Строгие границы

В компьютерное доказательство, Красиков и Лагариас показали, что количество целых чисел в интервале [1,Икс] который в конечном итоге достигнет 1, по крайней мере, равно Икс^0.84 для всех достаточно больших Икс.^[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}}}$

А цикл это последовательность (а₀; а₁; ...; а_q) различных положительных целых чисел, где Т(а₀) = а₁, Т(а₁) = а₂, ..., и Т(а_q) = а₀.

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

Продолжительность цикла

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

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

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

Аналогичное рассуждение, которое объясняет недавнюю проверку гипотезы вплоть до 2⁶⁸ приводит к улучшенной нижней оценке 114208327604 (или же 186265759595 без «ярлыка»). Эта нижняя оценка согласуется с приведенным выше результатом, поскольку ${\displaystyle 114208327604=17087915\times 361+85137581\times 1269}$.

k-циклы

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

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

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

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

Первый 21 уровень Collatz график генерируется снизу вверх. График включает все числа с длиной орбиты 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 ведет назад ко всем положительным целым числам. Для любого целого числа п, п ≡ 1 (мод 2) если и только если 3п + 1 ≡ 4 (мод. 6). Эквивалентно п − 1/3 ≡ 1 (мод 2) если и только если п ≡ 4 (мод 6). Предположительно это обратное соотношение образует дерево за исключением цикла 1–2–4 (инверсия цикла 4–2–1 неизмененной функции ж определено в Постановка задачи раздел этой статьи).

Когда отношение 3п + 1 функции ж заменяется обычным замещающим отношением "ярлык" 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}}.}$

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

В качестве альтернативы замените 3п + 1 с п′/ЧАС(п′) куда п′ = 3п + 1 и ЧАС(п′) самый высокий степень 2 что разделяет п′ (без остаток ). Результирующая функция ж карты из нечетные числа к нечетным числам. Теперь предположим, что для некоторого нечетного числа п, применяя эту операцию k раз дает число 1 (то есть ж^k(п) = 1). Затем в двоичный, номер п можно записать как конкатенацию струны ш_k ш_k−1 … ш₁ где каждый ш_час конечный и непрерывный отрывок из представления 1/3^час.^[23] Представление п поэтому держит повторяет из 1/3^час, где каждый повтор может быть повернут, а затем реплицирован до конечного числа битов. Это происходит только в двоичном формате.^[24] Предположительно каждая двоичная строка s который заканчивается на "1", может быть достигнуто представлением этой формы (где мы можем добавлять или удалять ведущие "0" кs).

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

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

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

Пример

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

           111          1111         10110        10111       100010      100011      110100     11011    101000   1011  10000

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

В этом разделе рассмотрим функцию Коллатца в слегка измененной форме

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

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

Если П(…) четность числа, то есть P (2п) = 0 и P (2п + 1) = 1, то мы можем определить последовательность четности Коллатца (или вектор четности) для числа п в качестве п_я = P (а_я), куда а₀ = п, и а_я+1 = ж(а_я).

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

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

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

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

Для функции Коллатца в виде

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

Последовательности града могут быть вычислены чрезвычайно простым 2-х теговая система с правилами производства

а → до н.э, б → а, c → ааа.

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

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

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

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

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

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

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

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

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

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

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

Если цикл четности имеет длину п и включает в себя ровно нечетные числа м раз по индексам k₀ < … < k_м−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п + 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 действующий на ℤ₂ в качестве

${\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-2-1-2-1-др. в реальном расширении карты Коллатца (оптимизировано заменой "3п + 1" с "3п + 1/2")

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

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

Если стандартная карта Коллатца, определенная выше, оптимизирована путем замены отношения 3п + 1 с общим замещающим отношением "ярлык" 3п + 1/2, его можно рассматривать как ограничение на целые числа гладкого действительного и комплексного отображения

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

Карта Коллатца фрактал в районе реальной линии

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

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

Оптимизация

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

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

ж^k(2^kа + б) = 3^c(б)а + d(б).

В c (или лучше 3^c) и d массивы предварительно рассчитываются для всех возможных k-битовые числа б, куда d(б) является результатом применения ж функция k раз, чтобы б, и c(б) - количество нечетных чисел, встречающихся на пути.^[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, а компромисс между пространством и временем.

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

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

ж^k(2^kа + б) = 3^c(б)а + d(б) < 2^kа + б

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

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

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

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

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

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

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

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

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

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

и а₀, б₀,...,а_{п − 1}, б_{п − 1} - рациональные числа, выбранные таким образом, что грамм(п) всегда целое число.

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

Данный грамм и п, последовательность итераций грамм^k(п) достичь 1?

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

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

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

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

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

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

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

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

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

дальнейшее чтение

• Окончательный вызов: 3Икс + 1 проблема:

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

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

1. О'Коннор, Дж. Дж .; Робертсон, Э. Ф. (2006). "Лотар Коллатц". Школа математики и статистики Университета Сент-Эндрюс, Шотландия.
2. Maddux, Cleborne D .; Джонсон, Д. Ламонт (1997). Логотип: ретроспектива. Нью-Йорк: Haworth Press. п. 160. ISBN  0-7890-0374-0. Проблема также известна под несколькими другими названиями, в том числе: гипотеза Улама, проблема Хейлстоуна, проблема Сиракуз, проблема Какутани, алгоритм Хассе и проблема Коллатца.
3. Лагариас, Джеффри К. (1985). "3Икс + 1 проблема и ее обобщения ». Американский математический ежемесячник. 92 (1): 3–23. Дои:10.1080/00029890.1985.11971528. JSTOR  2322189.
4. Согласно Лагариасу (1985),^[3] п. 4, название «Сиракузская проблема» было предложено Хассе в 1950-х годах во время посещения Сиракузский университет.
5. Пиковер, Клиффорд А. (2001). Чудеса чисел. Оксфорд: Издательство Оксфордского университета. стр.116 –118. ISBN  0-19-513342-0.
6. «Число града». MathWorld. Wolfram Research.
7. Хофштадтер, Дуглас Р. (1979). Гедель, Эшер, Бах. Нью-Йорк: Основные книги. стр.400–2. ISBN  0-465-02685-0.
8. Гай, Ричард К. (2004). ""E17: Последовательности перестановок"". Нерешенные проблемы теории чисел (3-е изд.). Springer-Verlag. С. 336–7. ISBN  0-387-20860-7. Zbl  1058.11001.
9. Гай, Р. К. (1983). «Не пытайтесь решить эти проблемы». Амер. Математика. Ежемесячно. 90 (1): 35–41. Дои:10.2307/2975688. JSTOR  2975688. Эрдос означает, что нет мощных инструментов для управления такими объектами.
10. Лагариас, Джеффри С., изд. (2010). Конечная проблема: 3Икс + 1 проблема. Провиденс, Р.И .: Американское математическое общество. п. 4. ISBN  978-0821849408.
11. Ливенс, Гэри Т .; Вермёлен, Майк (декабрь 1992 г.). «3Икс + 1 Поисковые программы ». Компьютеры и математика с приложениями. 24 (11): 79–99. Дои:10.1016 / 0898-1221 (92) 90034-Ф.
12. Розендал, Эрик. "3x + 1 записи задержки". Получено 14 марта 2020. (Примечание: «Записи о задержках» - это записи об общем времени остановки.)
13. Барина, Давид (2020). «Проверка сходимости проблемы Коллатца». Журнал суперкомпьютеров. Дои:10.1007 / s11227-020-03368-х. S2CID  220294340.
14. Гарнер, Линн Э. "Об алгоритме Коллатца 3n + 1" (PDF). Получено 27 марта 2015.
15. Лагариас (1985),^[3] раздел "Эвристический аргумент ».
16. Тао, Теренс (10 сентября 2019 г.). «Почти все орбиты Коллатца достигают почти ограниченных значений». Какие новости. Получено 11 сентября 2019.
17. Хартнетт, Кевин. «Математик доказал огромный результат над« опасной »проблемой». Журнал Quanta. Получено 26 декабря 2019.
18. Красиков Илья; Лагариас, Джеффри С. (2003). "Граница для 3Икс + 1 задача с использованием разностных неравенств ». Acta Arithmetica. 109 (3): 237–258. arXiv:математика / 0205002. Bibcode:2003AcAri.109..237K. Дои:10.4064 / aa109-3-4. МИСТЕР  1980260. S2CID  18467460.
19. Элиаху, Шалом (1993-08-01). "3Икс + 1 проблема: новые нижние оценки нетривиальных длин циклов ». Дискретная математика. 118 (1): 45–56. Дои:10.1016 / 0012-365X (93) 90052-U.
20. Simons, J .; де Вегер, Б. (2003). «Теоретические и расчетные оценки для м-циклы 3п + 1 проблема " (PDF). Acta Arithmetica. 117 (1): 51–70. Bibcode:2005AcAri.117 ... 51S. Дои:10.4064 / aa117-1-3.
21. Штайнер, Р. П. (1977). «Теорема о проблеме Сиракуз». Труды 7-й конференции Манитобы по вычислительной математике. С. 553–9. МИСТЕР  0535032.
22. Саймонс, Джон Л. (2005). «Об отсутствии 2-циклов для 3-хИкс + 1 проблема ". Математика. Comp. 74: 1565–72. Bibcode: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. Террас, Рихо (1976). «Проблема остановки времени на положительных целых числах» (PDF). Acta Arithmetica. 30 (3): 241–252. Дои:10.4064 / aa-30-3-241-252. МИСТЕР  0568274.
26. Лагариас, Джеффри (1990). «Набор рациональных циклов для задачи 3x + 1». Acta Arithmetica. 56 (1): 33–53. Дои:10.4064 / aa-56-1-33-53. ISSN  0065-1036.
27. Lagarias, Jeffrey C .; Бернштейн, Дэниел Дж. (1996). "3Икс + 1 карта сопряженности ». Канадский математический журнал. 48 (6): 1154–1169. Дои:10.4153 / CJM-1996-060-x. ISSN  0008-414X.
28. Чемберленд, Марк (1996). "Непрерывное продолжение трехИкс +1 проблема к реальной линии ». Dynam. Продолжить. Дискретные импульсные системы. 2 (4): 495–509.
29. Летерман, Саймон; Шлейхер, Дирк; Вуд, Рег (1999). "(3п + 1) -Проблема и голоморфная динамика ». Экспериментальная математика. 8 (3): 241–252. Дои:10.1080/10586458.1999.10504402.
30. Сколло, Джузеппе (2007). "Ищу рекорды в 3Икс + 1 Проблема с помощью сетевой инфраструктуры COMETA » (PDF). Дни открытых дверей в Университете Палермо.
31. Лагариас (1985),^[3] Теорема D.
32. Конвей, Джон Х. (1972). «Непредсказуемые итерации». Proc. 1972 г. конф. Теории чисел, Univ. Колорадо, Боулдер. С. 49–52.
33. Курц, Стюарт А .; Саймон, Янош (2007). «Неразрешимость обобщенной проблемы Коллатца». In Cai, J.-Y .; Купер, С.Б .; Чжу, Х. (ред.). Материалы 4-й Международной конференции по теории и приложениям моделей вычислений, TAMC 2007, проходившей в Шанхае, Китай, в мае 2007 г.. С. 542–553. Дои:10.1007/978-3-540-72504-6_49. ISBN  978-3-540-72503-9. В качестве PDF
34. Бен-Амрам, Амир М. (2015). «Смертность повторных кусочно аффинных функций над целыми числами: разрешимость и сложность». Вычислимость. 1 (1): 19–56. Дои:10.3233 / COM-150032.
35. Эммер, Мишель (2012). Представьте себе математику: между культурой и математикой. Издательство Springer. С. 260–264. ISBN  978-8-847-02426-7.
36. Мазманян, Адам (19 мая 2011 г.). "ОБЗОР ФИЛЬМА: 'Incendies'". Вашингтон Таймс. Получено 7 декабря 2019.
37. Лагариас, Джеффри С., изд. (2010). Окончательный вызов: 3Икс + 1 проблема. Американское математическое общество. ISBN  978-0-8218-4940-8. Zbl  1253.11003.

внешняя ссылка

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