Неожиданная красота простых чисел

Автор оригинала: Jesus Najera
  • Перевод
image

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

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

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

Однако несмотря на то, что мы постоянно полагаемся на их уникальные свойства, простые числа оставались для нас неуловимыми. На протяжении всей истории математики величайшие умы пытались доказать теорему о предсказании чисел, являющихся простыми, или о том, как далеко друг от друга они должны располагаться. На самом деле, некоторые нерешённые задачи, например задача о числах-близнецах, проблема Гольдбаха, простые числа-палиндромы и гипотеза Римана, связаны с этой общей непредсказуемостью и неопределённостью простых чисел при стремлении к бесконечности. Разумеется, со времён Евклида мы обнаружили алгоритмы, позволяющие предсказывать расположение некоторых чисел, но общие теоремы ещё не доказаны, а у предыдущих попыток не было инструментов для проверки больших чисел. Однако технологии 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):


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

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

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


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

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

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

Подробнее
Реклама

Комментарии 38

    +13

    https://habr.com/ru/post/417861/ там тоже рассказывали про интересные закономерности связанные с простыми числами — я уже год ими генерирую обои на рабочий стол

      +1

      Интересно, кто-нибудь додумался выпускать Ковёр Серпинского IRL, чтобы можно было его на стену повесить или как буржуи у кроватки или камина положить...

        0

        Такое впечатление, что что-то очень похожее на третью эдак итерацию такого ковра в узоре натурального ковра как элемент узора я когда-то вживую видел.

          +6

          Лучше тогда перфорированную Салфетку Серпинского, идеальный бизнес при условии переработки отходов — объект нулевой площади )

            +2
            Такой?
          +1
          Очень похоже на треугольник Серпинского. Они как-то связаны? Сам фрактал-то я рендерил, а вот в его историю и суть, к сожалению, не углублялся.
            0

            Треугольник Серпинского можно получить многими интересными способами, например клеточными автоматами или из треугольника Паскаля. Там же показано что эти треугольники естественно получаются из таблицы для операции конъюнкции. Целые же числа здесь играют роль фильтра. Аналогично можно выбирать из чисел Фиббоначи:



            https://habr.com/ru/post/426387/ тут есть готовые алгоритмы, которые можно выполнить на своем любимом языке

              +3

              Но самый поражающий своей бесконечной красотой, это для XOR


              картинка


              Код на Julia
              using Colors, Images, Primes
              
              cd("C:\\Users\\User\\Desktop\\Mycop")
              
              clr(x) = RGB(0, 0.3x, 0.4x)
              fibn(n) = ( [1 1; 1 0]^(n-1) )[1]
              isfibn(z) = in(z, mfbnc)
              
              mfbnc = [ fibn(i) for i=1:30];
              
              function makeimg(fun, filtr; M = 100, N = 100, startx = 0, starty = 0, name = "name", displ = false)
                  W = [ filtr(fun(x, y)) for x = startx:startx+N, y = starty:starty+M];
                  img = clr.(W)
                  println(sum(W))
                  save("$(name)_$(M)_$(N).png", img)
                  if displ
                      return img
                  end
              end
              # +, -, %, &, |, ⊻; isfibn, isprime
              makeimg(xor, isfibn, M = 5000, N = 5000, startx = 0, starty = 0, name = "andfib3", displ = false)
                +4
                cd(«C:\\Users\\User\\Desktop\\Mycop») :D
          +16

          Продублирую сюда про спирали


          Простые числа в полярных координатах, классы вычетов по модулям и прочее
            +2

            А ведь в видео как раз объясняется, что спиральный узор дают просто целые числа, а «фильтр» по простым убирает точки в случайных местах. Не случайны только пустые диагонали.

              0
              Не совсем. Вернемся к скатерти Улама. Если выкинуть какие-то точки по какому-то принципу, то появляются зачатки неслучайной структуры. Выкинули простые числа (или непростые, не важно) — получили структуру. Значит распределение простых чисел не случайно. Разве не так?
                0
                Нет, оно всё равно случайно. Просто в случае со спиралью получается так, что на некоторых ветвях не будет ни одного простого числа. Вот количество этих ветвей можно посчитать, и к тому же на рисунке они будут появляться регулярно, то есть глаз увидит закономерность в пустых линиях. Но на тех ветвях, где есть простые числа, их положение случайно.
                  0

                  Эти зачатки неслучайных структур и называют классом вычетов по модулю N. Для полярных координат классами становятся числа которые в целых радианах приближаются к целым аппроксимациям pi * 2 (22/7*2, 355⁄113 * 2 и т.д.). Для Улама коэффициэнты несколько иные, но принцип тот же.

                    0
                    Я б и готов поверить, но вот что мешает: 1. Рисуем спираль целых чисел. 2. Накладываем заведомо случайную маску точек. => 3. Получаем спирали-диагонали. Так что ли?
                      0

                      Если у ваших случайных точек есть ограничения на классы вычетов, то да какую-то такую структуру получите наверняка. Правда если только порядки будут относительно небольшими т.к. при стремлении к бесконечности плотность точек будет расти. Где-то там же на канале есть еще видео про классы вычетов и простые числа и там представляется некоторое "колесо по модулю n", где это свойство явно видно.

                +1
                Дополню примером способа визуализации:
                0
                а в авиационных двигателях с их помощью балансируется частота воздушных импульсов
                Выпал в ступор, открыл оригинал, крепко задумался, увидел там слово aeronautical, еще подумал, и после перекапывания поисковиков пришел к выводу, что в статье идет речь вот об этом: ПВРД. Нет, он когда-то на заре авиации использовался, конечно, но все же в современном мире авиационным двигателем называться никак не могут.
                  0
                  ПВРД.

                  Всё же ПуВРД.
                    0
                    Да, конечно же. Вы совершенно правы.
                    0

                    Я думаю речь всё же идёт о воздушных пульсациях (от лопаток турбины или компрессора, например) и о предотращении резонансов.

                    +2
                    А ещё в спирали Улама есть красивый «вихрь» из треугольных чисел.
                      0

                      О! Отличная идея для еще одного фильтра!

                      +1
                      цикады выстраивают по ним свои жизненные циклы
                      Это ошибка выжившего, ничего они не выстраивают.
                        +2
                        Минусующим советую почитать. en.wikipedia.org/wiki/Periodical_cicadas
                        Они ничего не выстраивают. Это результат естественного отбора, выжили более приспособленные популяции.
                          +3
                          По такой логике можно сказать что ваш комментарий писали не вы, просто в результате естественного отбора выжили только те люди, которые склонны писать этот текст.
                            +2

                            Правильнее сказать, что в нейронной сети конкретной особи происходит естественный отбор групп нейронов. Те, что получили доступ к моторному центру и передали свои команды, в следствие которых действия особи были успешными, получат поддержку и укрепление связей, а остальные будут чуть отставать. То есть то что я и Ваш оппонент не сдержались и начали изливать тут свои мысли, объясняется предустановками порожденными адаптивностью нейронных сетей. (Я вот получил удовольствие от самоутверждения и красиво сформулированной мысли — теперь вероятность того, что я буду встревать со своими доводами еще выше)

                              +1

                              Ну вполне верное утверждение. Некоторые тролли были выпилены с ресурса, кто-то попробовал клей в юном возрасте, а willyd, вот вошел в сонм альфа-интеллектуалов, способных вести оживлённую интересную дискуссию на этом ресурсе.

                            +1
                            Наверное, непросто вывести поколение людей от потомков тех, кого дельфины вытолкнули на берег, а не в море… Я к тому, что ошибка выжившего — это когда все кинули кости, а получившие, скажем, две шестерки, начали строить теории. Если какой-то вид цикад пришел к 13- и 17-летним циклам и закрепил это в геноме, то это уже отбор, а не «ошибка выжившего». А если один и тот же вид на одной территории пробует все возможные циклы, то это уже ерунда какая-то получается.
                              0
                              Это не «ошибка», это уже «закон» выжившего :)
                                0
                                Что-то вспомнилось, у Ларри Нивена в Ringworld часть истории базировалась на том, что какие-то ученые несколько поколений скрещивали между собой сильно удачливых людей, и получили в результате мегаудачливую девушку…
                                  0
                                  Еще была интересная идея для сверхдлительных космических путешествий, когда лететь 500 лет нужно было. В корабле сделали маленький земной мирок и населили его двумя разными племенами с низким IQ, дабы вопросов особых не задавали, а просто копались в земле и жили своей простой жизнью. Племенам запретили скрещиваться между собой под страхом смерти. Суть в том, что при подлете к месту назначения племена таки должны были породниться и их дети уже должны были иметь IQ очень-очень высокий, способные быстро выучиться на пилотов и колонистов… Еще была раса обслуживающего персонала (тоже с низким IQ), только чтобы технику обслуживать по-мелочи, которая была скрыта от этих племен…
                                  Как обычно, что-то пошло не так и парень с одного племени таки добрался до девушки из другого раньше времени, но весьма вовремя, как потом оказалось…
                            0
                            Канал 3Blue1Brown
                            Why do prime numbers make these spirals?
                            www.youtube.com/watch?v=EK32jo7i5LQ

                            П.С. Увидел что выше уже кидали.
                              0
                              > На самом деле, некоторые нерешённые задачи, например задача о числах-близнецах, проблема Гольдбаха

                              О Догадке Гольдбаха (и ее доказательстве) как и о природе простых чисел в свое время очень круто было написано на старом васме:
                              wasm.in/blogs/proletaja-nad-millionom-baksov-vmeste-s-goldbaxom.90
                              0
                              Статья чрезвычайно бестолковая. Так скучно написать о простых числах можно было лишь специально задавшись получением этого эффекта (или не владея темой совершенно). Я был чрезвычайно удивлён, посмотрев профиль автора на оригинальном ресурсе, что он специализируется на освещении математической тематики.
                              Насколько интересна сама тема простых чисел, можно почерпнуть из лекции Савватеева (в комментариях есть ссылки).
                              Значение «скатерти Улема» для математической науки до сих пор не очень велика. Она не дала подсказок и не подтолкнула к открытиям.
                              Спираль Улама — забава, но ее следует принимать всерьез. © М.Гарднер

                              Спираль Улама (которого «польским математиком» назвать можно лишь с очень большой «натяжкой»!) интересна тем, что ставит вопросы много более общего характера, нежели математические – вопросы об особенностях самого человеческого мышления. Числа – всего лишь некоторые идеальные образы, которыми оперирует наше сознание, их нет среди вещественных сущностей. «Натуральные числа», как мы можем вспомнить из школьного курса математики, вводились человеком в связи с осознанием им потребностей учёта и упорядочивания. И внезапно эта «единица абстракции» обнаруживает некое непредполагаемое его создателем независимое поведение! Спираль Улама показывает, что распределение простых чисел не случайно. То же показывало и любое из аналитически записанных распределений задолго до неё.

                              Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

                              Самое читаемое