Нерешенная математическая задача :. Достигает ли в конечной последовательности Коллатца 1 для всех положительных целых начальных значений? (больше нерешенных задач в математике) |
Гипотеза Коллатца - это гипотеза в математике, которая касается определите следующим образом: начинать с любого положительного целого числа n. Затем член каждый получается из предыдущего члена следующим образом: если предыдущий член равенство , даже, следующий член равенства члена предыдущего члена. Если предыдущий член нечетный, следующий член в 3 раза больше предыдущего члена плюс 1. Гипотеза состоит в том, независимо от того, какое значение n, последовательность всегда будет достигать 1.
Гипотеза названа в честь Коллатц, который представил эту идею в 1937 году, через два года после получения докторской степени. Она также известна как 3n + 1 проблема, 3n + 1 гипотеза, гипотеза Улама (после Станислав Улам ), проблема Какутани (после Шизуо Какутани ), гипотеза Туэйтса (по сэру Брайану Туэйтсу), алгоритм Хассе (по Гельмуту Хассе ) или проблема Сиракуз . Используемая последовательность чисел иногда называется последовательностью град или числами град (потому что значения обычно подвержены множественным спускам и подъемам, например, град в облаке), или как чудесные числа .
Пол Эрдёш сказал о гипотезе Коллатца: «Математика может быть не готова к таким задачам». Он также использует 500 долларов за ее решение. Джеффри Лагариас заявлено в 2010 году, что гипотеза Коллатца «является чрезвычайно сложной проблемой, совершенно недоступной для современной математики».
Рассмотрим следующее действие с произвольным положительным целым числом :
В нотации модульной арифметики определите функцию f следующим образом:
Теперь сформируйте последовательность, выполнив эту операцию несколько раз, начиная с любого положительного целого, и взяв результат на каждый шаг в качестве входных данных в следующем.
В обозначении:
(то есть есть: a i - значение f, примененное к n рекурсивно i раз; a i = f (n)).
Гипотеза Коллатца: этот процесс в конечном итоге достигнет число 1, независимо от того, какое положительное целое число выбрано изначально.
Это наименьшее i такое, что i = 1, называется общим временем остановки число N. Гипотеза утверждает, что каждый 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.
Числа с общим временем остановки больше, чем у любого меньшего начального значения, образуют последовательность, начинающуюся с:
Начальные значения, максимальная точка траектории которых больше t любое меньшее начальное значение имеет следующий вид:
Число шагов для n, чтобы достичь 1:
Самая длинная последовательность для любого начального начального числа
Это самые низкие числа с указанным выполнением шагов, но не обязательно единственные, которые ниже заданного предела. Например, 9780657631 имеет 1132 шага, как и 9780657630.
степени двух быстро сходятся к единице, потому что 2 уменьшается вдвое в n раз до 1 и никогда не увеличивается.
Направленный график, показывающий орбиты первых 1000 чисел.
Ось x представляет собой начальное число, ось y представляет собой наибольшее число, достигнутое в течение цепочки до 1. На этом графике ограниченная ось y: некоторые значения x производят промежуточные продукты размером до 2,7 × 10 (для x = 9663)
Дерево всех чисел, имеющее менее 20 шагов (щелкните, чтобы увеличить).
Хотя гипотеза не была доказана большинством математиков, изучивших проблему, думают, что она верна, поскольку ее подтверждают экспериментальные данные и эвристические аргументы.
По состоянию на 2020 год гипотеза была проверена компьютером для всех начальных значений до 2 ≈ 2,95 × 10. Все начальные значения, протестированные до сих пор, в конечном итоге заканчиваются повторяющимся циклом (4; 2; 1), который состоит только из трех членов. Из этой нижней границы начального значения можно также получить нижнюю границу для количества, должен иметь повторяющийся цикл, кроме (4; 2; 1). Когда эта взаимосвязь была установлена в 1981 году, формула дала нижнюю границу в 35400 членов.
Это компьютерное свидетельство не является доказательством того, что гипотеза верна. Как показано в случаях гипотезы Полиа, гипотезы Мертенса и числа Скьюза, иногда встречаются только контрпримеры гипотезы при использовании очень больших.
Если рассматривать только нечетные числа в отслеживании, сгенерированной последовательности Коллатца, то каждое нечетное число в среднем составляет 3/4 предыдущего. (Точнее, среднее геометрическое соотношение исходов составляет 3/4.) Это дает эвристический аргумент, что каждая последовательность Града уменьшаться в долгосрочной перспективе, хотя это не свидетельствует против других циклов, а только против расхождения. Аргумент не доказательством, потому что он предполагает, что он предполагает Града собраны из некоррелированных вероятностных событий. (Это строго устанавливает, что 2-адическое расширение процесса Коллатца имеет два шага деления для каждого шага умножения для всех 2-адических начальных значений.)
И даже если вероятностное рассуждения были строгими, это все равно означало бы только то, что гипотеза почти наверняка верна для любого заданного целого числа, что не обязательно означает, что оно верно для всех целых чисел.
Теренс Тао (2019) с помощью вероятности доказал, что почти все орбиты Коллатца ограничены любой функцией, уходящей в бесконечность. Отвечая на эту работу, Quanta Magazine написал, что Тао «пришел к одному из самых значительных результатов по гипотезе Коллатца за десятилетия».
компьютерное доказательство, Красиков и Лагариас показали, что количество целых чисел в интервале [1, x], которые в конечном итоге достигают 1, по крайней мере равно x для всех достаточно больших x.
В этой части рассмотрим "сокращенную" формулу функции Коллатца
Цикл - это последовательность (a 0 ; a 1 ;...; a q) различных положительных целых чисел, где T (a 0) = a 1, T (a 1) = a 2,... и T ( a q) = a 0.
Единственный известный цикл есть (1; 2) длина 2, называемый тривиальным циклом.
Известно, что длина нетривиального цикла составляет не менее 17087915. Фактически, Элиахоу (1993) доказал, что период нетривиального цикла имеет форма
где a, b и c - неотрицательные целые числа, b ≥ 1 и ac = 0. Этот результат основан на разложении непрерывной дроби ln 3 / ln 2.
Аналогичное рассуждение, которое учитывает недавнюю проверку гипотезы до 2, приводит к улучшенной нижней границе 114208327604 (или 186265759595 без "ярлыка"). Эта нижняя граница соответствует приведенным выше результатам, поскольку .
K -цикл - это цикл, который можно разделить на 2 k непрерывных подпоследовательностей: k возрастающих последовательностей нечетных чисел, чередующихся с k убывающих последовательностей четных чисел. Например, если цикл состоит из одной возрастающей последовательности нечетных чисел, за которой следует последовательность последовательных четных чисел, это называется 1-циклом.
Штайнер (1977) доказал, что не существует 1-цикла кроме тривиального (1; 2). Саймонс (2004) использовал метод Штейнера, чтобы доказать, что не существует 2-цикла. Simons de Weger (2005) расширили это доказательство до 68-циклов: не существует k-цикла до k = 68. За пределами 68 этот метод дает верхние границы для элементов в таком цикле: например, если есть 75-цикл, то хотя бы один элемент цикла меньше 2385 × 2. Следовательно, по мере продолжения исчерпывающих компьютерных поисков более длительные циклы могут быть исключены. Чтобы указать аргумент более интуитивно: нам не нужно искать циклы, которые имеют не более 68 траекторий, где каждая траектория состоит из последовательных подъемов, за которые следуют последовательные спады.
Существует другой подход к доказательству гипотезы, который рассматривает восходящий метод роста так называемого графа Коллатца. Граф Коллатца - это граф, определяемый обратным описанием
Итак, вместо доказывая, что все положительные числа в результате приводят к 1, мы пытаемся доказать, что 1 приводит ко всем положительным целым числам. Для любого целого n, n ≡ 1 (mod 2) тогда и только тогда, когда 3n + 1 ≡ 4 (mod 6). Эквивалентно, n - 1/3 ≡ 1 (mod 2) тогда и только тогда, когда n 4 (mod 6). Предположительно, это обратное отношение образует дерево, за исключением цикла 1–2–4 (обратного цикла 4–2–1 неизменной функции f, типичной в Постановке задачи этой статьи).
Когда отношение 3n + 1 f заменяется общим замещающим "сокращенным" отношением 3n + 1/2, график Коллатца определяется обратным использованием,
Для любого целого числа n, n 1 (mod 2) тогда и только тогда, когда 3n + 1/2 ≡ 2 (mod 3). Эквивалентно, 2n - 1/3 ≡ 1 (mod 2) тогда и только тогда, когда n 2 (mod 3). Предположительно, это обратное отношение образует дерево, за исключением цикла 1–2 (обратного цикла 1–2 функции f (n), исправленного, как указано выше).
В качестве альтернативы можно заменить 3n + 1 на n ′ / H (n ′), где n ′ = 3n + 1, а H (n ′) - наивысшая степень 2, которая делит n ′ (Без остатка ). Результирующая функция преобразует нечетные числа в нечетные числа. Теперь предположим, что для некоторого нечетного числа в применении этой операции k дает число 1 (то есть f (n) = 1). Тогда в двоичном число n может быть записано как конкатенация строк wkwk - 1 … w 1, где каждый w h - это конечный непрерывный отрывок из представления 1/3. Таким образом, представление n содержит , повторение 1/3, где каждое повторение необязательно поворачивается, а реплицируется до конечного числа битов. Это происходит только в двоичном формате. Предположительно, каждая двоичная строка s, оканчивающаяся на «1», может быть достигнута представлением этой формы (где мы можем добавить или удаление ведущей «0» к s).
Повторяющиеся применения функции Коллатца могут быть представлены как абстрактная машина, которая обрабатывает строки биты. Машина будет выполнять следующие три шага с любым нечетным числом, пока не останется только одна "1":
Начальное число 7 записывается по основанию два как 111. Результирующая последовательность Коллатца:
111 111 1101101011 110001010001 11101001101 1101000101 110000
В разделе рассмотрим функцию Коллатца в модифицированной форме
Это можно сделать, потому что, когда n нечетно, 3n + 1 всегда четно.
Если P (…) является четностью числа, то есть P (2n) = 0 и P (2n + 1) = 1, то мы можем определить последовательность четности Коллатца (или вектор четности) для числа n как p i = P (a i), где a 0 = n, и a i + 1 = f (а и).
Какая операция выполняется, 3n + 1/2 или n / 2, зависит от четности. Последовательность четности такая же, как и последовательность операций.
Используя эту форму для f (n), можно показать, что последовательности четности для двух чисел m и n будут согласовываться в первых k членах тогда и только тогда, когда m и n эквивалентны по модулю 2. Это подразумевает что каждое число однозначно идентифицируетсясвоей последовательностью четности, и, кроме того, если существует несколько циклов Хейлстона, соответствующие им циклы четности должны быть разными.
Применение функции fk раз к числу n = 2a + b даст результат 3a + d, где d - результат применения функции fk раз к b, а c - сколько увеличений произошло во время этой последовательности (например, для 2a + 1 есть 3 увеличения, поскольку 1 повторяется до 2, 1, 2, 1 и, наконец, до 2, поэтому результат будет 3a + 2; для 2a + 1 есть только 1 увеличение, поскольку 1 увеличивается до 2 и падает до 1, поэтому результат 3а + 1). Когда b равно 2 - 1, тогда будет возрастаний, и результат будет 2 × 3a - 1. Коэффициент 3 при умножении a не зависит от значения a; это зависит только от поведения б. Это позволяет предсказать, что формы чисел всегда будут приводить к меньшему после определенного количества итераций, например 4a + 1 становится 3a + 1 после двух применений f, а 16a + 3 становится 9a + 2 после 4 приложений f. Однако, продолжаются ли эти меньшие до числа 1, зависит от значения a.
Для функций Коллатца в форме
Последовательности града могут быть вычислены с помощью простого 2-тега система с производственными предписаниями
В этой системе положительное целое число в строках из n копий и итерациями операций тега останавливается на любых слове меньше 2 (адаптировано из De Mol.)
Гипотеза Коллатца эквивалентно утверждает, что эта система тегов с произвольной конечной строкой в качестве конечной конечной строки заканчивается (см. Система тегов # Пример: Расчет последовательностей Коллатца для рабочего примера).
Расширение гипотезы Коллатца должно быть все целые числа, а не только положительные целые числа. Не говоря уже о цикле 0 → 0, в который нельзя войти извне, существует всего 4 цикла, в котором все ненулевые целые числа, похоже, в конечном итоге попадают при итерации f. Эти циклы здесь, начиная с хорошо известного цикла для положительных значений n:
Нечетные значения выделены жирным шрифтом. Каждый цикл перечисляется первым с наименьшим абсолютным значением (всегда нечетным).
Цикл | Длина цикла с нечетным значением | Длина полного цикла |
---|---|---|
1→ 4 → 2 → 1... | 1 | 3 |
−1→ −2 → −1... | 1 | 2 |
−5→ −14 → −7→ −20 → −10 → −5... | 2 | 5 |
−17→ −50 → −25 → −74 → −37→ −110 → −55→ −164 → −82 → −41 → −122 → −61→ −182 → −91→ −272 → - 136 → −68 → −34 → −17 ... | 7 | 18 |
Обобщенная гипотеза Коллатца - это утверждение, что каждое целое число при итерации по f в конечном итоге попадает в одно из четырех перечисленных циклов или цикла 0 → 0. Цикл 0 → 0 часто рассматривается как «тривиальный», поскольку он включен только для полноты картины.
Карта Коллатца может быть расширена до (положительных или отрицательных) рациональных чисел, которые имеют нечетные знаменатели при записи в младших членов. Число считается «нечетным» или «четным» в зависимости от того, является ли его числитель нечетным или четным. Тогда формула для карты точно такая же, как и для целых чисел: «четное» такое рациональное число делится на 2; такое «нечетное» рациональное число умножается на 3, а затем добавляется 1. Тесно связано в том, что отображение Коллатца продолжается до кольца 2-адических целых чисел, которое содержит кольцо рациональных чисел с нечетными знаменателями в качестве подкольца.
При использовании "сокращенного" карты определения Коллатца известно, что любая периодическая последовательность четности генерируется ровно одним рациональным числом. И наоборот, экологическое рациональное число с нечетным знаменателем имеет в конечном итоге последовательность четности (гипотеза периодичности).
Если цикл четности имеет длину n и включает нечетные числа ровно m с индексами k 0< … < km - 1, то единственное рациональное число, которое периодически и периодически генерирует этот цикл четности, будет
(1) |
Например, цикл четности (1 0 1 1 0 0 1) имеет длину 7 и четыре нечетных членских индексами 0, 2, 3 и 6. Он многократно создается дробью
, поскольку последний использует рациональному циклу
Любая циклическая перестановка (1 0 1 1 0 0 1) связанная с одной из упомянутых дробей. Например, цикл (0 1 1 0 0 1 1) создается дробью
Для взаимно однозначного соответствия цикл четности должен быть несводимым, т. Е. Не разбиваться на идентичные субциклы. В качестве иллюстрации этого, цикл четности (1 1 0 0 1 1 0 0) и его подцикл (1 1 0 0) связаны с одной и той же долей 5/7 при сокращении до младших членов.
В этом контексте предположение о справедливости гипотезы Коллатца означает, что (1 0) и (0 1) - единственные циклы четности, генерируемые положительными целыми числами (1 и 2, соответственно).
Если нечетный знаменатель d рационального числа не кратен 3, то все итерации имеют один и тот же знаменатель, и последовательность числителей может быть получена путем применения обобщения "3n + d" функции Коллатца.
Функция
хорошо определен на кольце ℤ 2 из 2-адических целых чисел, где он является непрерывным и сохраняющим меру по отношению к 2-адической мере. Кроме того, известно, что его динамика эргодична.
. Определим вектор-функцию четкости Q, действующую на ℤ 2 как
Функция Q является 2-адической изометрией. Следовательно, каждая последовательность последовательностей формируется ровно для одного 2-адического целого числа, так что почти все траектории ацикличны в .
Эквивалентная формулировка формулы Коллатца гипотеза в том, что
Карта Коллатца может рассматриваться как ограничение на целые числа гладкой действительной и комплексной карты
Если стандартная карта Коллатца, определенная выше, оптимизирована путем замены отношения 3n + 1 на обычную замену "ярлык" " соотношение 3n + 1/2, можно рассматривать как ограничение числа гладкого вещественного и комплексного отображения
Точка зрения итерации на действительной прямой исследована Чемберлендом (1996) показал, что эта гипотеза не верна для действительных чисел, поскольку существует бесконечно много неподвижных точек, а также орбит, монотонно уходящих в бесконечность. что с уществует, по крайней мере, еще один цикл притяжения: 1,1925 → 2,1386.
На комплексной плоскости это было исследовано Летерманом, Шлейхером и Вудом (1999). Большинство точек плоскости расходятся до бесконечности, как показано синим цветом на иллюстрации ниже. Граница между расходящимися и нерасходящимися областями показывает образец фрактала , который называется «фракталом Коллатца».
Раздел Как последовательность четности выше дает способ ускорить моделирование последовательности. Чтобы продвинуться вперед на k шагов по каждой итерации (используя функцию f из этого числа), разбейте текущее число на две части, b (k младших значащих битов, интерпретируемых как целое число) и a (остальные биты как целое число). Переход вперед на k шагов можно найти как:
Массивы c (или лучше 3) и d вычисляются для всех k-битов числа b, где d (b) - результат k раз применения функции f к b, а c (b) - количество нечетных чисел, встречающихся на пути. Например, если k = 5, на каждой итерации можно перейти на 5 шагов вперед, выделив 5 младших битов числа и используя:
Это требует 2 предварительных вычислений и хранение для ускорения итоговых вычислений в k раз, компромисс между пространством и временем.
Для специальной цели поиска контрпримера к гипотезе Коллатца это предварительное вычисление приводит к еще более важному ускорению, используя Томас Оливейра и Силва в его вычислительных подтверждениях гипотезы Коллатца до больших значений n. Если для некоторых заданных b и k неравенство
выполнено для всех a, то первый контрпример, если он существует, не может быть b по модулю 2., первый контрпример должен быть нечетным, потому что f (2n) = n, меньше 2n; и оно должно быть 3 mod 4, потому что f (4n + 1) = 3n + 1, меньше 4n + 1. Для каждого начального значения a, которое не является контрпримером к гипотезе Коллатца, существует ak, для которого такое неравенство выполняется, поэтому проверка гипотезы Коллатца для одного начального значения так же хороша, как и проверка всего класса конгруэнтности. По мере увеличения k поиску необходимо проверить только те остатки b, которые не устраняются более низкими значениями k. Выживает только экспоненциально малая часть остатков. Например, единственными выжившими остатками по модулю 32 являются 7, 15, 27 и 31.
k - нечетное целое число, то 3k + 1 четное, поэтому 3k + 1 = 2k ′ С нечетным k ′ и a ≥ 1. Сиракузская функция - это функция f из множества I нечетных целых чисел в себя, для которой f (k) = k ′ (последовательность A075677 в OEIS ).
Некоторые свойства функции Сиракузы:
Гипотеза Коллатца эквивалентна утверждению, что для всех k в I существует целое число n ≥ 1 такое, что f (k) = 1.
В 1972 году Джон Хортон Конвей доказал, что естественное Обобщение проблемы Коллатца алгоритмически неразрешимо.
В частности, он рассматривал функции вида
и 0, b 0,..., a P - 1, b P - 1 - рациональные числа, выбранные таким образом, что g (n) всегда целое число.
Стандартная функция Коллатца задается как P = 2, a 0 = 1/2, b 0 = 0, a 1 = 3, b 1 = 1. Конвей доказал, что t Проблема:
неразрешима, представляя таким образом проблему остановки.
Ближе к проблеме Коллатца является следующая универсально определенная проблема:
Изменение условия таким образом может усложнить или облегчить решение проблемы (интуитивно сложнее обосновать положительный ответ, но может быть легче оправдать отрицательный). Курц и Саймон доказали, что указанная выше проблема фактически неразрешима и даже выше в арифметической иерархии, а именно в Π. 2-полной. Этот результат жесткости сохраняется, даже если ограничить класс функций g, зафиксировав модуль P равным 6480.
В фильме Incendies аспирант в чистой математике объясняет гипотезу Коллатца группе студентов. Она на время откладывает учебу, чтобы ответить на некоторые нерешенные вопросы о прошлом своей семьи. В конце фильма гипотеза Коллатца, оказывается, предвещает тревожное и трудное открытие, которое она делает о своей семье.