Алекс в стране чисел

Глава 7 Тайны следствия

В Атланте я познакомился с человеком, у которого довольно необычное хобби. Нил Слоун — так его зовут — собирает числа.

Не отдельные числа, а семейства чисел, организованных в упорядоченные ряды, называемые последовательностями. Например, натуральные числа — это последовательность, которую можно определить, сказав, что ее n-й член равен n:

Слоун начал собирать свою коллекцию в 1963 году, когда учился на старших курсах Корнеллского университета. Сначала он записывал последовательности на карточках. Это было довольно удобно, поскольку при этом упорядоченные ряды сами образовывали некий упорядоченный ряд. К 1973 году он собрал 2400 последовательностей и опубликовал их в книге под заглавием «Энциклопедия целочисленных последовательностей». К середине 90-х годов у него их было уже 5500. Но только с изобретением Интернета коллекция обрела идеальную среду для своего существования. Список Слоуна расцвел и превратился в «Онлайн-энциклопедию целочисленных последовательностей» — собрание, в котором сейчас более 160 000 записей и которое разрастается со скоростью около 10 000 записей в год.

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

По мнению Слоуна, сходство между изучением последовательностей и скалолазанием состоит в том, что оба этих занятия требуют умения решать головоломки. Я бы добавил, что есть и другая параллель: подобно тому, как скалолаз, покорив одну вершину, уже готов сразиться с новой, так и любитель последовательностей, дойдя до n-го члена, тут же начинает искать (n + 1)-й. При этом у скалолазов есть естественный ограничитель — географический фактор, зато последовательности, уходя в бесконечность, часто никаких ограничений не имеют.

Как истинный коллекционер, который складывает в одну коробку своих старых любимцев рядом с колоритными раритетами, Слоун принимает в «Энциклопедию» как обыкновенное, так и экстравагантное. В его коллекции, например, имеется «нулевая последовательность», состоящая из одних только нулей. (Каждой последовательности в «Энциклопедии» присвоен идентификационный номер, перед которым стоит буква А. Нулевая последовательность — четвертая в собрании Слоуна, и потому известна как А4):

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

Поддержание «Онлайн-Энциклопедии» — основная работа Слоуна, параллельная другой настоящей работе — занятию математикой в лабораториях компании AT&T в Нью-Джерси. Однако сейчас ему больше не нужно тратить время на поиски новых последовательностей. После того как к «Энциклопедии» пришел успех, Слоан постоянно получает новые — от профессиональных математиков, но по больше части от людей, одержимых числами. У Слоуна есть всего один критерий, на основе которого новой последовательности разрешается вступить в клуб: она должна быть «корректно определенной и интересной». Первое означает попросту, что каждый член в последовательности можно описать или алгебраически, или риторически. Удовлетворяет ли последовательность второму требованию — решает он сам, хотя обычно в случае сомнения он склонен решить вопрос скорее в пользу той или иной последовательности. Правда, из требований «корректной определенности» и «интересности» вовсе не следует, что последовательность обязательно должна быть математической. И история, и фольклор, и причуды также играют роль в его решении.

Среди последовательностей, включенных в «Энциклопедию», имеется и вот такая довольно древняя:

Числа в этой последовательности представляют собой перевод на язык цифр отметок, сделанных на самом старом из известных математических объектов — на кости Ишанго, артефакте возрастом 22 000 лет, найденном на территории нынешней Демократической Республики Конго[47]. Эта обезьянья кость сначала считалась инструментом для определения длины (попросту говоря, линейкой), однако потом ученые высказали идею, что поскольку насечки на кости хитро сгруппированы — тройка, ее удвоение, затем четверка, ее удвоение, десятка, за которой следует ее половина, — то эта последовательность может выражать какой-то более замысловатый ход мыслей, возможно связанный с выполнением арифметических действий.

В коллекции имеется также дьявольская последовательность:

Она составлена из так называемых Чисел Зверя — чисел, содержащих фрагмент 666.

Ради забавы Слоун также включил и такую последовательность:

Это числа из латиноамериканской детской песенки «La Farolera»: «Dos у dos son quatro, cuatro у dos son seis. Seis у dos son ocho, у ocho dieciseis» (Два и два — четыре, четыре и два — шесть, шесть и два — восемь и т. д.).

Но самая, быть может, классическая из всех последовательностей — это последовательность простых чисел:

Простые числа — это натуральные числа большие единицы, которые делятся только на себя и на единицу. Их очень просто описать, но их последовательность демонстрирует весьма впечатляющие, а временами и таинственные свойства. Во-первых, как доказал Евклид, простых чисел бесконечно много. Какое бы число вы ни взяли, всегда найдется простое число большее, чем данное. Во-вторых, каждое натуральное число больше 1 записывается — причем существует только один вариант — как произведение простых чисел. Другими словами, каждое число равно результату перемножения определенного набора простых чисел. Например, 221 есть 13 × 17. Следующее число, 222, есть 2 × 3 × 37. Идущее за ним — 223 — простое, так что можно записать только 1 × 223, а 224 есть 2 × 2 × 2 × 2 × 2 × 7. И так можно продолжать до бесконечности. Например, миллиард равен 2 × 2 × 2 × 2 × 2 × 2 × 2 × 2 × 2 × 5 × 5 × 5 × 5 × 5 × 5 × 5 × 5 × 5. Это свойство чисел известно как фундаментальная теорема арифметики, и именно оно определяет, почему простые числа рассматриваются как неделимые кирпичики всей системы натуральных чисел.

