Простые числа способы для диапазона

Еще раз о поиске простых чисел

В заметке обсуждаются алгоритмы решета для поиска простых чисел. Мы подробно рассмотрим классическое решето Эратосфена, особенности его реализации на популярных языках программирования, параллелизацию и оптимизацию, а затем опишем более современное и быстрое решето Аткина. Если материал о решете Эратосфена предназначен в первую очередь уберечь новичков от регулярного хождения по граблям, то алгоритм решета Аткина ранее на Хабрахабре не описывался.

На снимке — скульптура абстрактного экспрессиониста Марка Ди Суверо «Решето Эратосфена», установленная в кампусе Стэнфорского университета

Введение

Напомним, что число называется простым, если оно имеет ровно два различных делителя: единицу и самого себя. Числа, имеющие большее число делителей, называются составными. Таким образом, если мы умеем раскладывать числа на множители, то мы умеем и проверять числа на простоту. Например, как-то так:
(Здесь и далее, если не оговорено иное, приводится JavaScript-подобный псевдокод)
Время работы такого теста, очевидно, есть O(n ½ ), т. е. растет экспоненциально относительно битовой длины n. Этот тест называется проверкой перебором делителей.

Довольно неожиданно, что существует ряд способов проверить простоту числа, не находя его делителей. Если полиномиальный алгоритм разложения на множители пока остается недостижимой мечтой (на чем и основана стойкость шифрования RSA), то разработанный в 2004 году тест на простоту AKS [1] отрабатывает за полиномиальное время. С различными эффективными тестами на простоту можно ознакомиться по [2].

Если теперь нам нужно найти все простые на достаточно широком интервале, то первым побуждением, наверное, будет протестировать каждое число из интервала индивидуально. К счастью, если у нас достаточно памяти, можно использовать более быстрые (и простые) алгоритмы решета. В этой статье мы обсудим два из них: классическое решето Эратосфена, известное еще древним грекам, и решето Аткина, наиболее совершенный современный алгоритм этого семейства.

Решето Эратосфена

Древнегреческий математик Эратосфен предложил следующий алгоритм для нахождения всех простых, не превосходящих данного числа n. Возьмем массив S длины n и заполним его единицами (пометим как невычеркнутые). Теперь будем последовательно просматривать элементы S[k], начиная с k = 2. Если S[k] = 1, то заполним нулями (вычеркнем или высеем) все последующие ячейки, номера которых кратны k. В результате получим массив, в котором ячейки содержат 1 тогда и только тогда, когда номер ячейки — простое число.

Много времени можно сэкономить, если заметить, что, поскольку у составного числа, меньшего n, по крайней мере один из делителей не превосходит , процесс высевания достаточно закончить на . Вот анимация решета Эратосфена, взятая с Википедии:

Еще немного операций можно сэкономить, если — по той же причине — начинать вычеркивать кратные k, начиная не с 2k, а с номера k 2 .

Реализация примет следующий вид:

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

Оценим сложность алгоритма. Первое вычеркивание требует n/2 действий, второе — n/3, третье — n/5 и т. д. По формуле Мертенса

так что для решета Эратосфена потребуется O(n log log n) операций. Потребление памяти же составит O(n).

Оптимизация и параллелизация

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

Более развитая оптимизация (т. н. wheel factorization) опирается на то, что все простые, кроме 2, 3 и 5, лежат в одной из восьми следующих арифметических прогрессий: 30k+1, 30k+7, 30k+11, 30k+13, 30k+17, 30k+19, 30k+23 и 30k+29. Чтобы найти все простые числа до n, вычислим предварительно (опять же при помощи решета) все простые до . Теперь составим восемь решет, в каждое из которых будут входить элементы соответствующей арифметической прогрессии, меньшие n, и высеем каждое из них в отдельном потоке. Все, можно пожинать плоды: мы не только понизили потребление памяти и нагрузку на процессор (в четыре раза по сравнению с базовым алгоритмом), но и распараллелили работу алгоритма.

Наращивая шаг прогрессии и количество решет (например, при шаге прогрессии 210 нам понадобится 48 решет, что сэкономит еще 4% ресурсов) параллельно росту n, удается увеличить скорость алгоритма в log log n раз.

Сегментация

Что же делать, если, несмотря на все наши ухищрения, оперативной памяти не хватает и алгоритм безбожно «свопится»? Можно заменить одно большое решето на последовательность маленьких ситечек и высевать каждое в отдельности. Как и выше, нам придется предварительно подготовить список простых до , что займет O(n ½-ε ) дополнительной памяти. Простые же, найденные в процессе высевание ситечек, нам хранить не нужно — будем сразу отдавать их в выходной поток.

Не надо делать ситечки слишком маленькими, меньше тех же O(n ½-ε ) элементов. Так вы ничего не выиграете в асимптотике потребления памяти, но из-за накладных расходов начнете все сильнее терять в производительности.

Решето Эратосфена и однострочники

На Хабрахабре ранее публиковалась большая подборка алгоритмов Эратосфена в одну строчку на разных языках программирования (однострочники №10). Интересно, что все они на самом деле решетом Эратосфена не являются и реализуют намного более медленные алгоритмы.

Дело в том, что фильтрация множества по условию (например, на Ruby) или использование генераторных списков aka list comprehensions (например, на Haskell) вызывают как раз то, избежать чего призван алгоритм решета, а именно поэлементную проверку делимости. В результате сложность алгоритма возрастает по крайней мере до (это число фильтраций), умноженного на (минимальное число элементов фильтруемого множества), где — число простых, не превосходящих n, т. е. до O(n 3/2-ε ) действий.

Однострочник на Scala ближе к алгоритму Эратосфена тем, что избегает проверки на делимость. Однако сложность построения разности множеств пропорциональна размеру большего из них, так что в результате получаются те же O(n 3/2-ε ) операций.

