Как использовать рис и шахматную доску для поиска простых чисел?
По легенде, шахматы были придуманы индийским математиком. Раджа был настолько благодарен математику за увлекательную игру, что предложил ему самому назвать свое вознаграждение. Изобретатель подумал минутку, а потом попросил, чтобы на первую клетку шахматной доски положили одно зерно риса, на вторую клетку – две рисинки, на третью – четыре, на четвертую – восемь, и так далее, чтобы на каждой последующей клетке было в два раза больше зерен, чем на предыдущей.
Раджа мгновенно согласился, пораженный тем, что математик был готов довольствоваться столь малым, – однако его ждало потрясение. Когда на доску начали класть рис, то зернышки на первых клетках были едва видны. Но на 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-х.
