?

Log in

No account? Create an account
09.Он же
Brenik brenik
Previous Entry Поделиться Next Entry
Проблема 3x+1. Задачу не могут решить уже 80 лет
Насколько сложной может быть задача, составленная на материале начальной школы: сложении, умножении, делении и чётности/нечётности числа?

Оказывается, более 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 шага после пика мы опять-таки приходим к единице.
Однако чтобы анализировать большое количество данных лучше написать программу, что я, собственно, и сделал. Вы вводите, для какого количества натуральных чисел хотели бы получить статистику, и программа выдаёт для каждого наибольшее достигаемое значение и число шагов до единицы. Рекомендуется не вести расчёт больше чем для 50 миллионов чисел.

При анализе статистики также возникают интересные вопросы.
Метки:

Записи из этого журнала по тегу «Задача»


promo brenik декабрь 31, 2016 23:09 60
Buy for 100 tokens

12345

Трудная задача. Ломал башню 5 минут. Как только на шаге х появится число, разложимое на 2^n - финита ля комеди клаб. Очевидно, что за бесконечное число шагов это будет происходить всегда. Премию Клея прошу отправить на яндекс-кошелек ;)