СЕМАНТИЧЕСКИЙ И СТАТИСТИЧЕСКИЙ АНАЛИЗ ПРОСТЫХ ЧИСЕЛ И ОПТИМИЗАЦИЯ НА ЕГО ОСНОВЕ РЕШЕТА ПОПИКА

SEMANTIC AND STATISTICAL ANALYSIS OF PRIME NUMBERS AND OPTIMIZATION OF THE POPIK SIEVE BASED ON IT

Pavel Popik

Radio engineer,

Russia, St. Petersburg,

АННОТАЦИЯ

В настоящей статье представлены, полученные по результатам семантического и статистического анализа, неожиданные свойства простых чисел, позволившие существенно сократить объем вычислений при использовании алгоритма работы решета Попика (РП). При применении сегментированного варианта решета удалось сократить число циклов просеивания до полутора раз. Приведены результаты статистических исследований простых чисел, в том числе чисел Мерсенна М19 и М31, из которых видно, что все простые числа располагаются рядом с четными числами кратными делителю 6. Четные числа, расположенные между всеми близнецами, также без остатка делятся на 6. Предложено логическое объяснение выявленных закономерностей.

ABSTRACT

This paper presents unexpected properties of prime numbers obtained by semantic and statistical analysis, which allowed us to significantly reduce the amount of computations when using the Popik sieve (PS) algorithm. When the segmented version of the sieve was applied, it was possible to reduce the number of sifting cycles to one and a half times. The results of statistical studies of prime numbers are given, including the Mersenne numbers M19 and M31, which shows that all the prime numbers are located near even numbers divisible by 6. Even numbers located between all the twins also divide by 6 without a remainder. A logical explanation of the identified patterns is proposed.

Ключевые слова: простые числа Мерсенна; простые числа; составные числа; решето Попика; вычислительная модель; горизонтальное сегментирование решета; модифицированное решето Попика; делимость на шесть; геометрическая зависимость чисел Мерсенна; инверсия решета Эратосфена.

Keywords: Mersenne prime numbers; prime numbers; composite numbers; Popik sieve; computational model; horizontal segmentation of the sieve; modified Popik sieve; divisibility by six; geometrical dependence of Mersenne numbers; inversion of the sieve of Eratosthenes.

Введение.

Мотивом для проведения очередного исследования явилось предположение, которое возникло при взгляде на формулу, описывающую простые числа Мерсенна (ПЧМ). Среди первых простых чисел (ПЧ) видно невооруженным взглядом, что ПЧМ располагаются рядом с четными числами, являющимися степенями двойки. Свою лепту в мотивацию внесли также другие наблюдения, которые возникли при оценке некоторых закономерностей, лежащих на поверхности при взгляде на значения ПЧ в первых двух-трёх сотнях списка натуральных чисел (НЧ). Бросается в глаза факт, связанный с тем, что четные числа, расположенные между близнецами (кроме 3 и 5), без остатка делятся на шесть. Также обратили на себя внимание большие простые числа, у которых по аналогии с Законом больших чисел изменения на небольшом интервале списка ПЧ происходили лишь в нескольких младших разрядах ПЧ. Старшие разряды больших простых чисел остаются неизменными. Отсюда возникло желание сконструировать алгоритм для определения простоты больших чисел, который позволил бы обойтись без трудоемких расчетов, связанных с необходимостью деления НЧ на длинный список предыдущих ПЧ. Ещё одним, лежащим на поверхности мотивом для семантического исследования, стал факт наличия в младшем разряде всех ПЧ всего четырех цифр: 1, 3, 7, и 9. Это оказалось странным только на первый взгляд, так как остальные цифры свидетельствуют о кратности НЧ. Хотя существует всего две пары близнецов с числом 5. В результате статистических исследований оптимизм относительно теста простоты для больших чисел оказался не оправданным. Но делимость без остатка на 6 множества НЧ принесла свои плоды.

Статистика простых чисел Мерсенна

