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

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

Эта проблема названа в честь Лотара Коллатца, предложившего ее впервые в 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 (здесь вы можете также ввести начальный член последовательности и получить ее члены).

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

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