Однако, несмотря на свою особенность, простые числа не обладают монополией на производство последовательностей, несущих в себе специальные секреты математического порядка (или беспорядка). Все последовательности так или иначе способствуют нашему лучшему пониманию того, как устроены числа. «Онлайн-энциклопедию целочисленных последовательностей» можно также рассматривать как собрание разнообразных примеров, справочное руководство по численному порядку, лежащему в основании мира. Возникнув из личного пристрастия Нила Слоуна, этот проект оказался действительно важным научным ресурсом.

Слоун считает «Энциклопедию» математическим эквивалентом хранящейся в ФБР базы данных по отпечаткам пальцев. «Взяв отпечатки пальцев на месте преступления, их затем проверяют по базе с целью опознать подозреваемого, — говорит он. — То же самое и с „Энциклопедией“. Математики, столкнувшись с какой-то последовательностью чисел, которая естественным образом возникла в ходе их работы, смотрят в базе, — и страшно радуются, если оказывается, что их последовательность там уже есть». Такая база данных приносит пользу не только чистым математикам. Инженеры, химики, физики и астрономы также искали и находили свои последовательности в «Энциклопедии», таким образом обнаруживая неожиданные междисциплинарные связи и глубже проникая в суть своей собственной области знания. Если люди работают в области, постоянно изрыгающей недоступные для понимания числовые последовательности, которым они надеются придать некий смысл, то такая база данных — настоящая золотая жила.

«Энциклопедия» позволяет Слоуну быть в курсе множества новых математических идей, а кроме того, он проводит часть времени, рождая свои собственные. В 1973 году он предложил концепцию «продолжительности жизни» числа. Она измеряется числом шагов, которое требуется сделать, чтобы получить однозначное число, перемножая все цифры предыдущего числа, затем перемножая все цифры полученного числа, что даст третье число, и т. д., пока не получится однозначное число. Например, 88 → 8 × 8 = 64 → 6 × 4 = 24 → 2 × 4 = 8. Таким образом, говорит Слоун, число 88 имеет продолжительность жизни, равную 3, поскольку требуются три шага, чтобы добраться до одной цифры. Кажется, что чем больше число, тем выше его продолжительность жизни. Например, 679 имеет продолжительность жизни, равную 5: 679 → 378 → 168 → 48 → 32 → 6. Подобным же образом, слегка потрудившись, можно узнать, что число 277 777 788 888 899 имеет продолжительность жизни, равную 11. Однако Слоуну не удалось найти числа, продолжительность жизни которого была бы больше 11, даже после того, как он перебрал все числа до 10²³³, что есть единица с 233 нулями. Другими словами, какое бы 233-значное число вы ни выбрали, применив к нему правила перемножения цифр для определения продолжительности жизни, вы непременно доберетесь до одной-единственной цифры за 11 шагов или ранее.

Этот результат восхитительным образом противоречит нашей интуиции. Казалось бы, если взять число, состоящее из 200 или около того цифр, причем по большей части из больших цифр, скажем восьмерок и девяток, то произведение всех этих цифр окажется достаточно большим, и для того, чтобы в конце концов добраться до однозначного числа, потребуется существенно больше и шагов. Однако, как оказалось, большие числа схлопываются под собственным весом. Дело в том, что если в числе хоть раз появится нуль, то произведение всех его цифр окажется равным нулю. Если в числе, с которого вы начали, нет нулей, то нуль непременно появится на 11-м шаге, если только число уже не свелось к этому моменту к единственной цифре. Слоун считает свой алгоритм необычайно эффективным убийцей чисел-гигантов.

Не останавливаясь на достигнутом, Слоун составил последовательность, в которой n-й член есть наименьшее число с продолжительностью жизни, равной n. (Мы рассматриваем только числа, имеющие по крайней мере две цифры.) Первый такой член равен 10, потому что 10 → 0, так что 10 — это наименьшее двузначное число, которое претерпевает редукцию за один шаг.

Второй член равен 25, потому что 25 → 10 → 0 и 25 есть наименьшее число, которое редуцируется за два шага.

Третий член равен 39, потому что 39 → 27 → 14 → 4 и 39 есть наименьшее число, которое редуцируется за три шага.

Приведем всю последовательность:

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

Друг Слоуна профессор Джон Хортон Конуэй из Принстона тоже любит нестандартные математические концепции. В 2007 году он изобрел понятие степенной трансмиссии. Степенная трансмиссия числа, записанного в виде abcd…, — это abc^d… В случае чисел с нечетным числом цифр его последней цифре не во что возводиться, так что abcde переходит в abc^de. Возьмем 3462. Из него получаем 3462 = 81 × 36 = 2⁹1⁶. Будем применять степенную трансмиссию повторно, пока не останется однозначное число:

Конуэй пожелал узнать, имеются ли какие-либо неразрушаемые числа — те, которые не сводятся к однозначному числу при применении степенной трансмиссии. Ему удалось найти только одно:

Но не такой человек Нил Слоун, чтобы сидеть сложа руки, глядя на то, как другие изобретают числа! Он открыл второе такое число[48]

Слоун в настоящее время уверен, что других неразрушаемых чисел нет.

