замат
Умник
 Offline
Сообщений: 548
СПАСИБО
-вы поблагодарили: 572
-вас поблагодарили: 520
Необходимость не знает закона
|
 |
� Ответ #135 : Апрель 07, 2012, 13:24:54 � |
|
Насколько сложной может быть задача, составленная на материале начальной школы: сложении, умножении, делении и чётности/нечётности числа?
Оказывается, более 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 шагов?
|
