Текст книги "Тайны чисел: Математическая одиссея"

Как использовать рис и шахматную доску для поиска простых чисел?

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

Раджа мгновенно согласился, пораженный тем, что математик был готов довольствоваться столь малым, – однако его ждало потрясение. Когда на доску начали класть рис, то зернышки на первых клетках были едва видны. Но на 16-ю клетку потребовалось около килограмма риса. Для двадцатой клетки его слуга прикатил тачку риса. До 64-й клетки, последней на доске, так и не дошли. Для этого общее количество рисинок должно было дойти до ошеломительного числа

18 446 744 073 709 551 615.

Пожелай мы повторить этот подвиг в центре Лондона, гора риса достигла бы окружающей город автомагистрали М25 и была бы настолько высокой, что покрыла бы все здания. Фактически, в этой горе оказалось бы больше риса, чем было выращено на всем земном шаре в предшествующем тысячелетии.

Рис. 1.24. Продолжение удвоения приводит к быстрому росту чисел

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

Но какое отношение имеет весь этот рис к поиску больших простых чисел? С того времени, как греки доказали, что простые числа продолжаются бесконечно, математики находились в непрестанном поиске умных формул, генерирующих все бо́льшие и бо́льшие простые числа. Одна из лучших таких формул была открыта французским монахом по имени Марен Мерсенн. Мерсенн был близким другом Пьера де Ферма и Рене Декарта, он служил своего рода интернет-хабом XVII в. Мерсенн состоял в переписке с учеными по всей Европе и делился идеями с теми, кто, на его взгляд, мог бы способствовать их дальнейшему развитию.

Его общение с Ферма привело к открытию мощной формулы для нахождения простых чисел. Секрет этой формулы спрятан в притче о рисе и шахматной доске. Когда вы считаете рисинки начиная с первой клетки, то сумма часто оказывается простым числом. Например, после первых трех клеток результат равен 1 + 2 + 4 = 7 рисинок, что является простым числом. Общее количество на пяти клетках будет 1 + 2 + 4 + 8 + 16 = 31 рисинка.

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

К несчастью для Мерсенна и математики, эта идея оказалась не совсем верной. Так, когда вы выберете 11-ю клетку на шахматной доске (этот номер соответствует простому числу), то с первой по эту клетку включительно будет 2047 рисинок. К сожалению, 2047 – составное число, оно равно 23 × 89. Но, хотя идея Мерсенна срабатывает не всегда, она привела к нахождению некоторых из самых больших известных простых чисел.

Книга Гиннесса простых чисел

Во время правления королевы Елизаветы I самым большим известным простым числом было количество рисинок на шахматной доске до девятнадцатой клетки включительно: 524 287. К тому моменту, когда лорд Нельсон сражался в Трафальгарской битве, рекордное простое число дошло до 31-й клетки: 2 147 483 647. Швейцарский математик Леонард Эйлер доказал в 1772-м, что это десятизначное число – простое. Оно удерживало первенство до 1867 г.

4 сентября 2006 г. рекорд перешел к числу, которое соответствует 32 582 657-й клетке, будь у нас достаточно большая шахматная доска. В этом новом простом числе более 9,8 миллиона цифр. Чтобы прочитать его вслух, потребовалось бы полтора месяца. Оно было найдено не каким-то гигантским суперкомпьютером, а математиком-любителем, который использовал программу, загруженную из интернета.

Замысел этой программы состоит в том, чтобы использовать компьютер во время его бездействия для проведения вычислений. В ней используется умная стратегия, которая была разработана для проверки того, являются ли числа Мерсенна простыми. Все же настольному компьютеру понадобилось несколько месяцев для проверки числа с 9,8 миллиона цифр. Но это намного быстрее методов, которые используются для тестирования того, является ли случайное число такого же размера простым. К 2009 г. более 10 тысяч человек присоединились к проекту по поиску простых чисел Мерсенна GIMPS (Great Internet Mersenne Prime Search).

Однако будьте начеку, этот поиск небезопасен. Один доброволец GIMPS работал в американской телефонной компании. Он решил привлечь к своему поиску простых чисел Мерсенна 2585 компьютеров компании. Вскоре у руководства возникли подозрения: компьютерам требовалось 5 минут, а не 5 секунд, чтобы выдавать телефонные номера. Когда в конечном счете ФБР сумело найти причину замедления, служащий признался: «Вся эта вычислительная мощь была слишком большим искушением для меня». Но телефонная компания не прониклась симпатией к научному поиску и уволила служащего.

Если вы хотите, чтобы ваш компьютер присоединился к GIMPS, загрузите программное обеспечение на сайте www.mersenne.org.

После сентября 2006 г. математики ждали затаив дыхание, что рекорд преодолеет барьер в 10 000 000 цифр. У предвкушения были не только академические причины: премия в $ 100 000 ждала того, кто первым преодолеет этот барьер. Деньги были выделены расположенным в Калифорнии Фондом электронных рубежей EFF (Electronic Frontier Foundation). Эта организация способствует сотрудничеству в киберпространстве и его развитию.

Понадобилось еще два года, чтобы рекорд пал. По жестокой прихоти судьбы с промежутком в несколько дней были найдены два простых числа-рекордсмена. Немецкий энтузиаст Ганс-Михаэль Элвених, занимавшийся любительским поиском простых чисел, решил, что он сорвал джекпот, когда его компьютер объявил 6 сентября 2008 г., что найдено новое простое число Мерсенна с 11 185 272 цифрами. Элвених представил результат жюри, но возбуждение сменилось отчаянием – его опередили на 14 дней. 23 августа компьютер Эдсона Смита, работавшего на математическом факультете Калифорнийского университета в Лос-Анджелесe (UCLA), нашел большее простое число с 12 978 189 цифрами. Обновление рекорда простых чисел не было в новинку для Калифорнийского университета. Математик Рафаэль Робинсон, работавший в UCLA, открыл пять простых чисел Мерсенна в 1950-х гг., и еще два были найдены Алексом Гурвицем в начале 1960-х.

Разработчики программы, используемой GIMPS, решили, что призовые деньги не должны просто быть отправлены счастливчику, получившему для проверки число Мерсенна. $ 5000 получили разработчики программного обеспечения, $ 20 000 были поделены между теми, кто обновлял рекорды после 1999 г., $ 25 000 пошли на благотворительность, а оставшиеся деньги достались Эдсону Смиту из Калифорнии.

Если вы по-прежнему хотите выиграть деньги посредством поиска простых чисел, не берите в голову, что отметка в 10 000 000 цифр уже пройдена. За каждое новое число Мерсенна будет выдан приз в $ 3000. Но, если вам нужны большие деньги, знайте, что $ 150 000 предлагается превзошедшему отметку в 100 миллионов цифр, а $ 200 000 получит тот, кто пересечет рубеж в миллиард цифр. Благодаря древним грекам мы знаем, что такие рекордные простые числа дожидаются, пока кто-нибудь обнаружит их. Вопрос лишь в том, насколько инфляция уничтожит призовые деньги, когда очередной рекордсмен подаст заявку на их получение.

Как написать число с 12 978 189 цифрами

Простое число Эдсона Смита феноменально велико. Чтобы записать его цифры в этой книге, понадобилось бы 3000 страниц. К счастью, небольшое математическое упражнение приводит к формуле, которая представляет это число значительно более кратким образом.

Полное число рисинок с 1 по N-ю клетку доски включительно определяется выражением

R = 1 + 2 + 4 + 8 +… + 2^N – 2 + 2^{N – 1}.

Прием для нахождения формулы для этого числа состоит в следующем. Перепишем R = 2R – R, данное преобразование настолько очевидно, что на первый взгляд кажется бесполезным. Каким же образом столь очевидное выражение может помочь в вычислении R? В математике часто оказывается полезным взглянуть на вещи с несколько иной перспективы, после чего они могут самым неожиданным образом поменять свой вид.

Давайте сначала вычислим 2R. Это лишь означает удвоение всех слагаемых в большой сумме. Но смысл преобразования в том, что удвоение числа рисинок на одной из клеток приводит к числу рисинок на следующей клетке. Итак,

2R = 2 + 4 + 8 + 16 +… + 2^N – 1 + 2^N.

Следующий шаг состоит в вычитании R. Это выбьет из 2R все члены, кроме последнего:

R = 2R – R = (2 + 4 + 8 + 16 +… + 2^N – 1 + 2^N) –

– (1 + 2 + 4 + 8 +… + 2^N – 2 + 2^N – 1) =

= (2 + 4 + 8 + 16 +… + 2^N – 1) +

+ 2^N – 1 – (2 + 4 + 8+… + 2^N – 2 + 2^N – 1) =

= 2^N– 1.

Итак, полное число рисинок с 1-й по N-ю клетки шахматной доски равно 2^N – 1, эта формула и отвечает за бьющие рекорд простые числа сегодняшнего дня. Удваивайте достаточное количество раз, затем отнимите 1, и вы можете надеяться, что наткнетесь на простое число Мерсенна. Так называются простые числа, полученные с помощью данной формулы. В ней нужно положить N = 43 112 609, и вы получите простое число Эдсона Смита с его 12 978 189 цифрами.

Как драконова лапша пересекает Вселенную

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

Повара по всей Азии соревнуются в удвоении длины лапши максимальное количество раз. В 2001 г. тайваньский повар Чанг Хан Ю сумел удвоить длину своего теста 14 раз за 2 минуты. В конце у него получилась настолько тонкая лапша, что она могла бы пройти сквозь игольное ушко. Могущество удвоения таково, что полученная лапша могла бы протянуться из ресторана господина Чанга в центре Тайбэя до окраины города. Когда она была нарезана, то получилось 16 384 куска лапши.

Эта сила удвоения очень быстро приводит к крайне большим числам. Например, если бы Чанг Хан Ю мог продолжить и удвоить длину своей лапши 46 раз, толщина лапши была бы порядка размера атома. Она была бы достаточно длинной, чтобы протянуться из Тайбэя до внешних пределов Солнечной системы. Удвоившись по длине 90 раз, лапша могла бы протянуться от одного края наблюдаемой Вселенной до другого. Чтобы ощутить, насколько велик сегодняшний рекордсмен простых чисел, открытый в 2008 г., представьте, что лапшу удвоили 43 112 609 раз и затем отняли один кусок лапши.

Насколько велик шанс, что ваш телефонный номер – простое число?

Одна из причуд, свойственных математикам, состоит в проверке того, является ли телефонный номер простым числом. Я недавно переехал в другой дом, и мне требовалось поменять телефонный номер. Мой предыдущий телефонный номер не был простым числом, а номер дома, 53, был. Я надеялся, что по новому адресу (номер 1, бывшее простое число) мне повезет больше.

Первый номер, который мне предложила телефонная компания, выглядел обещающе, но, когда я проверил его на компьютере, оказалось, что он делится на 7. «Я не уверен, что сумею запомнить этот номер… нет ли возможности получить другой?» Но следующий также был составным – он делился на 3. (Легкий способ проверки того, делится ли ваш номер на 3, состоит в следующем: нужно сложить вместе его цифры, если сумма делится на 3, то тем же свойством обладает и номер.) После трех последующих попыток терпение служащего телефонной компании лопнуло: «Сэр, боюсь, что я попросту присвою вам первый появившийся номер». И, увы, теперь он у меня четный. Вот это номер!

Итак, каковы были мои шансы получить простой телефонный номер? В нем восемь цифр. У восьмизначного числа приблизительно один шанс из семнадцати оказаться простым. Но как меняется эта вероятность с увеличением количества цифр? Например, имеется 25 простых чисел, меньших 100, что означает, что у числа с 1 или 2 цифрами один шанс из четырех оказаться простым. В среднем при счете от 1 до 100 каждое четвертое число будет простым. Но чем дальше вы считаете, тем реже становятся простые числа.

В приведенной таблице показано изменение вероятности:

Таблица 1.02

Простые числа становятся все реже и реже, но их уменьшение происходит регулярным образом. Каждый раз, когда я добавляю разряд, число во втором столбце увеличивается на 2,3. Первым, кто заметил это, был пятнадцатилетний мальчик. Его звали Карл Фридрих Гаусс (1777–1855), впоследствии он стал одним из величайших математиков.

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

Но как можно быть уверенным в том, что вы неожиданно не столкнетесь с чем-то странным, когда дойдете до рубежа чисел из 100 цифр или 1 000 000 цифр? Будет ли вероятность по-прежнему сводиться к добавлению 2,3 при появлении нового разряда, либо вероятности неожиданно начнут вести себя совершенно иначе? Гаусс предполагал, что закономерность не подвергнется изменению, но лишь в 1896 г. его убеждение получило обоснование. Два математика, Жак Адамар и Шарль де ла Валле Пуссен, независимо доказали то, что теперь называется теоремой о распределении простых чисел. Она состоит в продолжении этого разрежения простых чисел.

Открытие Гаусса привело к созданию весьма действенной модели, которая позволяет предсказать многое о поведении простых чисел. Все выглядит, словно природа кидает игральные кости для определения того, будет ли число простым. Все грани этих костей пусты, за исключением одной, где написано слово «ПРОСТОЕ»:

Рис. 1.25. Игральные кости природы

Подбросьте игральную кость, чтобы решить, станет ли число простым. Если внизу окажется подписанная грань, то оно станет простым, если пустая грань, то нет. Конечно, это всего-навсего эвристическая модель – вы не можете лишить число 100 его делителей посредством удачного броска игральной кости. Но данная модель дает числа, распределение которых, как полагают, крайне напоминает распределение простых чисел. Теорема о распределении простых чисел Гаусса говорит нам, сколько должно быть граней у игральной кости. Так, для числа с тремя цифрами нужно использовать кость с шестью гранями, или кубик с одной подписанной гранью. Для чисел с четырьмя цифрами возьмите кость с восемью гранями, октаэдр. Если же в числе пять цифр, используйте кость с 10,4 грани… Конечно, такая игральная кость сугубо теоретическая, ведь не может быть многогранника, у которого число граней 10,4.

В чем состоит задача на миллион долларов?

Вопрос на миллион долларов касается природы этих игральных костей: честные они или шулерские? Будут ли они распределять простые числа во вселенной всех чисел справедливо или же будут области с предвзятыми результатами, где простых чисел слишком много либо слишком мало? Эта задача называется гипотезой Римана. Бернхард Риман был студентом Гаусса в немецком городе Гёттингене. Он разработал крайне изощренный математический аппарат, позволяющий понять, каким образом эти кости распределяют простые числа. Используя специальную функцию, называемую дзета-функцией, особые числа, называемые компле́ксными, и проведя анализ, ошеломляющий по своему объему, Риман разработал математику, контролирующую падение этих игральных костей. Он полагал, основываясь на своем анализе, что игральные кости должны быть «честными», но не мог доказать этого. Доказать гипотезу Римана – ваша задача.

Другая интерпретация гипотезы Римана состоит в уподоблении простых чисел молекулам газа в комнате. Вы не можете знать в произвольном случае, где находится каждая из молекул, но физика утверждает, что молекулы будут довольно равномерно распределены по комнате. Невозможно такое, что в одном углу будет повышенная концентрация молекул, а в другом – полный вакуум. У гипотезы Римана схожие следствия применительно к простым числам. Она не может подсказать нам, где находится каждое из простых чисел, но гарантирует, что во вселенной чисел они распределены справедливым, пусть и случайным образом. Для математиков часто хватает такого вида гарантии, чтобы пуститься в навигацию по вселенной чисел с достаточной степенью уверенности. Тем не менее, пока не получен приз в миллион долларов, мы не вполне можем осознавать, как ведут себя простые числа, по мере того как наш счет уводит все глубже и глубже в нескончаемые просторы математического космоса.

Глава 2
Рассказ о неуловимой форме

Великий ученый XVII в. Галилео Галилей однажды написал:

Вселенная не может быть прочитана, пока мы не выучили язык и не ознакомились с буквами, из которых он состоит. Она написана на математическом языке, а буквами являются треугольники, круги и другие геометрические фигуры, без посредства которых понять одно-единственное слово не в человеческих силах. Несведущий в них блуждает в темном лабиринте[2]2
  Пробирных дел мастер (Il Saggiatore), 1623 г.


[Закрыть].

В этой главе представлен алфавит причудливых и замечательных форм природы: oт шестиконечной снежинки до спирали ДНК, от поворотной симметрии алмаза до сложной формы листка. Отчего пузыри безупречно сферичны? Как в живом теле появляются чрезвычайно сложные формы вроде человеческого легкого? Какая форма у нашей Вселенной? Математика лежит в основе понимания того, как и почему природа порождает подобное разнообразие форм. Она также наделяет нас возможностью создавать новые формы и способностью рассудить, в каком случае новые формы невозможны.

Не только математики интересуются формами: архитекторы, инженеры, ученые и художники – все хотят понять, как действуют формы природы. При этом они опираются на математику геометрии. Древнегреческий философ Платон поместил над входом в свою школу надпись: «Не знающий геометрии да не войдет сюда». В этой главе я постараюсь выдать вам пропуск к Платону, в мир математических форм. А в конце открою вам головоломку, решение которой оценивается в другой миллион долларов.

Почему пузыри сферичны?

Возьмите кусок проволоки и согните его в квадрат. Погрузите его в мыльный раствор, выньте и подуйте. Почему у пузыря, который выходит с другой стороны, не будет формы куба? А если проволока согнута в виде треугольника, почему не получается выдуть пирамидальный пузырь? Отчего, какой бы ни была форма рамки, пузырь получается безупречно сферичным? Ответ состоит в том, что природа ленива, а сфера для природы – самая легкая форма. Пузырь стремится приобрести такую форму, которая использует наименьшую энергию, а последняя пропорциональна площади поверхности. В пузыре содержится заданный объем воздуха, который не меняется при преобразованиях формы. А у сферы, содержащей заданное количество воздуха, – наименьшая площадь поверхности. Это делает ее энергетически выгодной, она использует меньше всего энергии.

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

Когда жидкие капли расплавленного металла падают с верхушки высокой башни, то в своем падении они подобно пузырям приобретают сферическую форму поверхности. Уоттс заинтересовался тем, что будет, если внизу башни поставить чан с водой, – застынут ли капельки с сохранением идеальной формы при попадании в воду. Он решил проверить эту идею в собственном доме в Бристоле. Загвоздка была в том, что требовалась высота более трех этажей, чтобы дать каплям расплавленного свинца достаточное время для приобретения сферической формы.

Тогда Уоттс пристроил к своему дому еще три этажа и проделал в полах отверстия, чтобы свинец падал сквозь все здание. Соседи были слегка шокированы неожиданным появлением башни, хотя владелец и пытался придать ей готический флер, добавив сверху архитектурные украшения, как у замка. Эксперименты Уоттса оказались настолько успешны, что подобные башни стали появляться по всей Англии и Америке. Его башня по отливу дроби продолжала работать до 1968 г.

Рис. 2.01. Умное использование Уильямом Уоттсом свойств природы для производства дроби

Хотя природа и использует сферу столь часто, как мы можем быть уверены, что не существует какой-то более странной формы, которая окажется энергетически более эффективной, чем сфера? Великий греческий математик Архимед первым предположил, что у сферы на самом деле наименьшая площадь поверхности, когда содержащийся внутри объем фиксирован. Чтобы попытаться доказать это, Архимед начал с выведения формул для площади сферы и для объема, содержащегося в ней.

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

Рис. 2.02. Шар может быть приближен положенными друг на друга дисками разного размера

Затем последовала по-настоящему умная часть. Если он будет делать диски тоньше и тоньше, пока они не станут бесконечно тонкими, то их суммарный объем даст в точности объем шара. Это был один из первых случаев использования идеи бесконечности в математике. Подобная техника стала впоследствии основой математического анализа, развитого Исааком Ньютоном и Готфридом Лейбницем спустя почти две тысячи лет.

Архимед продолжал использовать этот метод для вычисления объемов, ограниченных различными формами. Особенно он был горд открытием того, что объем воздуха в цилиндре, высота которого равна диаметру вписанного в него шара, составляет половину объема шара. Он был так взволнован этим фактом, что завещал, чтобы на его надгробии были высечены цилиндр и шар.

Хотя Архимед нашел успешный метод для вычисления площади сферы и объема ограниченного ею шара, ему не хватило умения для доказательства предположения, что сфера – самая эффективная форма в природе. Поразительно, но лишь к 1884 г. математика была достаточно разработана для того, чтобы немец Герман Шварц сумел доказать, что не имеется таинственных форм, которые могут побить энергетическую эффективность сфер.