Перегляд вихідного коду сторінки Гіпотеза Коллатца

{{unibox}}

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

== Сіракузька послідовність ==
Для пояснення суті гіпотези розглянемо наступну послідовність чисел, яка називається '''Сіракузькою послідовністю'''. Беремо будь-яке [[натуральне число]] ''n''. Якщо воно [[Парність (математика)|парне]], то ділимо його на 2, а якщо непарне, то множимо на 3 і додаємо 1 (отримуємо ''3n + 1''). Над отриманим числом виконуємо ті ж самі дії, і так далі.
[[Файл:Collatz5.svg|обрамити|праворуч|Графік послідовності для числа 27]]

Наприклад, для числа 3 отримуємо:
: 3&nbsp;— непарне, 3 × 3 + 1 = 10
: 10&nbsp;— парне, 10:2 = 5
: 5&nbsp;— непарне, 5 × 3 + 1 = 16
: 16&nbsp;— парне, 16:2 = 8
: 8&nbsp;— парне, 8:2 = 4
: 4&nbsp;— парне, 4:2 = 2
: 2&nbsp;— парне, 2:2 = 1
: 1&nbsp;— непарне, 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'''.

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

'''Числа&nbsp;— градини'''&nbsp;— також поширена назва для сукупності розглянутих послідовностей. Така назва виникла через те, що графіки послідовностей (див. ілюстрацію) схожі на траєкторію руху градин в атмосфері.

== Проєкт «Collatz Conjecture» ==

У серпні [[2009]] року на платформі [[BOINC]] був запущений проєкт добровільних [[Розподілені обчислення|розподілених обчислень]] «[http://boinc.thesonntags.com/collatz/ Collatz Conjecture] {{Webarchive|url=https://web.archive.org/web/20171204131813/http://boinc.thesonntags.com/collatz/ |date=4 грудня 2017 }}», метою якого є перевірка гіпотези Коллатца на великих числах. Обчислювальний модуль проєкту може використовувати обчислювальні потужності сучасних [[Відеокарта|відеокарт]] для одночасної обробки і вирахування послідовностей.

== Візуалізація ==
<gallery heights="240" widths="160">
Collatz-graph-all-30-no27.svg|Напрямлений [[Граф (математика)|граф]], що показує орбіти невеликих чисел при відображенні карти Коллатца.
Collatz Orbits of FIrst 1000 Integers.svg|Напрямлений граф, що показує орбіти перших 1000 номерів.
CollatzConjectureGraphMaxValues.jpg|х — стартовий номер<br/>у — найбільше число в ланцюгу на шляху до 1.
</gallery>

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

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

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

=== Строгі обмеження ===
Хоча достеменно не відомо чи всі додатні числа в кінцевому підсумку зводяться до одиниці відповідно до гіпотези Коллатца, відомо, що багато чисел дійсно зводяться. Зокрема, Красиков і Лагарис довели, що кількість цілих чисел в інтервалі [1, х], що в кінцевому підсумку зводяться до одиниці, принаймні пропорційна ''x''<sup>0.84</sup>.

== Цикли ==
{{Див. також|Періодична послідовність}}
У цій частині розглянемо скорочену форму функції Коллатца<math display="block"> f(n) = \begin{cases} \frac{n}{2} &\text{if } n \equiv 0 \pmod{2},\\[4px] \frac{3n+1}{2} & \text{if } n \equiv 1 \pmod{2}. \end{cases}</math>[[періодична послідовність|Цикл]]&nbsp;— це послідовність {{Math|(''a''<sub>0</sub>, ''a''<sub>1</sub>, ..., ''a<sub>q</sub>'')}} різних натуральних чисел, де {{Math|''f''(''a''<sub>0</sub>) {{=}} ''a''<sub>1</sub>}}, {{Math|''f''(''a''<sub>1</sub>) {{=}} ''a''<sub>2</sub>}}, … і {{Math|''f''(''a<sub>q</sub>'') {{=}} ''a''<sub>0</sub>}}.

Єдиним відомим циклом є {{Math|(1,2)}} з періодом 2, який називають тривіальним циклом.

=== Довжина циклу ===
Відомо, що довжина нетривіального циклу становить не менше {{Val|17087915}}<ref name="Eliahou (1993)">{{Cite journal|last=Eliahou|first=Shalom|year=1993|title=The 3''x'' + 1 problem: new lower bounds on nontrivial cycle lengths|journal=Discrete Mathematics|volume=118|issue=1|pages=45–56|doi=10.1016/0012-365X(93)90052-U|doi-access=free}}</ref>. Точніше, Еліаху довів, що період {{Mvar|p}} будь-якого нетривіального циклу має вигляд<math display="block">p = 301994 a + 17087915 b + 85137581 c</math>де {{Mvar|a}}, {{Mvar|b}} і {{Mvar|c}}&nbsp;— цілі невід'ємні числа, {{Math|''b'' ≥ 1}} і {{Math|1=''ac'' = 0}} (тобто, хоча б одне з чисел ''a'' чи ''c'' дорівнює нулю). Цей результат ґрунтується на розкладі {{math|{{sfrac|ln 3|ln 2}}}} в [[ланцюговий дріб]].

Подібне міркування, яке враховує нещодавню перевірку гіпотези до {{Math|2<sup>68</sup>}}, призводить до покращеної нижньої межі {{Val|114208327604}} (або {{Val|186265759595}} без «ярлика»). Ця нижня межа узгоджується з наведеним вище результатом, оскільки {{Nobr|1={{val|114208327604}} = {{val|17087915}} × 361 + {{val|85137581}} × {{val|1269}}.}}

=== {{Mvar|k}}-цикли ===
{{Mvar|k}} -цикл&nbsp;— це цикл, який можна розбити на {{Math|2''k''}} неперервних підпослідовностей: {{Mvar|k}} послідовностей непарних чисел, що зростають, які чергуються з {{Mvar|k}} спадними послідовностями парних чисел<ref name="Simons & de Weger (2005)">{{cite journal |first1=J. |last1=Simons |first2=B. |last2=de Weger |title=Theoretical and computational bounds for ''m''-cycles of the 3''n''&nbsp;+&nbsp;1 problem |journal=Acta Arithmetica |volume=117 |issue=1 |pages=51–70 |year=2005 |doi=10.4064/aa117-1-3 |url=http://deweger.xs4all.nl/papers/%5B35%5DSidW-3n+1-ActaArith%5B2005%5D.pdf |bibcode=2005AcAri.117...51S |doi-access=free |accessdate=2022-07-02 |archive-date=2017-05-17 |archive-url=https://web.archive.org/web/20170517124216/http://deweger.xs4all.nl/papers/%5B35%5DSidW-3n%201-ActaArith%5B2005%5D.pdf }}</ref>. Наприклад, якщо цикл складається з однієї зростаючої послідовності непарних чисел, за якою йде спадна послідовність парних чисел, він називається ''1-циклом''.

Штайнер (1977) довів, що не існує 1-циклу, крім тривіального {{Math|(1; 2)}}<ref name="Steiner (1977)">{{cite book |first=R. P. |last=Steiner |chapter=A theorem on the syracuse problem |title=Proceedings of the 7th Manitoba Conference on Numerical Mathematics |year=1977 |pages=553–9 |mr=535032}}</ref>. Сімонс (2005) за допомогою методу Штайнера довів, що не існує 2-циклу<ref>{{Cite journal|last=Simons|first=John L.|year=2005|title=On the nonexistence of 2-cycles for the 3''x'' + 1 problem|journal=Math. Comp.|volume=74|pages=1565–72|bibcode=2005MaCom..74.1565S|doi=10.1090/s0025-5718-04-01728-4|mr=2137019|doi-access=free}}</ref>. Сімонс і де Вегер (2005) розширили це доведення до 68-циклів: немає {{Mvar|k}}-циклу до {{Math|''k'' {{=}} 68}}<ref name="Simons & de Weger (2005)"/>. Для кожного {{Math|''k''}} поза 68 цей метод дає верхню межу для найменшого члена {{Mvar|k}}-циклу: наприклад, якщо є 77-цикл, тоді принаймні один елемент циклу менший за {{Gaps|38137|×|2<sup>50</sup>}}<ref name="Simons & de Weger (2005)"/>. Разом із перевіркою гіпотези до {{Math|2<sup>68</sup>}} це означає відсутність нетривіального {{Mvar|k}}-циклу до {{Math|''k'' {{=}} 77}}<ref name="Barina">{{Cite journal|last=Barina|first=David|year=2020|title=Convergence verification of the Collatz problem|journal=The Journal of Supercomputing|volume=77|issue=3|pages=2681–2688|doi=10.1007/s11227-020-03368-x}}</ref>. У міру просування комп'ютерних пошуків, більші значення {{Math|''k''}} можуть бути виключені. Простішими словами: нам не потрібно шукати цикли, які мають щонайбільше 77 циклів, де кожен контур складається з послідовних підйомів, за якими йдуть послідовні спади.

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

== Примітки ==
{{примітки|2}}

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

== Посилання ==
* [http://intelmath.narod.ru/problem3xp1.html Проблема 3x+1] {{Webarchive|url=https://web.archive.org/web/20131216091305/http://intelmath.narod.ru/problem3xp1.html |date=16 грудня 2013 }}&nbsp;— стаття на сайті вчителя математики, Сербіної Надії Олексіївни.
* [http://boinc.thesonntags.com/collatz/ Collatz Conjecture] {{Webarchive|url=https://web.archive.org/web/20171204131813/http://boinc.thesonntags.com/collatz/ |date=4 грудня 2017 }}&nbsp;— проект [[Розподілені обчислення|розподілених обчислень]] на платформі [[BOINC]] з перевірки гіпотези Коллатца на великих числах.
* [http://www.ericr.nl/wondrous/index.html On the 3x&nbsp;+&nbsp;1 problem] {{Webarchive|url=https://web.archive.org/web/20131214225919/http://www.ericr.nl/wondrous/index.html |date=14 грудня 2013 }}&nbsp;— проект [[Розподілені обчислення|розподілених обчислень]], заснований Еріком Рузендалем (''Eric Roosendaal''), з перевірки гіпотези Коллатца на великих числах.
* [http://preprint.math.uni-hamburg.de/public/papers/hbam/hbam2011-09.pdf Аналітичний підхід до проблеми Коллатца] {{Webarchive|url=https://web.archive.org/web/20130320021800/http://preprint.math.uni-hamburg.de/public/papers/hbam/hbam2011-09.pdf |date=20 березня 2013 }}.
{{Authority control}}
[[Категорія:Математичні гіпотези]]
[[Категорія:Арифметика]]
[[Категорія:Теорія чисел]]