Задумаемся об этом на минутку: конуэевская степенная трансмиссия — это смертоносная машина, убивающая каждое число во Вселенной, за исключением 2592 и 24 547 284 284 866 560 000 000 000 — двух с виду никак не связанных неподвижных точек в безграничном мире чисел. «Это потрясающий результат», — говорит Слоун. Большие числа при применении степенной трансмиссии умирают достаточно быстро по тем же причинам, по которым они умирают при вычислении их продолжительности жизни, — появляется нуль, и все становится ничем. Я спросил Слоуна, может ли устойчивость этих двух чисел по отношению к степенной трансмиссии найти какое-либо применение в реальном мире. Он думает, что нет. «Это просто забавно. И ничего плохого в этом нет — надо же иногда просто развлечься».

И Слоун развлекается вовсю. Он исследовал так много последовательностей, что развил свою собственную числовую эстетику. Одну из его любимых последовательностей изобрел математик из Колумбии Бернардо Рекаман Сантос, и называется она последовательностью Рекамана:

Давайте взглянем на эти числа и постараемся углядеть закономерность. Смотрите внимательно. Они скачут вроде бы без всякого порядка.

На самом же деле эти числа получаются применением следующего простого правила: «вычитайте, если возможно, а если невозможно — то складывайте». Чтобы получить n-й член, мы берем (n - 1)-й и либо прибавляем к нему, либо вычитаем из него n. Правило гласит, что следует применять вычитание во всех случаях кроме тех, когда результат оказался бы или отрицательным числом, или числом, уже присутствующим в последовательности. Вот как вычисляются первые четыре члена, если начать с нуля (нулевого члена):

Первый член равен нулевому члену плюс 1.

Результат: 1.

Второй член равен первому члену плюс 2.

Результат: 3.

Третий член равен второму члену плюс 3.

Результат: 6.

Четвертый член равен третьему члену минус 4. Результат: 2.

И так далее.

Во время всего этого довольно занудливого процесса мы имеем дело с целыми числами и получаем ответы, которые выглядят совершенно бессистемными. Однако закономерность, которая здесь возникает, можно увидеть, если изобразить последовательность в виде графика. По горизонтальной оси отложим номер члена, так что n-й член будет расположен над числом n, а по вертикальной оси — значение этого члена. График для первой тысячи членов последовательности Рекамана не похож, наверное, ни на один из ранее виденных вами графиков. Он подобен брызгам из садового распылителя, или же рисунку ребенка, пытающегося соединить точки друг с другом. (Толстые линии на графике — это скопления точек, выглядящие так из-за неподходящего масштаба.) «Интересно посмотреть, сколь много порядка можно привнести в хаос, — заметил Слоун. — Последовательность Рекамана находится ровно на границе между хаосом и изящной математикой, поэтому-то она так и захватывает».

Последовательность Рекамана

Столкновение порядка и беспорядка в последовательности Рекамана можно выразить и музыкально. В «Энциклопедии» имеется функция, позволяющая прослушать любую последовательность, как если бы она была записана с помощью нот. Представим себе, что имеется фортепиано с 88 клавишами (что составляет диапазон чуть меньше восьми октав). Число 1 соответствует самой нижней ноте, число 2 — второй ноте снизу, и так далее, до числа 88, которое соответствует самой верхней ноте. Когда ноты заканчиваются, мы опять начинаем снизу, так что число 89 возвращает нас к первой клавише. Натуральные числа 1, 2, 3, 4, 5 звучат как восходящая гамма, повторяющаяся без конца. Но музыка, создаваемая последовательностью Рекамана, леденит кровь. Она подобна саундтреку из фильма ужасов. Она звучит негармонично, однако не воспринимается как нечто совершенно хаотичное. Можно различить отчетливые музыкальные фразы, как если бы за какофонией скрывалось творение таинственной человеческой руки[49].

Вопрос, который интересует математиков, — все ли числа встречаются в последовательности Рекамана. Были изучены 10²⁵ членов последовательности, и оказалось, что наименьшее из не присутствующих чисел — это 852 655. Слоун подозревает, что в конце концов в этой последовательности появятся все числа, включая и 852 655, но это его предсказание пока не доказано. Нет ничего удивительного в том, что Слоун находит последовательность Рекамана столь увлекательной.

Другой фаворит Слоуна — это последовательность Гийсвийта[50]. В отличие от многих последовательностей, которые растут с победоносной быстротой, последовательность Гийсвийта растет с тягучей неторопливостью, способной свести с ума. Она представляет собой прекрасную метафору идеи «никогда не сдаваться»:

Первая тройка появляется на девятом месте. Четверка первый раз возникает на 221-м месте. Появление пятерки ожидается не раньше, чем ад замерзнет — она возникнет на месте с номером 10^{100000000000000000000000}.

Это экстремально большое число. Например, вся Вселенная содержит только 10⁸⁰ элементарных частиц. В конце концов появится и шестерка, но на таком расстоянии от начала, которое разумно можно описать только как степень степени степени степени степени: . Остальные числа тоже рано или поздно возникнут, хотя — и это следует подчеркнуть — не выказывая при этом решительно никакой спешки. «Земля умирает, даже океаны умирают, — замечает Слоун с поэтическим пафосом, — но приют и спасение можно найти в абстрактной красоте последовательности типа А090822 Диона Гийсвийта».

