Формула расчёта простых чисел и оптимизация перебора делителей

Приветствую! Решил на досуге исследовать задачу поиска простых чисел. Тема обширная и интересная. Хочу поделиться парой соображений по ней, которые пришли в голову. Поиск в сети интернет подобных не выявил, указав на их оригинальность.

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

Для некоторой последовательности чисел $(x_{m})={x_{1},x_{2},x_{3},...x_{max}}$ введём оператор обнаружения первого числа, равного a:

$\mathbf{Dt_{a}}(x_{m}):=\left\{\begin{matrix} m \ \mathbf{if} \ \exists \ m: \forall \, k<m \ x_{k}\neq a \ \mathbf{and} \ x_{m}=a \\ 0\ \mathbf{otherwise}\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \end{matrix}\right.$


Все простые числа, начиная с 5-ки, можно вычислить по формуле:

$P_{n}=P_{n-1}+2 \mathbf{Dt_{0}^{i}}(\mathbf{Dt_{0}^{j}}((P_{n-1}+2i) \, mod \, P_{j+1})), \ \ \ \forall \, n \geqslant 3 \\ \forall \, i_{max}\geqslant \max\frac{P_{\alpha}-P_{\alpha -1}}{2}+10 \,, \ \ 2 \leqslant\alpha \leqslant n-1; \ \ j_{max}=\pi (\sqrt{P_{n-1}+2i})-1 $


Оператор $\mathbf{Dt_{0}^{j}}$ перебирает по $j$ остатки от деления каждого числа-кандидата на простоту с $i$-м номером $(P_{n-1}+2i)$ на уже найденные простые числа в диапазоне до $P_{j_{max}+1}$. Числа-кандидаты выбираются по порядку из множества нечётных чисел, больших предыдущего простого числа $P_{n-1}$. $\pi (\sqrt{P_{n-1}+2i})$ — это пи-функция, показывающая количество простых чисел $\leqslant\sqrt{P_{n-1}+2i}$.
Оператор $\mathbf{Dt_{0}^{i}}$ перебирает по $i$ выходные значения оператора $\mathbf{Dt_{0}^{j}}$ до тех пор, пока не обнаружит 0. Так как ряд простых чисел бесконечен, это рано или поздно произойдёт. На выходе оператора $\mathbf{Dt_{0}^{i}}$, таким образом, всегда будет некоторый номер $i$. Нижняя граница $i_{max}$ определяется максимальной разностью соседних простых чисел, меньших искомого. Прирост такой разности происходит логарифмически. На графике ниже представлены зависимости максимального и среднего прироста $\Delta P_{\alpha } $ от n для первых 100000 простых чисел. Выборка максимального значения и усреднение проводились для каждой тысячи чисел. image
Максимальный прирост разности простых чисел $\delta _{max}(\Delta P_{\alpha }) $ к предыдущему максимальному значению $max(\Delta P_{\alpha })$ равен 20 (для разности простых чисел 31397-31469=72 по отношению к разности 25523-25471=52). Он находится в области, где производная логарифма огибающей $\Delta P_{\alpha } $ ещё достаточно велика, а простые числа уже не слишком малы. Исходя из этого значения получено условие для $i_{max}$. График $\delta _{max}(\Delta P_{\alpha }) $ для первых 50000 простых чисел дан ниже. Значения вычислялись для каждой тысячи.image
Виден пик на значении 20. С увеличением n график уходит в минус, показывая уменьшение скорости прироста больших простых чисел.

Второе соображение касается оптимизации вычисления последовательности простых чисел.
Алгоритм, заложенный в формуле выше- это улучшенный метод перебора делителей. Улучшения заключаются в исключении из рассмотрения чётных чисел и проверке делимости только на простые числа, меньшие кв. корней чисел-кандидатов. Самая сложная часть алгоритма- это вычисление множества функций взятия остатка mod. Уменьшить сложность можно путём оптимизации этой функции. Однако, есть ещё более эффективный способ. Пусть $(r_{j+1}^{n-1})={r_{2},r_{3},...r_{\pi (\sqrt{P_{n-1}})}}$ — это последовательность остатков от деления последнего найденного простого числа на простые числа от 3-ки до корня из него. Будем составлять последовательности вида

$(r_{i,j+1}^{n})={(r_{2}+2i) \, mod \, P_2,(r_{3}+2i) \, mod \, P_3,... \\ (r_{\pi (\sqrt{P_{n-1}})}+2i) \, mod \, P_{\pi (\sqrt{P_{n-1}})},(P_{n-1}+2i) \, mod \, P_{\pi (\sqrt{P_{n-1}+2i})}}$

по порядку, начиная с $i=1$. Последний член вычисляется в случае, если $\pi (\sqrt{P_{n-1}+2i}) \neq \pi (\sqrt{P_{n-1}})$. Когда на некотором шаге вычисления остаток $r_{i,j+1}^{n}$ становится равным 0, выполняется переход к следующей последовательности. Это делается до тех пор, пока не будет обнаружено i, при котором все остатки ненулевые. Это означает обнаружение очередного простого числа. Последовательность $(r_{j+1}^{n})$ при этом необходимо сохранить до обнаружения следующего простого числа. Рекуррентная формула расчёта простых чисел таким способом преобразуется к виду:

$P_{n}=P_{n-1}+2 \mathbf{Dt_{0}^{i}}(\mathbf{Dt_{0}^{j}}(r_{i,j+1}^{n})), \ \ \ \forall \, n \geqslant 3$


В представленном алгоритме операция mod облегчена: делимые всего в $(r_{j+1}+2i)/P_{j+1}$ раз больше делителей. Исключение составляют только случаи появления новых простых делителей. В памяти ЭВМ при реализации алгоритма необходимо хранить массив простых чисел до корня из искомого, а также переменный массив остатков. Сложность алгоритма в общем смысле (объём работы) может быть меньше, чем у других известных методов. Самые сложные операции в нём- это извлечение квадратного корня, вычисление остатков и умножение. Корень можно извлекать с точностью до целой части. Для получения остатков можно использовать эффективный алгоритм, основанный на общем правиле делимости. Умножение используется только на 2-ку относительно малых чисел i. Временную сложность алгоритма можно уменьшить, распределив работу по значениям i. Полученное таким путём сегментированное сито должно работать быстрее на многопоточных вычислителях. Однако, выполняемая работа будет больше ввиду увеличения делимых. Ещё к алгоритму можно «прикрутить» колёсную факторизацию. При оптимальном размере колёс это может уменьшить сложность в некотором диапазоне n — до тех пор, пока аппаратные «дебри» не затормозят его.

Возможно, кому-то мои соображения пригодятся.

Similar posts

Ads
AdBlock has stolen the banner, but banners are not teeth — they will be back

More

Comments 46

    +4
    Во-первых, нигде не нашёл математическую формулу расчёта простых чисел.

    Если исследование начать с википедии, то можно сразу увидеть пример формулы в виде полинома.
      –2
      Спасибо. Внёс правку: «нигде не нашёл математическую формулу вычисления последовательности простых чисел».
        0

        Но та же википедия даёт ссылку на https://oeis.org/A000040 где, как мне кажется, формул вычисления последовательности довольно много.

          –1
          Много алгоритмов вычисления последовательности. Математической формулы я не нашёл.
            +3

            В чем принципиальная разница между вашей "математической формулой" и алгоритмом?


            (не по формальному определению, а по свойствам)

              –3
              См. определения «математическая формула» и «алгоритм» в википедии.
                +1

                По свойствам.

              +3

              Чем соответствие карри-ховарда не устраивает?

                –1

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

                  +2
                  > Только речь в нём о доказательствах
                  Но доказательство можно представить в виде формулы.

                  Я по прежнему не понимаю почему было важно написать правило $P_n = P_(n-1)+$… на языке TeX, а не P n = P (n-1)+… на хаскеле или любом другом языке.
                    –2

                    Нельзя. Это разные понятия. Может быть только схожая символическая запись.

                      +3
                      >Нельзя.
                      X = 1 и X = 1

                      В чем разница?
                        –2

                        Доказательство может включать в себя формулу. Формула может сама доказать что-то. Формула в отсутствии доказательства также будет иметь своё соответствие. Таким образом, принцип можно расширить как минимум на два "класса объектов": доказательства и формулы.

                          +2
                          >Доказательство может включать в себя формулу.
                          А может и не включать?

                          Если доказательство без формулы будет переписано с формулой то означает ли это что исходно доказательство без формулы содержит формулу? Можно ли считать это одно и то же доказательство?

                          И ещё — расшифруйте пожалуйста «класс объектов» и опишите процедуру отнесения к ним на моем последнем примере — $X=1$ и X=1
                            –6

                            Это метафора на известные Вам термины. Флуд не поддерживаю. До свидания!

              –2
              Спасибо. Наиболее близкая формула из статьи- это формула по теореме Вильсона. Но она даёт последовательность простых чисел не по порядку, они перемежаются двойками без какой-либо закономерности. Внёс ещё уточнение: «нигде не нашёл математическую формулу вычисления простых чисел по порядку».
              0

              Формулы, возвращающей n-ое простое число не существует.


              Задание функции формулой и алгоритмом эквивалентны. Можно ещё таблицей функцию задавать.

                0
                Формулы какого вида? В частично рекурсивных функциях формулу записать можно)
            +8
            Ничего не читай @ пост на хабр пиши.
              0
              Улучшения заключаются в исключении из рассмотрения чётных чисел и проверке делимости только на простые числа, меньшие кв. корней чисел-кандидатов.

              Эту идею конечно давно придумали (может никто не публиковал на Хабре подобные статьи). Создать массив простых чисел до p <= N1/2.
              Для создания этого массива делителей наверное нужно проверять делимость на 2 и дальше на непарные числа 3 < n <= N1/2.
                –1
                На нечётные числа, да. Эти улучшения не новы, конечно.
                +5
                решето Эратосфена, Аткина, Сундарама — нет, не слышал…
                Просто поразительно, до чего был прав Достоевский — «Покажите вы русскому школьнику карту звездного неба, о которой он до тех пор не имел никакого понятия, и он завтра же возвратит вам эту карту исправленную. Никаких знаний и беззаветное самомнение».
                  0
                  О данных алгоритмах Вы можете почитать в других постах. В этом речь не о них.
                  +3
                  Интересно понять разницу представления алгоритма в виде формулы и просто словами. Вы привели оба варианта, поэтому разница весьма наглядна. Словами всё просто — перебираем все простые делители до корня из N. А вот формулой…

                  Мне кажется, что в данном случае представление алгоритма в виде формулы лишь запутывает читателя. Здесь уместно заметить, что языки программирования не зря получились именно такие, какими мы их знаем, и что важно — там нет возможностей для представления алгоритмов в виде подобных формул. Почему там нет таких возможностей? Наверное ваша статья даёт ответ — с формулами выходит ужасно сложно.

                  Хотя, возможно, я чего-то не понял. Тогда автор мог бы пояснить, в чём он видит преимущество представления выбранного алгоритма в виде формулы. Кроме того в заключении есть указания на оценку сложности алгоритма. Но неужели автор думает, что сложность переборного алгоритма до сих пор никто не оценил? Или в его алгоритме всё же есть какие-то отличия? Мне не хватило настойчивости на дешифрование алгоритма из предложенной формулы, а потому оставляю надежду на возможность выявления каких-то преимуществ предложенного подхода. И для этого надеюсь на комментарии автора.
                    –3
                    В моём посте изложено 2 соображения, касающихся:
                    1. составления более-менее лаконичной математической формулы вычисления простых чисел. В ней заложен известный алгоритм перебора делителей с известными улучшениями.
                    2. оптимизации данного алгоритма (в формуле не представлена).
                    Формулу можете пропустить, если интересует только моя оптимизация алгоритма перебора делителей. Можно читать с «Однако, есть ещё более эффективный способ...»
                      +3

                      Вот только формулы Ваши означают совсем не то, что Вы полагаете. Так, возьмем Ваше определение функции image. Вы говорите, что эта функция вернет индекс первого числа, равного a. А я говорю, что это не так.


                      Простейший контрпример — возьмем image (специально для Вас взял простые числа, чтоб не подумали, будто я Вас обманываю) и посчитаем image. К слову, почему последовательность image имеет индекс m, и как этот индекс связан с аргументом image ?


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


                      Дальше в выражении


                      image


                      совсем какая-то жуть происходит. Вы определили функцию image для последовательностей, а подаете на вход число. Я так понимаю, там каким-то образом закодирована последовательность, но каким образом это сделано — совершенно непонятно. Плюс какие-то неизвестно откуда взявшиеся переменные i,j.


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

                        0
                        1. Последовательность в математике обозначается скобками. Вы ставите равенство между членом последовательности x_m и последовательностью, это не корректно.
                        2. Обозначение оператора обнаружения Dt (сокращённо от detection) я ввёл таким образом, что в подписи снизу указывается искомое число, сверху- индекс членов последовательности, по которому ведётся поиск. Помимо этого индекса члены последовательности могут включать в себя другие индексы или переменные. В нашем случае члены последовательности по j включают в себя индекс i. Чтобы было понятно, по которому индексу работает оператор, я ввёл верхнюю подпись.
                        3. На входе оператора обнаружения последовательность, на выходе- число. Оператор- это отображение одного множества в другое. Их размерности могут быть разными. Оператор обнаружения обрабатывает только те члены последовательности, номера которых меньше либо равны номера искомого числа. Потом он заканчивает работу согласно его внутренней логике. В этом его преимущество над функцией поиска минимального значения, например. Последняя работает во всём заданном диапазоне.
                        4. В приведённом Вами «контрпримере» по моей формуле получится именно 3. Верхний индекс оператора нужно было написать m, других индексов члены указанной последовательности в себя не включают. Почему m? Используйте другую букву, сути это не изменит.
                        5. Я не претендую на математическую строгость обозначений, могут быть и более удачные.
                        6. Возможно, подобная формула уже где-то написана. Можете поискать. Я не нашёл.
                          +1
                          Оператор обнаружения обрабатывает только те члены последовательности, номера которых меньше либо равны номера искомого числа. Потом он заканчивает работу согласно его внутренней логике.

                          … так чем же это отличается от алгоритма?

                            +4
                            Вы ставите равенство между членом последовательности x_m и последовательностью, это не корректно.

                            Нет, я говорю, что x_m — это последовательность чисел (2, 3, 5, 7, 11) (девятка там была лишней). Никакого соответствия члена последовательности и самой последовательности я не утверждал. Но теперь я понял смысл Вашего m тут.


                            В приведённом Вами «контрпримере» по моей формуле получится именно 3.

                            Боюсь, тут Вы заблуждаетесь. На самом деле и я ошибся, так как не понял, что параметр m в Dt не играет никакой роли. Поэтому после выяснения этой ошибки, я утверждаю, что оператор image может вернуть не только 3, но любое число из множества {1,2,3}. Я даже не думаю, что в этом случае этот объект можно называть оператором или функцией. Какой-то этот Dt не шибко детерминирован. Никогда еще не встречал подобных "функций".


                            А теперь конкретно, почему последовательность image является контрпримером для утверждения image. Все согласно Вашему определению


                            image


                            Подставьте j = 1. И справа Вы получите правдивое утверждение, так как в последовательности (2, 3, 5, 7, 11) нет элемента, равного 5 на интервале индексов [1,1), но такой элемент найдется на интеpвале индексов [1,5]. Подставьте j = 2, и снова верное утверждение. Для j = 3 будет то же самое. Этот оператор может вернуть любое из вышеозначенных чисел! И независимо от входной последовательности, Dt всегда может вернуть 1!


                            NB: никто не пишет интервалы целых чисел как [a, b). Эта форма записи зарезервирована для действительных чисел. Если хотите указать, что элементы перебираются по какому-то интервалу целых чисел, то можно написать вот так [a...b]. И желательно никаких открытых или полуоткрытых интервалов. А иначе выглядит странно. Я записал этот интервал Вашим способом только для того, чтоб Вам было видней.


                            Вы размышляете о квантификаторах, как программист. Они ничего не перебирают, ничего не ищут. Они сразу возвращают ответ. Если в множестве или последовательности есть подходящий элемент — ответ моментально да, если нет — то нет. Не имеет смысла говорить о временной сложности формулы, поскольку формулы не обладают временной сложностью. Это понятия применимо только к алгоритмам. Поэтому Ваша ремарка, что Dt работает эффективней min абсолютно бессмысленна.


                            И да, формулы — это не алгоритмы. Тут я с Вами согласен. Можно составить формулу с невычислимыми функциями. И формула будет верна, но не существует алгоритма, который мог бы ее вычислить.


                            Возможно, подобная формула уже где-то написана. Можете поискать. Я не нашёл.

                            Я Вам могу сразу сказать, что такой формулы не существует, потому что она просто неверна (по причине, которую я показал выше) и записана как-то нелепо и непонятно.


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


                            Ух, сколько написал.

                              –3
                              Нет, я говорю, что x_m — это последовательность чисел

                              x_m- это член последовательности с номером m, последовательность обозначается (x_m)

                              Боюсь, тут Вы заблуждаетесь...

                              Вы сами придумали новую формулу и сами её опровергли… Формула в посте имеет совсем другой вид.

                              никто не пишет интервалы целых чисел как [a, b)

                              Запись корректна, т. к. множество натуральных чисел входит во множество вещественных. Ваше обозначение- это набор, а не интервал.

                              Вы размышляете о квантификаторах, как программист.

                              Ни о каких квантификаторах я не размышлял.

                              Не имеет смысла говорить о временной сложности формулы, поскольку формулы не обладают временной сложностью.

                              Я не писал о временной сложности формулы. Речь была о преимуществе оператора обнаружения над функцией поиска минимального значения в заданном интервале. Приведённая формула с операторами позволяет более-менее кратко описать известный алгоритм перебора делителей на языке математики.

                              … И формула будет верна, но не существует алгоритма, который мог бы ее вычислить.

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

                              Я Вам могу сразу сказать, что такой формулы не существует, потому что она просто неверна

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

                              Так вот, даже не видя Вашей реализации или какой-нибудь реализации min, я могу смело утверждать, что их временная сложность одинаковая — линейная,

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

                              Ввиду того, что конструктив в вашем «писании» отсутствует, разъяснение Вам поста заканчиваю. Спасибо, до свидания.

                                0
                                В формуле для оператора, действительно, была ошибка. Исправил. Коверкать её не стоило, но за мотивацию повторной проверки спасибо.
                      0
                      Сложность алгоритма в общем смысле (объём работы)

                      Это как?
                        –3

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

                          0
                          Я чёт сомневаюсь, что вы действительно нашли алгоритм, который лучше существующий для этой задачи. Нужны доказательства.
                            –2

                            Я предполагаю, но не утверждаю этого. Был бы благодарен за помощь профессионального сообщества в прояснении этого вопроса!

                              0

                              Эээ, бремя доказательства лежит на утверждающем.

                                –2

                                А кто утверждает? Будут доказательства- будет утверждение. Пока могу только размышлять на эту тему.

                        0
                          –3

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

                          +4
                          Автор изобретает велосипеды, пытаясь задно убедить себя и других в наличии разницы между «алгоритмом» и «математической формулой». Это фейспалм, господа. Совершенно не представляю, кто и почему ставит таким бессодержательным статьям плюсы.
                            –5

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

                              +1
                              мне статья не понравилась, такая изящная тема, и такое скучное изложение, никаких тебе оценок алгортима, введение не нужного оператора, ни слова про библиотеку больших натуральных чисел или как вы собираетесь масштабировать ваш оператор.
                                –3
                                Это краткий пост, а не научная статья. Возможно, кому-то он понравится. Идеи можно развить.
                                  0
                                  Добавил рекуррентную формулу расчёта простых чисел эффективным методом перебора делителей.
                                    0
                                    Дошли руки до реализации описанного алгоритма (на Python):
                                    github.com/Alexander-IK/Prime-number-generators-with-residues-caching/blob/main/Prime_number_generators.ipynb
                                    Оценка вычислительной сложности — O(N*loglog(N^0.5))
                                    По использованию памяти — θ(N^0.5)

                                    Only users with full accounts can post comments. Log in, please.