Как отмечено выше, вероятным мотивом Марена Мерсенна к тому, чтобы предложить свою формулу для ПЧ явилось, видимо, расположение некоторых из них рядом с НЧ, являющимися степенями двойки. Оставалось лишь выяснить, что степени в ней должны быть простыми числами. Но, как оказалось позже, не все числа, полученные с помощью этой простой формулы, являются простыми. Первым исключением стало 2¹¹-1 (число Мерсенна М11), равное произведению 23 на 89. Недостатком такой формулы является то, что образованные ею ПЧ растут в геометрической прогрессии. И с ростом их номинала всё меньшее количество из них, относительно НЧ, оказывается простыми. Так, согласно приведенному в Википедии списку из первых 38 ПЧ Мерсенна [Л1], до НЧ <=1000 простые составляют чуть более 8%. До НЧ <=10000 их уже менее 2%, а до НЧ менее миллиона – менее 0,05%. Соответственно до тридцать восьмого по списку ПЧ Мерсенна их уже менее 0,01%, и так далее. Практическое значение в настоящее время для этой формулы трудно найти.

Краткое описание вычислительных экспериментов

Моделирование двух гипотез проводилось в офисном приложении Excel. Сначала, в списке близнецов на интервале до, примерно, НЧ=4 млн. была установлена целочисленная делимость на 6 всех четных чисел расположенных между близнецами. Затем, было проанализировано распределение цифр в младшем разряде ПЧ, кроме ПЧ=5 все приведенные выше нечетные числа распределились равномерно. Но среди составных НЧ также оказалось огромное их количество. Второй справа разряд никакого влияния на первый не оказывает, и в нем равномерно распределены все НЧ от 0 до 9. Среди близнецов, взятых в том же диапазоне ПЧ, распределение нарушается, 1 и 9 встречаются в 2 раза чаще, чем 3 и 7. Попыток объяснить это предпринято не было. Затем была построена вычислительная модель (ВМ) для статистических исследований. Необходимо отметить, что такой алгоритм представления ПЧ, когда ПЧ находятся рядом с НЧ, которые целочисленно делятся на шесть, в отличие от аналитического выражения для ПЧМ, даёт прирост ПЧ не пропорционально геометрической прогрессии, а пропорционально арифметической прогрессии. Это приводит к обнаружению потенциальных ПЧ в количестве большем на несколько порядков, чем формула Мерсенна.

Описание результатов статистических исследований

ВМ для исследования была организована известным способом, который позволял бы прояснить справедливость двух гипотез. 1) Все ли близнецы подчиняются правилу, по которому между ними располагаются  НЧ целочисленно делящихся на 6 (ЦДШ).  2) Все ли ПЧ находятся рядом с НЧ целочисленно делящихся на 6.

На восьми интервалах НЧ, каждому из них присваивался в столбце рядом символ "р", если НЧ являлось ПЧ. И "пусто", если НЧ - составное. В следующем столбце каждому НЧ соответствовал результат деления на 6, если ЦДШ. И, наконец, для двух НЧ выше и ниже ЦДШ вычислялся младший разряд (правый символ). По результатам этих простых вычислений строилась сводная таблица. По строкам два значения "р" или не "р" (пусто). По столбцам пять значений: "пусто", 1, 3, 7, 5, 9. Все результаты по восьми интервалам сведены в Таблицу 1. Значения столбца "пусто" не приводятся, поскольку их легко вычислить, и они не содержать никакой новой информации. Из неё видно, что все ПЧ находятся рядом с ЦДШ. Все ПЧ в младшем разряде оканчиваются на 1, 3, 7, 9 и одно на 5. Сумма всех ПЧ и не ПЧ равна интервалу, деленному на 6. Сумма всех ПЧ по столбцам 1, 3, 5, 7, 9 для строки "р" равна количеству ПЧ, фактически имеющемуся в данном интервале. Что как раз и свидетельствует о справедливости обеих выше приведённых гипотез.

Алгоритм работы модифицированного решета

Далее на девятом интервале было выполнено с помощью решета Попика просеивание НЧ на фрагменте одного и того же размера двумя вариантами. 1) просеяны все НЧ диапазона. 2) просеяны из того же диапазона только пары НЧ, которые расположены выше и ниже ЦДШ. На просеивание по первому варианту на весь диапазон потребовалось 32 цикла, по второму - 22 циклов. Фактический выигрыш меньше заявленного в  Таблице 1 в два раза за счет того, что при просеивании по РП учитывались только нечетные числа. Результаты полученных ПЧ в  обоих вариантах оказались абсолютно идентичными. Таким образом, в результате проведения семантических и статистических исследований удалось модифицировать алгоритм решета Попика (МРП) на существенное значение.

Проверка работы ЦДШ на М19 и М31.

Для просеивания горизонтального фрагмента с помощью РП был выбран небольшой фрагмент НЧ, при котором ПЧМ расположены были, примерно, посередине и выполнялось условие (1) из [Л2].  Фрагменты таблиц полученных с помощью РП для М19 и М31 можно найти по ссылкам [Л3] и [Л4]    соответственно. На них видно также подтверждение гипотезы о том, что все ПЧ расположены рядом с ЦДШ. Проверку гипотезы о ЦДШ для других больших НЧ ограничивают параметры таблицы Excel.

Таблица 1.

Таблица распределения простых чисел, расположенных вблизи НЧ целочисленно делящихся на шесть, на интервалах в 500 тыс. НЧ

Периодичность натурального ряда чисел.

Для объяснения обнаруженного явления, связи ПЧ с ЦДШ, имеет смысл предложить простое логическое объяснение, которое опирается на свойство натурального ряда чисел (НРЧ). Натуральный ряд чисел обладает одним почти очевидным свойством - периодичностью чисел, из которых он состоит. Так двойка содержится в качестве множителя в каждом втором натуральном числе. Само значение НЧ является периодом повторения. Номер периода является вторым множителем и повторяет сам НРЧ. Например, для тройки имеем: 3, 2*3=6, 3*3=9, 3*4=12 и так далее. Для 4 имеем 4, 2*4=8, 3*4=12, 4*4=16 ...

N=T(n)*i.                                                                                         (1)

где N - текущее значение, n - НЧ, и одновременно величина периода, i - номер периода, равный одному из значений НРЧ.

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

Инверсия решета Эратосфена.

Инверсия заключается в противоположность вычеркиванию в восстановлении НРЧ, начиная с 2. Используя периодичность и ПЧ=2, инверсия восстанавливает все четные числа. Первую пустоту в полученном ряде, заполняет 3, и далее ряд с периодичностью тройки. Далее используем алгоритм РП, до 3*3 есть еще две пустоты, для НЧ, которых гарантирована простота по РП. Следующая пустота заполняется 5, и затем 7. Из ИРЭ становится понятно, как появляются ПЧ. Никакой периодичностью из предыдущих НЧ, образуемые в результате восстановления НРЧ пустоты, ничем не заполнить, необходимо вводить в НРЧ новые простые числа.

Наиболее сильное влияние на НРЧ с учетом периодичности оказывают ПЧ тем большее, чем они меньше по значению. Соответственно произведение 2*3 и генерирует с периодичностью всех близнецов. То есть при восстановлении НРЧ только с помощью двойки и тройки, рядом с их произведением образуются пустоты вплоть до бесконечности. А последующие ПЧ (5, 7, 11, 13…), входя в составные НЧ, заполняют одну из пустот в паре, и образуют одиночные ПЧ в НРЧ. Первым таким ПЧ является ПЧ = 23, его парой является квадрат ПЧ = 5. Следующая пара содержит 5*7, далее 7*7. Вышеприведенное описание ИРЭ создаёт предпосылки для построения аналитического выражения для получения ПЧ по значению порядкового номера. Вызывает, однако, сомнение его практическая полезность. Гораздо более эффективным и практически значимым выглядит сегментированный алгоритм РП и его рекуррентный вариант из [Л2].

Заключение

В результате семантических и статистических вычислительных экспериментов было установлено:

1) Все ПЧ, кроме 5, заканчиваются в младшем разряде на одно из четырёх значений 1, 3, 7, 9.

2) Все четные числа, расположенные между близнецами, являются ЦДШ.

3) Все другие ПЧ, не имеющие пары (близнеца), также расположены рядом с ЦДШ.

4) Закономерность по п.п. 2,3 о ЦДШ позволяет на две трети сократить объем просеиваемых НЧ в решете Попика.

5) Предложено логическое объяснение появления ПЧ и близнецов при восстановлении (формировании) НРЧ используя ИРЭ.

Список литературы:

1. Википедия. Список простых и совершенных чисел Мерсенна. https://translated.turbopages.org/proxy_u/en-ru.ru.5ae48706-63235fff-7843f743-74722d776562/https/en.wikipedia.org/wiki/List_of_Mersenne_primes_and_perfect_numbers
2. Решето попика и тест простоты на его основе.  https://sibac.info/conf/modernscience/lxxvi/248566
3. Фрагмент таблицы, полученной с помощью РП для М19. https://disk.yandex.ru/i/TH_uhVWvqhtxIw
4. Фрагмент таблицы, полученной с помощью РП для М31. https://disk.yandex.ru/i/7jY_eQvBdgX8LA