Древние греки уделяли простым числам серьезное внимание. Но еще больше они были очарованы числами, которые называли совершенными. Рассмотрим число 6: числа, на которое оно делится, его делители, — это 1, 2 и 3. Если сложить 1, 2 и 3 — voilà, снова получается 6. Совершенное число — это любое число, которое, подобно шестерке, равно сумме своих делителей. (Строго говоря, у 6 есть еще делитель 6, но при рассмотрении совершенных чисел имеет смысл включать только те делители, которые меньше данного числа.) Следующее за шестеркой совершенное число — это 28, потому что числа, на которые оно делится, — это 1, 2, 4, 7 и 14, а их сумма равна как раз 28. Не только греки, но и евреи и христиане приписывали космологическое значение такому численному совершенству. Живший в XI веке выдающийся богослов и писатель Рабан Мавр писал: «Шесть не потому совершенно, что Бог сотворил мир за 6 дней, но Бог совершил акт творения за 6 дней потому, что число это совершенно».

Греки обнаружили также неожиданную связь между совершенными и простыми числами, которая породила многочисленные связанные с ними приключения. Рассмотрим последовательность удвоений, начинающуюся с 1:

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

Доказательство Евклида было, конечно, геометрическим. Он не записывал его в терминах чисел, а использовал отрезки прямых. Однако если бы он мог позволить себе роскошь современных алгебраических обозначений, то заметил бы, что сумму удвоений 1 + 2 + 4 +… можно выразить как сумму степеней двойки, 2⁰ + 2¹ + 2² +… (Заметим, что любое число в степени 0 есть 1 и что любое число в степени 1 есть само это число.) Тогда становится понятным, что любая сумма удвоений равна следующему удвоению за вычетом единицы. Например:

Это можно обобщить в виде формулы 2⁰ + 2¹ + 2² +… + 2^n-1 = 2ⁿ - 1. Другими словами, сумма первых n удвоений равна 2ⁿ - 1.

Итак, используя исходное заявление Евклида о том, что «когда сумма удвоений есть простое число, можно построить совершенное число, умножая сумму на наибольшее из тех удвоений, что в нее входят» и добавляя к этому современные алгебраические обозначения, мы можем получить намного более четкое утверждение:

Для цивилизаций, которые превозносили совершенные числа, данное Евклидом доказательство было потрясающей новостью. Если совершенные числа можно породить всякий раз, когда число 2ⁿ - 1 простое, то все, что нужно для нахождения новых совершенных чисел, — это нахождение простых чисел, которые можно записать в виде 2ⁿ - 1. Охота за совершенными числами свелась к охоте за простыми числами определенного типа.

Конечно, математический интерес к простым числам, записываемым в виде 2ⁿ - 1, мог быть связан с совершенными числами, однако к XVII столетию простые числа стали объектом увлечения сами по себе. В то время как одни математики были поглощены вычислением числа π со все большим и большим количеством десятичных знаков, другие посвящали себя нахождению все больших и больших простых чисел. Эти два рода деятельности похожи, но противоположны: если вычисление десятичных знаков в числе π — это поиск все меньших и меньших объектов, то погоня за простыми числами — это взлет вверх, в небеса. Развитию обоих направлений способствовала скорее романтическая аура самого путешествия, нежели возможности практического использования чисел, открытых по дороге.

В ходе этого поиска простые числа вида 2ⁿ - 1 зажили своей собственной жизнью. Эта формула не давала простых чисел при всех значениях n, но для малых чисел процент успеха был весьма неплох. Как мы уже видели, при n = 2, 3, 57 число 2ⁿ - 1 — простое.

Французский монах (и одновременно один из выдающихся ученых своего времени) Марен Мерсенн (1588–1648) просто зациклился на использовании чисел вида 2ⁿ - 1 для производства простых. В 1644 году он выступил с широкомасштабным заявлением о том, что ему известны все значения n до 257, при которых число 2ⁿ - 1 простое. По его словам, это были значения

Мерсенн был дельным математиком, однако его список — по большей части плод угадывания. Число 2²⁵⁷ - 1 состоит из 78 цифр — определенно слишком много для проверки человеческими силами на предмет того, простое оно или нет. Мерсенн осознавал, что его числа — это стрельба наугад. Он говорил о своем списке: «Всего времени не хватит, дабы определить, простые ли они».

Но одному математику времени тем не менее все-таки хватило, — такое нередко бывает в науке. В 1876 году, через два с половиной столетия после того, как Мерсенн предложил свой список, французский специалист по теории чисел Эдуар Люка изобрел метод, позволяющий проверить, являются ли числа вида 2ⁿ - 1 простыми, и выяснил, что Мерсенн был не прав по поводу числа 67 и, кроме того, он пропустил числа 61, 89 и 107. Потрясающе, однако, что Мерсенн оказался прав насчет числа 127. Люка применил свой метод для доказательства того, что число 2¹²⁷ - 1 (то есть 170 141 183 460 4 69 231 731 687 303 715 884 105 727) — простое. Оно оставалось самым большим известным простым числом до наступления века компьютеров. Люка, однако, не смог определить, простое или нет число 2²⁵⁷ - 1 — оно было слишком большим для ручных вычислений.

Несмотря на отдельные ошибки, список Мерсенна обессмертил своего создателя; простые числа вида 2ⁿ - 1 в наше время известны как простые числа Мерсенна.

