Что такое гипотеза коллатца

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

Гипо́теза Коллатца (гипо́теза 3n+1, гипо́теза 3x+1, пробле́ма Коллатца, пробле́ма 3n+1, пробле́ма 3x+1, сираку́зская пробле́ма) — одна из нерешённых проблем математики, названная по имени немецкого математика Лотара Коллатца (англ.), предложившего её в 1937 году. Для объяснения сути гипотезы рассмотрим следующую последовательность чисел, называемую сираку́зской после́довательностью. Берём любое натуральное число 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»

См. также

Примечания

Литература

Ссылки

Полезное

Смотреть что такое «Гипотеза Коллатца» в других словарях:

Последовательность жонглёра — В математике последовательность жонглёра целочисленная последовательность, начинающаяся с натурального числа a0, в которой каждый следующий элемент определяется следующим рекуррентным соотношением: [1] Содержание … Википедия

Открытые проблемы в теории чисел — Теория чисел это раздел математики, занимающийся преимущественно изучением натуральных и целых чисел и их свойств, часто с привлечением методов математического анализа и других разделов математики. Теория чисел содержит множество проблем,… … Википедия

Открытые математические проблемы — Открытые (нерешённые) математические проблемы проблемы, которые рассматривались математиками, но до сих пор не решены. Часто имеют форму гипотез, которые предположительно верны, но нуждаются в доказательстве. В научном мире популярна… … Википедия

Источник

Гипотеза Коллатца — самый крутой математический фокус всех времён

Авторизуйтесь

Гипотеза Коллатца — самый крутой математический фокус всех времён

В книгах и в Интернете часто можно встретить разные математические фокусы. В таких фокусах вас просят задумать какое-то число, затем выполнить с ним ряд арифметических действий. После этого собеседник точно называет вам получившееся у вас число. Большинство этих фокусов основано на том, что исходное число в ходе преобразований незаметно подменяется другим, а затем за несколько шагов сводится к известному ответу. Такие фокусы, например, можно встретить в книгах Якова Перельмана.

Гипотеза Коллатца оставляет все подобные фокусы позади. На первый взгляд может показаться, что это тоже какой-то фокус с подвохом. Однако при внимательном рассмотрении оказывается, что никакого подвоха нет. Вы загадываете число и несколько раз повторяете для него одно из двух арифметических действий. Удивительно, что результат этих действий будет всегда одним и тем же. Или не всегда? Этого пока наверняка никто не знает, но получить что-то другое пока никому не удалось.

Давайте попробуем. Итак, загадайте любое целое положительное число. Дальше следуйте простому алгоритму:

1. Если число чётное, разделите его на 2. Иначе умножьте его на 3 и прибавьте 1.
2. Повторите шаг 1 с полученным числом.

Как вы думаете, что мы получим в итоге, если будем много раз выполнять шаги 1 и 2?

Немецкий математик Лотар Коллатц считает, что для любого целого положительного числа мы рано или поздно получим сначала 4, потом закономерно — 2, а потом 1. И после этого мы будем ходить по кругу, вновь и вновь получая цепочку 4–2–1. Самое удивительное в том, что мы придём к такому результату, с какого бы числа мы ни начали.

Не верите? Это не сложно проверить, тем более, что условия задачи очень просты. Пожалуй, на данный момент это простейшая формулировка нерешённой математической задачи — умножать и складывать умеет каждый. Справедливости ради стоит заметить, что для некоторых исходных чисел считать придётся долго. Так что для загадывания в дружеской компании этот «фокус» если и подойдёт, то только для небольших исходных чисел. Но мы всегда можем написать маленькую программку — куда уж проще: цикл с одним условием. Вот мой вариант простейшей программы на любимом мною Delphi (да, такой я динозавр):

Попробуйте написать такую программу на своём языке программирования и поэкспериментировать с этой гипотезой. Кстати, в сети можно найти много интересных визуализаций, показывающих распределение решений и шагов для разных исходных данных. А ещё для ленивых в сети есть сайт, который содержит варианты реализации этой задачи для множества языков программирования.

