Brenik (brenik) wrote,
Brenik
brenik

Category:

Проблема 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 миллионов чисел.

При анализе статистики также возникают интересные вопросы.
Tags: Задача
Subscribe

Posts from This Journal “Задача” Tag

promo brenik december 31, 2016 23:09 60
Buy for 100 tokens
  • Post a new comment

    Error

    default userpic

    Your IP address will be recorded 

    When you submit the form an invisible reCAPTCHA check will be performed.
    You must follow the Privacy Policy and Google Terms of use.
  • 1 comment