Значимость простых чисел, как в повседневном применении, так и во всех отраслях математики, невозможно переоценить. Мы спокойно полагаемся на их особые свойства, используя их как фундамент бесчисленного количества элементов нашего общества, ведь они являются неделимой частью самой ткани природы. Простые числа, устойчивые к любому делению на множители, часто называют «атомами» мира математики. Карл Саган сказал о них так:

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

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

Однако несмотря на то, что мы постоянно полагаемся на их уникальные свойства, простые числа оставались для нас неуловимыми. На протяжении всей истории математики величайшие умы пытались доказать теорему о предсказании чисел, являющихся простыми, или о том, как далеко друг от друга они должны располагаться. На самом деле, некоторые нерешённые задачи, например задача о числах-близнецах, проблема Гольдбаха, простые числа-палиндромы и гипотеза Римана, связаны с этой общей непредсказуемостью и неопределённостью простых чисел при стремлении к бесконечности. Разумеется, со времён Евклида мы обнаружили алгоритмы, позволяющие предсказывать расположение некоторых чисел, но общие теоремы ещё не доказаны, а у предыдущих попыток не было инструментов для проверки больших чисел. Однако технологии 21-го века позволяют исследователям проверять предположения на чрезвычайно больших числах, но такая методика сама по себе вызывает споры, ведь проверка грубым перебором не считается надёжным доказательством. Другими словами, простые числа противятся подчиняться какой-либо универсальной формуле или уравнению, а их расположение в природе кажется случайным.

Однако, одному человеку случайными каракулями удалось доказать, что они как минимум не полностью случайны…

От закорючек к подсказке — скатерть Улама

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


Схема скатерти Улама

Как гласит история, польский математик Станислав Улам обнаружил этот графический паттерн во время семинара в 1963 году. Рисуя сетку из линий, он решил пронумеровать пересечения по квадратно-спиральному паттерну и начал обводить те числа в спирали, которые были простыми. К его удивлению, обведённые простые числа приходились на диагональные прямые линии, или, как чуть строже сформулировал Улам, «проявляли сильно неслучайное поведение». Скатерть Улама, или спираль простых чисел — это получившееся в результате графическое отображение размеченных в квадратной спирали множества простых чисел. Изначально скатерть была опубликована и получила широкую известность в рубрике «Математические игры» Мартина Гарднера в Scientific American.


Скатерть Улама размером 377x377 (числа примерно до 142 тысяч)

Показанная выше визуализация очевидно выявляет примечательные паттерны, особенно по диагоналям. Но возможно, мы обманываем себя? Часто утверждают, что скатерть Улама — это просто трюк нашего мозга, пытающегося находить паттерны в случайности. К счастью, мы можем использовать две разные методики, чтобы убедиться, что это не так. И визуальное сравнение, и логический анализ с определённостью говорят нам, что паттерн не случаен. Во-первых, мы сравним скатерть Улама, заданную матрицей размером NxN, с матрицей того же размера, содержащей случайно заданные точки. Во-вторых, мы можем воспользоваться своими знаниями о многочленах, чтобы понять, почему нужно ожидать появления некоторого паттерна при графическом отображении простых чисел.

Как говорилось выше, скорее всего, наиболее интуитивно понятным подтверждением неслучайности паттерна будет непосредственное сравнение со скатертью Улама. Для этого нужно создать скатерть Улама и квадратную спираль со случайными расположениями того же размера. Ниже показаны две разные матрицы 200x200, представляющие числовые спирали:


При визуальном сравнении становится достаточно очевидно, что скатерть Улама содержит потрясающие паттерны, особенно вдоль диагональных осей; кроме того, в ней почти нет скоплений точек. С другой стороны, случайное расположение точек не создаёт никаких сразу же заметных паттернов и приводит к скоплению точек в разных направлениях. Несомненно, такой методике не достаёт строгости традиционных доказательств; однако в визуализации спиралей простых чисел есть нечто безупречное: это случайно обнаруженная методика, позволяющая создать график, стимулирующий логику и привлекательный эстетически.

Если подходить к природе простых чисел в более логической и традиционной манере, то вполне разумно ожидать появления паттернов в таких визуализациях. Как сказано выше, линии в диагональных, горизонтальных и вертикальных направлениях, похоже, содержат подсказку. Некоторые из этих линий, не являющихся простыми числами, можно объяснить обычными квадратными многочленами, исключающими возможность появления простых чисел — например, одна из диагональных линий, соответствующая уравнению y = x?, очевидно, исключает простые чила. С другой стороны, известно, что некоторые квадратные многочлены, называемые формулами простых чисел (о них мы поговорим ниже), создают высокую плотность простых чисел, например, многочлен генерации простых чисел Эйлера: x? — x — 41; это ещё одна линия, отражающаяся как паттерн в спирали (хотя на показанной выше схеме сложно найти разрывы).

Визуальное сравнение указывает на наличие паттернов, а логический анализ подтверждает существование ожидаемых паттернов. Разумеется, мы ещё далеки от универсальной формулы для нахождения всех простых чисел, но скатерть Улама без сомнений прекрасна, и как символ нашего знания, и как шедевр природного искусства.

Спираль Сакса