Дабы выяснить, простое или нет число 2²⁵⁷ - 1, пришлось дожидаться наступления 1952 года. Для доказательства был использован метод Люка, правда при существенной поддержке. В том году в Институте численного анализа в Лос-Анджелесе собралась команда ученых. Они наблюдали за 24-футовыми барабанами с магнитной лентой, вводившейся в один из первых цифровых компьютеров, который назывался SWAC. Один только этот процесс занял несколько минут. Затем оператор ввел число, которое предстояло проверить: 257. Через долю секунды появился результат. Компьютер сообщил, что число 2²⁵⁷ - 1 — не простое.

Вечером того же дня, когда было получено, что число 2²⁵⁷ - 1 — не простое, в вычислительную машину один за другим были введены новые претенденты на право занять место в списке Мерсенна. SWAC отказал первым 42 из них. И только в 10 вечера появился результат: компьютер сообщил, что число 2⁵²¹ - 1 — простое. Это число было наибольшим из простых чисел Мерсенна, выявленным за 75 лет, что, кстати, давало и соответствующее совершенное число 2⁵²⁰(2⁵²¹ - 1) — всего лишь тринадцатое открытое за чуть ли не вдвое большее число столетий. Но число 2⁵²¹ - 1 только два часа наслаждалось своим статусом старшего в колоде. Незадолго до полуночи SWAC подтвердил, что число 2⁶⁰⁷ - 1 тоже простое. За последующие несколько месяцев SWAC, работая на пределе своих возможностей, нашел еще три простых числа. 17 простых чисел Мерсенна были открыты в период с 1957 по 1996 год.

Начиная с 1952 года почти всегда наибольшим известным простым числом было простое число Мерсенна. Единственным исключением явилась трехлетняя интерлюдия между 1989 и 1992 годом, когда самым большим простым числом считалось (391 581 × 2^{216 193}) - 1, которое, впрочем, относится к типу простых чисел, связанных с мерсенновскими простыми. Среди всех существующих простых чисел (а мы знаем, что их бесконечно много) в таблице наибольших открытых простых преобладают простые числа Мерсенна, поскольку они представляют собой прекрасную мишень для охотников за простыми числами. Лучшая тактика поиска больших простых чисел — это искать простые числа Мерсенна; другими словами, отправлять число 2ⁿ - 1 в компьютер при все больших и больших значениях n и использовать для проверки его простоты тест Люка — Лемера, представляющий собой усовершенствованный вариант упоминавшегося выше метода Эдуара Люка.

Самого влиятельного из охотников за простыми числами нашего времени привела на этот путь марка на конверте. В 1960-х годах, когда Джордж Уолтман был еще ребенком, его отец показал ему почтовую марку, на которой был изображен Университет Иллинойса и написано «2¹¹²¹³ - 1 простое» — это был результат, только что установленный в этом университете. «Это меня просто потрясло — оказывается, можно доказать, что такое большое число — простое», — вспоминает он.

Уолтман внес немалый вклад в написание программ, существенным образом продвинувших поиск простых чисел. Все проекты, имевшие дело с масштабной обработкой чисел, как правило, выполнялись на суперкомпьютерах, доступ к которым ограничен. Начиная с 1990 года, однако, немало больших задач подвергались «нарезке» наподобие салями — работа разбивалась на части, которыми занимались тысячи меньших машин, связанных друг с другом через Интернет. В 1996 году Уолтман написал программу, которую пользователи могут бесплатно скачать, а установив ее, получить маленький кусок еще неисследованной части числовой прямой для поиска там простых чисел. Эта программа использует процессор, только когда ваш компьютер ничего не делает. Пока вы крепко спите, ваша машина занята тем, что перетряхивает числа на дальнем рубеже познания.

Великий «интернет-поиск мерсенновских простых», или GIMPS, в настоящее время связывает около 75 000 компьютеров. Часть из них стоит в научно-исследовательских учреждениях, другие — в офисах, а некоторые — дома у энтузиастов поиска. GIMPS был одним из первых проектов «распределенных вычислений» и оказался одним из наиболее успешных. (Самый масштабный из подобных проектов — SetiKhome, который занят расшифровкой космического шума в поисках сигналов от внеземных цивилизаций. Утверждается, что в нем участвуют три миллиона ученых, правда, они до сих пор ничего не открыли.) Спустя всего лишь несколько месяцев после запуска GIMPS 29-летний французский программист поймал в свои сети 35-е простое число Мерсенна, 2^1398269 - 1. С тех пор GIMPS обнаружил еще 11 мерсенновских простых, что соответствует в среднем одному числу в год. Мы живем в золотой век больших простых чисел.

На настоящий момент рекорд самого большого простого числа удерживает 45-е простое число Мерсенна, 2^43112609 - 1 — это число, в котором почти 13 миллионов цифр, найдено в 2008 году на компьютере, подсоединенном к GIMPS, в Калифорнийском университете в Лос-Анджелесе. Простые числа Мерсенна, найденные по счету 46-м и 47-м, оказались меньше 45-го. Это произошло потому, что различные компьютеры с различными быстродействиями одновременно работают на различных участках числовой прямой, и может так случиться, что простые числа на более далеком ее участке будут открыты раньше, чем на более близком.