Знаете, что ещё интересно? Утверждение Коллатца не зря называется гипотезой — пока никто так и не смог придумать её логическое доказательство. Лотар Коллатц сформулировал свою гипотезу ещё в 30-х годах 20 века и с тех пор предпринимались многочисленные попытки доказать или опровергнуть это утверждение с помощью строгой математической логики. Но всё, чего смогли добиться математики, — это просто проверить гипотезу экспериментально. В этой задаче программный поиск решения по сути ничем не ограничен, кроме вычислительных мощностей. Пока гипотеза не опровергнута — даже для огромных исходных чисел рано или поздно алгоритм достигает 1. Для решения этой задачи даже был организован проект добровольных распределённых вычислений. Но для классической математики этого недостаточно. Числа иногда бывают очень коварны. Где-то среди неимоверно огромных исходных чисел может скрываться такое исходное число, для которого гипотеза не подтвердится.

Кстати, у гипотезы Коллатца есть ещё несколько менее известных названий:
– дилемма 3n+1 — это вариант шага для нечётных чисел;
– гипотеза градины — графики последовательностей чем-то напоминают траектории движения града в атмосфере;
– гипотеза Улама — по имени польского математика Станислава Улама;
– проблема Какутани — по имени японского математика Сидзуо Какутани;
– гипотеза Туэйтса — по имени английского математика Брайна Туэйта;
– алгоритм Хассе — по имени немецкого математика Хельмута Хассе;
– сиракузская проблема.

По количеству разнообразных наименований видно, что математиков всерьёз заинтересовала эта проблема. Однако оказалось, что это одна из тех «вредных» задач, которые очень легко формулируются, но чрезвычайно тяжело решаются. Прямо как Великая теорема Ферма.

Числа в этой задаче ведут себя крайне странно: в некоторых случаях вычисления доходят до единицы очень быстро, а иногда промежуточный итог добирается до довольно большого числа, а затем быстро «срывается» вниз — до самой единицы. Например, для начального числа 27 промежуточный итог достигает 9232, а затем за несколько шагов быстро спускается до 1. В итоге количество шагов для 27 равно 111. И это при том, что для 26 оно равно 10 (максимальное промежуточное число — 40), а для 28 — 18 (максимальное промежуточное число — 52).

Хоть математикам и не удалось полностью логически подтвердить или опровергнуть гипотезу, они всё же кое-чего достигли. Как это часто бывает, учёные подбираются к решению постепенно. Совсем недавно, 8 сентября 2019, математик из Калифорнийского университета Теренс Тао опубликовал доказательство, где показано, что гипотеза Коллатца, по меньшей мере, «почти» верна «почти» для всех чисел. История того, как математики штурмовали эту проблему и о том, чего удалось достичь Теренсу Тао подробно описана в этой статье.

В журналах и в сети уже неоднократно появлялись варианты доказательства гипотезы Коллатца. Однако, к большому сожалению, все они либо содержали ошибки, либо были неполными. Так что гипотеза пока остаётся гипотезой, а ещё — самым красивым и крутым математическим фокусом.

Источник

О формировании последовательностей в гипотезе Коллатца ( 3n+1 )

Меня привлекают такие задачи, как проблема Коллатца. Они просты в формулировке и отлично тренируют голову, в особенности алгоритмического мышления, что очень полезно программисту.

Формулируется задача довольно просто:

Берём любое натуральное число n. Если оно чётное, то делим его на 2, а если нечётное, то умножаем на 3 и прибавляем 1 (получаем 3n + 1). Над полученным числом выполняем те же самые действия, и так далее.

Гипотеза Коллатца заключается в том, что какое бы начальное число n мы ни взяли, рано или поздно мы получим единицу.

Алгоритмически это выглядит так:

Я прошу простить меня за мою математику, дайте знать, если где-то ошибусь.

Давайте выделим общее количество сведений к единице и истинное количество сведений к единице. Обозначим это за шаги.

Рассмотрим последовательность для n = 7:

22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1.

Истинным шагом Sa(n) будем называть количество операций 3n+1 над числом, необходимых, чтобы достичь единицы.

Идея наглядно демонстрируется на примере таблицы:

Sn (0)	Sn (1)	Sn (2)	Sn (3)	Sn (4)	Sn (5)	Sn (6)	Sn (7)	Sn (8)	Sn (9)	Sn (10)	Sn (11)	Sn (12)
2	5	3	17	11	7	9	25	33	43	57	39	105
4	10	6	34	22	14	18	49	65	86	59	78	203
8	20	12	35	23	15	19	50	66	87	114	79	209
16	21	13	68	44	28	36	51	67	89	115	153	210
32	40	24	69	45	29	37	98	130	182	118	156	211
64	42	26	70	46	30	38	99	131	173	119	157	406
128	80	48	75	88	56	72	100	132	174	228	158	407
256	84	52	136	90	58	74	101	133	177	229	305	409
512	85	53	138	92	60	77	102	134	178	230	306	418

