Тайны чисел. Математическая одиссея - Маркус Дю Сотой Страница 13

Разработчики программы, используемой 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 +… + 2N – 2 + 2N – 1.

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

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

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

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

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

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

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

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

= 2N– 1.

Итак, полное число рисинок с 1-й по N-ю клетки шахматной доски равно 2N – 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), впоследствии он стал одним из величайших математиков.