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

Гипотеза Ко́ллатца — одна из нерешённых проблем математики: верно ли, что последовательность чисел, строящаяся от произвольного натурального ${\displaystyle n_{0}}$, каждое ${\displaystyle (i+1)}$-е число в которой равно ${\displaystyle 3n_{i}+1}$, если ${\displaystyle n_{i}}$ — нечётное, и ${\displaystyle n_{i}/2}$, если ${\displaystyle n_{i}}$ — чётное, рано или поздно вырождается в единицу. Такие последовательности называются сиракузскими, а гипотеза иногда фигурирует как под наименованием «сираку́зская проблема».

Названа по имени немецкого математика Лотара Коллатца, сформулировавшего похожую задачу 1 июля 1932 года^[1].

Последовательности для первых чисел:

При ${\displaystyle n=27}$ последовательность состоит из 111 членов до первой единицы, достигая в пике значения 9232.

Благодаря элементарности формулировки проблема снискала широкую известность, фигурировала во множестве научно-популярных публикаций, создано множество визуализаций для умозрительного поиска закономерностей. Запущено несколько проектов добровольных вычислений по проверке гипотезы: в августе 2009 года — на платформе BOINC^[2] (с поддержкой GPGPU), в августе 2017 года — в рамках проекта «yoyo@home»^[3].

В последние годы^{[уточнить]} проверены все натуральные числа до 3×10²⁰, и каждое из них продемонстрировало соответствие гипотезе Коллатца.

• 
  Направленный график, показывающий орбиты первых 1000 чисел.
• 
  Ось ${\displaystyle x}$ представляет начальное число, ось ${\displaystyle y}$ — наибольшее число, достигнутое в цепочке до 1. Этот график показывает ограниченность оси y: некоторые значения ${\displaystyle x}$ дают промежуточные значения, достигающие 2,7e7 (для ${\displaystyle x=9663}$)
• 
  График в логарифмическом масштабе; первая жирная линия в середине графика соответствует вершине в точке 27, которая достигает максимума в точке 9232.
• 
  Дерево всех чисел, имеющих меньше 20 шагов.
• 
  Количество итераций, необходимое для достижения единицы для первых 100 миллионов чисел.
• 
  Пути по гипотезе Коллатца для 5000 случайных начальных точек меньше миллиона.

• Хэйес, Брайан.Взлёты и падения чисел-градин // В мире науки (Scientific American, издание на русском языке). — 1984. — № 3. — С. 102—107.
• Стюарт, Иэн. Величайшие математические задачи. — М.: Альпина нон-фикшн, 2015. — 460 с. — ISBN 978-5-91671-318-3.
• Jeff Lagarias.The 3x+1 problem and its generalizations (англ.) // American Mathematical Monthly. — 1985. — Vol. 92. — P. 3—23.

• последовательность A014682 в OEIS.
• Самая простая нерешённая задача — гипотеза Коллатца (YOUTUBE)  (рус.) (Видео). www.youtube.com. Дата обращения: 2 ноября 2022. Архивировано 2 ноября 2022 года.
• Das Collatz-Problem интерактивные скрипты Юргена Денкерта для решения (3n+1)- и (3n−1)-задач, создаёт последовательность для чисел любой длины, также выдаёт статистику последовательности.
• Collatz ConjectureАрхивная копия от 4 декабря 2017 на Wayback Machine — проект распределённых вычислений на платформе BOINC по проверке гипотезы Коллатца на больших числах.
• On the 3x + 1 problemАрхивная копия от 14 декабря 2013 на Wayback Machine — проект распределённых вычислений, основанный Эриком Рузендалем (Eric Roosendaal), по проверке гипотезы Коллатца на больших числах.
• Аналитический подход к проблеме КоллатцаАрхивная копия от 20 марта 2013 на Wayback Machine. (англ.)
• Реализация сиракузской последовательности на разных языках программированияАрхивная копия от 4 апреля 2018 на Wayback Machine (на сайте Rosetta Code^[англ.]).
• Collatz conjecture A.A Durmagambetov, A. A Durmagambetova. https://www.researchgate.net/publication/359521315_Collatz_conjecture

В другом языковом разделе есть более полная статья Collatz conjecture (англ.).

Вы можете помочь проекту, расширив текущую статью с помощью перевода