Вообще решето Эратосфена тяжело эффективно реализовать в рамках функциональной парадигмы неизменяемых переменных. В случае, если функциональный язык (например, OСaml) позволяет, стоит нарушить нормы и завести изменяемый массив. В [3] обсуждается, как грамотно реализовать решето Эратосфена на Haskell при помощи техники ленивых вычеркиваний.

Решето Эратосфена и PHP

Запишем алгоритм Эратосфена на PHP. Получится примерно следующее:

Вторая проблема: массивы в PHP ужасны по накладным расходам памяти. У меня на 64-битной системе каждый элемент $S из кода выше съедает по 128 байт. Как обсуждалось выше, необязательно держать сразу все решето в памяти, можно обрабатывать его порционно, но все равно такие расходы дóлжно признать недопустимыми.

Для решения этих проблем достаточно выбрать более подходящий тип данных — строку!

Теперь каждый элемент занимает ровно 1 байт, а время работы уменьшилось примерно втрое. Скрипт для измерения скорости.

Решето Аткина

В 1999 году Аткин и Бернштейн предложили новый метод высеивания составных чисел, получивший название решета Аткина. Он основан на следующей теореме.

Теорема. Пусть n — натуральное число, которое не делится ни на какой полный квадрат. Тогда

1. если n представимо в виде 4k+1, то оно просто тогда и только тогда, когда число натуральных решений уравнения 4x 2 +y 2 = n нечетно.
2. если n представимо в виде 6k+1, то оно просто тогда и только тогда, когда число натуральных решений уравнения 3x 2 +y 2 = n нечетно.
3. если n представимо в виде 12k-1, то оно просто тогда и только тогда, когда число натуральных решений уравнения 3x 2 −y 2 = n, для которых x >y, нечетно.

C доказательством можно ознакомиться в [4].

Из элементарной теории чисел следует, что все простые, большие 3, имеют вид 12k+1 (случай 1), 12k+5 (снова 1), 12k+7 (случай 2) или 12k+11 (случай 3).

Для инициализации алгоритма заполним решето S нулями. Теперь для каждой пары (x, y), где , инкрементируем значения в ячейках S[4x 2 +y 2 ], S[3x 2 +y 2 ], а также, если x > y, то и в S[3x 2 −y 2 ]. В конце вычислений номера ячеек вида 6k±1, содержащие нечетные числа, — это или простые, или делятся на квадраты простых.

В качестве заключительного этапа пройдемся по предположительно простым номерам последовательно и вычеркнем кратные их квадратам.

Из описания видно, что сложность решета Аткина пропорциональна n, а не n log log n как у алгоритма Эратосфена.

Авторская, оптимизированная реализация на Си представлена в виде primegen, упрощенная версия — в Википедии. На Хабрахабре публиковалось решето Аткина на C#.

Как и в решете Эратосфена, при помощи wheel factorization и сегментации, можно снизить асимптотическую сложность в log log n раз, а потребление памяти — до O(n ½+o(1) ).

О логарифме логарифма

На самом деле множитель log log n растет крайне. медленно. Например, log log 10 10000 ≈ 10. Поэтому с практической точки зрения его можно полагать константой, а сложность алгоритма Эратосфена — линейной. Если только поиск простых не является ключевой функцией в вашем проекте, можно использовать базовый вариант решета Эратосфена (разве что сэкономьте на четных числах) и не комплексовать по этому поводу. Однако при поиске простых на больших интервалах (от 2 32 ) игра стоит свеч, оптимизации и решето Аткина могут ощутимо повысить производительность.

P. S. В комментариях напомнили про решето Сундарама. К сожалению, оно является лишь математической диковинкой и всегда уступает либо решетам Эратосфена и Аткина, либо проверке перебором делителей.

Источник

Алгоритм нахождения простых чисел

Оптимизация алгоритма нахождения простых чисел

2 3 5 7 11 13 17 19 23 29 31… $250.000…

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

Алгоритм был придуман и тутже реализован на изучаемом языке. Программа запрашивала у пользователя число N и искала все простые числа до N включительно. После первого успешного теста сразу же возникло непреодолимое желание ввести N = «много». Программа работала, но не так быстро как хотелось бы. Естественно, дело было в многочисленных проверках (порядка N*N/2), поэтому пришлось избавиться от лишних. В итоге получилось 5 похожих алгоритмов каждый из которых работал быстре предыдущего. Недавно захотелось их вспомнить и реализовать, но на этот раз на Python.

Итак, поехали. Первый алгоритм, ударивший в студенческую голову, продемонстрирован в Листинге 1.

Очень быстро понимаешь, что в подсчете делителей каждого числа нет никакой надобности и поэтому переменную k можно освободить от своих обязанностей. Действительно, если хотябы один делитель имеется, то число уже не простое. Смотрим Листинг 2.

Конструкция break позволяет нам завершить выполнение внутреннего цикла и перейти к следующей итерации внешнего.
Далее возникает вопрос: «а зачем делить на 4, если на 2 число не делится?». Приходим к выводу, что искать делители нужно только среди простых чисел не превышающих делимое. Наш алгоритм превращается в… см. Листинг 3.

А потом вспоминаем теорию чисел и понимаем, что переберать надо только числа, не превосходящие корня из искомого. К примеру, если число M имеет делитель pi, то имеется делитель qi, такой, что pi * qi = M. То есть, чтобы найти пару, достаточно найти меньшее. Среди всех пар, предполагаемая пара с максимальным наименьшим — это пара с равными pi и qi, то есть pi * pi = M => pi = sqrt(M). Смотрим Листинг 4.