Как и во многих областях математики, после появления оригинальной идеи идущая по следам армия коллег-математиков начала делать попытки внести свой вклад в новую тему. Логично, что скатерть Улама вдохновила поколения математиков, стремившихся развить его потрясающую находку. В 1994 году инженер по разработке ПО Роберт Сакс решил использовать свои навыки программиста для визуализации простых чисел различными способами.

Почти как и в случае со скатертью Улама, Сакс решил структурировать свою схему при помощи другой спиральной плоскости. Аналогично показанной выше квадратной спирали, спиральные плоскости отказываются при задании точек от традиционной декартовой числовой системы, потому что являются системой однополярного позиционирования. Просто зная число, можно узнать его расположение в спирали, его позицию относительно всех других чисел в спирали, а также расстояние от него до предыдущего и следующего квадрата числа. Однако вместо квадратной спирали Сакс попытался найти паттерны при помощи целых чисел, наложенных на архимедову спираль со следующими полярными координатами:


Полярные координаты спирали Архимеда/Сакса

При такой методике архимедова спираль центрирована относительно нуля, а квадраты всех натуральных чисел (1,4,9,16,25) расположены на пересечениях спирали и полярной оси (расположенной к востоку от точки начала координат).


Структура спирали Архимеда/Сакса

Подготовив эту схему, мы будем заполнять точки между квадратами вдоль спирали (против часовой стрелки), нанося их на равном расстоянии друг от друга. А в конце, как и в примере со скатертью Улама, мы выделим простые числа, содержащиеся в получившейся спирали.

Числовая спираль Сакса, впервые опубликованная онлайн в 2003 году, привлекательна и визуально, и интеллектуально. Кроме того, как мы вскоре убедимся, она даёт нам более глубокое понимание паттернов простых чисел, чем хорошо известная скатерть Улама, потому что она объединяет разорванные линии псевдоспирали Улама:


Архимедова спираль с отмеченными простыми числами, она же спираль Сакса.

Получившийся график снова демонстрирует заметные паттерны. Почти сразу становится понятно, что есть чистая белая линия, проходящая из центра и растянувшаяся горизонтально на восток. Обратившись к нашей схеме, мы можем убедиться, что это просто линия, содержащая все квадраты целых чисел (r = n^(.5)). Второе наблюдение: паттерн пометок, в отличие от прямых линий скатерти Улама, здесь больше напоминает кривые линии. Оказывается, эти кривые, также известные как кривые произведений, возвращают нас к многочленам, объясняющим паттерны, возникающие в предыдущей спирали. Но прежде чем мы обратимся к ним, ради единства снова сравним спираль Сакса со спиралью случайных значений:

Многочлены и кривые произведений

Работа Роберта Сакса, последовавшая за этим открытием, целиком была сосредоточена на этих кривых произведений, начинающихся в центре спирали или рядом с ним, и под разными углами пересекающихся с витками спирали. Кривые почти прямы, но более типично для них то, что они выполняют частичные, полные или многократные повороты по часовой стрелке (против движения самой спирали) вокруг точки начала координат перед тем, как выпрямиться на определённом смещении от оси «восток-запад». Один из самых поразительных аспектов числовой спирали Сакса заключается в преобладании таких кривых произведений в западном полушарии (в противоположной от квадратов чисел стороне).

Сакс описал кривые произведений как представляющие «произведения множителей с постоянной разностью между ними». Другими словами, каждую кривую можно представить квадратным уравнением (многочленом второй степени), что опять-таки не является простым совпадением, учитывая превалирование квадрата натурального числа в спирали Сакса. Возможно, эти кривые произведений могут привести нас к выводу, что спираль Сакса значительно полезнее в нашем пути к пониманию простых чисел, чем скатерть Улама. Хотя скатерть Улама указала нам на паттерны и возможное существование уравнений, спираль Сакса даёт точки опоры в поиске формул простых чисел — их кривизна и целостность постоянны, а значит, их гораздо проще будет обнаружить. Например, показанная ниже спираль Сакса содержит помеченные линии и относящуюся к ним формулу простых чисел, записанную в стандартном виде. Как я и обещал, знаменитая формула Эйлера для генерации простых чисел снова нам встретилась (последняя запись: n? + n +41):


Благодаря этой числовой спирали Сакс смог сделать потрясающее заявление о том, чем является простое число: положительным целым, лежащим только на одной кривой произведений. Поскольку спираль может раскручиваться бесконечно, сами кривые произведений тоже можно считать бесконечными; теоретически, эти кривые произведений, возможно, могут предсказывать расположение достаточно больших чисел — по крайней мере, такие числа стоят более внимательного изучения.

В целом, спираль Сакса без сомнений подтолкнула нас к более глубокому пониманию простых чисел, предложив более удобные формулы простых чисел.

Значение всего этого

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

Какой же урок можно извлечь из всего этого?

Никогда нельзя отказываться от пересмотра кажущихся неразрешимыми проблем, даже если вы занимаетесь этим из чистого любопытства и скуки; открытия может делать каждый и часто они возникают как результат совершенно необычных процессов. Изменив точку зрения на знаменитую задачу благодаря визуализации, Станислав Улам на один шаг приблизил нас к пониманию простых чисел: кто знает, на какие ещё неожиданные открытия мы наткнёмся?