Проблема 3x+1

Насколько сложной может быть задача, составленная на материале начальной школы: сложении, умножении, делении и чётности/нечётности числа?

Оказывается, более 70 лет назад Лотарем Коллатцем сформулирована так называемая проблема «3x+1», над которой бились математики лучших университетов мира, потрачены миллионы часов машинного времени, но никакие усилия к окончательному решению не привели.

В то же время понять условие этой задачи может даже первоклассник. Оно звучит так:
Возьмём какое-нибудь натуральное число. Далее, если число чётное, разделим его на 2, а если нечётное – умножим на 3 и прибавим 1. Затем будем выполнять эти действия с полученным числом. Например, вот что будет происходить, если начать с пятёрки.
5 –>3*5+1=16 –>16/2=8 –> 8/2=4 –>4/2=2 –> 2/2=1 –>1*3+1=4 Круг замкнулся. Теперь мы будем постоянно получать значения 1 –4 – 2.
Требуется узнать, существует ли такое число, начав с которого не скатишься к единице?:

Современная математика не в силах дать ответ на такой, казалось бы, простой вопрос. Даже недавно доказанная великая теорема Ферма – и та формулируется с использованием возведения в степень и целых четырёх переменных. А для задачи 3x+1 на сегодня достоверно известно, что последовательность приходит в единице для всех не более чем девятнадцатизначных чисел, но в общем случае это ничего не доказывает. Есть даже предположение, что проблема 3x+1 – одно из так называемых «недоказуемых» утверждений, существование которых следует из теоремы Гёделя о неполноте.

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

Чтобы не щёлкать калькулятором, можно сделать для вычислений таблицу в Excel'е. Создаём новый документ. В ячейку А1 будем вводить число, а в ячейку А2 введём формулу:
=ЕСЛИ(ОСТАТ(A1;2)=0;A1/2;3*A1+1)
В формуле проверяется чётность числа в ячейке А1 и в зависимости от исхода проверки оно либо делится на 2, либо утраивается и прибавляется единица. Затем эту формулу с помощью автозаполнения копируем в остальные ячейки столбца А (для начала можно в первые 200, а там по необходимости продлим). Таблица готова, можно начинать экспериментировать. Советую попробовать ввести число 27. После 77 шагов достигается рекордная для чисел первых пяти сотен отметка: 9232. Однако затем следует сокрушительный обвал – 4 уполовинивания подряд, и в конечном итоге, через 34 шага после пика мы опять-таки приходим к единице.

Однако чтобы анализировать большое количество данных лучше написать программу, что я, собственно, и сделал. Вы вводите, для какого количества натуральных чисел хотели бы получить статистику, и программа выдаёт для каждого наибольшее достигаемое значение и число шагов до единицы. Результаты находятся в файле results.txt.  Рекомендуется не вести расчёт больше чем для 50 миллионов чисел.

При анализе статистики также возникают интересные вопросы. К примеру, рассмотрим 7 последовательных чисел:

Число	Максимальное  достигнутое значение	Число шагов до единицы
943	9556	36
944	944	36
945	2836	36
946	1600	36
947	4264	36
948	948	36
949	2848	36

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

Если вы заинтересовались проблемой, стоит также прочитать следующие статьи:

Брайан Хэйес Взлёты и падения чисел-градин, Scientific American N 3 МАРТ 1984 – Несмотря на то, что прошло уже почти четверть века, статья по-прежнему актуальна. Автор рассказывает об истории проблемы, основных трудностях, связанных с ней, алгоритмах вычислений и попутно возникающих вопросах.
М. Л. Гервер Сиракузская последовательность – Автор рассматривает проблему 3x+1 совместно с 3x-1 проблемой, исследует закономерности в цепочках получаемых чисел.
Лебедев Ю.А. О некоторых эвереттических аспектах сиракузской последовательности ("3N+1"-проблемы в теории чисел) – Рассматриваются обобщённые проблемы вида nx+1.

Программа для вычисления наивысшего значения и количества шагов с исходниками на Delphi (600 кБ)
Документ Excel с вычислением цепочки чисел и со статистикой по первым 65536 числам (700 кБ)