Проект GIMPS стал примером массового добровольного сотрудничества в целях научного прогресса, и это сделало его символом свободного Интернета. Уолтман, даже не помышляя ни о чем подобном, превратил поиск простых чисел в квазиполитическое предприятие. С целью подчеркнуть символическую важность этого проекта Фонд электронных рубежей (Electronic Frontier Foundation, EFF) — группа, ведущая кампанию за цифровые права, — начиная с 1999 года предлагает денежное вознаграждение за каждое новое простое число, количество цифр в котором достигнет следующего порядка величины. Первым простым числом, добравшимся до 10 миллионов цифр, оказалось 45-е простое число Мерсенна, призовая сумма за него составила 100 000 долларов. Фонд EFF предлагает 150 000 долларов за первое простое число, состоящее из 100 миллионов цифр, и 250 000 долларов за первое, состоящее из миллиарда. Если нанести на график самые большие простые числа, полученные за все последние годы начиная с 1952-го, то в логарифмическом масштабе, как показано ниже, эти числа выстроятся почти в прямую линию. Эта прямая показывает, как замечательным образом постоянно возрастала мощь процессоров, а кроме того, позволяет оценить, когда будет открыто первое простое число, состоящее из миллиарда цифр. Бьюсь об заклад, это открытие произойдет ближе к 2025 году.

Число цифр в наибольших известных простых числах в различные годы

При том что простых чисел бесконечно много (хотя бесконечно ли количество мерсенновских простых — пока не известно), поиск все больших и больших простых — задача, конца которой нет. Какого бы простого числа мы ни достигли, и не важно, насколько большого, всегда найдется еще большее простое число — дразнящее нас и бросающее вызов.

Продолжение, которому нет конца, — самая, пожалуй, глубокая и многообещающая идея в фундаментальной математике. Человеческое сознание с трудом воспринимает понятие бесконечности. Например, что случится, если мы начнем считать 1, 2, 3, 4, 5 и никогда не остановимся? Я помню, как ребенком задавал этот с виду простой вопрос — и не получал ясного ответа. Как правило, я слышал от родителей и школьных учителей, что вот тогда мы доберемся до «бесконечности», что есть, по сути, лишь перефразировка самого вопроса.

Тем не менее нам с относительного юного возраста внушают мысль, что с бесконечностью можно обращаться как с числом — необычным, но тем не менее числом. Нам показывают обозначение для бесконечности — горизонтальную замкнутую петлю («лемнискату») и знакомят нас с ее необычной арифметикой. Прибавление любого конечного числа к бесконечности дает бесконечность. Вычитание любого конечного числа из бесконечности дает бесконечность. Умножение или деление бесконечности на конечное число, если только это не нуль, снова дает бесконечность. Легкость такого обращения с бесконечностью как с числом скрывает более двух тысячелетий борьбы за то, чтобы найти общий язык с ее тайнами.

Первым, кто показал, что если иметь дело с бесконечностью, то могут возникнуть проблемы, был греческий философ Зенон Элейский (490 до н. э. — 430 до н. э.). В одном из своих знаменитых парадоксов он описал теоретическую гонку между Ахиллом и черепахой. Ахилл быстрее черепахи, поэтому черепаха при старте имеет фору. Прославленный воин начинает движение из точки А, а бросившая ему вызов рептилия — из точки В. Ахилл устремляется вперед и вскоре достигает точки В, но к тому моменту, как он туда добирается, черепаха уже продвинулась в точку С. Ахилл мчится в точку С. Но опять, когда он достигает этой точки, черепаха уже продвинулась вперед до точки D. Ахиллу надо, конечно, добраться до D, но, когда он туда попадает, черепаха уже будет в точке E. Зенон утверждает, что эта игра в «догонялки» будет продолжаться вечно, и поэтому быстроногий Ахилл никогда не обгонит неторопливого четвероногого соперника.

Как и в приведенном парадоксе, во всех парадоксах Зенона явно абсурдные заключения получаются в результате бесконечного разбиения непрерывного процесса движения на дискретные события. Ахиллу, прежде чем он сможет догнать черепаху, надо совершить бесконечное число дискретных «шагов». Парадокс возникает из допущения, что невозможно совершить бесконечное число «шагов» за конечное время.

У древних греков, впрочем, не было глубокого математического понимания бесконечности, позволявшего заключить, что это предположение ошибочно. Можно совершить бесконечное число «шагов» за конечное время. Основное требование состоит в том, что эти «шаги» должны становиться все короче, а их прохождение — занимать все меньше времени, так что при этом как расстояние, так и время стремятся к нулю. Хотя это и необходимое условие, оно не является достаточным; «шаги» также должны уменьшаться достаточно быстро.

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

Если бы Ахиллу требовалась секунда, чтобы пройти каждый из этих «шагов», то прохождение всего расстояния заняло бы у него вечность. Но дело обстоит не так. Предположим, он бежит с постоянной скоростью, тогда ему понадобится секунда, чтобы пробежать метр, полсекунды — чтобы пробежать полметра, четверть секунды — чтобы пробежать четверть метра и т. д. Таким образом, время в секундах, которое потребуется ему для того, чтобы догнать черепаху, описывается той же самой суммой:

Когда и время, и расстояние описываются последовательностью, каждый член которой в два раза меньше предыдущего, их суммы одновременно сходятся к определенному конечному значению — в нашем случае к 2 секундам и 2 метрам. Итак, в конце концов выясняется, что Ахилл все же догонит черепаху.

Впрочем, не все парадоксы Зенона решаются с помощью математики бесконечных рядов. В «парадоксе дихотомии» бегун отправляется из А в В. Назовем первую точку, которую он пройдет после того, как выйдет из точки А, точкой С. Но чтобы попасть в С, он должен сначала пройти через точку, расположенную на полпути до С. Следовательно, С не может быть первой точкой, через которую он пройдет. Получается, нет никакой «первой точки», через которую проходит бегун, потому что всегда найдется точка, через которую он должен пройти до того. Если же нет первой точки, через которую проходит бегун, говорит нам Зенон, значит, бегун никогда не сможет сдвинуться с точки А.

Согласно легенде, для опровержения этого парадокса киник Диоген молча встал и прошел от А до В, тем самым продемонстрировав, что движение возможно. Но зеноновский парадокс дихотомии не удается так просто списать со счета. За два с половиной тысячелетия, в течение которых ученые чесали затылки, никто не смог полностью разрешить эту загадку. Часть проблемы состоит в том, что непрерывная линия не допускает адекватного представления последовательностью ни из бесконечного числа дискретных точек, ни из бесконечного числа малых интервалов. Подобным же образом непрерывный промежуток времени невозможно адекватно представить бесконечным числом дискретных временных интервалов. Концепции непрерывности и дискретности не хотят уживаться друг с другом.

Десятичная система предоставляет нам чудесный пример парадокса в духе Зенона. Каково самое большое число, меньшее единицы? Это не 0,9, потому что 0,99 больше него, но при этом меньше единицы. Но это и не 0,99, поскольку 0,999 еще больше, но все равно меньше единицы. Единственный возможный кандидат — это периодическая десятичная дробь 0,9999…, где многоточие означает, что девятки продолжаются неограниченно. Здесь-то и заключается парадокс. Искомое число не может быть равно 0,9999…, потому что 0,9999… совпадает с числом 1!

Вот как на это можно смотреть. Если бы 0,9999… было числом, отличным от 1, то между ними был бы некий интервал на числовой прямой. А тогда было бы возможно втиснуть в этот интервал еще какое-то число — число больше 0,9999… и меньше 1. Но что это могло бы быть за число? Подобраться к 1 ближе, чем 0,9999…, нельзя. Таким образом, если 0,9999… и 1 неразличимы, то они должны совпадать. Сколь бы странным такое ни казалось, 0,9999… = 1.

Так какое же самое большое число, меньшее единицы? Единственное удовлетворительное заключение, которое можно сделать, исходя из этого парадокса, состоит в том, что самого большого числа меньше единицы не существует.

Парадокс, связанный с гонкой Ахилла за черепахой, разрешился, когда мы записали продолжительности его «шагов» как сумму с бесконечным числом слагаемых. Такие суммы известны также как бесконечные ряды. При сложении членов бесконечного ряда возможны два случая в зависимости от того, конечным или бесконечным будет предел, то есть то число, к которому сумма подходит все ближе и ближе по мере прибавления все новых членов. Если предел конечный, то ряд называется сходящимся. Если нет — ряд называется расходящимся.

Например, мы видели, что ряд

сходится, и сходится он к числу 2. Кроме того, много рядов, как мы видели, сходятся к числу π.

Напротив, ряд

расходится, устремляясь в бесконечность.

Когда я учил математику, одним из моих любимых упражнений было занятие с бесконечными рядами, состоявшее в выяснении того, сходится данный ряд или расходится. Меня всегда поражало, что при всем колоссальном различии между сходимостью и расходимостью — различии между конечным числом и бесконечностью, отличающимися на бесконечность, — детали, определяющие поведение ряда, порой кажутся совершенно несущественными.

Взглянем на гармонический ряд:

Числитель каждого из членов здесь равен 1, а знаменатели — просто все натуральные числа. С виду ряд должен бы сходиться. Каждый следующий член в этом ряду делается все меньше и меньше, так что можно было бы ожидать, что сумма всех членов окажется ограниченной некоторым фиксированным числом. Однако же гармонический ряд — расходящийся, подобно замедляющейся, но не останавливающейся улитке. Сумма первых 100 членов ряда едва превышает 5. Сумма впервые превышает число 100 только после суммирования 15 092 688 622 113 788 323 693 563 264 538 101 449 859 497 членов. Эта упорная улитка будет продолжать свое движение к свободе, преодолевая любое заданное ей расстояние. В конце концов ряд достигнет миллиона, затем миллиарда, уходя все далее и далее к бесконечности. (Доказательство этого факта приводится в приложении 5 на сайте, посвященном этой книге.)

Гармонический ряд возникает при рассмотрении процесса укладки кирпичей. Пусть у вас имеются два одинаковых кирпича и вы желаете расположить их один на другом так, чтобы верхний кирпич выступал над нижним далеко, насколько возможно, но не падал. Для этого нужно положить верхний кирпич в точности на половину нижнего, как показано на рисунке, — так центр тяжести верхнего кирпича будет опираться на самый край нижнего.

А как же расположить три кирпича, спросим мы себя, чтобы суммарное их нависание было максимальным, но сама конструкция не опрокидывалась? Решение состоит в том, что самый верхний кирпич должен лежать на половине среднего, а средний — был бы сдвинут вдоль нижнего на четверть его длины, как показано на рисунке.

