Гіпотеза Коллатца (гіпотеза 3n+1, гіпотеза 3x+1, проблема Коллатца, проблема 3n+1, проблема 3x+1, Сіракузька проблема) — одна з нерозв'язаних проблем математики, названа на честь німецького математика Лотара Коллатца, який запропонував її у 1937 році.

Гіпотеза запитує, чи повторення двох простих арифметичних операцій зрештою перетворить кожне додатне ціле число на 1. Вона стосується послідовностей цілих чисел, у яких кожен член отримується з попереднього члена наступним чином: якщо член парний, наступний член дорівнює його половині(n/2). Якщо член непарний, наступний член дорівнює 3 разам попередньому плюс 1(3n+1). Гіпотеза полягає в тому, що ці послідовності завжди досягають 1, незалежно від того, яке додатне ціле число вибрано для початку послідовності. Було показано, що гіпотеза виконується для всіх додатних цілих чисел до 2,36 ×10²¹, але загального доказу не знайдено.

Сіракузька послідовність Для пояснення суті гіпотези розглянемо послідовність чисел, яка називається Сіракузькою послідовністю. Беремо будь-яке натуральне число n. Якщо воно парне, то ділимо його на 2, а якщо непарне, то множимо на 3 і додаємо 1 (отримуємо 3n + 1). Над отриманим числом виконуємо ті ж самі дії, і так далі.

Наприклад, для числа 3 маємо: 3 — непарне, 3 × 3 + 1 = 10 10 — парне, 10:2 = 5 5 — непарне, 5 × 3 + 1 = 16 16 — парне, 16:2 = 8 8 — парне, 8:2 = 4 4 — парне, 4:2 = 2 2 — парне, 2:2 = 1 1 — непарне, 1 × 3 + 1 = 4

Очевидно, що, починаючи з 1, циклічно повторюються числа 1, 4, 2.

Для числа 27 маємо : 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, …

Послідовність прийшла до одиниці тільки через 111 кроків, досягнувши пікового значення 9232.

Гіпотеза Коллатца полягає в тому, що яке б початкове число ми не взяли, рано чи пізно ми отримаємо одиницю.

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

Проєкт «Collatz Conjecture»

У серпні 2009 року на платформі BOINC запущено проєкт добровільних розподілених обчислень «Collatz Conjecture », метою якого є перевірка гіпотези Коллатца на великих числах. Обчислювальний модуль проєкту може використовувати для одночасної обробки і вирахування послідовностей обчислювальні потужності сучасних відеокарт.

Візуалізація

Аргументи на користь теорії

Хоча гіпотезу не доведено, більшість математиків, які розглядали цю проблему, вважають гіпотезу істинною, оскільки експериментальні дані й евристичні міркування підтримують її.

Ймовірнісний підхід

Якщо врахувати тільки непарні числа в послідовності, породженій процесом Коллатца, то кожне непарне число становить у середньому 3/4 попереднього. З цього випливає евристичний аргумент, що будь-яка послідовність чисел-градин у довгостроковій перспективі повинна збігатися, хоча це не є аргументом проти інших циклів, тільки проти розбіжності. Аргумент не є доведенням, оскільки він припускає, що послідовності чисел-градин складаються з некорельованих ймовірнісних подій.

Ймовірнісний аналіз задіяння парності у послідовності, на проміжку [10Е2: 10Е18] із 8Е6 значеннями, показує не гладку поведінку оцінки густини розподілу (гістограми) для варіантів переходу. Для найбільш ймовірного значення парного переходу (головної моди на 2/3), приналежні проміжки показують відсутність послідовностей які б могли давати вклад у розподіл.

Разом з багато-модовістю розподілу та кореляцією величин ймовірностей парне/непрарне у послідовності ( залежність від відстані/затримки lag англ.), - можна говорити про необхідність пошуку та застосування більш розвинутих методів аналізу результатів припущення Коллатца, що також підтверджено доказами не аналітичного розв'язку.

Строгі обмеження Хоча достеменно не відомо чи всі додатні числа зрештою зводяться до одиниці відповідно до гіпотези Коллатца, відомо, що багато чисел дійсно зводяться. Зокрема, Красиков і Лагарис довели, що кількість цілих чисел в інтервалі [1, х], що зрештою зводяться до одиниці, принаймні пропорційна x0.84.

Цикли

У цій частині розглянемо скорочену форму функції КоллатцаЦикл — це послідовність різних натуральних чисел, де , , … і .

Єдиним відомим циклом є з періодом 2, який називають тривіальним циклом.

Довжина циклу Відомо, що довжина нетривіального циклу становить не менше . Точніше, Еліаху довів, що період будь-якого нетривіального циклу має виглядде , і  — цілі невід'ємні числа, і (тобто, хоча б одне з чисел a чи c дорівнює нулю). Цей результат ґрунтується на розкладі в ланцюговий дріб.

Подібне міркування, яке враховує нещодавню перевірку гіпотези до , приводить до покращеної нижньої межі (або без «ярлика»). Ця нижня межа узгоджується з наведеним вище результатом, оскільки

-цикли -цикл — це цикл, який можна розбити на неперервних підпослідовностей: послідовностей непарних чисел, що зростають, які чергуються з спадними послідовностями парних чисел. Наприклад, якщо цикл складається з однієї зростаючої послідовності непарних чисел, за якою йде спадна послідовність парних чисел, він називається 1-циклом.

Штайнер (1977) довів, що не існує 1-циклу, крім тривіального . Сімонс (2005) за допомогою методу Штайнера довів, що не існує 2-циклу. Сімонс і де Вегер (2005) розширили це доведення до 68-циклів: немає -циклу до . Для кожного поза 68 цей метод дає верхню межу для найменшого члена -циклу: наприклад, якщо є 77-цикл, тоді принаймні один елемент циклу менший за . Разом із перевіркою гіпотези до це означає відсутність нетривіального -циклу до . У міру просування комп'ютерних пошуків, більші значення можуть бути виключені. Простішими словами: не потрібно шукати цикли, які мають щонайбільше 77 циклів, де кожен контур складається з послідовних підйомів, за якими йдуть послідовні спади.

Див. також BOINC Відкриті математичні питання

Примітки

Література Хейєс, Браян. Злети та падіння чисел-градин // В світі науки (Scientific American, видання російською мовою). — 1984. — № 3. — С. 102—107.

Примітки

Посилання Проблема 3x+1  — стаття на сайті вчителя математики, Сербіної Надії Олексіївни. Collatz Conjecture  — проект розподілених обчислень на платформі BOINC з перевірки гіпотези Коллатца на великих числах. On the 3x + 1 problem  — проект розподілених обчислень, заснований Еріком Рузендалем (Eric Roosendaal), з перевірки гіпотези Коллатца на великих числах. Аналітичний підхід до проблеми Коллатца .