Математические головоломки профессора Стюарта

Бóльшая часть вычислительных усилий при этом приходится на операцию деления, так что мы можем оценить эффективность алгоритма, подсчитав, сколько раз производится эта операция. Первым этот вопрос исследовал Антуан Рейно, в 1911 г. он доказал, что число операций деления в процедуре поиска НОД составляет максимум m, то есть не превышает меньшего из двух чисел. Это очень грубая оценка, и позже Рейно снизил ее до m/2 + 2, что ненамного лучше. В 1841 г. П. Финк снизил эту оценку до 2 log₂ m + 1, что пропорционально числу десятичных знаков в m. В 1844 г. Габриель Ламе доказал, что число операций деления не более чем в пять раз превосходит число десятичных знаков в m. Так что даже для двух чисел по 100 знаков каждое алгоритм позволяет получить ответ не более чем за 500 шагов. В целом можно сказать, что сделать это так же быстро с использованием простых множителей невозможно.

Что представляет собой наихудший сценарий? Ламе доказал, что алгоритм выполняется медленнее всего в том случае, когда m и n являются последовательными членами ряда Фибоначчи

1 1 2 3 5 8 13 21 34 55 89…,

в котором каждое следующее число представляет собой сумму двух предыдущих. Для этих чисел на каждом шаге от прямоугольника отсекается ровно один квадрат. К примеру, при m = 34, n = 55 получаем

деление 55 на 34 дает 1, остаток 21;

деление 34 на 21 дает 1, остаток 13;

деление 21 на 13 дает 1, остаток 8;

деление 13 на 8 дает 1, остаток 5;

деление 8 на 5 дает 1, остаток 3;

деление 5 на 3 дает 1, остаток 2;

деление 3 на 2 дает 1, остаток 1;

деление 2 на 1 дает 1 ровно.

Необычайно длинный расчет для таких небольших чисел.

Математики проанализировали также среднее число операций деления. При фиксированном n число таких операций, усредненное по всем меньшим m, составляет примерно

где C – так называемая постоянная Портера, равная

Здесь ζ'(2) – оценка производной от римановой дзета-функции в точке 2, а γ – постоянная Эйлера, равная 0,577. Было бы трудно найти разумную задачу, при решении которой в одной формуле собирается более представительная выборка математических констант. Отношение вычисленного по этой формуле значения к точному ответу стремится к 1 по мере возрастания n.

123456789 раз по X

Иногда самые простые идеи приводят к загадочным результатам. Попробуйте умножить 123456789 на 1, 2, 3, 4, 5, 6, 7, 8 и 9. Что вы заметили? Когда закономерность перестает работать?

Ответы см. в главе «Загадки разгаданные». Расширение темы в главе «123456789 раз по X. Продолжение».

Знак одного. Часть третья Из мемуаров доктора Ватсапа

Горы бумаг, испещренных загадочными письменами, росли как грибы на всех горизонтальных поверхностях обиталища Сомса. В этом, как вы понимаете, ничего необычного не было; миссис Сопсудс часто и притом совершенно безрезультатно ругала его за способ хранения бумаг, больше напоминающий глубокие залежи мусора. Но на этот раз каракули на листах представляли собой результаты суммирования.

– Я могу получить 8 из двух единиц, не прибегая к помощи гипотетического выражения для 7, – объявил я. – Вот так:

Но даже под угрозой смерти я не в состоянии получить 7.

– Действительно, это число, судя по всему, является камнем преткновения, – согласился со мной Сомс. – Но ваш результат позволяет нам продвинуться и другими способами:

где, разумеется, вместо восьмерки мы при необходимости подставляем ваше выражение. Я мог бы расписать это выражение полностью…

– Нет-нет, Сомс, вы меня убедили!

– Но теперь у нас образовалось еще две лакуны на 12 и 13. Однако, Ватсап, я подозреваю, что эти проблемы взаимосвязаны. Так, посмотрим… Ну да,

а 15 на основе двух единиц у нас уже есть. Тогда

и далее

и, наконец,

что вполне удовлетворительно решает нашу проблему. Таким образом, подставляя по очереди выражения для всех использованных чисел, получаем, что

– Мне невыносимо стыдно, что я не увидел этого сразу.

– Неужели это простейшее решение, Сомс? – вопросил я, проглотив комок в горле. – Надеюсь, что нет!

– Понятия не имею. Возможно, кто-то изобретательный смог бы придумать что-нибудь получше. В подобных вещах трудно сказать наверняка. Я уверен, что тот, кто сумеет превзойти наши слабые усилия, немедленно известит нас телеграммой.

– Во всяком случае, – сказал я, – если нам удастся выразить какое-то целое число при помощи двух единиц, то теперь мы сможем выразить при помощи четырех единиц все числа в диапазоне от n – 17 до n + 17.

– Вот именно, Ватсап. Наша задача упрощается с каждой минутой. Все, что нам нужно, – это последовательность чисел, каждое из которых превосходит предыдущее не более чем на 35, так, чтобы эти интервалы с двух сторон перекрывали пробел. Это позволит нам добраться до наибольшего из таких чисел плюс 17.

– Что означает… – начал я…

– Что мы должны действовать систематически!

– Именно.

– Мы уже добрались… напомните мне, Ватсап. Загляните в свои обширные записи.