Распечатать запись Распечатать запись

Гипотеза Коллатца, или числа-градины

Фрактал Коллатца (модификация отображения для натуральных чисел) в окрестности вещественной оси

Эта проблема названа в честь Лотара Коллатца, предложившего ее впервые в 1937 году. Она имеет много других названий, в частности, числа-градины, сиракузская последовательность, проблема 3n+1 и др.). Задача эта имеет очень простую и доступную формулировку, однако до сих пор считается нерешенной.

Пол Эрдёш сказал по поводу гипотезы Коллатца: “Математика еще не готова к таким задачам’’. Он предложил также 500 долларов за ее решение.

В 2006 году Куртц и Симон, основываясь на работах Конвея 1970-х годов, доказали неразрешимость обобщенной гипотезы Коллатца, однако из этого не следует, что сама гипотеза недоказуема.

Совсем недавно (в июне текущего года) появились сообщения о том, что гипотеза Коллатца доказана Герхартом Опфером из Гамбургского университета. Однако его работа пока еще не опубликована, она находится на рецензии в журнале Mathematics of Computation.

Итак, вот в чем состоит проблема.

Возьмем произвольное натуральное число n и построим последовательность по следующему правилу:

если n четно, то поделим его на 2 и получим n ^{\prime}=n/2;
если n нечетно, то домножим его на 3 и прибавим 1, получим n^{\prime}=3n+1.

Затем берем n ^{\prime} как новое стартовое число и повторяем процесс.

Пример. Если возьмем n=5, получим последовательность

5,16,8,4,2,1,4,2,1\ldots

При n=11 получаем

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

Так вот, гипотеза Коллатца состоит в том, что для любого стартового числа n через конечное число шагов всега получится последовательность 4,2,1,4,2,1,\ldots

Название “числа-градины’’ связано с тем, что графики получаемых последовательностей (см. рис.) похожи на движение в атмосфере градин.

Числа-градины для n=27

Гипотеза проверялась на компьютере для всех начальных значений до 20\cdot2^{58}\approx 5.764\cdot10^{18}. Во всех этих случаях она заканчивалась повторяющимся циклом 4,2,1, состоящим из трех элементов. Однако такая проверка не является доказательством гипотезы. Как показывают случаи гипотезы Пойа, гипотезы Мертенса и число Скьюза, иногда контрпримеры находятся только для очень больших чисел. Поскольку последовательное тестирование всех натуральных чисел — это процесс, который никогда не может быть закончен (их бесконечно много ;) ), то такой подход не может доказать истинность гипотезы, он может показать только, что контрпример еще не найден.

http://en.wikipedia.org/wiki/Collatz_conjecture
http://plus.maths.org/content/mathematical-mysteries-hailstone-sequences (здесь вы можете также ввести начальный член последовательности и получить ее члены).

Оставьте свой отзыв

Добавить изображение