Код из Листинга 4 при N=10000 выполняется примерно в 1000 раз быстрее, чем самый первый вариант. Есть еще один «ускоритель», проверять только те числа, которые заканчиваются на 1, 3, 7 или 9 (так как остальные очевидно делятся на 2 или 5). Наблюдаем Листинг 5.

В следствии незначительного изменения Листинга 5 получаем небольшую прибавку в скорости:

Итого: Программа из последнего листинга выполняется, примерно, в 1300 раз быстрее первоначального варианта.
Я не ставил перед собой задачи написать программу максимально быстро решающую данную задачу, это скорее демонстрация начинающим программистам того, что правильно составленный алгоритм играет далеко не последнюю роль в оптимизации Ваших программ.

P.S.
Благодаря замечаниям получаем Листинг 7:

при N=10000, поучаем время:
time 1 = 26.24
time 2 = 3.113
time 3 = 0.413
time 4 = 0.096
time 5 = 0.087
time 6 = 0.083
time 7 = 0.053

Результаты при n = 1 000 000:
time 7 = 7.088
time 8 = 1.143

Источник

Структура и случайность простых чисел

Разбросаны ли простые числа по числовой оси подобно рассеянным ветром семенам? Разумеется нет: простота — это не вопрос случайности, а результат элементарной арифметики. Число является простым тогда и только тогда, когда ни одно меньшее положительное целое число кроме единицы не делит его нацело.

Но на этом история не заканчивается. Распределение простых чисел выглядит случайным, с неравномерными разрывами и скоплениями, которые выглядят довольно хаотично. Если и существует какая-то схема, то она непостижима. На самом деле, простые числа выглядят достаточно случайными, чтобы можно было сыграть с ними в кости. Создайте список последовательных простых чисел (допустим, начав с 11, 13, 17, 19. ) и разделите их по модулю 7. Другими словами, разделите каждое простое число на 7 и сохраните только остаток. Результатом будет последовательность целых чисел из множества <1, 2, 3, 4, 5, 6>, которая выглядит почти как результат нескольких бросков правильной кости.

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

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

Но условием случайности является не только равномерное распределение результатов в допустимом интервале. Кроме того, отдельные события в последовательности должны быть независимы друг от друга. Один бросок кости не должен влиять на результат следующего броска. Для проверки независимости можно взглянуть на последовательные события. Сколько раз за единицей идёт ещё одна единица, или двойка, или тройка, и так далее? Запишем в матрицу количество всех 36 возможных пар. Если процесс действительно случаен, все 36 пар должны иметь одинаковую частотность, если не принимать во внимание небольшие статистические флуктуации. Можно превратить матрицу в цветную «тепловую карту», в которой ячейки с количеством выше среднего будут отображены в тёплых оттенках розового и красного, а ниже среднего — залиты более холодными оттенками синего. (Вносимые количества являются не действительным количеством , а нормализованной переменной , где — это снова среднее значение, в нашем случае .) Вот тепловая карта симулированной правильной кости:

Здесь нет ничего интересного. Почти все количества настолько близки к среднему значению, что ячейки матрицы кажутся нейтрально серыми, только немногие оказались бледно-розовыми или голубыми. Именно такого результата и ждёшь, когда последовательные броски кости не коррелируют друг с другом, и все возможные пары одинаково вероятны.

Теперь перейдём к соответствующей матрице последовательных простых чисел по модулю 7:

Ого! Похоже мы покинули Страну случайных чисел, здесь старое серое кино превратилось в Technicolor. На тепловой карте появилась голубая полоса вдоль основной диагонали (из левого верха в правый низ), означающая, что последовательные пары простых чисел, имеющие одинаковое значение остатка от деления на 7, очень маловероятны. Другими словами, пары возникают реже, чем это было бы в действительно случайной последовательности. Наддиагональ (прямо над основной диагональю) имеет более светлый голубой цвет. Это означает, что пары , где , возникают немного реже, чем средняя частота. Например, и имеют немного отрицательные значения нормализованной частоты. С другой стороны, поддиагональ (под основной диагональю) полностью розовая и красная; такие пары как или , где , возникают с частотой выше средней. Вдали от диагонали, в верхнем правом и нижнем левом углу мы видим пастельный шахматный узор.

Если вы предпочитаете иметь дело с числами, а не с цветными квадратами, то вот вам матрица значений:

Отклонения от единообразия можно назвать какими угодно, но не «незначительными». В третьем ряду, например, видно, что если вы только что встретили 3 в последовательности простых чисел mod 7, то следующее число с намного большей вероятностью будет 2, а не ещё одна 3. Если бы вы играли в игру с костями из простых чисел, то такое смещение колоссально повлияло бы на результат. Кости на простых числах — «заряженные» кости!

Эти примечательно сильные корреляции в парах были открыты Робертом Дж. Лемке-Оливером и Каннаном Соундарараджаном из Стэнфордского университета. Они обсуждали их в препринте, опубликованном на arXiv в марте этого года. Для меня самым удивительным в этом открытии стало то, что никто за долгие годы не заметил эти структуры. Они довольно очевидны, если знать, где из искать.

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

В 1850-х российский математик Пафнутий Львович Чебышев указал на незначительное искажение в простых числах. Деление нечётных простых чисел по модулю 4 разбивает их на два подмножества. Все простые числа в ряду 5, 13, 17, 29, 37. конгруэнтны 1 по модулю 4; в ряду 3, 7, 11, 19, 23, 31. конгруэнтны 3 по модулю 4. Чебышев заметил, что простые числа во второй категории кажутся более многочисленными. Например, среди первых 10 000 нечётных простых чисел есть 4 943 конгруэнтных 1 и 5 057 конгруэнтных 3. Однако это воздействие мало по сравнению с неравномерностями, замеченными в парах последовательных простых чисел.

В наше время несколько авторов увидели намёк на феномен последовательных простых чисел. Лемке-Оливер и Соундарараджан упоминают о трёх таких свидетельствах. (См. список справочных материалов в конце статьи.) В 1950-х и 60-х Станислав Кнаповски и Пал Туран исследовали различные аспекты остатков от деления простых чисел по модулю m. В одной статье, посмертно опубликованной 1977 году, они рассматривали деление последовательных простых чисел по модулю 4 с остатками 1 или 3. Они «предположили», что последовательные пары с одинаковым остатком и пары с отличающимися остатками «не равновероятны». В 2002 году Чун-Мин Ко исследовал ряды последовательных простых чисел (не только их пар) и создал проработанные фрактальные паттерны на основе их меняющихся частот. Затем в 2011 году Авнер Эш с коллегами опубликовал подробный анализ «Частоты последовательных пар остатков простых чисел», в том числе несколько матриц, в которых диагональное снижение чётко заметно.

С учётом этих прецедентов были ли Лемке-Оливер и Соундарараджан на самом деле открывателями корреляций последовательных простых чисел? По моему мнению, ответ должен быть положительным. Хотя другие и видели эти паттерны ранее, они не описывали их так, чтобы те зафиксировались в сознании математического сообщества. На самом деле, когда Лемке-Оливер и Соундарараджан объявили о своих находках, реакцией стало удивление, граничащее с недоверием. Эрика Кларарайх в статье для Quanta процитировала реакцию оксфордского теоретика чисел Джеймса Мэйнарда:

Когда Соундарараджан впервые сказал Мэйнарду об открытии пары, Мэйнард сказал «Я поверил ему только наполовину. Как только я вернулся к себе в офис, я провёл численный эксперимент, чтобы убедиться в этом самому».

Очевидно, что такой была всеобщая реакция. Эвелин Лэмб в статье для Nature цитирует Соундарараджана: «Каждый, кому мы рассказывали об этом, в конце концов писал свою компьютерную программу, чтобы убедиться в этом самому».

Так же поступил и я! За последние несколько недель я написал кучу строк кода для анализа деления простых чисел по модулю m. Моя статья — это отчёт о моим попытках разобраться в том, откуда взялись эти паттерны. Мои методы больше вычислительные и визуальные, чем математические, я не могу ничего доказать. Лемке-Оливер и Соундарараджан применили более строгий и аналитический подход, в конце этой статьи я расскажу немного больше об их результатах.

Если вы хотите начать собственное расследование, то можете взять за основу мой код. Он написан на языке программирования Julia, упакован в Jupyter notebook и доступен на GitHub. (Так получилось, что эта программа стала моим первым нетривиальным экспериментом с Julia. В другой статье я расскажу подробнее о моей работе с языком.)

Во всех представленных выше примерах приведено деление простых чисел по модулю 7, но в числе 7 нет ничего особенного. Я выбрал его просто потому, что шесть возможных остатков <1, 2, 3, 4, 5, 6>соответствуют граням обычной кубической кости. Другие модули дают схожие результаты. Лемке-Оливер и Соундарараджан бо́льшую часть анализа провели над делением простых чисел по модулю 3, при котором есть только два класса конгруэнции: простое число больше 3 должно при делении на 3 иметь остаток 1 или 2. Вот матрица количеств пар для первого миллиона простых чисел больше :

Паттерн довольно минималистичен, но всё равно узнаваем: элементы вне диагонали для последовательностей и больше, чем элементы на диагонали для и .

Простые числа по модулю 10 имеют четыре класса конгруэнции: 1, 3, 7, 9. Чтобы увидеть это, работая в десятичной нотации, нам даже не нужна арифметика. Когда числа записываются по основанию 10, каждое простое число больше 5 имеет конечную цифру 1, 3, 7 или 9. Вот частоты для 16 пар последовательных конечных цифр:

Чётко видна голубая полоса по основной диагонали, хотя в других местах матрицы паттерн немного ослаблен и смазан.

Я обнаружил, что корреляции между последовательными простыми числами проявляются наиболее чётко, когда сам модуль является простым числом, и при этом не слишком маленьким. Посмотрите на тепловые карты для последовательных простых чисел mod 13 и mod 17:

А как насчёт модуля 31?

Из этих матриц получится отличный узор для килта или мозаичного пола, правда? И во всех них видны интересные закономерности. Диагональные полосы выделяются не только на основной диагонали, но и во всей матрице. Такие полосы также создают узор шахматной доски. Вдоль любой строки или столбца ячейки обычно попеременно красные и синие. Более незаметной особенностью является приблизительная двухсторонняя симметрия вдоль противоположной диагонали (идущей из левого низа в правый верх). Если сложить по этой линии квадрат, то соединённые вместе ячейки будут примерно одного цвета. (Этот факт заметил Эш и его соавторы.)

Для дальнейшего анализа я решил сосредоточиться на последовательных простых числах mod 19. Модуль достаточно велик, чтобы давать в результате чётко дифференцированные полосы, но не настолько велик, чтобы сделать матрицу огромной.

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

Диагональные полосы в матрице предполагают наличие сильной корреляции между всеми парами, разделёнными определённым числовым интервалом. Например, самая тёмно-синяя диагональ и самая ярко-красная диагональ состоят из ячеек, разделённых шестью элементами вдоль оси j. В первой строке находятся ячейки 1 и 7, потом 2 и 8, 3 и 9, и так далее. Мне показалось, что эту взаимосвязь проще воспринимать, если «изогнуть» матрицу, чтобы диагонали стали столбцами. Идея заключается в том, чтобы применить к каждой строке циклический сдвиг, все значения в строке сместятся влево, а те, которые «упадут» с левого края, будут вставлены справа. Первая строка смещается на ноль позиций, следующая — на одну позицию, и так далее. (Есть ли название для такого преобразования? Я просто буду называть его «изгиб».)

Затем я написал код для этого преобразования, но в результате получил не совсем то, что ожидал:

Что это за зигзаги вдоль обратной диагонали? Я предположил, что совершил ошибку и сместил на один лишний элемент. И корень проблемы действительно оказался в этом, но «баг» находится не в алгоритме, а в самих данных. Матрицы, показанные мной во всех предыдущих рисунках, являются только частичными, они отбрасывают пустые классы конгруэнции. В частности, матрица для пар простых чисел по модулю 19 игнорирует все простые числа, конгруэнтные 0 по модулю 19 на том логичном основании, что таких простых чисел нет. В конце концов, если 19$» data-tex=»inline»/> и , то не может быть простым, потому что оно делится на 19. Тем не менее, строка и столбец для являются действительной частью матрицы. Если их добавить, то наше табло с цветовой кодировкой будет выглядеть так:

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

О чём нам говорят эти вертикальные полосы? В исходной матрице элемент представлял собой частоту, с которой за следует . Здесь цвет ячейки обозначает частоту, с которой за следует . Другими словами, каждый столбец объединяет элементы с одинаковым интервалом mod 19 между двумя простыми числами. Например, самый левый столбец содержит все пары, разделённые интервалом длиной , а ярко-красный столбец в учитывает все случаи, когда последовательные простые числа отделены друг от друга .

Цветовое кодирования даёт нам качественное представление о том, какие интервалы появляются более или менее часто. Для более точного количественного измерения мы можем суммировать вдоль столбцов и отобразить результаты в столбчатом графике:

• Замеченная выше неравномерность чётных-нечётных чисел явно заметна и на графике. За исключением 0, каждый чётный интервал выделяется на фоне его нечётных соседей.
• Интервал между простыми числами mod 19, равный 6 — самый популярный из всех. Числа, кратные 6 (а именно 12 и 18) тоже часты, но хоть и в меньшей степени.
• Интервал между простыми числами mod 19, равный 0, примечательно непопулярен. Это элементы вдоль основной диагонали исходной матрицы, поэтому неудивительно, что их сумма находится на нижней части, однако дефицит сильнее, чем я предполагал.

Я хотел разобраться с источниками этих паттернов. Что делает интервал 6 таким притягательным для пар последовательных простых чисел, и почему почти все простые числа сторонятся бедного интервала 0?

У меня уже есть отдалённая догадка относительно популярности 6. В 1990-х Эндрю Одлыжко, Майкл Рубинштейн и Марек Вулф выполнили вычислительное исследование «чемпионов по прыжкам» среди простых чисел:

Целое число D называется чемпионом по прыжкам, если его наиболее часто возникающая разность между последовательными простыми числами ≤ x для некоторого x.

Среди наименьших простых чисел (x меньше, чем примерно 600), чемпионом по прыжкам обычно является 2, но потом выигрывает 6 и доминирует на довольно большом интервале числовой оси. Примерно возле число 6 уступает чемпионство числу 30, которое со временем уступает 210. Одлыжко с коллегами оценили, что этот последний переход происходит примерно около . Числа в этой последовательности чемпионов по прыжкам — 2, 6, 30, 210,… — являются праймориалами; n-ный праймориал является произведением первых n простых чисел.

Почему праймориалы становятся предпочтительными интервалами между последовательными простыми числами? Если является достаточно большим простым числом, то не может делиться на 2, не может делиться на 2 и 3, не может делиться на 2, 3 и 5, и в целом , где — это n-ный праймориал, не делится ни на один из первых n простых чисел. Разумеется всё равно может делиться на какое-то большое простое число, или может существовать другое простое число между и , такое, что интервал между простыми числами не гарантированно является праймориалом. Но эти интервалы имеют преимущество перед остальными претендентами.

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

Снова явно выделяется интервал 6, насчитывающий 13,7% от общего количества, бо́льшие кратные числа 6 тоже выделяются среди своих непосредственных соседей. Стоит заметить и общую форму распределения: скопление слева (с пиком на числе 6) с последующим плавным снижением. Тренд похож на распределение Пуассона, и на самом деле это можно считать верным описанием.

Цветовая схема разрезает множество данных на доли по 19 значений в каждой. Голубая доля, в которую входят интервалы между простыми числами длиной от 0 до 18, насчитывает 68 процентов от всех интервалов, присутствующих в выборке из миллиона простых чисел; золотая доля добавляет ещё 23 процента. Остальные 9 процентов распределены широко и равномерно. На графике показаны не все интервалы: спектр продолжается до 210. (Одна пара последовательных простых чисел в выборке имеет расстояние 210, а именно 20 831 323 и 20 831 533.)

Похоже, на Рисунке 13 показана бо́льшая часть паттерна последовательных простых чисел по модулю19. Я могу сделать график ещё более информативным, внеся простое изменение. Начнём сдвигать каждую долю из 19-элементов, пока она не выровняется с долей 0, собираясь в столбики, находящиеся в одном столбце. Поскольку вторая (золотая) доля перемещается влево, пока столбик 19 не выровняется с столбцом 0, а третья (розовая) доля соединяет столбик 38 со столбиком 0. Физически этот процесс можно представить как вращение графика вокруг цилиндра с длиной окружности 19. Математически он составляет деление интервалов между простыми числами по модулю 19.

Если не обращать внимание на слишком яркие цвета, Рисунок 14 аналогичен Рисунку 12: высоты всех столбиков совпадают. Это не должно нас удивлять. На Рисунке 12 мы делим простые числа по модулю 19, а затем берём разности между последовательными разделёнными простыми числами. На Рисунке 14 мы берём разности между самими простыми числами, а затем делим эти разности по модулю 19. Две процедуры аналогичны:

Изучив цвета, мы можем расставить все фрагменты головоломки на места. Почему простые числа mod 19 так часто разделены интервалом 6? Ну, на самом деле mod 19 имеет с этим мало общего; само число 6 в этой выборке является наиболее частым интервалом между простыми числами. Единственный другой существенный взнос в возникает из третьей доли, особенно несколько пар простых чисел с расстоянием в 44.

Превосходство первой доли также объясняет неравенство между чётными и нечётными интервалами. Все интервалы в первой доле обязательно чётные, нечётные интервалы (mod 19) начинают появляться только во второй доле (интервалы от 19 до 37) и только по этой причине они менее часты. Для восьмиразрядных простых чисел выборки больше двух третей последовательных пар ближе, чем на 19 единиц, и поэтому оказываются в первой доле. (Медианное расстояние между простыми числами равно 12. Средний интервал равен 16,68, что близко к теоретическому предсказанию в 16,72.)

Наконец, Рисунок 14 может кое-что нам рассказать и о редкости интервалов 0 mod 19. Никакие два последовательных простых числа не могут попасть в один класс конгруэнции mod 19, если только они не разделены расстоянием 38 или числом, кратным 38. Поэтому такие пары не выходят на сцену до начала третьей доли, и в ней их не может быть слишком много. Выборка из миллиона простых чисел содержит 8 384 последовательных пар с расстоянием 38 — меньше одного процента от общего числа. И это основная причина того, что кость простых чисел так редко выпадает одной и той же гранью дважды подряд. В этом заключается причина появления голубой диагональной полосы во всех матрицах.

Я нахожу очень интересным то, что мы можем объяснить так много о паттерне последовательных простых чисел mod m, не углубляясь в подробности и не рассматривая особые свойства простых чисел. На самом деле мы можем воссоздать значительную часть паттерна вообще без использования простых чисел.

Две сотни лет назад Гаусс и Лежандр заметили, что по соседству с числом доля всех целых чисел, являющихся простыми, составляет примерно . В 1936 году шведский математик Харальд Крамер предпожил интерпретировать эту долю как вероятность. Идея заключалась в том, чтобы пройти по всем целым числам по порядку, приняв каждое с вероятностью . Числа в принятом множестве не будут являться простыми, кроме как по совпадению, но они будут иметь то же крупномасштабное распределение, что и распределение простых чисел. Вот несколько первых элементов списка миллиона таких «простых чисел Крамера», где процесс случайного выбора начинается с :

Теперь предположим, что мы пропустим эти числа через тот же механизм, который применяли к простым числам. Мы поделим каждое простое число Крамера по модулю 19, а затем создадим матрицу последующих чисел :

Выделяющиеся диагональные особенности выглядят похожими, но они гораздо проще, чем в соответствующих графиках простых чисел. Для любого простого числа Крамера p mod 19, наиболее вероятным последователем будет p + 1 mod 19, а наименее вероятным — p + 19 mod 19. Между этими предельными случаями находится плавный градиент частоты или вероятности со всего лишь несколькими небольшими флуктуациями, которые скорее всего можно списать на статистический шум.

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

Вот так лучше! При исключении из последовательности чётных чисел минимальный интервал между полупростыми числами равен 2, и это также является наиболее вероятным расположением.

Добавив ещё одно изменение, мы ещё сильнее приблизимся к имитации к матрице истинных простых чисел. Кроме исключения всех целых чисел, кратных 2, мы избавимся ещё и от кратных 3 и соответствующим образом изменим вероятность выборки. Назовём получившиеся числа «полуполупростыми числами Крамера».

Заметьте, что 6 mod 19 — наиболее вероятный интервал между полуполупростыми числами Крамера, как и между истинными простыми числами, и что присутствуют те же отголоски на интервалах 12 и 18. И в самом деле, единственная очевидная разница между этой матрицей и Рисунком 10 (соответствующий график для истинных простых чисел) находится в столбце и строке для чисел, конгруэнтных 0 по модулю 19. Среди простых чисел таких чисел быть не может. Если мы устраним их и из чисел Крамера, то две матрицы становятся почти неотличимыми. Вот они обе:

Если присмотреться, то можно найти различия — посмотрите на расширение диагонали на юго-восток от строки 1, столбца 15 — но в целом эти модифицированные числа Крамера на удивление хорошо имитируют простые числа. На обеих диаграммах даже заметна симметрия относительно обратной диагонали. И не забывайте, что эти два множества содержат в общем только 19 процентов их значений: числа Крамера включают в себя 189 794 истинных простых чисел.

Я хочу добавить к этой истории ещё один поворот сюжета. Все приведённые выше примеры основаны на простых числах (или их аналогах) из восьми десятичных цифр, или, другими словами, числами по соседству с . Справедливы ли те же результаты для простых чисел с бо́льшими значениями? Рассмотрим таблицу, созданную из последовательных пар миллиона 40-разрядных простых чисел, взятых по модулю19. Паттерн оказывается знакомым, но более бледным:

Перейдём к простым числам из 400 разрядов, снова поделённые по модулю 19, и получим цвета, выцветшие почти до неузнаваемости:

Голубая полоса на основной диагонали едва различима, а остальные особенности превращаются в простые случайные пятна.

Итак, похоже, что для пар последовательных простых чисел размер имеет значение. Чтобы разобраться в причинах этого, давайте посмотрим на группу различий между последовательными простыми числами в 40-разрядной выборке:

По сравнению с распределением интервалов для восьмиразрядных простых чисел (Рисунок 13), спектр намного шире и более плоский. В этой форме график усекается на интервале 240; длинный «хвост» на самом деле растягивается далеко вправо, а наибольший разрыв между последовательными простыми числами находится в 1 328. Также, как предсказал Одлыжко с его коллегами, наиболее частый интервал между 40-разрядными простыми числами является не 6, а 30.

Из-за более широкого распределения интервалов, первая доля не может доминировать над поведением системы так, как она это делает среди восьмиразрядных простых чисел. Когда мы начинаем расставлять одну над другой доли mod 19 (Рисунок 22 ниже), первые шесть или восемь долей вносят существенный вклад. Неравномерность чётных-нечётных по-прежнему присутствует, но амплитуда этих колебаний намного снижена. Самый левый столбец графика, представляющий интервалы, конгруэнтные 0 по модулю 19, отстаёт в росте, но не так значительно.

Выравнивание спектра становится ещё более выраженным в выборке миллиона 400-разрядных простых чисел:

Теперь разрывы между простыми числами растянулись до 15 080, создавая почти 800 долей mod 19 (однако показаны только 13). И здесь в массиве есть очень интригующая гребенчатая структура. В целом, столбцы на числах, кратных 6 выделяются почти в два раза по сравнению с высотой ближайших соседей, показывая сохраняющееся влияние наименьших простых делителей 2 и 3. Числа, кратные 6, которые также являются кратными 30, достигают ещё больших высот. Значения в последовательности 42, 84, 126, 168, 210,… тоже вносят большой вклад: эти числа кратны . И заметьте, что 210, которое является кратным 6 и 30 и 42, является новым интервалом-чемпионом, снова подтверждая прогноз Одлыжко.

Несмотря на всю эту внутреннюю структуру, когда столбцы, расставленные один на другой mod 19, смесь 800 доль настолько аккуратна, что высоты почти одинаковы. Единственное, что остаётся — небольшая неравномерность чётных-нечётных.

Рисунок 24.

И хронически непопулярный класс конгруэнтных 0 по модулю 19 интервалов наконец нашёл себе равных. Бо́льшая часть высоты столбца получается не от дюжины ранних доль, а от сотни более поздних, представляющих интервалы между 228 и 15 080 (все они скопились в бирюзовой области графика).

Эксперименты с большими простыми числами позволяют нам сделать правдоподобное предположение: при стремлении размера простых чисел к бесконечности все следы корреляций постепенно увядают, а последовательные пары простых чисел будут такими случайными, как броски идеальной кости. Но так ли это? Есть несколько причин относиться к этой гипотезе скептически. Во-первых, если мы будем увеличивать модуль m вместе с размером простых чисел, делая его сравнимым по величине с медианным разрывом между простыми числами, то корреляции по-прежнему будут проявляться. В моей 40-разрядной выборке медианный разрыв между простыми числами равен 66, поэтому давайте рассмотрим матрицу последовательных пар mod 61. (Чтобы ограничить статистический шум, я проведу вычисления с выборкой не из одного, а из десяти миллионов 40-разрядных простых чисел.)

Полосы вернулись! И в самом деле, в дополнение к знакомым ярко-красным полосам на интервалах 6, есть более рассеянные розовые и голубые частоты с периодом 30. Я бы хотел посмотреть на матрицу для простых 400-разрядных чисел, у которой могут быть ещё более сложные черты, с взаимодействующими волнами в периодах 6, 30 и 210. К сожалению, я не могу показать вам этот рисунок. Медианный разрыв между 400-разрядными простыми числами равен примерно 640, так что нам придётся присвоить m значение, равное простому числу в этом интервале, скажем 641. Для заполнения матрицы потребуется примерно миллиард последовательных 400-разрядных чисел, а это больше, чем я готов вычислять.

Существуют и другие причины сомневаться в том, что при увеличении простых чисел корреляции полностью исчезают. Гребенчатая структура, столь заметная на Рисунках 21 и 23, подсказывает нам, что правила делимости на малые простые числа сильно влияет на распределение больших простых чисел mod m, и это влияние всё равно не исчезает, когда числа увеличиваются. Более того, даже когда m намного меньше медианного интервала между простыми числами, голубая полоса остаётся слабо видимой. Вот матрица для пар последовательных 400-разрядных простых чисел mod 3:

Разность элементов на диагоналях и вне диагоналей намного меньше, чем с восьмиразрядными простыми числами (сравните с Рисунком 3), но отклонения по-прежнему не выглядят, как случайная вариация.

Чтобы получить более чёткое представление о том, как меняется корреляция как функция от размера простых чисел, я решил создать выборку простых чисел на всём интервале от одноразрядных до 400-разрядных чисел. В этом проекте я решил сделать лучше, чем Гаусс: он заносил простые числа в таблицы по хилиадам (по группам из 1 000), а я вычислял их по мириадам (группам по 10 000). Для измерения корреляций среди простых чисел mod m я вычислил среднее значение диагональных элементов матрицы и среднее элементов вне диагоналей, а затем взял соотношение вне/на диагонали. Если последовательные простые числа совершенно не коррелируют, то соотношение должно стремиться к 1.

На Рисунке 26 показан результат для 797 мириад простых чисел mod 3. Кривая выгнута вверх, имеет резкое начальное снижение, а затем гораздо более плоский сегмент. Начиная примерно с 100 разрядов есть выборки с соотношением меньше 1, означающим, что диагональ более густо заселена, чем области вне диагонали. Но даже при 400 разрядах большинство соотношений всё равно выше 1. Что мы здесь видим? Приближается ли кривая медленно к соотношению 1, или существует ограничивающее значение, немного большее 1? К сожалению, вычислительные эксперименты не позволяют дать окончательный ответ.

