Числа Серпинского
Специалисты по теории чисел, занятые поисками больших простых чисел, часто рассматривают числа вида k2n + 1 для какого-то выбранного k при разных n. Пробные расчеты позволяют предположить, что для большинства значений k среди этих чисел встречается по крайней мере одно простое число, часто больше. К примеру, если k = 1, то 1 × 2n + 1 является простым для n = 2, 4, 8. Если k = 3, то 3 × 2n + 1 простое при n = 1, 2, 5, 6, 8, 12. Если k = 5, то 5 × 2n + 1 простое при n = 1, 3, 7. (В общем случае мы можем разделить k на 2 столько раз, сколько нужно, чтобы получить нечетное число, а все двойки включить в 2n. Поэтому можно смело считать k нечетным, не теряя общности. К примеру, 24 × 2n = 3 × 23× 2n = 3 × 2n+3.)
Соблазнительно предположить, что для любого k³≥2 существует по крайней мере одно простое число вида k2n + 1. Однако в 1960 г. Вацлав Серпинский доказал, что существует бесконечно много нечетных k, для которых все числа вида k2n + 1 являются составными. Эти числа получили название чисел Серпинского.
В 1992 г. Джон Селфридж доказал, что 78 557 – число Серпинского; он показал, что все числа вида 78 557 × 2n + 1 делятся по крайней мере на одно из чисел 3, 5, 7, 13, 19, 37, 73. Говорят, что эти числа образуют покрывающее множество. Приведем первые десять известных чисел Серпинского:
78 557 271 129 271 577 322 523 327 739
482 719 575 041 603 713 903 983 934 909
Считается, что 78 557 – наименьшее число Серпинского, но пока этот факт никем не доказан и не опровергнут. В 2002 г. на сайте www.seventeenorbust.com был организован поиск простых чисел вида k2n + 1, существование которых доказывало бы, что k не является числом Серпинского. Когда поиск только начинался, у математиков было 17 кандидатов на роль чисел Серпинского, не превышающих 78 557, но постепенно они были ликвидированы, так что осталось только шесть: 10 223, 21 181, 22 699, 24 737, 55 459 и 67 607. Попутно в рамках проекта было найдено несколько очень больших простых чисел.
Джеймс Джозеф кто?
Джеймс Джозеф Силвестер – английский математик, работавший с Артуром Кейли, в частности в области теории матриц и теории инвариант. Всю жизнь он очень интересовался поэзией и часто вставлял стихотворные цитаты в свои математические научные статьи. В 1841 г. он переехал в США, но вскоре вернулся обратно. В 1877 г. он вновь пересек Атлантику, занял место первого профессора математики в Университете Джона Хопкинса и основал American Journal of Mathematics, издающийся с немалым успехом и сегодня. Он вернулся в Англию в 1883 г.
Изначально его звали просто Джеймс Джозеф. Когда его старший брат эмигрировал в США, в офисе иммиграционной службы ему сказали, что у каждого должно быть по три имени: два имени и фамилия. По какой-то причине брат взял себе новую фамилию – Силвестер, сделав прежнюю вторым именем. Джеймс Джозеф последовал примеру брата.
Ограбление в Баффлхэме
Из мемуаров доктора Ватсапа
При ограблении величественного особняка лорда Баффлхэма из сейфа похитили несколько изумрудов и рубинов. Сомс, которого пригласили расследовать дело, быстро заподозрил двух гостей – леди Изабеллу Никетт и баронессу Руби Робхэм. Та и другая испытывали серьезные материальные трудности и, без сомнения, не устояли перед искушением. Но где доказательства?
Обе дамы признались, что у них есть кое-какие драгоценности, но утверждали, что это их собственность. Сомсу пока не удалось убедить инспектора Роулейда получить ордер на обыск в аристократических домах, хотя это могло бы разрешить все проблемы; пока же он не мог заглянуть в шкатулки с драгоценностями означенных дам.
– Дело, – сказал Сомс, – определяется тем, сколько драгоценностей имеют наши две дамы. Если их число совпадает с числом похищенных вещей, мы получаем последнее необходимое доказательство. Роулейд готов запросить ордер на обыск, но только если мы сможем снабдить его этими двумя числами.
– Изабелла заявила, что у нее имеются только изумруды, – пробормотал я вполголоса. – А Руби говорит, что у нее только рубины.
– В самом деле. Я уверен, что оба эти заявления правдивы. Далее, из показаний лакея следует, что число тех и других драгоценностей лежит в интервале от 2 до 101 включительно.
– Кухарка не настроена болтать о хозяйках, – заметил я. – Но мне удалось убедить ее открыть произведение этих двух чисел.
– А дворецкий, тоже неболтливый, но убежденный аргументом в виде десяти золотых соверенов, назвал мне их сумму, – отозвался Сомс.
– Значит, мы можем, решив квадратное уравнение, найти оба числа! – возбужденно воскликнул я.
– Разумеется, хотя мы не будем знать, какое из чисел относится к изумрудам, а какое – к рубинам, – протянул Сомс. – Данные симметричны. Но любого совпадения будет достаточно, чтобы инспектор Роулейд получил ордер на обыск, а там все, я не сомневаюсь, найдется.
– Если вы назовете мне произведение, – сказал я, – то я смогу решить уравнение.
– Ах, мой дорогой Ватсап, вам не достает утонченности, – критически заметил Сомс. – Дайте посмотреть, нельзя ли вывести числа без этого… Так, знаете, чему они равны?
– Нет.
– Я так и знал, – заявил Сомс, к моему раздражению. Если знал, зачем спрашивать? Неожиданно меня осенило.
– Теперь я тоже знаю эти числа, – объявил я.
– В таком случае я тоже их знаю, Ватсап.
Какие это два числа? Ответ см. в главе «Загадки разгаданные».
Квадриллион знаков числа π
В настоящее время нам известно десятичное значение π с точностью до 12 100 000 000 050 знаков; соответствующий расчет провел в 2013 г. Сигеру Кондо, и потребовалось ему на это 94 дня. На самом деле никому нет дела до того, какой получен ответ, но известно, что замечательные рекордные усилия такого рода нередко приводят к новым озарениям, а также являются хорошим способом проверки новых суперкомпьютеров. Одно из самых забавных открытий состоит в том, что можно вычислять отдельные цифры десятичной записи π без нахождения всех предыдущих цифр. Однако в настоящее время мы можем это делать только в шестнадцатеричной нотации, то есть в системе счисления с основанием 16, из которой можно без труда получить цифры в системах счисления с основаниями 8, 4 и 2 (двоичной). Эта идея работает и для других констант, не только для π, а также для троичной системы счисления, но систематической теории на этот счет пока нет. Для десятичной нотации, то есть для системы счисления с основанием 10, ничего подобного не известно.
Первоначальное открытие, формула ББП (Бейли – Боруэйна – Плаффа), изложена ниже; вы найдете ее также в «Кабинете…» на с. 264. Это бесконечный ряд, при помощи которого можно вычислить конкретный шестнадцатеричный знак числа π, не вычисляя при этом предыдущих его знаков. Так что мы можем быть уверены, что квадриллионный двоичный знак числа π – нуль, благодаря проекту PiHex; пройдя еще дальше, скажем, что двухквадриллионный двоичный знак π также равен 0, благодаря расчету, проведенному одним из сотрудников компании Yahoo! и занявшему 23 дня. Несмотря на все наши познания, для того чтобы найти предыдущий знак, потребовался бы еще один столь же длительный расчет.
В 2011 г. Дэвид Бейли, Джонатан Боруэйн, Эндрю Маттинли и Гленн Уайтвик составили обзорное исследование этого вопроса[27]. Авторы описали способ нахождения знаков числа π² в системе счисления с основанием 64, знаков числа π² в системе счисления с основанием 729 и знаков числа, известного как постоянная Каталана, в системе счисления с основанием 4096, начиная с 10-триллионной позиции.
История начинается с последовательности, известной еще Эйлеру:
Благодаря степеням двойки, которые здесь фигурируют, этот ряд можно преобразовать в метод вычисления конкретных двоичных знаков ln 2. По мере роста номера знака вычисления остаются реализуемыми, хотя и занимают гораздо больше времени.
Формула ББП выглядит так:
и степени 16 делают возможным вычисление конкретных шестнадцатеричных знаков числа π. Поскольку 16 = 24, ряд можно использовать также для вычисления двоичных знаков.
Ограничивается ли такой подход только этими двумя константами? С 1997 г. математики ведут непрекращающийся поиск аналогичных бесконечных рядов для других постоянных величин, и им уже удалось найти их немалое количество. В том числе для π², ln² 2, π ln 2, ζ (3), π³, ln³ 2, π²ln 2, π4, ζ (5),
Формула ББП выглядит так:
и степени 16 делают возможным вычисление конкретных шестнадцатеричных знаков числа π. Поскольку 16 = 24, ряд можно использовать также для вычисления двоичных знаков.
Ограничивается ли такой подход только этими двумя константами? С 1997 г. математики ведут непрекращающийся поиск аналогичных бесконечных рядов для других постоянных величин, и им уже удалось найти их немалое количество. В том числе для π², ln² 2, π ln 2, ζ (3), π³, ln³ 2, π²ln 2, π4, ζ (5),
где
есть Риманова дзета-функция. Удалось сделать то же для постоянной Каталана
Некоторые из этих рядов дают знаки в троичной системе счисления или системе с основанием, равным какой-нибудь степени 3. К примеру, при помощи поразительной формулы Дэвида Броудхерста
можно вычислять знаки π² в системе счисления с основанием 729 = 36.
Нормально ли число π?
Десятичные знаки числа π кажутся случайными, но они не могут быть по-настоящему случайными, потому что всякий раз при вычислении числа π вы получаете ровно одно и то же (если, конечно, не ошибаетесь в процессе вычисления). Считается, что, как почти в любой случайной последовательности цифр, где-то в десятичном выражении числа π встречается любая конечная последовательность цифр. Более того, данная последовательность встречается бесконечно часто, хотя и с кучей мусора между двумя последовательными включениями, и в той же пропорции, которую следовало бы ожидать для случайной последовательности.
Можно доказать, что это свойство, известное как нормальность, выполняется для «почти всех» чисел: в любом достаточно большом наборе чисел доля нормальных подходит сколь угодно близко к 100 %. Но это правило оставляет и лазейку, поскольку любое конкретное число, скажем π, может оказаться исключением. Но является ли оно исключением? Мы не знаем. До недавнего времени этот вопрос казался безнадежным, но формулы, подобные приведенным выше, открыли новую линию атаки, которая в принципе может решить вопрос в отношении двоичных (или шестнадцатеричных) чисел.
Связь между этими задачами возникает через другую математическую процедуру, итерационную. Здесь мы начинаем с какого-то числа, применяем к нему некое правило, чтобы получить другое число, и последовательно применяем то же правило к полученным числам, чтобы получить некую последовательность чисел. К примеру, если мы начнем с 2 и применим правило «возвести в квадрат», получим последовательность
2 4 16 256 65 636 4 294 967 296 …
Двоичные знаки числа, к примеру ln 2, можно получить при помощи итерационной формулы
начиная с x0 = 0. Пояснение (mod 1) означает «вычесть целую часть», так что π (mod 1) = 0,14159… Эта формула привела бы к доказательству того, что ln 2 нормален по основанию 2, если бы удалось показать, что полученные в результате числа равномерно распределены по интервалу от 0 до 1. Подобная «равнораспределенность» встречается довольно часто. К несчастью, никто не знает, как доказать, что она распространяется на приведенную итеративную формулу, но сама по себе эта идея перспективна и, вполне возможно, со временем даст результат.
Для π тоже существует похожая, но более сложная итеративная формула:
Если эта формула дает равномерное распределение, то π нормально в двоичной системе.
Все вышеизложенное приводит нас наконец к очень странному открытию. Растянем интервал от 0 до 1 в 16 раз, так что yn = 16xn будут распределены на интервале от 0 до 16. Тогда целая часть последовательных yn будет лежать в интервале от 0 до 15. Эксперимент показывает, что эти числа в точности соответствуют последовательным шестнадцатеричным знакам числа π – 3. Этот факт проверен на компьютере для первых 10 млн знаков. Получается, по существу, что это дает нам формулу для n-го шестнадцатеричного знака π. Чем дальше вы заходите, тем сложнее становятся вычисления, и на упомянутую проверку ушло 120 часов.
Есть веские причины ожидать, что это утверждение подтвердится, но пока оно недотягивает до строгого доказательства. Известно, что ошибок, если они есть, очень мало. Поскольку на первых 10 млн шагов их не обнаружено, вероятность того, что они встретятся позже, составляет около одной миллиардной. Однако это не доказательство – всего лишь отличная причина надеяться, что доказательство существует и его можно найти.
Последняя гипотеза, также основанная на убедительных данных, показывает, насколько необычна эта область математики. А именно: ничего подобного нельзя сделать с другой известной константой – числом e, основанием натуральных логарифмов, приблизительно равным 2,71828. Похоже, в числе π есть что-то особенное в сравнении с числом e.
Математик, статистик и инженер…
…отправились на скачки. После забегов они встретились в баре. Инженер топил в пиве свои печали.
– Не могу понять, как я умудрился потерять все свои деньги. Я измерил коней, рассчитал, какой из них механически самый эффективный и выносливый, и вывел, как быстро каждый из них способен бежать…
– Это все очень хорошо, – сказал статистик, – но вы забыли, что индивидуальное состояние изменчиво. Я провел статистический анализ их предыдущих забегов и нашел при помощи байесовских методов и оценки максимального правдоподобия, какой конь выиграет с наибольшей вероятностью.
– И он выиграл?
– Нет.
– Позвольте мне угостить вас всех, парни, – сказал математик, вытаскивая из кармана распухший бумажник. – У меня сегодня дела шли неплохо.
Остальные посмотрели на него с интересом. Вот человек, который понимает кое-что в лошадях. Математика с трудом уговорили поделиться секретом, и он неохотно начал:
– Рассмотрим бесконечное число одинаковых сферических коней…
Озера Вады
Топология часто контринтуитивна. Это делает ее трудной для освоения, но и интересной. Вот странный топологический факт, имеющий прикладное значение в численном анализе.
Две области на плоскости могут иметь общую границу; представьте себе, к примеру, англо-шотландскую или американо-канадскую границу. Три и больше областей могут иметь общую граничную точку: в американских «Четырех углах» сходятся штаты Аризона, Колорадо, Нью-Мексико и Юта.
При некоторой изобретательности любое число областей можно организовать так, чтобы они имели две общие граничные точки. Однако представляется невозможным, чтобы три или более областей имели более двух общих граничных точек. Не говоря уже о том, чтобы они имели целиком общую границу.
Однако это возможно.
Во-первых, мы должны точно определить, что такое граничная точка. Предположим, у нас имеется некоторая область на плоскости. Необязательно многоугольник, это может быть любая фигура, в том числе очень сложная – вообще любой набор точек. Говорят, что точка лежит в замыкании области, если любой круг ненулевого (пусть сколь угодно малого) радиуса с центром в этой точке содержит некую точку, лежащую в этой области. Говорят, что точка лежит внутри области, если область включает в себя некоторый круг ненулевого радиуса с центром в этой точке. Тогда граница области состоит из всех точек ее замыкания, не лежащих внутри нее.
Поняли? По существу это то, что лежит на краю, но не внутри.
Для области в виде многоугольника, ограниченной набором отрезков прямых, граница состоит из этих отрезков, так что данное нами определение в этом случае вполне соответствует обычным представлениям. Можно доказать, что три и более многоугольных областей не могут иметь одну и ту же границу. Но для более сложных областей это неверно. В 1917 г. японский математик Кунидзё Ёнеяма опубликовал пример трех областей, имеющих одну и ту же границу. Он сказал, что идею таких областей предложил его учитель Такео Вада. Соответственно, сами области (или аналогичные им) были названы «озерами Вады».
Эти три области строятся шаг за шагом в ходе бесконечного процесса. Начинаем с трех квадратных областей.
Затем расширяем первую область, добавив дорожку, которая обойдет вокруг всех трех областей. Делаем это так, чтобы каждая точка на границе любого из квадратов лежала близко к дорожке. Проследим также, чтобы дорожка не замыкалась сама на себя, оставив дыру в получившейся области.
Затем расширяем вторую область, добавляя к ней более узкую тропку, которая обходит вокруг всех трех областей, построенных до сих пор.