Математические головоломки профессора Стюарта Стюарт Иэн
(Dorin Andrica, 1986).
Имран Гори использовал данные о наибольших промежутках между простыми числами, чтобы подтвердить эту гипотезу для n вплоть до 1,3002 1016. На рисунке вы можете видеть зависимость (pn+1) – pn от n для первых 200 простых чисел. Число 1 располагается в самом верху вертикальной оси, а все остальные пики, показанные на графике, – ниже. Они явно уменьшаются с увеличением n, но мы не можем быть уверены, что на каком-то очень большом n не наблюдается гигантский пик, превосходящий 1. Чтобы данная гипотеза оказалась ошибочной, где-то должен существовать особенно большой промежуток между двумя очень большими последовательными простыми числами. Это представляется весьма маловероятным, но и полностью исключить такой вариант пока невозможно.
Любое целое число a, не равное 1 и не являющееся полным квадратом, есть первообразный корень по модулю бесконечного числа простых чисел. То есть всякое число от 1 до p 1 есть некая степень a минус некое число, кратное p. Существуют конкретные формулы для количественного соотношения таких простых чисел по мере их увеличения (Emil Artin, 1927).
При n > 1 существует по крайней мере четыре простых числа между p и pn+1 (Henri Brocard, 1904). Ожидается, что это верно; более того, по идее должны быть верны куда более сильные утверждения.
Промежуток pn+1 pn между последовательными простыми числами для больших n не превосходит (ln pn) с постоянным коэффициентом (Harald Cramr, 1936).
Крамер доказал аналогичное утверждение, в котором вместо (ln pn) фигурирует при условии что верна гипотеза Римана – возможно, самая важная нерешенная проблема математики (см. «Кабинет…»).
Величина строго уменьшается (Farideh Firoozbakht, 1982 г.). Это означает, что для любого n. Это утверждение верно для всех целых чисел вплоть до 4 1018.
Пусть 2 (x) обозначает число простых чисел p x, таких, что p + 2 такж простое число. Определим постоянную простых чисел-близнецов
(где символ П указывает на произведение по всем простым числам p 3). Тогда гипотеза заключается в том, что
где знак ~ означает, что данное отношение стремится к 1 по мере того, как n становится сколь угодно большим (Godfrey Harold Hardy and John Edensor Littlewood, 1923).
Существует также вторая гипотеза Харди – Литтлвуда (см. ниже).
Начнем с простых чисел
2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, …
и вычислим разницу между соседними членами последовательности:
1, 2, 2, 4, 2, 4, 2, 4, 6, 2, …
Повторим те же вычисления для новой последовательности, не обращая внимания на знак, и продолжим в том же духе. Пять первых последовательностей будут выглядеть следующим образом:
1, 0, 2, 2, 2, 2, 2, 2, 4, …
1, 2, 0, 0, 0, 0, 0, 2, …
1, 2, 0, 0, 0, 0, 2, …
1, 2, 0, 0, 0, 2, …
1, 2, 0, 0, 2, …
Гилбрейт и Прот предположили, что первым членом каждой из этих последовательностей всегда будет 1, сколько бы раз мы ни повторяли процедуру (Norman Gilbreath, 1958, Franois Proth, 1978).
В 1993 г. Эндрю Одлизко проверил эту гипотезу для первых 3,4 1011 последовательностей.
Всякое четное целое число, большее 2, можно выразить как сумму двух простых чисел (Christian Goldbach, 1742).
Т. Оливейра-и-Силва проверил эту гипотезу на компьютере для n 1,609 1018.
Каждому элементу множества последовательных составных чисел можно поставить в соответствие отдельное простое число, которое является его делителем (C. A. Grimm, 1969).
К примеру, если взять составные числа 32, 33, 34, 35, 36, то им можно поставить в соответствие простые числа 2, 11, 17, 5, 3.
В 1912 г. Эдмунд Ландау перечислил четыре фундаментальные проблемы, связанные с простыми числами и известные в настоящее время как проблемы Ландау. Первые три – это гипотеза Гольдбаха (см. выше), гипотеза о простых числах-близнецах (см. ниже) и гипотеза Лежандра (см. ниже). Четвертая проблема выглядит так: существует ли бесконечно много простых чисел p, таких что p 1 является полным квадратом? То есть p = x + 1 для целого x.
Вот первые несколько таких чисел: 2, 5, 17, 37, 101, 197, 257, 401, 577, 677, 1297, 3137, 4357, 5477, 7057, 8101, 8837, 12 101, 13 457, 14 401 и 15 377. А вот пример побольше (но ни в коем случае не самый большой):
p = 1, 524, 157, 875, 323, 883, 675, 049, 535, 156, 256, 668, 194, 500, 533, 455, 762, 536, 198, 787, 501, 905, 199, 875, 019, 052, 101
x = 1, 234, 567, 890, 123, 456, 789, 012, 345, 678, 901, 234, 567, 890.
В 1997 г. Джон Фридлендер и Хенрик Иванец доказали, что существует бесконечно много простых чисел вида x2 + y4 для целых x, y. Первые из этого ряда: 2, 5, 17, 37, 41, 97, 101, 137, 181, 197, 241, 257, 277, 281, 337, 401 и 457. Иванец доказал, что существует бесконечно много чисел вида x + 1, имеющих не более двух простых множителей.
Близко, но не то.
Адриан-Мари Лежандр предположил, что для любого положительного n существует простое число, лежащее между n и (n + 1). Это утверждение могло бы быть следствием из гипотезы Андрики (см. выше) и гипотезы Опперманна (см. ниже). Из гипотезы Крамера (см. выше) следует, что гипотеза Лежандра верна для всех достаточно больших чисел. Известно, что она верна вплоть до 1018.
Все нечетные целые числа, большие 5, могут быть представлены как сумма нечетного простого числа и удвоенного простого числа (mile Lemoine, 1894, Hyman Levy, 1963).
Д. Корбитт подтвердил эту гипотезу вплоть до 109.
В 1644 г. Марен Мерсенн объявил, что числа 2n – 1 являются простыми для n = 2, 3, 5, 7, 13, 17, 19, 31, 67, 127 и 257 и составными для всех остальных положительных целых n<257. Позже было показано, что Мерсенн допустил пять ошибок: n = 67 и 257 дают составные числа, а n = 61, 89, 107 дают простые. Гипотеза Мерсенна привела к созданию новой гипотезы Мерсенна и гипотезы Ленстры – Померанца – Вагстаффа, которые значатся в нашем перечне следующими.
Для любого нечетного p если выполняются любые два из следующих условий, то выполняется и третье:
1. p = 2k ± 1 или p = 4k ± 3 для некоторого натурального числа k;
2. число 2p 1 – простое (простое Мерсенна);
3. число (2p + 1)/3 – простое (простое Вагстаффа).
(Paul Bateman, John Selfridge and Samuel Wagstaff Jr., 1989)
Существует бесконечное число простых Мерсенна, причем число простых Мерсенна, меньших x, приблизительно равно e ln ln x/ln 2, где – постоянная Эйлера, приблизительно равная 0,577 (Hendrik Lenstra, Carl Pomerance and Samuel Wagstaff Jr., не опубликовано).
Для любого целого числа n>1 существует по крайней мере одно простое число между n (n – 1) и n и по крайней мере еще одно простое число между n и n (n + 1) (Ludvig Henrik Ferdinand Oppermann, 1882).
Для любого положительного четного n существует бесконечное число пар последовательных простых чисел с разницей в n (Alphonsede Polignac, 1849).
Для n = 2 это утверждение соответствует гипотезе о простых числах-близнецах (см. ниже). Для n = 4 она означает, что существует бесконечно много пар «двоюродных простых чисел» (p, p + 4). Для n = 6 она означает, что существует бесконечно много пар простых чисел (p, p + 6), известных как sexy (от латинского названия числа 6); при этом между числами p и p + 6 простых чисел нет.
Всякий интервал [xm, yn] (то есть любое множество чисел от xm до yn) содержит по крайней мере одно простое число, за исключением [2, 3], [5, 3], [25, 6], [11, 5], [37, 13], [55, 56], [181, 215], [43, 282], [46, 312], [22434, 555] (Stephen Redmond and Zhi-Wei Sun, 2006).
Эта гипотеза подтверждена для всех интервалов [xm, yn] до 10.
Если (x) есть число простых чисел вплоть до x, включая x, то (x + y) (x) + (y) для x, y 2 (Godfry Harold Hardy and John Littlewood, 1923).
Существуют технические соображения, согласно которым можно ожидать, что это предположение окажется ложным, но первое нарушение возникнет, скорее всего, при очень больших величинах x, вероятно, больших, чем 1,5 10174, но меньших, чем 2,2 101198.
Существует бесконечно много простых чисел p, таких, что число p + 2 тоже простое.
25 декабря 2011 г. PrimeGrid – «проект распределенных вычислений», в котором используются свободные ресурсы на компьютерах добровольцев, пожелавших принять в нем участие, объявил наибольшую известную на сегодняшний день пару простых чисел-близнецов:
3 756 801 695 685 2666 669 ± 1.
Каждое из этих чисел содержит 200 700 знаков.
В интервале до 1018 содержится 808 675 888 577 436 пар простых чисел-близнецов.
Оптимальная пирамида
Стоит подумать о Древнем Египте, и в голову сразу же приходят пирамиды, в первую очередь Великая пирамида Хеопса в Гизе, самая большая из всех, и стоящая рядом с ней пирамида Хефрена, чуть поменьше, и относительно небольшая пирамида Микерина. Известны остатки более чем 36 крупных и сотен более мелких египетских пирамид – от громадных и почти полностью сохранившихся до простых отверстий в земле, содержащих лишь несколько обломков камня от погребальной камеры, а иногда и того меньше.
О форме, размерах и ориентации пирамид написаны огромные тома. Большая часть их содержимого умозрительна; на основе различных численных соотношений выстраиваются весьма амбициозные цепочки рассуждений. Особенно любят исследователи Великую пирамиду: с чем только ее ни связывали – и с золотым сечением, и с числом , и даже со скоростью света. К подобным рассуждениям возникает столько вопросов, что трудно воспринимать их серьезно: в любом случае данные, на которых они основаны, часто неточны; к тому же с таким количеством измерений и параметров всегда можно подобрать нужную комбинацию.
Один из лучших источников по пирамидам – книга The Complete Pyramids Марка Ленера. Помимо прочего в ней можно найти данные о наклоне граней пирамид: углы между плоскостями, проходящими через треугольные грани, и квадратным основанием пирамиды. Вот несколько примеров:
Более обширные данные вы можете найти на сайте http://ru.wikipedia.org/wiki/Список_египетских_пирамид
На ум приходят два наблюдения. Первое состоит в том, что приводить некоторые из этих углов с точностью до угловой секунды (а остальные до минуты) неразумно. Сторона основания Черной пирамиды Аменемхета III в Дашуре составляет 105 м, а высота – 75 м. Изменение угла наклона грани пирамиды на одну угловую секунду соответствует изменению высоты пирамиды на один миллиметр. Правда, следы ребер основания сохранились, как и некоторые фрагменты камней облицовки, но, учитывая общую степень сохранности пирамиды, вам трудно было бы оценить первоначальный наклон ее граней в пределах хотя бы 5° от истинной величины.
Второе, на что невольно обращаешь внимание, – это тот факт, что, хотя наклон граней пирамид немного варьируется (иногда даже в пределах одной пирамиды, как, к примеру, у Ломаной), у всех этих древних сооружений он близок к 54°. Почему?
В 1979 г. Р. Макмиллан[17] начал с того надежно установленного факта, что строители пирамид использовали для отделки своих сооружений с внешней стороны дорогостоящий облицовочный камень, к примеру белый турский известняк или гранит. Внутри они использовали более дешевые материалы: низкокачественный мокаттамский известняк, саманный кирпич и щебенку. Поэтому для них имело смысл всячески снижать количество каменной облицовки. Какой формы должна быть пирамида, если фараон желает, чтобы при заданной стоимости облицовочного камня монумент получился как можно больше? То есть какой угол наклона граней пирамиды к основанию позволяет получить максимальный объем при фиксированной суммарной площади четырех треугольных граней?
Вообще-то это прекрасное упражнение из области дифференциального исчисления, но эту задачу можно решить и проще, геометрически, если применить хитрый прием. Разрежем пирамиду пополам вертикальной плоскостью, проходящей через диагональ основания (серый треугольник). Получаем равнобедренный треугольник. Объем получившейся полупирамиды пропорционален площади этого треугольника, а площади наклонных граней полупирамиды пропорциональны длинам его соответствующих сторон. Поэтому задача эквивалентна поиску равнобедренного треугольника максимальной площади при фиксированной длине двух равных его сторон.
Зеркально отобразив треугольник относительно основания, получим, что наша задача эквивалентна поиску ромба максимальной площади при заданной длине стороны. Решением является квадрат (ориентированный диагональю по вертикали). Следовательно, углы при вершине каждой треугольной секции такого рода составляют 90°, а углы при основании – по 45°. Базовая тригонометрия подсказывает, что угол наклона грани пирамиды при этом равен
arctg 2 = 54°44,
что близко к средней величине наклона грани у настоящих пирамид.
Макмиллан ничего не утверждает в отношении того, что говорят приведенные им расчеты о строительстве пирамид; его основная мысль заключается в том, что эта задача – показательный пример практического владения геометрией. Однако в Московском математическом папирусе приводится правило нахождения объема усеченной пирамиды (то есть пирамиды со срезанной верхушкой) и задача, из которой явствует, что египтяне понимали подобие. В нем объясняется также, как найти высоту пирамиды по ее основанию и наклону. Более того, и в этом папирусе, и в математическом папирусе Ринда объясняется, как найти площадь треугольника. Так что древнеегипетские математики вполне могли решить задачу Макмиллана.
Поскольку папируса, в котором содержался бы именно этот расчет, в нашем распоряжении нет, то нет и убедительных причин полагать, что эта задача действительно была решена в Древнем Египте. У нас нет никаких свидетельств того, что египтяне были заинтересованы в оптимизации формы своих пирамид. И даже если были, они вполне могли определить оптимальную форму экспериментально, при помощи глиняных моделей. Или просто произвести эмпирическую оценку. А может быть, форма постепенно эволюционировала в направлении наименьшей стоимости: строители и фараоны, они такие. В альтернативном варианте угол наклона грани мог определяться инженерными соображениями: считается, скажем, что необычная форма Ломаной пирамиды объясняется тем, что на середине строительства она начала разваливаться и строителям пришлось уменьшить крутизну граней. Тем не менее можно с уверенностью заявить, что этот небольшой математический пример имеет более непосредственное отношение к пирамидам, чем, скажем, скорость света.
Знак одного: часть вторая
Из мемуаров доктора Ватсапа
Сомс начал, как одержимый, расхаживать по комнате из угла в угол. Внутренне я громко кричал «Ура!», поскольку ясно видел, что он попался на крючок. Теперь я мог спокойно «вываживать» его, чтобы вывести из черной депрессии, в которую он умудрился впасть, и заодно избавить себя от боливийских погребальных напевов.
– Мы должны действовать систематически, Ватсап! – объявил он.
– Каким образом, Сомс?
– Более систематическим образом, Ватсап, – воцарившееся молчание заставило его поубавить загадочности. – Мы должны составить список небольших чисел, которые можно получить с использованием всего лишь двух единиц. Соединяя их, мы сможем… ну, я уверен, через минуту вы все поймете.
После этого Сомс записал:
На этом этапе Сомса заклинило.
– Признаюсь, 7 и 8 пока не даются мне, на их местах останутся лакуны, – сказал он. – Но это не важно, позвольте мне продолжить:
9 = 1/0,(1)
10 = 1/0,1
11 = 11.
– Признаюсь, я пока не…
– Будьте уверены, Ватсап, вы все поймете. Предположим, для обобщения, что мы придумали, как выразить 7 и 8 при помощи двух единиц. Тогда в нашем распоряжении окажутся все числа от 0 до 11. Теперь в случае, если некое число n можно выразить при помощи двух едини, мы получим возможность выразить все числа между n – 11 и n + 11 при помощи всех четырех единиц – просто вычитая или складывая выражения из моего систематического списка.
– Ах, теперь я понял, – сказал я.
– Обычно вам это удается, после того как я вам расскажу, – саркастически отозвался он.
– Тогда позвольте мне кое-что добавить, чтобы показать, что я и правда понял! Поскольку мы знаем, как выразить 24 при помощи двух единиц, к примеру, как мы мгновенно получаем возможность выразить все числа от 24–11 до 24 + 11 при помощи четырех единиц. Это значит, что мы получаем все числа в диапазоне от 13 до 35 включительно.
– Вот именно! Думаю, записывать это не обязательно.
– Да, наверное. Ага! Мы можем пойти еще дальше! Взгляните:
– Да, – ответил он. – Однако, пока энтузиазм не унес вас в несказанные дали, я напомню, что у нас пока нет выражений для 7 и 8 с использованием только двух единиц.
Я принял подобающе удрученный вид. Но затем меня осенила дикая мысль.
– Сомс? – спросил я нерешительно.
– Да?
– Факториалы делают числа больше?
Он раздраженно кивнул.
– А извлечение квадратного корня делает их меньше, так?
– Согласен. Переходите же к делу!
– А операции округления в пол и в потолок вновь делают числа целыми?
Я видел, как на его лице медленно проступает понимание.
– Браво, Ватсап! Да, теперь понятно. Мы знаем, к примеру, как выразить 24 при помощи двух единиц. Следовательно, мы можем также выразить 24! При помощи все тех же двух единиц, а это будет… – его брови сошлись к переносице – 620 448 401 733 239 439 360 000. А корень квадратный из этого числа, – его лицо покраснело от напряжения, пока он производил в уме соответствующие расчеты, – равен 887 516,46; еще раз извлечем квадратный корень, получим 942,08; а еще раз – 30,69.
– Так что мы можем выразить 30 и 31 с использованием всего лишь двух единиц, – сказал я. – А именно:
– Ни то ни другое, разумеется, не помогает нам выразить 7 и 8 через две единицы, но если бы мы могли это сделать, то расширили бы диапазон наших чисел до 31 + 1, то есть до 42. И все это говорит о том, что нам, как вы столь убедительно сказали, Сомс, следует действовать систематически. Я предлагаю теперь исследовать многократное извлечение квадратного корня из факториала чисел, которые мы можем выразить через две единицы.
– Согласен! И совершенно очевидно, – заявил тут же Сомс, – что такое выражение для 7 сразу же даст нам выражение для 8.
– Э-э… правда?
– Естественно. Поскольку 7! = 5040, квадратный корень из этого числа равен 70,99, а следующий квадратный корень равен 8,42, мы делаем вывод, что
– Так что не впервые в истории человечества ключом к загадке является число 7! (В этих словах, дорогой читатель, он подчеркивал число 7 восклицательным знаком, а не имел в виду факториал. Пожалуйста, обратите на это внимание, я об этом уже упоминал.)
Сомс нахмурился.
– Я могу сделать это, если использую двойной факториал.
– Вы имеете в виду факториал факториала?
– Нет.
– Субфакториал? Вы пока не объяснили…
– Нет. Двойной факториал – это немного запутанная штука; он равен
n!! = n (n – 2) (n – 4) … 4 2
для четных n и n!! = n (n – 2) (n – 4) … 3 1
для нечетных. Так, к примеру,
6!! = 6 4 2 = 48.
Корень квадратный из этого числа равен 6,82, а его потолок равен 7.
Я послушно записал:
Но Сомс по-прежнему выглядел недовольным.
– Проблема в том, Ватсап, что при помощи введения все более загадочных и вычурных арифметических функций можно с легкостью выразить вообще любое число. К примеру, мы могли бы воспользоваться арифметикой Пеано.
Я шумно запротестовал:
– Сомс, вы же знаете, что наша хозяйка не устает жаловаться на ваш кларнет. Она никогда не позволит поставить к нам пианино!
– Я говорил о Джузеппе Пеано, так звали итальянского математика и специалиста по логике, Ватсап.
– Откровенно говоря, не такая уж большая разница. Я не уверен, что миссис Сопсудс…
– Тихо! Согласно арифметической аксиоматике Пеано, наследником любого целого числа является число
s (n) = n + 1.
– Так что Пеано вполне мог бы записать:
1 = 1,
2 = s (1),
3 = s (s (1)),
4 = s (s (s (1))),
5 = s (s (s (s (1)))),
и эта последовательность будет продолжаться до бесконечности. В этой системе любое целое число можно выразить при помощи всего одной единицы. Или даже одного нуля, поскольку 1 = s (0). Это слишком тривиально, Ватсап.
Сможете ли вы найти способ записать 7 с использованием только двух единиц, не прибегая ни к чему более экзотическому, чем функции, которые Сомс и Ватсап использовали прежде, чем начали спорить о двойных факториалах и наследниках? Ответ см. «Загадки разгаданные».
Сомс и Ватсап еще не закончили. «Знак одного» продолжается в главе «Знак одного. Часть третья».
Путаница с инициалами
Р. Х. Бинг – американский математик, родился в Техасе, специализировался на геометрической топологии. Что означает Р. Х.? Ну, как сказать… Его отца звали Руперт Генри, но его мать считала, что для Техаса такое имя звучит слишком по-британски, поэтому при крещении ребенка она укоротила его до предела, оставив одни инициалы. Поэтому Р. Х. означает Р. Х., и ничего больше. Это вызывало, конечно, некоторое удивление, но не доставляло ему серьезных неудобств – до тех пор, пока Бинг не обратился за визой для поездки куда-то. Когда его попросили назвать имя, он, предвидя обычную реакцию, сказал: «R-only H-only Bing»[18].
В результате он получил визу, выданную на имя Ронли Хонли Бинга.
Евклидовы каракули
Это математическая загадка, которая была решена более двух тысяч лет назад и долгое время преподавалась в школах, но теперь уже не преподается – по разумным, вероятно, соображениям. Однако с ней стоит познакомиться, поскольку она намного эффективнее того метода, который используется вместо нее. Кроме того, она позволяет установить связь со многими важными математическими понятиями более высоких уровней.
Люди, как правило, любят выводить каракули. Нередко можно увидеть, как кто-то, разговаривая по телефону, бездумно заштриховывает шариковой ручкой, к примеру, все буквы «о» на газетной странице. Или выводит извилистые линии, которые длятся и длятся без конца, свиваясь в какие-то неправильные спирали. Слово doodle, обозначавшее первоначально глупца, впервые ввел, судя по всему, сценарист Роберт Рискин в комедии 1936 г. «Мистер Дидс переезжает в город»; в фильме мистер Дидс говорит о каракулях (doodle) как о средстве, помогающем человеку думать.
Если математик рисует каракули (а большинство из них грешат этим), он вполне может нарисовать, к примеру, прямоугольник. Что можно сделать с прямоугольником? Можно заштриховать его, можно закрутить вдоль сторон спиралеобразные линии… а можно отрезать от него кусок с одной стороны и получить прямоугольник поменьше. После этого естественно – и, кстати говоря, типично для ментальности рисовальщика каракулей – повторить проделанную процедуру.
Что при этом происходит? Может быть, вам, прежде чем читать дальше, захочется самому нарисовать пару прямоугольников.
Ну, хорошо, продолжаем. Я начал с длинного узкого прямоугольника, и вот что получилось.
В конце концов я получил маленький квадратик, на котором мой прямоугольник закончился.
Всегда ли так получается? Всякий ли прямоугольник в конце концов заканчивается? Это хороший вопрос, способный дать математику пищу для размышлений.
Каого размера был мой прямоугольник? Ну, последний рисунок показывает, что:
• сумма сторон двух маленьких квадратиков равна стороне среднего квадрата;
• сумма сторон двух средних квадратов и одного маленького квадратика образует сторону большого квадрата и равна при этом одной из сторон прямоугольника;
• сумма сторон трех больших квадратов и одного среднего равна второй стороне прямоугольника.
Если сторона маленького квадратика равна единице, то сторона среднего квадрата равна 2, а сторона большого равна 2 2 + 1 = 5. Следовательно, короткая сторона прямоугольника равна 5, а длинная равна 3 5 + 2 = 17. Таким образом, я начал с прямоугольника размером 17 5.
Это интересно: глядя на то, как складываются квадраты, я могу определить размеры своего прямоугольника. Более тонкий момент: если процесс завершается, это означает, что обе стороны первоначального прямоугольника нацело делятся на одно и то же число – сторону последнего изъятого квадрата. Иными словами, отношение его сторон имеет форму p/q, где p и q – целые. Что делает его рациональным числом.
Это общая идея: если процесс деления на квадраты рано или поздно прекращается, значит, отношение сторон прямоугольника выражается рациональным числом. Более того, обратное тоже верно: если отношение сторон прямоугольника рационально, каракули рано или поздно закончатся. Так что «конечные» каракули в точности соответствуют «рациональным прямоугольникам».
Чтобы понять почему, взглянем на числа повнимательнее. По существу, рисунок сообщает нам следующее:
17 – 5 = 12;
12 – 5 = 7;
7 – 5 = 2.
После этого у нас остается прямоугольник 5 2 и пора переходить к среднему квадрату:
5 – 2 = 3;
3 – 2 = 1.
Остался прямоугольник 2 1, пора переходить к маленькому квадратику:
2 – 1 = 1;
1 – 1 = 0.
Стоп! И дело рано или поздно должно дойти до остановки, потому что все задействованные целые числа положительны и с каждым шагом они делаются все меньше и меньше. Так и должно быть, ведь мы каждый раз либо вычитаем из них что-то, либо оставляем, как есть. А последовательность положительных целых чисел не может уменьшаться до бесконечности. Если вы, к примеру, начнете с миллиона и будете все время уменьшать, то вам придется остановиться не более чем через миллион шагов.
Короче говоря, каракули сообщают нам вот что:
при делении 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.
Техническое название этого метода – алгоритм Евклида. Вообще, алгоритм – это рецепт для расчета. Евклид поместил такой рецепт в свои «Начала» и использовал его в качестве основы для теории простых чисел. В символьном виде алгоритм каракулей выглядит так. Возьмем два положительных целых числа mn. Начнем с пары (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 ровно.
Необычайно длинный расчет для таких небольших чисел.
Читать бесплатно другие книги:
