Тайны чисел: Математическая одиссея - Сотой Маркус. Страница 11
Но какое отношение имеет весь этот рис к поиску больших простых чисел? С того времени, как греки доказали, что простые числа продолжаются бесконечно, математики находились в непрестанном поиске умных формул, генерирующих все бо́льшие и бо́льшие простые числа. Одна из лучших таких формул была открыта французским монахом по имени Марен Мерсенн. Мерсенн был близким другом Пьера де Ферма и Рене Декарта, он служил своего рода интернет-хабом 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 получит тот, кто пересечет рубеж в миллиард цифр. Благодаря древним грекам мы знаем, что такие рекордные простые числа дожидаются, пока кто-нибудь обнаружит их. Вопрос лишь в том, насколько инфляция уничтожит призовые деньги, когда очередной рекордсмен подаст заявку на их получение.
Простое число Эдсона Смита феноменально велико. Чтобы записать его цифры в этой книге, понадобилось бы 3000 страниц. К счастью, небольшое математическое упражнение приводит к формуле, которая представляет это число значительно более кратким образом.
Полное число рисинок с 1 по N-ю клетку доски включительно определяется выражением
Прием для нахождения формулы для этого числа состоит в следующем. Перепишем R = 2R – R, данное преобразование настолько очевидно, что на первый взгляд кажется бесполезным. Каким же образом столь очевидное выражение может помочь в вычислении R? В математике часто оказывается полезным взглянуть на вещи с несколько иной перспективы, после чего они могут самым неожиданным образом поменять свой вид.
Давайте сначала вычислим 2R. Это лишь означает удвоение всех слагаемых в большой сумме. Но смысл преобразования в том, что удвоение числа рисинок на одной из клеток приводит к числу рисинок на следующей клетке. Итак,
Следующий шаг состоит в вычитании R. Это выбьет из 2R все члены, кроме последнего:
Итак, полное число рисинок с 1-й по N-ю клетки шахматной доски равно 2N – 1, эта формула и отвечает за бьющие рекорд простые числа сегодняшнего дня. Удваивайте достаточное количество раз, затем отнимите 1, и вы можете надеяться, что наткнетесь на простое число Мерсенна. Так называются простые числа, полученные с помощью данной формулы. В ней нужно положить N = 43 112 609, и вы получите простое число Эдсона Смита с его 12 978 189 цифрами.