Продолжая в том же духе с большим числом кирпичей, мы получим общую закономерность: чтобы гарантировать максимальное суммарное нависание, самый верхний кирпич надо сдвинуть относительно второго на половину его длины, второй — на четверть длины третьего, третий — на одну шестую длины четвертого, а тот — на одну восьмую длины пятого и т. д. Получается «Пизанская башня» из кирпичей.

Как сложить кирпичи с максимальным нависанием так, чтобы они не опрокинулись

Полное нависание этой башни, представляющее собой сумму отдельных нависаний, дается следующим рядом:

что можно записать в виде

Но это — половина суммы гармонического ряда, если только мы не будем останавливаться и возьмем все бесконечное число членов. А поскольку мы знаем, что гармонический ряд растет до бесконечности, то после его деления на два все равно останется бесконечность, потому что бесконечность, деленная на два, — снова бесконечность. В терминах кирпичной кладки это означает, что теоретически возможно создать ничем не скрепленную конструкцию, свисающую на любую наперед заданную величину. Коль скоро деленный на два гармонический ряд рано или поздно превысит любое заданное число, если только взять достаточно много членов, нависание наклонной башни из кирпичей рано или поздно превысит любое заданное значение, если только положить друг на друга достаточно много кирпичей. Хотя это теоретически и возможно, практические аспекты построения башни с большим нависанием довольно пугающи. Дабы достичь нависания в 50 кирпичей, понадобится башня из 15 × 1042 кирпичей — что намного превысит расстояние от строительной площадки до края наблюдаемой Вселенной.

Гармонический ряд оказывается обильным источником разнообразных забав, так что давайте поиграем с ним еще немного. Рассмотрим гармонический ряд, в котором выкинут каждый член, содержащий в себе 9; получится снова бесконечный ряд. Другими словами, мы выкинем следующие члены:

А «общипанный» ряд будет иметь вид:

Вспоминая, что члены гармонического ряда суммируются к бесконечности, можно было бы думать, что гармонический ряд, лишенный девяток, также суммируется к достаточно большому числу. А вот и нет! Его сумма чуть меньше числа 23.

Отфильтровав девятки, мы приручили грозную бесконечность.

Этот результат представляется удивительным, но, посмотрев на происходящее повнимательнее, мы, несомненно, поймем, в чем тут дело. Устранение девяток избавляет нас только от одного из первых 10 членов гармонического ряда. Но уже в первой сотне удаляются 19 членов, а в первой тысяче — 271. Когда числа становятся очень большими, скажем, длиной в 100 цифр, подавляющее большинство их содержит хотя бы одну девятку. И оказывается, что «утоньшение» гармонического ряда за счет удаления членов с девятками удаляет почти все члены.

Однако тонкая настройка гармонического ряда может оказаться еще более захватывающей. Мы произвольным образом решили удалить девятки. Если бы мы удалили из гармонического ряда все члены, содержащие 8, то оставшиеся члены также сходились бы к конечному числу, и то же самое повторилось бы при удалении всех членов, содержащих 7, и вообще любую выбранную цифру. На самом деле нет никакой необходимости ограничиваться отдельными цифрами. Удалим все члены, содержащие любое выбранное число, и «утоньшенный» таким способом гармонический ряд окажется сходящимся. Таким числом может быть, например, 9 или 42, или 666, или 314 159, — в каждом случае действует то же самое рассуждение.

Возьмем для примера число 666. В числах между 1 и 1000 сочетание цифр 666 встречается один раз. Между 1 и 10 000 оно встречается 20 раз, между 1 и 100 000 — 300 раз. Другими словами, процент его появления равен 0,1 % в первой тысяче чисел, 0,2 % — в первых 10 000 и 0,3 % — в первых 100 000. По мере перехода ко все большим и большим числам сочетание 666 будет встречаться все чаще и чаще. В конце концов окажется, что почти все числа содержат в себе 666. Стоит только выбросить их из гармонического ряда — и полученный «утоньшенный» ряд будет сходиться.

В 2008 году Томас Шмелцер и Роберт Бейли вычислили, что гармонический ряд, лишенный членов, содержащих число 314 159, суммируется к числу, немного превосходящему 2,3 миллиона. Это большое число, но ему ох как далеко до бесконечности.

Отсюда следует, что «гармонический ряд», состоящий из одних только членов, включающих сочетание цифр 314 159, должен суммироваться к бесконечности. Другими словами, ряд

суммируется к бесконечности. Хотя он и начинается с очень маленького числа, и затем его члены становятся только меньше, сумма всех членов в конце концов преодолеет любое наперед заданное число. Причина, как и раньше, состоит в том, что, когда числа делаются очень большими, почти каждое число содержит в себе последовательность цифр 314 159. Почти все дроби с единичным числителем содержат 314 159 в знаменателе.

Напоследок взглянем на еще один бесконечный ряд, который тоже позволит нам прикоснуться к тайнам простых чисел. Простой гармонический ряд — это дроби с единичным числителем, знаменатели которых суть простые числа:

По мере увеличения чисел простые числа встречаются все реже и реже, так что можно было бы ожидать, что у этого ряда в конце концов не хватит сил, чтобы достичь бесконечности. Но — вы не поверите — он ее достигает! Этот впечатляющий результат, идущий вразрез с интуицией, заставляет нас осознать мощь и важность простых чисел. На них можно смотреть не только как на строительные элементы для натуральных чисел, но и как на строительные элементы, слагающие бесконечность.