Короче говоря, каракули сообщают нам вот что:
при делении 17 на 5 получается 3 с остатком 2;
при делении 5 на 2 получается 2 с остатком 1;
2 делится на 1 нацело с нулевым остатком,
а процесс останавливается, как только остаток становится равным нулю.
Евклид использовал подобные каракули для решения одной арифметической задачи: поиска наибольшего общего делителя для двух заданных целых чисел. Наибольший общий делитель – это наибольшее целое число, на которое оба заданных числа делятся нацело; его часто обозначают аббревиатурой НОД. К примеру, для чисел 4500 и 840 НОД равен 120.
Меня в школе учили искать НОД таким способом: разложить заданные числа на простые множители и посмотреть, какие множители у них окажутся общими. К примеру, пусть нам надо найти НОД чисел 68 и 20.
Раскладываем то и другое на простые множители:
68 = 2²× 17; 20 = 2²× 5.
НОД равен 2² = 4.
Применимость этого метода ограничена тем, что числа должны быть достаточно небольшими, чтобы их можно было быстро разложить на простые множители. Для более крупных чисел он совершенно неэффективен. Древние греки знали более эффективный способ – процедуру, которой они дали забавное название антифарезис. В данном случае ее применение выглядит так:
68 делим на 20, получаем 3 с остатком 8;
20 делим на 8, получаем 2 с остатком 4;
8 делим на 4, получаем 2 ровно.
Стоп!
Это тот же расчет, что мы проделали для 17 и 5, но теперь все числа вчетверо больше (но делятся они друг на друга столько же раз). Если вы расчертите прямоугольник 68 × 20 каракулями, то картинка получится та же, что и в прошлый раз, только последний маленький квадратик будет иметь размер 4 × 4, а не 1 × 1.
Техническое название этого метода – алгоритм Евклида. Вообще, алгоритм – это рецепт для расчета. Евклид поместил такой рецепт в свои «Начала» и использовал его в качестве основы для теории простых чисел. В символьном виде алгоритм каракулей выглядит так. Возьмем два положительных целых числа m£n. Начнем с пары (m, n) и заменим ее парой (m, n – m) в порядке величин, начиная с меньшего: то есть преобразуем
(m, n) → (min (m, n – m), max (m, n – m)),
где min и max обозначают, соответственно, минимум и максимум. Повторим процедуру. На каждом шаге большее число пары уменьшается, так что в конечном итоге процесс завершается, к примеру, парой (0, h). Тогда h и есть искомое НОД. Доказательство несложно: любой делитель m и n является также делителем (n – m) и наоборот. Поэтому на каждом шаге НОД обоих чисел пары не меняется.
Этот метод по-настоящему эффективен: с его помощью можно вычислять НОД вручную для действительно больших чисел. Чтобы доказать это, вот вам задание. Найдите НОД чисел 44 758 272 401 и 13 164 197 765.
Ответ в главе «Загадки разгаданные».
Евклидова эффективность
Насколько эффективен алгоритм Евклида?
Отсекание по одному квадрату за раз проще для теоретических целей, но более компактная форма в терминах деления с остатком лучше подходит для практического использования. При этом вся работа с квадратами одного размера сокращается до одной операции.
Бóльшая часть вычислительных усилий при этом приходится на операцию деления, так что мы можем оценить эффективность алгоритма, подсчитав, сколько раз производится эта операция. Первым этот вопрос исследовал Антуан Рейно, в 1911 г. он доказал, что число операций деления в процедуре поиска НОД составляет максимум m, то есть не превышает меньшего из двух чисел. Это очень грубая оценка, и позже Рейно снизил ее до m/2 + 2, что ненамного лучше. В 1841 г. П. Финк снизил эту оценку до 2 log2 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.
– Во всяком случае, – сказал я, – если нам удастся выразить какое-то целое число при помощи двух единиц, то теперь мы сможем выразить при помощи четырех единиц все числа в диапазоне от n – 17 до n + 17.
– Вот именно, Ватсап. Наша задача упрощается с каждой минутой. Все, что нам нужно, – это последовательность чисел, каждое из которых превосходит предыдущее не более чем на 35, так, чтобы эти интервалы с двух сторон перекрывали пробел. Это позволит нам добраться до наибольшего из таких чисел плюс 17.
– Что означает… – начал я…
– Что мы должны действовать систематически!
– Именно.
– Мы уже добрались… напомните мне, Ватсап. Загляните в свои обширные записи.
Я с головой зарылся в несколько высоких бумажных башен и в конце концов отыскал свой блокнот под чучелом какого-то скунса.
– Мы дошли до 32, Сомс, если учесть замечание, которое вы мимоходом сделали во время поиска выражения для 7.
– И разумеется,
– сказал он. – Очень хорошо. Таким образом, в идеале нам нужно выразить числа 68, 103, 138 и т. д. через две единицы. Но мы можем пользоваться при этом готовыми выражениями для маленьких чисел, если так будет удобнее. Лишь бы разница между двумя соседними числами не была больше 35.
Несколько часов усиленных расчетов – и новые кипы бумаги – дали нам короткий, но важный список:
Но на этом все и застопорилось.
– Возможно, я слишком поспешно отказался от использования двойных факториалов, Ватсап.
– Очень может быть, Сомс.
Сомс кивнул и записал:
105 = 7!!
Затем, в порыве внезапного озарения, добавил:
И воскликнул:
– Если нам удастся найти способ записать 18 при помощи двух единиц, то доступный нам диапазон вокруг целого числа, выражаемого через две единицы, увеличится: мы тогда сможем гарантировать число от n – 20 до n + 20, – он прервался, чтобы перевести дух, и добавил: – Если же нет, то пропущенными в этом диапазоне окажутся только числа n – 18 и n + 18, которые нам, может быть, удастся выразить как-то иначе.
– Мне кажется, пора подвести промежуточный итог, – сказал я и еще раз внимательно просмотрел наши накопившиеся каракули. – По-моему, мы уже выразили через четыре единицы все числа от 1 до 33. Далее
требуют только двух единиц, так что мы немедленно заполняем все пропуски между 26 и 61. Возникает пробел на 62 (потому что это 44 + 18, а на выражении 18 через две единицы мы застряли), но 63 и 64 у нас есть. Далее, опираясь на 80, мы можем добраться до 97. На 98 опять возникает пробел, но 99 и 100 можно получить.
– И намного проще, кстати говоря, – заметил Сомс:
99 = 11/0,1 × 0,1;
100 = 1/(0,1 × 0,1);
101 = 1/(0,1 × 0,1) + 1.
– Таким образом, у нас есть все вплоть до 100, – сказал я, – за исключением 62 и 98.
– Но о 98 позаботится 105, вместе со всеми остальными числами вплоть до 122, – сказал Сомс.
– О, я и забыл, что у нас есть 105 из двух единиц.
– А поскольку 120 = 5! то есть тоже выражается через две единицы, мы можем добраться до 137. Более того, у нас есть еще 139 и 140.
– Так что единственные пробелы до 140 – это 62 и 138, – сказал я.
– Похоже на то, – сказал Сомс. – Интересно, можно ли заполнить эти пробелы каким-то другим способом?
Сможете ли вы найти способ записать 62 и 138 при помощи четырех единиц, не используя ничего более эзотерического, чем те функции, которые Сомс и Ватсап уже использовали? Ответ см. в главе «Загадки разгаданные».
Сомс и Ватсап все еще не закончили. Но финал уже близок: «Знак одного» завершается в главе «Знак одного. Часть четвертая – завершение».
Номера такси
Сриниваса Рамануджан – индийский математик-самоучка с поразительным талантом к формулам, как правило очень странным формулам, обладавшим, однако, своеобразной необычной красотой. В 1914 г. математики Годфри Харолд Харди и Джон Эденсор Литтлвуд из Кембриджа привезли его в Англию. К 1919 г. у него уже были неизлечимо больные легкие, и в 1920 г. он умер в Индии. Харди писал:
«Помню, как я однажды поехал навестить его, когда он лежал больной в Путни. Я приехал в такси номер 1729 и заметил вскользь, что номер этот показался мне довольно скучным и что я надеюсь, что это не дурное предзнаменование. „Нет, – ответил он, – это очень интересный номер; это наименьшее число, которое можно выразить в виде суммы двух [положительных] кубов двумя разными способами“».
Наблюдение о том, что
1729 = 1³ + 12³ = 9³ + 10³,
впервые опубликовал Бернар Френикль де Бесси в 1657 г. Если разрешить отрицательные кубы, то наименьшим таким числом будет
91 = 6³ + (–5)³ = 4³ + 3³.
Специалисты по теории чисел обобщили эту концепцию, заявив, что n-й номер такси Ta (n) есть наименьшее число, которое можно выразить в виде суммы двух положительных кубов n и другими способами.
В 1979 г. Харди и Э. М. Райт доказали, что некоторые числа могут быть выражены в виде суммы произвольно большого числа положительных кубов, так что Ta (n) существует для любых n. Однако вплоть до настоящего времени известны лишь первые шесть таких чисел:
Ta (1) = 2 = 1³ + 13;
Ta (2) = 1729 = 1³ + 12³ = 9³ + 10³;
Ta (3) = 87539319 = 167³ + 436³ = 228³ + 423³ = 255³ + 414³;
Ta (4) = 6963472309248 = 2421³ + 19083³ = 54363 + 18948³ = 10200³ + 18072³ = 13322³ + 166308³;
Ta (5) = 48988659276962496 = 38787³ + 3657573 = 107839³ + 362753³ = 205292³ + 342952³ = 221424³ + 336588³ = 231518³ + 331954³;
Ta (6) = 24153319581254312065344 = 582162³ + 28906206³ = 3064173³ + 28894803³ = 8519281³ + 28657487³ = 16218068³ + 27093208³ = 17492496³ + 26590452³ = 18289922³ + 26224366³.
Ta (3) открыл Джон Лич в 1957 г. Ta (4) нашли Э. Розенстил, Дж. А. Дардис и К. Р. Розенстил в 1991 г. Ta (5) обнаружил Дж. А. Дардис в 1994 г. и подтвердил Дэвид Уилсон в 1999 г. В 2003 г. К. С. Калуд, Э. Калуд и М. Дж. Диннин установили, что приведенное выше число, вероятно, является Ta (6), а в 2008 г. Уве Холлербах опубликовал доказательство.
Волна перемещения
Математические исследования верхом?
Почему бы нет? Вдохновение может осенить где угодно. Выбирать не приходится.
В 1834 г. шотландский инженер-кораблестроитель Джон Скотт Рассел, ехавший на лошади вдоль канала, обратил внимание на поразительное явление:
«Я наблюдал за движением лодки, которую стремительно тянула по узкому каналу пара лошадей, как вдруг лодка остановилась – лодка, но не та масса воды в канале, которую она увлекла и приводила в движение; эта вода собралась вокруг носа судна в состоянии неистового возбуждения, затем внезапно оторвалась от него и покатилась вперед с огромной скоростью, принимая форму большого одиночного возвышения, округлой, гладкой и четко очерченной водяной массы, которая продолжила движение вдоль канала без всякого видимого изменения формы или снижения скорости. Я последовал за ней верхом и догнал; она катилась дальше со скоростью примерно 13 или 15 км/ч, сохраняя первоначальную форму, размером около 9 м в длину и 30–45 см в высоту. Ее высота постепенно снижалась, и после преследования на протяжении 1,5–3 км я потерял ее среди извивов канала. Вот такой в августе 1834 г. была моя первая случайная встреча с этим исключительным и красивым явлением, которое я назвал волной перемещения».
Рассела заинтриговало это явление, поскольку обычно одиночные волны расходятся в стороны по мере движения или рассыпаются, как прибой на пляже. Он соорудил дома волновой бассейн и провел серию экспериментов. В ходе испытаний выяснилось, что такая волна очень устойчива и может пройти большое расстояние, не меняя формы. Волны разных размеров движутся с разными скоростями. Если одна такая волна догоняет другую, она выходит вперед после сложного взаимодействия. А большая волна на мелководье разделяется на две – среднюю и маленькую.
Эти открытия поставили физиков того времени в тупик, потому что совершенно не поддавались объяснению с позиции тогдашних взглядов на поведение жидкостей. Более того, видный астроном Джордж Эйри и ведущий специалист по динамике жидкостей Джордж Стокс долго не верили, что такая волна существует. Сегодня мы знаем, что Рассел был прав. В некоторых обстоятельствах нелинейные эффекты, неизвестные математикам того времени, компенсируют тенденцию всякой волны к расхождению, потому что скорость движения волны зависит от частоты колебаний. В этих эффектах первыми разобрались лорд Рэлей и Жозеф Буссинеск примерно в 1870 г.
В 1895 г. Дидерик Кортевег и Густав де Врис предложили уравнение Кортевега – де Вриса, в которое вошли подобные эффекты, и показали, что у него есть обособленные (солитарные) волновые решения. Аналогичные результаты были получены для других уравнений математической физики, и феномен получил новое название: солитон. Серия крупных открытий позволила Питеру Лаксу сформулировать очень общие условия, при которых уравнения имеют обособленные решения, и объяснить эффект туннелирования. Математически этот процесс сильно отличается от того, как взаимодействуют мелководные волны, к примеру, на пруду, когда их формы складываются; все это – прямое следствие математической формы волнового уравнения. Солитоноподобные явления наблюдают во многих областях науки – от ДНК до волоконной оптики. Именно этим объясняется существование широкого спектра явлений со странными названиями вроде «бризер», «кинк» и «осциллон».