Для рассмотрения этой задачи в статье Лемке-Оливера и Соунарараджана используются иные инструменты. Хотя они и используют численные исследования, их целью является нахождение аналитического решения. Цель — это математическая функция или формула, входными данными которой являются четыре положительных целых числа: m — модуль, a и b — классы конгруэнции простых чисел mod m, а x — верхний предел размера простых чисел. Формула должна показать нам, насколько часто за a следует b среди всех простых чисел меньше x. Если бы мы обладали такой формулой, мы бы могли раскрасить все квадраты в матрице последовательных чисел без необходимости даже вычислять сами простые числа до x.

Описание поведения всех простых чисел до x — намного более сложная задача, чем взятие выборки из простых чисел по соседству с x. Аналитический подход сложен и по другим причинам: он требует идей, а не просто циклов вычислений ЦП. Но и награда потенциально может оказаться намного ценнее. Например, вычислив уравнение , мы получаем истинные значения для всех окружностей, то, чего нам не может дать конечное количество вычислений (с конечным приближением к ). Это обещает нам не только получение строгих решений, но возникновение озарений.

Увы, мне не удалось получить озарение от чтения анализа Лемке-Оливера и Соундарараджана. Виноваты в основном зияющие пробелы в моих знаниях аналитической теории чисел, но я думаю, что будет честным сказать, что в некоторых частях статьи математика становится довольно устрашающей. Представленное ниже уравнение является Основной Гипотезой Лемке-Оливера и Соундарараджана. (Я немного изменил её запись и упростил один аспект уравнения: оригинал применим к ряду из r последовательных простых чисел, но в моей версии описываются только пары, то есть .)

Мне кажется, я достаточно хорошо понимаю то, что здесь происходит, чтобы предложить свои пояснения. Слева от знака равенства обозначает считающую функцию, при этом считает простые числа до , — это число пар последовательных простых чисел , попадающих в классы конгруэнции и . Справа от знака равенства основной коэффициент является средним или ожидаемым количеством пар, если бы простые числа были бы случайным образом равномерно распределены без корреляций между последовательными простыми числами; — это логарифмический интеграл , аппроксимация , а — это функция Эйлера, считающая квадрат числа возможных классов конгруэнции для \(m\), или, иными словами, количество элементов в матрице последовательных чисел.

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

А как насчёт коэффициентов этих трёх уточняющих членов? Запись для наименьшего члена означает, что нас будет интересовать только порядок величины члена, который для большого будет малым. Коэффициент при принимает следующий вид:

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

Что касается коэффициента , то Лемке-Оливер и Соунарараджан указывают, что «в общем случае, [он] кажется сложным». И они правы. На этом моменте я должен посоветовать читателям, желающим узнать больше, прочитать оригинал статьи самостоятельно.

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

«Бог, возможно, и не играет с Вселенной в кости, но с простыми числами происходит что-то странное», — так сказал Пал Эрдёш и/или Марк Кац, с небольшой помощью Карла Померанса. Странность проявляется страньше всего, когда мы играем в кости с помощью простых чисел.

Дополнение. Я упомянул выше, что распределение простых чисел по модулю 7 кажется более плоским или более приближенным к равномерному, чем результат бросков правильной кости. Джон Д. Кук провёл с данными проверку хи-квадрат и оказалось, что они вписываются в равномерное распределение слишком хорошо, чтобы это было правдоподобным результатом случайного процесса. В его первом посте рассматривается конкретный случай простых чисел по модулю 7; в его втором посте рассматриваются другие модули.

Справочные материалы

Ash, Avner, Laura Beltis, Robert Gross, and Warren Sinnott. 2011. Frequencies of successive pairs of prime residues. Experimental Mathematics 20(4):400–411.
Chebyshev, Pafnuty Lvovich. 1853. Lettre de M. le Professeur Tchébychev à M. Fuss sur un nouveaux théorème relatif aux nombres premiers contenus dans les formes 4n + 1 et 4n + 3. Bulletin de la Class Physico-mathematique de l’Academie Imperiale des Sciences de Saint-Pétersbourg 11:208. Google Books

Cramér, Harald. 1936. On the order of magnitude of the difference between consecutive prime numbers. Acta Arithmetica 2:23–46. PDF

Granville, Andrew. 1995. Harald Cramér and the distribution of prime numbers. Harald Cramér Symposium, Stockholm, 1993. Scandinavian Actuarial Journal 1:12–28. PDF

Granville, Andrew, and Greg Martin. 2004. Prime number races. arXiv

Hamza, Kais, and Fima Klebaner. 2012. On the statistical independence of primes. The Mathematical Scientist 37:97–105.

Klarreich, Erica. 2016. Mathematicians discover prime conspiracy. Quanta.

Knapowski, S., and P. Turán. 1977. On prime numbers? 1 resp. 3 mod 4. In Number Theory and Algebra: Collected Papers Dedicated to Henry B. Mann, Arnold E. Ross, and Olga Taussky-Todd, pp. 157–165. Edited by Hans Zassenhaus. New York: Academic Press.

Ko, Chung-Ming. 2002. Distribution of the units digit of primes. Chaos Solitons Fractals 13(6):1295–1302.

Lamb, Evelyn. 2016. Peculiar pattern found in ‘random’ prime numbers. Nature doi:10.1038/nature.2016.19550.

Lemke Oliver, Robert J., and Kannan Soundararajan. 2016 preprint. Unexpected biases in the distribution of consecutive primes. arXiv

Odlyzko, Andrew, Michael Rubinstein, and Marek Wolf. 1999. Jumping champions. Experimental Mathematics 8(2):107–118.

Rubinstein, Michael, and Peter Sarnak. 1994. Chebyshev’s bias. Experimental Mathematics 3:173–197. Project Euclid

Tao, Terrence. Structure and randomness in the prime numbers. PDF

Источник