В такой таблице уже проглядывается порядок, своя закономерность.
Как видно степень двойки никогда нечетной не станет, поэтому все сводится к простому делению.
Образуется последовательность от Sa(0) всего 1 формулой.

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

Sn (0)	Sn (1)	Sn (2)	Sn (3)	Sn (4)	Sn (5)	Sn (6)	Sn (7)	Sn (8)	Sn (9)	Sn (10)	Sn (11)	Sn (12)
5	3	17	11	7	9	25	33	43	57	39	105
21	13	35	23	15	19	49	65	87	59	79	203
85	53	69	45	29	37	51	67	89	115	153	209
341	113	75	93	61	77	99	131	173	119	157	211
1365	213	141	181	117	81	101	133	177	229	305	407

Сейчас уже сложнее уловить закономерность, однако она есть. Сейчас самое интересное — образование последовательностей. Не просто так следующей цифрой после 5 стоит 21, а после неё 85.
На самом деле Sa(1) – это последовательность A002450 (0, 1, 5, 21, 85, 341, 1365, 5461, 21845, 87381… ). Она образуется формулой:

Эту же последовательность можно описать рекурсивной формулой:

И так далее…

Ряд первого шага построен, хотя он может продолжаться до бесконечности. Перейдем к шагу два. Формулу перехода к шагу 2 можно выразить из нечетной формулы.
Зная, что мы собираемся делить результат несколько раз, можно это записать как , где – количество делений.

Итоговая формула принимает вид:

Так же введем поправку на , как , чтобы не случилось варианта деления числа не кратного 3 на 3.

Давайте проверим формулу, так как альфа неизвестная, проверим для подряд идущих 5 альф:

Тем самым начинает образовываться последовательность второго шага. Однако, можно заметить, что 113 нет в последовательности, важно помнить, что формула рассчитывалась от 5.

n = 113 на самом деле:

Множество от порождается функцией от каждого элемента множества от .

13 от α=1 порождает:
17
69
277
1109
4437

53 от α=2 порождает:
35
141
565
2261
9045

213 от α=3 порождает:
Ничего

853 от α=4 порождает:
1137
4549
18197
72789
291157

113 от α=0 порождает:
75
301
1205
4821
19285

453 от α=1 порождает:
Ничего

1813 от α=2 порождает:
2417
9669
38677
154709
618837

7253 от α=3 порождает:
4835
19341
77365
309461
1237845

29013 от α=4 порождает:
Ничего

227 от α=0 порождает:
151
605
2421
9685
38741

909 от α=1 порождает:
Ничего

3637 от α=2 порождает:
4849
19397
77589
310357
1241429

14549 от α=3 порождает:
9699
38797
155189
620757
2483029

58197 от α=4 порождает:
Ничего

Объединив эти множества, получим множество от Sa(3):

17, 35, 69, 75, 141, 151, 277, 301, 565, 605, 1109, 1137, 1205, 2261, 2275, 2417, 2421, 4437, 4549, 4821, 4835, 4849, 9045, 9101, 9669, 9685, 9699, 17749, 18197, 19285, 19341, 19397, 19417…

Почему где-то , а где-то ?

Вернемся снова к последовательности A002450. Есть интересная зависимость:

– не производит дочерних последовательностей.
– производит дочерние последовательности при .
– производит дочерние последовательности при .

Есть всего 3 потенциальных дочерних множества у числа.
Если применить к рекурсивной формуле, то:

Функция , где — любое число кратное 3, образует пустое множество ⨂.

Функция , где — любое число порожденное , при образует множество чисел K принадлежащих множеству натуральных чисел N.

Функция , при образует множество чисел L принадлежащих множеству натуральных чисел N.

Очевидно, что это каким-то образом можно свести к более строгой и доказательной формулировке.

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

Формула для нечетных:

Помимо нечетных, нужно восстановить множество четных. Для этого вспомним формулу:

Осталось только соотнести все вместе:

Тем самым любая k может породить последовательность.

Справедливо ли обратное, что любое из натуральных чисел определенно принадлежит к какой-либо последовательности от ?

Если так, то вполне возможно, что Коллатц был прав.

Под финал пример реализации функции на javascript:

Источник