Алекс в стране чисел. Необычайное путешествие в волшебный мир математики

Беллос Алекс

(А90822)1, 1, 2, 1, 1, 2, 2, 2, 3, 1, 1, 2, 1, 1, 2, 2, 2, 3, 2, 1, 1, 2…

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

Это экстремально большое число. Например, вся Вселенная содержит только 10 ⁸⁰элементарных частиц. В конце концов появится и шестерка, но на таком расстоянии от начала, которое разумно можно описать только как степень степени степени степени степени:

.

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

* * *

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

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

(А 79)1, 2, 4, 8, 16…

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

1 + 2 = 3. Число 3 простое, так что мы умножим 3 на старшее из наших удвоений, то есть на 2: 3 x 2 = 6, а число 6 совершенно.

1 + 2 + 4 = 7. Число 7 снова простое. Поэтому умножим 7 на 4, что даст еще одно совершенное число, а именно 28.

1 + 2 + 4 + 8 = 15. Это число не простое. Не появится здесь и совершенного числа.

1 + 2 + 4 + 8 + 16 = 31. Это число простое, а 31 x 16 = 496 — совершенное число.

1 + 2 + 4 + 8 +16 + 32 = 63. Это число не простое.

1 + 2 + 4 + 8 + 16 + 32 + 64 = 127. Это число также простое, а 127 x 64 = 8128 — совершенное число.

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

1 + 2 = 3 = 4 - 1, или 2 ⁰+ 2 ¹= 2 ² – 1

1 + 2 + 4 = 7 = 8–1, или 2 ⁰+ 2 ¹+ 2 ²= 2 ³– 1.

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

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

Если число 2 ⁿ– 1 простое, то число (2 ⁿ– 1) x 2 ^n-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 простое. По его словам, это были значения

(А109 461)2, 3, 5, 7, 13, 17, 19, 31, 67, 127, 257.

Мерсенн был дельным математиком, однако его список — по большей части плод угадывания. Число 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 — оно было слишком большим для ручных вычислений.