Числовую последовательность можно определить, как пронумерованный в определенном порядке набор чисел, заданного вида. Располагая числовой последовательностью на ее основе всегда можно получить числовой ряд, как бесконечную сумму всех членов этой последовательности. В том числе и числовые ряды, представляющие собой измененный по тем или иным правилам исходный числовой ряд. В свою очередь исследование этих рядов может позволить определить общие свойства набора чисел, составляющих исходную последовательность. Тут необходимо обратить внимание на то, что возможные результаты таких исследований, их ценность, во многом определяется способом задания исходной числовой последовательности.
В настоящее время известно три основных способа задания числовой последовательности [1]. Это аналитический – последовательность задается формулой от порядкового номера ее члена, рекуррентный, при котором любой член последовательности, начиная с некоторого, выражается через предшествующие члены и словесный – задание последовательности описанием.
Наиболее предпочтительным считается аналитический способ задания числовой последовательности или хотя бы рекуррентный. Несмотря на то, что способ словесного описания обеспечивает задание последовательности из набора любых чисел, вплоть до набора случайных чисел, данный способ применяется только в крайнем случае, когда первые два способа задания числовой последовательности не удается использовать. Так как, заданную словесным способом последовательность практически никак не возможно исследовать.
В настоящее время последовательность простых чисел задают исключительно способом словесного описания, а это означает, что ни достаточно эффективную формулу, генерирующую все простые числа в порядке их возрастания, ни хотя бы аналогичную рекуррентную формулу пока получить не удалось. И даже в учебной литературе уже прямо указывается, что существующие формулы для простых чисел являются совершенно бесполезными [2]. Поэтому, соответственно, последовательность простых чисел до сих пор относят к нетривиальным бесконечным числовым последовательностям.
Последовательность простых чисел обычно рассматривается в качестве подпоследовательности последовательности натуральных чисел, которая получается путем удаления из последовательности натуральных чисел всех составных чисел. Для чего чаще всего применяют различные алгоритмы просеивания простых чисел, основанных на решете (сите) Эратосфена [2] и других ситах, представляющих собой различные модификации решета Эратосфена. Несмотря на то, что появление решета Эратосфена относят к 250 году до н.э. просеивание все еще продолжает считаться самым быстрым способом детерминированного перечисления простых чисел в пределах выбранного интервала.
Простейший алгоритм просеивания простых чисел работает путем создания списка всех натуральных чисел до заранее выбранного максимального числа и постепенного удаления из него всех чисел кратных простым, то есть составных чисел. В результате выполнения этой процедуры в списке остаются только простые числа, так как ряд натуральных чисел состоит из единицы, простых чисел и составных чисел. Из оставшихся простых чисел и формируется числовая последовательность, содержащая только простые числа. Исследовать или как-либо использовать, сформированные таким образом последовательности, бывает весьма затруднительно. Поэтому в литературе чаще такие числовые последовательности называют списками или таблицами.
Необходимо отметить, что последовательности простых чисел используются не только для их исследования, но и для решения таких практических задач, как разложения чисел на простые множители, поиска больших простых чисел и многих других. Использование же при этом любых очень длинных списков, никак не связанных друг с другом, простых чисел является просто неудобным.
В связи с этим вместо последовательности простых чисел используют последовательности, значение каждого члена которых может быть относительно легко вычислено, но при этом содержащие наряду с простыми числами и некоторое количество составных чисел. Разумеется, такие последовательности тоже представляют собой бесконечные подпоследовательности натурального ряда и наиболее просто представимы арифметическими прогрессиями [3].
С одной стороны в любой арифметической прогрессии каждый ее n-й член всегда может быть вычислен по формуле общего члена (1) [1]:
an = a1 + (n-1)·m, (1)
где a1 – первый член прогрессии, m – разность прогрессии.
При этом порядковый номер n члена прогрессии будет являться и порядковым номером члена числовой последовательности, заданной формулой (1). Чем обеспечивается аналитический способ задания такой числовой последовательности.
С другой стороны, в соответствии с теоремой Дирихле о простых числах в арифметической прогрессии, каждая бесконечная арифметическая прогрессия первый член a1 и разность m, которой являются натуральными взаимно простыми числами, содержит бесконечное число простых чисел [3].
Очевидным недостатком последовательностей, формируемых за счет применения арифметических прогрессий, является наличие в них наряду с простыми числами еще и составных чисел, что приводит к неоправданному увеличению объема вычислений при их использовании. Кроме этого, если арифметическая прогрессия определяет не полный натуральный ряд чисел, то для обеспечения возможности использования всех простых чисел без исключения необходимо формировать, объединенные в одну систему, несколько последовательностей, задаваемых различными арифметическими прогрессиями. Тем не менее, существуют примеры использования таких последовательностей. В качестве такого примера может быть приведен метод пробных делений тестирования чисел на простату [4]. В одном из вариантов, которого проверяется делится ли тестируемое число на 2 и на 3, и если нет, то далее проверяется его делимость только на числа an и bn вида (2) и (3) соответственно.
an = 1 + 6·n, (2)
bn = 5 + 6·n, (3)
где n = 1, 2, 3,…
В данном случае используется система арифметических прогрессий, состоящая из двух различных арифметических прогрессий (2) и (3).
При довольно частом использовании, задаваемых арифметическими прогрессиями, последовательностей, содержащих простые числа, почему-то не рассматривается вопрос о том, а все ли арифметические прогрессии, при использовании в этом качестве, будут одинаково корректны и эффективны? Между тем этот вопрос является важным. Так как с одной стороны, в соответствии с теоремой Дирихле о простых числах в арифметической прогрессии, имеется бесконечно большое количество арифметических прогрессий, содержащих бесконечное число простых чисел и поэтому желательно уметь отличать арифметические прогрессии, от использования которых лучше воздержаться. С другой стороны арифметические прогрессии используются для модификации формул простых чисел в целях сокращения объема вычислительных операций и, соответственно, при этом желательно иметь наиболее эффективные их варианты. Поэтому далее приведены правила составления наиболее рациональных арифметических прогрессий для формирования последовательностей содержащих все простые числа начиная с выбранного заранее простого числа.
Если посмотреть в литературе предлагаемые для использования арифметические прогрессии, то можно заметить одну странность. Все без исключения системы арифметических прогрессий в обязательном порядке содержат одну арифметическую прогрессию, у которой первый член a1 равен единице. Почему использование в арифметической прогрессии в качестве первого члена единицы является странным? А потому, что единица не является ни простым, ни составным числом и, следовательно, такая арифметическая прогрессия не сможет корректно сгенерировать последовательность, в которой должны быть только простые и составные числа.
Казалось бы появление в последовательности состоящей из простых и составных чисел еще и единицы не вызовет никаких проблем, но это не так. Например, если в ходе применения решета Эратосфена или метода пробных делений попытаться в качестве делителя использовать единицу, то эти алгоритмы работать не будут, так как на единицу делятся все числа без исключения. Поэтому для исключения таких ситуаций, при применении решета Эратосфена специально прописывается, что просеивание необходимо начинать с первого простого числа 2. А в формулах (2) и (3) вместо выражения (n-1) из формулы (1) используется порядковый номер n и указывается, что первое значение n должно быть равно единице и, соответственно, не должно быть нулем. Конечно, эти действия приводят к тому, что формула (2) утрачивает способность возвращать единицу, но так же одновременно у формулы (3) утрачивается способность возвращать 5, и проверка тестируемого числа на делимость на 5 осуществляться не будет, что в конечном итоге может привести к появлению ошибок.
Например, описанным выше методом пробных делений, протестируем на простоту составное число 145=5·29. Для этого вычислим максимально необходимое значение пробного делителя: [1450,5]=12 и составим список пробных делителей: 2, 3, a1 = 7, b1 = 11, a2 = 13, b2 = 17. Легко убедиться, что ни один пробный делитель из этого списка не делит число 145. А это означает, что в результате тестирования было ошибочно установлено, что число 145 является простым.
Разумеется, при помощи внесения дополнительных условий в алгоритм тестирования, в конце концов, можно избавиться от всех проблем. Однако, в любом случае, внесение условий в алгоритм тестирования, при написании программы потребуется вписать в нее и соответствующий код для выполнения этих условий. А это повлечет за собой при тестировании на простоту выполнения уже на компьютере дополнительных операций.
Очевидно, что для исключения этих проблем нужно просто не использовать арифметические прогрессии, у которых первый член a1 равен единице и, соответственно, не заменять выражение (n-1) из формулы (1) порядковым номером n. Или, говоря иначе, использовать формулу (1) в ее классическом виде, так как она приводится в учебной литературе.
Согласно теореме Дирихле о простых числах в арифметической прогрессии первый член a1 и разность m должны быть взаимно простыми числами в каждой арифметической прогрессии, содержащей бесконечное число простых чисел. Если это условие выполняется, то формула (1) не будет возвращать все составные числа кратные каждому простому числу, входящему в разложение на простые сомножители числа m. При этом использование в качестве числа m простого числа 2 приведет к исключению из натурального ряда каждого второго числа. Использование в качестве числа m простого числа 3 приведет к исключению из натурального ряда каждого третьего числа. А, например, использование в качестве числа m простого числа 31 приведет к исключению из натурального ряда уже лишь каждого тридцать первого числа. Чем более большие простые сомножители будут входить в разложение числа m, тем меньшее число чисел будет исключаться из натурального ряда. Кроме этого необходимо учитывать, что использование в разложение на простые сомножители числа m двух и более одинаковых чисел не приведет к исключению из натурального ряда большего числа составных чисел, а вызовет лишь увеличение выполняемых вычислительных операций.
Из изложенного следуют очевидные правила составления эффективных арифметических прогрессий, которые будут содержать наименьшее число составных чисел.
Каждая такая арифметическая прогрессия должна строго задаваться формулой (1). При этом разность прогрессии m = p1·p2·…·pn, где pn простые числа, следующие строго в порядке их возрастания начиная с p1 = 2. Значения первых членов прогрессий a1 равны числам из натурального ряда от 2 до m + 1 взаимно простым с разностью прогрессии m. Здесь наибольший член натурального ряда m + 1, из которого выбираются первые члены a1, увеличен на единицу за счет ее переноса из начала натурального ряда. Очевидно, что числа m и m + 1 будут всегда взаимно простыми и, следовательно, всегда будет задаваться арифметическая прогрессия с первым членом a1 = m + 1.
Для обеспечения возможности задания арифметическими прогрессиями с одинаковой разностью m всех простых чисел без исключения потребуется использовать число таких арифметических прогрессий равное числу чисел из натурального ряда от 2 до m + 1 взаимно простых с разностью прогрессии m.
Далее приведены примеры систем наиболее эффективных арифметических прогрессий, составленных по сформулированным выше правилам.
Для m = 2 из натурального ряда от 2 до 3 можно выделить взаимно простое с m одно число a1 = 3. И соответственно составить при помощи формулы (1) всего одну арифметическую прогрессию (4).
an = 3 + 2·(n-1) (4)
Арифметическая прогрессия (4) в определенном смысле уникальна, так как при исключении, из генерируемой ею последовательности, единицы и всех четных чисел оставляет все простые числа за исключением 2.
Для m = 2·3 = 6 из натурального ряда от 2 до 7 можно выделить взаимно простые с m два числа a1 = 5; 7. И соответственно составить при помощи формулы (1) систему (5) из двух арифметических прогрессий.
an = 5 + 6·(n-1), an = 7 + 6·(n-1) (5)
Для m = 2·3·5 = 30 из натурального ряда от 2 до 31 можно выделить взаимно простые с m восемь чисел a1 = 7; 11; 13; 17; 19; 23; 29; 31. И соответственно составить при помощи формулы (1) систему (6) из восьми арифметических прогрессий.
an = 7 + 30·(n-1), an = 11 + 30·(n-1), an = 13 + 30·(n-1), an = 17 + 30·(n-1),
an = 19 + 30·(n-1), an = 23 + 30·(n-1), an = 29 + 30·(n-1), an = 31 + 30·(n-1) (6)
Система (6) арифметических прогрессий является первой, у которой разность m кратна 10 и дальше все рациональные арифметические прогрессии будут иметь разность m кратную 10.
Для m = 2·3·5·7 = 210 из натурального ряда от 2 до 211 можно выделить взаимно простые с m числа a1 = 11; 13; 17; … 211. И соответственно составить при помощи формулы (1) систему (7) из арифметических прогрессий.
an = 11 + 210·(n-1), an = 13 + 210·(n-1), an = 17 + 210·(n-1), ... an = 211 + 210·(n-1) (7)
Для m = 2·3·5·7·11 = 2310 из натурального ряда от 2 до 2311 можно выделить взаимно простые с m числа a1 = 13; 17; 19; … 2311. И соответственно составить при помощи формулы (1) систему (8) из арифметических прогрессий.
an = 13 + 2310·(n-1), an = 17 + 2310·(n-1), an = 19 + 2310·(n-1), ... an = 2311 + 2310·(n-1) (8)
Для m = 2·3·5·7·11·13 = 30030 из натурального ряда от 2 до 30031 можно выделить взаимно простые с m числа a1 = 17; 19; 23; … 30031. И соответственно составить при помощи формулы (1) систему (9) из арифметических прогрессий.
an = 17 + 30030·(n-1), an = 19 + 30030·(n-1), an = 23 + 30030·(n-1), ... an = 30031 + 30030·(n-1) (9)
Очевидно, что ряд таких систем арифметических прогрессий теоретически можно продолжать до бесконечности, а практически пока это будет возможно технически. Ведь с ростом m растет и количество арифметических прогрессий в системе.
Пример числовой последовательности, задаваемой системой (6) арифметических прогрессий приведен в Таблице 1.
Таблица 1
|
n |
7+30(n-1) |
11+30(n-1) |
13+30(n-1) |
17+30(n-1) |
19+30(n-1) |
23+30(n-1) |
29+30(n-1) |
31+30(n-1) |
|
1 |
7 |
11 |
13 |
17 |
19 |
23 |
29 |
31 |
|
2 |
37 |
41 |
43 |
47 |
49 |
53 |
59 |
61 |
|
3 |
67 |
71 |
73 |
77 |
79 |
83 |
89 |
91 |
|
4 |
97 |
101 |
103 |
107 |
109 |
113 |
119 |
121 |
|
5 |
127 |
131 |
133 |
137 |
139 |
143 |
149 |
151 |
|
6 |
157 |
161 |
163 |
167 |
169 |
173 |
179 |
181 |
|
7 |
187 |
191 |
193 |
197 |
199 |
203 |
209 |
211 |
|
8 |
217 |
221 |
223 |
227 |
229 |
233 |
239 |
241 |
|
9 |
247 |
251 |
253 |
257 |
259 |
263 |
269 |
271 |
|
10 |
277 |
281 |
283 |
287 |
289 |
293 |
299 |
301 |
|
11 |
307 |
311 |
313 |
317 |
319 |
323 |
329 |
331 |
Как видно из Таблицы 1 в начале, представленной в ней числовой последовательности, простые числа встречаются заметно чаще, чем составные, но с ростом n эта ситуация очень быстро изменится и составных чисел в этой последовательности будет намного больше чем простых. А, учитывая, что для числовых последовательностей такого вида не существует достаточно эффективного метода разделения их членов на простые и составные числа нельзя рассматривать их в качестве эффективной замены для последовательностей, содержащих только простые числа.
Поэтому в статье [5] было предложено заменять последовательности, содержащие только простые числа, или заданные при помощи арифметических прогрессий числовым рядом (последовательностью, если удалить знаки суммирования) (10).
0 + 2 + 3 + 0 + 5 + 0 + 7 + 0 + 0 + 0 + 11 + 0 + 13 + 0 + 0 + 0 + 17 + 0 + 19 + 0 + 0 + 0 +
+ 23 + 0 + 0 + 0 + 0 + 0 + 29 + 0 + 31 + 0 + 0 + 0 + 0 + 0 + 37 + 0 + 0 + 0 + 41 + 0 + 43 +
+ 0 + 0 + 0 + 47 + 0 + 0 + 0 + 0 + 0 + 53 + 0 + 0 + 0 + 0 + 0 + 59 + 0 + 61 + 0 + 0 + 0 +
+ 0 + 0 + 67 + 0 + 0 + 0 + 71 + 0 + 73 + 0 + 0 + 0 + 0 + 0 + 79 + 0 + 0 + 0 + 83 + 0 + 0 +... (10)
Последовательность (10) представляет собой последовательность натуральных чисел, в которой все составные числа заменены нулями. В результате любой ее член может быть либо простым числом, либо равным нулю. Это обеспечивает решение проблемы разделения членов этой последовательности на простые и составные числа. Действительно в последовательности (10) нет ни одного составного числа, так как ноль не является ни составным, ни простым числом. И любое число в последовательности (10) большее нуля следует считать простым числом. Кроме этого порядковые номера членов последовательности (10) не будут отличаться от порядковых номеров членов последовательности натуральных чисел. Например, простое число 11 в натуральном ряду имеет порядковый номер 11 и в последовательности (10) оно тоже будет иметь порядковый номер 11, что облегчает установление закономерности в появлении простых чисел в последовательности (10).
Среди целых чисел кроме нуля есть еще единица, которая так же не является ни простым не составным числом и, следовательно, может быть использована в ряду (10) вместо нуля. Однако, если ряд (10) предполагается использовать для исследования последовательности простых чисел, то замену нуля на единицу производить не желательно. В связи с тем, что добавление к членам ряда членов, равных единице, вызывает большие изменения свойств ряда (10), чем добавление членов, равных нулю. Так члены ряда (10), равные нулю, никак не повлияют на частичные суммы ряда (10). То есть частичные суммы ряда (10) будут такими же, как у ряда, состоящего только из простых чисел [5].
По этим же причинам свойства ряда (10) никак не изменятся, если в целях сокращения числа его членов между простыми числами из ряда 10 будут удалены все его члены с порядковыми номерами кратными какому либо числу. Ведь все члены ряда (10), имеющие порядковые номера кратные, какому либо числу, равны нулю.
Очевидно, что формирование последовательности (10) может быть осуществлено при помощи любого детерминированного (истинного) универсального теста простоты, то есть применимого ко всем без исключения числам и обеспечивающего гарантированное подтверждение простоты числа. Например, существуют тривиальные формулы, основанные на теореме Вильсона [3], которые при внесении в них незначительных изменений принципиально могут задавать последовательность (10). Однако все подобные формулы предполагают вычисление факториалов больших чисел, что пока не обеспечивают современные компьютерные алгоритмы. Кроме этого за годы существования таких формул, их так и не удалось модифицировать в целях обеспечения их практического применения. Да и в целом проблема создания эффективного универсального теста простоты больших чисел, все еще так и остается не решенной.
Конечно для формирования последовательности (10) можно применить решето Эратосфена или его модификации. Отличие будет заключаться лишь в том, что составные числа не будут удаляться из натурального ряда, а будут заменяться нулями. При этом вычислительная сложность формирования последовательности (10) не будет отличаться от вычислительной сложности формирования последовательности простых чисел.
Но в статье [5] было показано, что существует функциональная связь между рядом натуральных чисел и рядом (10), что означает возможность составления, как минимум, рекуррентной формулы для последовательного вычисления значений всех членов ряда (10). Из-за, перечисленных выше, особенностей ряда (10) наличие формулы для последовательного вычисления по порядку всех его членов фактически будет означать и наличие формулы для последовательного вычисления по порядку без исключений всех членов последовательности простых чисел. И такая формула тривиально следует из малой теоремы Ферма, которая утверждает, что если р – простое число и d – целое число, не делящееся на р, то dр-1-1 делится на р.
В настоящее время в понятиях и символьных обозначениях теории сравнений это утверждение обычно сводится к простому выражению (11):
dр-1 ≡ 1 (mod p), (11)
которое означает, что dр-1 сравнимо с 1 по простому модулю р [3].
Однако тест Ферма, основанный на малой теореме Ферма, считается вероятностным тестом, то есть тестом, который даёт ответ о составности числа либо его несоставности лишь с некоторой вероятностью [4]. В связи с этим, возможно, будет не понятно, как на основе малой теоремы Ферма может быть получена формула последовательного вычисления значений всех членов ряда (10)? Но дело в том, что тест Ферма был отнесен к вероятностным тестам ошибочно и никаких проблем по этим основаниям с составлением такой формулы не существует. На самом деле тест Ферма является истинным. Конечно при соблюдении в ходе его применения ряда условий. Из-за большого объема подробно этот вопрос будет рассмотрен в следующей статье [6]. Вообще этот вопрос надо бы было рассмотреть еще в статье [5], но поскольку после появления статьи никто так и не обратил на это обстоятельство внимания, то можно предположить, что истинность теста Ферма и так всем очевидна. Кроме этого из дальнейших рассуждений так же будет следовать истинность теста Ферма, основанного на малой теореме Ферма.
Несмотря на то, что в статье [5] указывалось на значительные объемы вычислений при использовании для формирования ряда (10) малой теоремы Ферма, она все же предлагается в качестве основы для составления формулы последовательного вычисления членов ряда (10). Так как при этом, с малой теоремой Ферма потребуется совершить лишь очевидные элементарные операции, облегчается объяснение принципов работы формулы и обеспечивается возможность ее модификации в целях повышения вычислительной эффективности.
Еще необходимо отметить, что для целей настоящей статьи формулировка малой теоремы Ферма в понятиях и символьных обозначениях теории сравнений плохо подходит.
В связи с этим ниже приведен вариант формулировки малой теоремы Ферма, содержащий формулу, выполняющую процедуру замены исходного числа остатком от его целочисленного деления на модуль. В этой формуле роль модуля выполняет число р.
Если р – простое число, то для каждого натурального числа d, не делящегося на число р, будет выполняться равенство (12).
dр-1-р·[dр-1/р] = 1, (12)
где [ ] – знак, обозначающий целую часть числа или обозначает операцию по отбрасыванию дробной части от результата вычисления выражения, стоящего в прямоугольных скобках (здесь и далее по тексту).
Теперь если в выражении (12) число р заменить на число n – порядковый номер последовательности (10) и или последовательности натуральных чисел, и совершить с выражением (12) ряд очевидных элементарных операций, то можно получить тривиальную рекуррентную формулу (13) для последовательного вычисления членов ряда (10).
a0 = 0, an = n·(dn-1-n·[dn-1/n]), (13)
где d = П1n-1 (an-1 + 0^an-1) – данное выражение фактически представляет собой произведение всех простых членов an последовательности (10) от a2 = 2 до an-1 включительно.
Далее приведен пример вычисления при помощи формулы (13) по порядку всех членов последовательности (10) начиная с первого члена.
n = 1 d = 0 + 00 = 1 a1 = 1·(10 - 1·[10/1]) = 0
n = 2 d = 1·(0 + 00) = 1 a2 = 2·(11 - 2·[11/2]) = 2
n = 3 d = 1·(2 + 02) = 2 a3 = 3·(22 - 3·[22/3]) = 3
n = 4 d = 2·(3 + 03) = 6 a4 = 4·(63 - 4·[63/4]) = 0
n = 5 d = 6·(0 + 00) = 6 a5 = 5·(64 - 5·[64/5]) = 5
n = 6 d = 6·(5 + 05) = 30 a6 = 6·(305 - 6·[305/6]) = 0
n = 7 d = 30·(0 + 00) = 30 a7 = 7·(306 - 7·[306/7]) = 7
n = 8 d = 30·(7 + 07) = 210 a8 = 8·(2107 - 8·[2107/8]) = 0
n = 9 d = 210·(0 + 00) = 210 a9 = 9·(2108 - 9·[2108/9]) = 0
n = 10 d = 210·(0 + 00) = 210 a10 = 10·(2109 - 10·[2109/10]) = 0
n = 11 d = 210·(0 + 00) = 210 a11 = 11·(21010 - 11·[21010/11]) = 11
n = 12 d = 210·(11 + 011) = 2310 a12 = 12·(231011 - 12·[231011/12]) = 0
n = 13 d = 2310·(0 + 00) = 2310 a13 = 13·(231012 - 13·[231012/13]) = 13
n = 14 d = 2310·(13 + 013) = 30030 a14 = 14·(3003013 - 14·[3003013/14]) = 0
n = 15 d = 30030·(0 + 00) = 30030 a15 = 15·(3003014 - 15·[3003014/15]) = 0
n = 16 d = 30030·(0 + 00) = 30030 a16 = 16·(3003015 - 16·[3003015/16]) = 0
n = 17 d = 30030·(0 + 00) = 30030 a17 = 17·(3003016 - 17·[3003016/17]) = 17
n = 18 d = 30030·(17 + 017) = 510510 a18 = 18·(51051017 - 18·[51051017/18]) = 0
n = 19 d = 510510·(0 + 00) = 510510 a19 = 19·(51051018 - 19·[51051018/19]) = 19
n = 20 d = 510510·(19 + 019) = 9699690 a20 = 20·(969969019 - 20·[969969019/20]) = 0
n = 21 d = 9699690·(0 + 00) = 9699690 a21 = 21·(969969020 - 21·[969969020/21]) = 0
n = 22 d = 9699690·(0 + 00) = 9699690 a22 = 22·(969969021 - 22·[969969021/22]) = 0
n = 23 d = 9699690·(0 + 00) = 9699690 a23 = 23·(969969022 - 23·[969969022/23]) = 23
В ходе выполнения вычислений по формуле (13) необходимо обращать внимание на то, что 00 = 1. Если в вашем вычислительном средстве это не так, что еще бывает, случается, то для получения корректных результатов в программу вычислений необходимо будет внести изменения, устраняющие эту ошибку. Вообще выражение an-1 + 0^an-1 необходимо, для того чтобы при an-1 = 0 an-1 + 0^an-1 = 1, а при an-1 > 0 an-1 + 0^an-1 = an-1. Этот же результат можно получить и при помощи иных аналогичных выражений и, используя соответствующее условие или символьную функцию. Но при этом формула (13) фактически будет содержать словесные высказывания. Кроме этого выражение an-1 + 0^an-1, по всей видимости, является самым компактным из всех возможных для обеспечения, указанных целей.
Очевидно, что продолжать вычисление по формуле (13) членов последовательности (10) можно бесконечно и при этом формула (13) всегда без ошибок будет возвращать простые числа, а вместо составных чисел – нули. Такой результат будет получаться всегда из-за того, что любое следующее простое число n, не вошедшее в произведение d, не сможет являться делителем произведения d и в соответствии с малой теоремой Ферма результатом вычисления выражения dn-1-n·[dn-1/n] всегда будет получаться единица. А любое составное число n до следующего простого числа n в соответствии с основной теоремой арифметики [4] может быть разложено на простые сомножители только уже входящие в произведение d, так как любое простое число большее составного числа никак не может являться делителем такого составного числа. Кроме этого всегда 2n-1 > n для n > 1 и, следовательно, даже в случае, если каноническое разложение составного числа на простые сомножители будет состоять из степеней простых чисел, то любое составное число n до следующего простого числа n будет все равно делить выражение dn-1. Таким образом, для любого составного n, из указанного диапазона, результатом вычисления выражения dn-1-n·[dn-1/n] всегда будет получаться ноль.
Поэтому, при применении малой теоремы Ферма совместно с формулой (13) появление псевдопростых чисел [4] становится невозможным и требование делимости целого числа d на тестируемое число тоже можно не учитывать. И, следовательно, формулу (13), составленную на основе малой теоремы Ферма, можно так же рассматривать в качестве истинного теста простоты.
Несмотря на то, что формула (13), основанная на малой теореме Ферма, обеспечивает более низкую вычислительную сложность формирования последовательности (10), чем аналогичные формулы, основанные на теореме Вильсона, объемы необходимых, при практическом применении формулы (13), вычислений остаются все еще слишком большими. В связи с этим формула (13) нуждается в модификациях. Поэтому далее будут рассмотрены некоторые возможные направления таких модификаций формулы (13).
Самым простым и очевидным методом модификации формулы (13) является не выполнение вычислений по формуле (13) с порядковыми номерами n, которые достоверно являются составными числами. Это, возможно, осуществить, так как произведение d = П1n-1 (an-1 + 0^an-1) изменяется только при простом значении an-1, а при составном значении n-1, когда an-1 = 0 не изменяется. То есть, если пропустить вычисления по формуле (13) с составными значениями n, то это никак не повлияет на вычисление значений простых an. Кроме этого, так как в последовательности (10) все порядковые номера n, соответствующие простым членам, им же и равны, то все значения членов последовательности (10), для порядковых номеров n, которых вычисления не осуществлялись, могут быть просто приравнены нулю.
Очевидно, что минимума вычислений можно достигнуть, если подставлять в формулу (13) только порядковые номера n, являющиеся простыми числами, но известных алгоритмов их вычисления не существует. А если бы такие алгоритмы существовали, то и данная статья была бы не нужна. Однако все же можно, при минимальных затратах, исключить сравнительно большое количество составных значений n.
Например, если в качестве порядковых номеров n для подстановки в формулу (13) использовать в порядке возрастания члены арифметической прогрессии (4), то в формулу (13) не потребуется подставлять все четные значения n, что приведет к сокращению объема вычислений по формуле (13) в два раза. Кроме этого, так как разность арифметической прогрессии (4) m = 2, то и порядковых номеров n кратных двум в формулу (13) подставляться не будет, а значит, нет необходимости в качестве сомножителя произведения d использовать 2. Что фактически будет означать уменьшение в два раза всех используемых значений произведений d и дальнейшее сокращение объемов вычислений при применении формулы (13).
Нужно отметить, что при использовании арифметической прогрессии (4) совместно с формулой (13) выражение для произведения d необходимо изменить: d = П1n-2 (an-2 + 0^an-2). Правда, столь простой вид выражение для произведения d будет иметь только при использовании арифметической прогрессии (4). В случае же использования арифметических прогрессий с разностями m превышающими 2 выражение для произведения d будет быстро усложняться. Поэтому выражение для произведения d в общем случае при использовании арифметических прогрессий должно иметь следующий вид: d = П1nп (anп + 0^anп), где anп – значение вычисленного предыдущего члена последовательности (10) по отношению к an.
Далее приведен пример вычисления членов последовательности (10) при помощи формулы (13) и использовании в качестве порядковых номеров n членов системы (6) арифметических прогрессий.
Так как у всех арифметических прогрессий системы (6) разность m = 2·3·5 = 30, то, не проводя вычислений, можно записать значения следующих членов последовательности (10): a2 = 2, a3 = 3, a5 = 5, а произведение d разделить на 30 и в качестве начального значения принять d = 1.
Для вычисления по порядку всех членов последовательности (10), которые предположительно могут быть простыми, в порядке возрастания, в качестве порядковых номеров n подставим в формулу (13) члены системы (6) арифметических прогрессий. Часть членов системы (6) арифметических прогрессий уже вычислена и занесена в Таблицу 1. Поэтому их значения для проведения вычислений будут взяты в Таблице 1.
n=7 d=1 a7=7·(16-7·[16/7])=7
n=11 d=1·(7+07)=7 a11=11·(710-11·[710/11])=11
n=13 d=7·(11+011)=77 a13=13·(7712-13·[7712/13])=13
n=17 d=77·(13+013)=1001 a17=17·(100116-17·[100116/17])=17
n=19 d=1001·(17+017)=17017 a19=19·(1701718-19·[1701718/19])=19
n=23 d=17017·(19+019)=323323 a23=23·(32332322-23·[32332322/23])=23
n=29 d=323323·(23+023)=7436429 a29=29·(743642928-29·[743642928/29])=29
n=31 d=7436429·(29+029)=215656441 a31=31·(21565644130-31·[21565644130/31])=31
n=37 d=215656441·(31+031)=6685349671 a37=37·(668534967136-37·[668534967136/37])=37
n=41 d=6685349671·(37+037)=247357937827 a41=41·(24735793782740-41·[24735793782740/41])=41
n=43 d=247357937827·(41+041)=10141675450907 a43=43·(1014167545090742-43·[1014167545090742/43])=43
n=47 d=10141675450907·(43+043)=436092044389001 a47=47·(43609204438900146-47·[43609204438900146/47])=47
n=49 d=436092044389001·(47+047)=20496326086283047 a49=49·(2049632608628304748-49·[2049632608628304748/49])=0
n=53 d=20496326086283047·(0+00)=20496326086283047 a53=53·(2049632608628304752-53·[2049632608628304752/53])=53
И так далее по порядку можно и дальше до бесконечности вычислять члены последовательности (10). Причем все члены последовательности (10), которые не были вычислены, имеют в качестве порядковых номеров n составные числа и соответственно равны нулю. Так, например между a7=7 и a11=11 будут a8= a9= a10=0, между a11=11 и a13=13 будет a12=0, между a13=13 и a17=17 будут a14= a15= a16=0. Продолжать ряд таких членов последовательности (10) тоже можно до бесконечности. При этом значительную их часть вычислять не требуется.
Смысл рассматриваемого алгоритма заключается в том, что вычисленные, вероятно простые, члены арифметических прогрессий окончательно тестируются на простоту при помощи формулы (13), а числа, которые являются гарантированно составными, при вычислениях вообще не используются, что и обеспечивает весьма значительное сокращение объема вычислений по формуле (13). Так, в приведенном выше примере, были определены значения 53 членов последовательности (10), а вычислить по формуле (13) пришлось лишь 14 значений.
Разумеется, весь рассмотренный здесь алгоритм можно представить в виде формулы, но объем такой формулы будет весьма значительным и, соответственно, ее использование будет нецелесообразным.
Еще одно направление модификации формулы (13) может быть основано на том обстоятельстве, что возведение произведения d в степень n-1 в формуле (13) всегда является избыточным для установления факта делимости dn-1 на n и тем самым установления факта составности n. Причем эта избыточность является значимой для сокращения объема вычислений.
Так, если, для примера, принять самый невыгодный вариант, когда порядковый номер n представим в качестве степени самого маленького простого числа: n = 23 = 8, то dn-1 = 2107 = 18010885410000000 и 18010885410000000/8=2251360676250000. Однако если d возводить не в степень n-1, а в минимально необходимую степень: k=[ln(8)/ln(2)]=3, то будут получены существенно меньшие числа dk = 2103 = 9261000 и 9261000/8=1157625. То есть произойдет сокращение используемых при вычислениях чисел в 18010885410000000/9261000=1944810000 раз.
Правда, при замене показателя степени n-1 на k перестанет выполняться малая теорема Ферма и соответственно формулу (13) с такими изменениями использовать тоже станет нельзя. Поэтому на основании выше изложенного для простых чисел придется составить иную теорему.
Теорема 1. Число рi – простое тогда и только тогда, когда выполняется выражение (14).
dk-рi·[dk/рi] > 0, (14)
где d = П1i-1рi – данное выражение представляет собой произведение всех простых чисел по порядку от р1 = 2 до рi-1 включительно, k=[ln(рi)/ln(р1)], рi – число большее простого числа рi-1 и может быть как простым, так и составным.
Если выполняется равенство: dk-рi·[dk/рi] = 0, то рi является точно составным.
Теорема 1 представляет собой детерминированный и универсальный тест простоты, и ее применение будет более эффективно по сравнению с малой теоремой Ферма только в этом качестве.
На основе Теоремы 1 можно получить тривиальную рекуррентную формулу (15) для последовательного вычисления членов ряда (10), которая будет также более эффективна, чем формула (13).
a0 = 0, an = n·(dk-n·[dk/n])/(dk-n·[dk/n]+0^(dk-n·[dk/n])), (15)
где n – порядковый номер членов последовательности (10) и или последовательности натуральных чисел, d = П1n-1(an-1+0^an-1) – данное выражение фактически представляет собой произведение всех простых членов an последовательности (10) от a2 = 2 до an-1 включительно, k=[ln(n)/ln(a2)].
Если повторяющееся в формуле (15) выражение dk-n·[dk/n] обозначить буквой s, то есть принять что s=dk-n·[dk/n], то формулу (15) можно будет записать в виде более компактной формулы (16).
a0 = 0, an = n·s/(s+0s) (16)
Далее приведен пример вычисления при помощи формулы (16) по порядку всех членов последовательности (10) начиная с первого члена.
n=1 d=0+00=1 k=[ln(1)/ln(2)]=0 s=10 - 1·[10/1]=0 a1=1·0/(0+00)=0
n=2 d=1·(0+00)=1 k=[ln(2)/ln(2)]=1 s=11 - 2·[11/2]=1 a2=2·1/(1+01)=2
n=3 d=1·(2+02)=2 k=[ln(3)/ln(2)]=1 s=21 - 3·[21/3]=2 a3=3·2/(2+02)=3
n=4 d=2·(3+03)=6 k=[ln(4)/ln(2)]=2 s=62 - 4·[62/4]=0 a4=4·0/(0+00)=0
n=5 d=6·(0+00)=6 k=[ln(5)/ln(2)]=2 s=62 - 5·[62/5]=1 a5=5·1/(1+01)=5
n=6 d=6·(5+ 05)=30 k=[ln(6)/ln(2)]=2 s=302 - 6·[302/6]=0 a6=6·0/(0+00)=0
n=7 d=30·(0+00)=30 k=[ln(7)/ln(2)]=2 s=302 - 7·[302/7]=4 a7=7·4/(4+04)=7
n=8 d=30·(7+07)=210 k=[ln(8)/ln(2)]=3 s=2103 - 8·[2103/8]=0 a8=8·0/(0+00)=0
n=9 d=210·(0+00)=210 k=[ln(9)/ln(2)]=3 s=2103 - 9·[2103/9]=0 a9=9·0/(0+00)=0
n=10 d=210·(0+00)=210 k=[ln(10)/ln(2)]=3 s=2103 - 10·[2103/10]=0 a10=10·0/(0+00)=0
n=11 d=210·(0+00)=210 k=[ln(11)/ln(2)]=3 s=2103 - 11·[2103/11]=1 a11=11·1/(1+01)=11
n=12 d=210·(11+011)=2310 k=[ln(12)/ln(2)]=3 s=23103 - 12·[23103/12]=0 a12=12·0/(0+00)=0
n=13 d=2310·(0+00)=2310 k=[ln(13)/ln(2)]=3 s=23103 - 13·[23103/13]=1 a13=13·1/(1+01)=13
n=14 d=2310·(13+013)=30030 k=[ln(14)/ln(2)]=3 s=300303 - 14·[300303/14]=0 a14=14·0/(0+00)=0
n=15 d=30030·(0+00)=30030 k=[ln(15)/ln(2)]=3 s=300303 - 15·[300303/15]=0 a15=15·0/(0+00)=0
n=16 d=30030·(0+00)=30030 k=[ln(16)/ln(2)]=4 s=300304 - 16·[300304/16]=0 a16=16·0/(0+00)=0
n=17 d=30030·(0+00)=30030 k=[ln(17)/ln(2)]=4 s=300304 - 17·[300304/17]=16 a17=17·16/(16+016)=17
n=18 d=30030·(17+ 017)=510510 k=[ln(18)/ln(2)]=4 s=5105104 - 18·[5105104/18]=0 a18=18·0/(0+00)=0
n=19 d=510510·(0+00)=510510 k=[ln(19)/ln(2)]=4 s=5105104 - 19·[5105104/19]=1 a19=19·1/(1+01)=19
n=20 d=510510·(19+019)=9699690 k=[ln(20)/ln(2)]=4 s=96996904 - 20·[96996904/20]=0 a20=20·0/(0+00)=0
n=21 d=9699690·(0+00)=9699690 k=[ln(21)/ln(2)]=4 s=96996904 - 21·[96996904/21]=0 a21=21·0/(0+00)=0
n=22 d=9699690·(0+00)=9699690 k=[ln(22)/ln(2)]=4 s=96996904 - 22·[96996904/22]=0 a22=22·0/(0+00)=0
n=23 d=9699690·(0+00)=9699690 k=[ln(23)/ln(2)]=4 s=96996904 - 23·[96996904/23]=2 a23=23·2/(2+02)=23
Очевидно, что продолжать вычисление по формуле (16) членов последовательности (10) можно бесконечно и при этом формула (16), как и формула (13), всегда без ошибок будет возвращать простые числа, а вместо составных чисел – нули. Такой результат будет получаться всегда по тем же причинам, что и в формуле (13), но зато при выполнении значительно меньшего объема вычислений.
В целях дальнейшего сокращения объемов вычислений формулу (16) можно использовать совместно с арифметическими прогрессиями. При этом правила их совместного использования почти не будут отличаться от выше приведенных правил совместного использования формулы (13) и арифметических прогрессий.
Далее рассмотрено такое применение формулы (16) на примере вычисления членов последовательности (10) при помощи формулы (16) и использовании в качестве порядковых номеров n членов системы (6) арифметических прогрессий.
Так как у всех арифметических прогрессий системы (6) разность m = 2·3·5 = 30, то, не проводя вычислений, можно записать значения следующих членов последовательности (10): a2 = 2, a3 = 3, a5 = 5, а произведение d разделить на 30 и в качестве начального значения принять d = 1.
Кроме этого, так как в произведении d наименьшим сомножителем теперь будет a7=7, то выражение для вычисления показателя степени k можно тоже изменить: k=[ln(n)/ln(a7)], что позволит дополнительно сократить объемы вычислений. Это, конечно, если не учитывать сомножители равные единице.
Для вычисления по порядку всех членов последовательности (10), которые предположительно могут быть простыми, в порядке возрастания, в качестве порядковых номеров n подставим в формулу (16) члены системы (6) арифметических прогрессий. Часть членов системы (6) арифметических прогрессий уже вычислена и занесена в Таблицу 1. Поэтому их значения для проведения вычислений будут взяты в Таблице 1.
n=7 d=1 k=[ln(7)/ln(7)]=1 s=11 - 7·[11/7]=1 a7=7·1/(1+01)=7
n=11 d=1·(7+07)=7 k=[ln(11)/ln(7)]=1 s=71 - 11·[71/11]=7 a11=11·7/(7+07)=11
n=13 d=7·(11+011)=77 k=[ln(13)/ln(7)]=1 s=771 - 13·[771/13]=12 a13=13·12/(12+012)=13
n=17 d=77·(13+013)=1001 k=[ln(17)/ln(7)]=1 s=10011 - 17·[10011/17]=15 a17=17·15/(15+015)=17
n=19 d=1001·(17+017)=17017 k=[ln(19)/ln(7)]=1 s=170171 - 19·[170171/19]=12 a19=19·12/(12+012)=19
n=23 d=17017·(19+019)=323323 k=[ln(23)/ln(7)]=1 s=3233231 - 23·[3233231/23]=12 a23=23·12/(12+012)=23
n=29 d=323323·(23+023)=7436429 k=[ln(29)/ln(7)]=1 s=74364291 - 29·[74364291/29]=17 a29=29·17/(17+017)=29
n=31 d=7436429·(29+029)=215656441 k=[ln(31)/ln(7)]=1 s=2156564411 - 31·[2156564411/31]=12 a31=31·12/(12+012)=31
n=37 d=215656441·(31+031)=6685349671 k=[ln(37)/ln(7)]=1 s=66853496711 - 37·[66853496711/37]=9 a37=37·9/(9+09)=37
n=41 d=6685349671·(37+037)=247357937827 k=[ln(41)/ln(7)]=1 s=2473579378271 - 41·[2473579378271/41]=33 a41=41·33/(33+033)=41
n=43 d=247357937827·(41+041)=10141675450907 k=[ln(43)/ln(7)]=1 s=101416754509071 - 43·[101416754509071/43]=41 a43=43·41/(41+041)=43
n=47 d=10141675450907·(43+043)=436092044389001 k=[ln(47)/ln(7)]=1 s=4360920443890011 - 47·[4360920443890011/47]=9 a47=47·9/(9+09)=47
n=49 d=436092044389001·(47+047)=20496326086283047 k=[ln(49)/ln(7)]=2 s=204963260862830472 - 49·[204963260862830472/49]=0 a49=49·0/(0+00)=0
n=53 d=20496326086283047·(0+00)=20496326086283047 k=[ln(53)/ln(7)]=2 s=204963260862830472 - 53·[204963260862830472/53]=13 a53=53·13/(13+013)=53
И так далее по порядку можно и дальше до бесконечности вычислять члены последовательности (10). Причем все члены последовательности (10), которые не были вычислены, как и в случае использования формулы (13), имеют в качестве порядковых номеров n составные числа и соответственно равны нулю. При этом, как видно из приведенных примеров, из-за того, что k всегда будет меньше чем n-1, существенно уменьшается объем необходимых вычислений.
Кроме этого с ростом разности m арифметических прогрессий k будет равно единице для более больших чисел n. То есть формулы (13) и (16) будут фактически выполнять метод пробных делений тестирования чисел на простату, что, как утверждалось в статье [5], является наиболее рациональным при составлении формул для простых чисел. При этом алгоритм метода пробных делений изменяется и тоже становится более эффективным. Появляется возможность отказаться от использования в ходе выполнения вычислительных операций слишком больших чисел d. Подробнее этот вопрос будет рассмотрен в следующей статье [6].
Возможность отказа от вычисления степеней в формулах простых чисел также следует из того обстоятельства, что малая теорема Ферма является частным случаем алгоритма Евклида для нахождения наибольшего общего делителя [2]. Так как малая теорема Ферма фактически предусматривает нахождение равного единице наибольшего общего делителя числа dр-1 и простого числа р НОД(dр-1, р)=1 за один цикл алгоритма Евклида. Вообще алгоритм Евклида всегда установит, что НОД(v, р)=1 не только для dр-1, но и для любого случайного числа v не равного единице и не кратного р, но только обычно более чем за выполнение одного цикла алгоритма. Малая теорема Ферма утверждает, что этот результат получается всегда за один цикл при использовании числа dр-1, но к сожалению в случае псевдопростых чисел р НОД(dр-1, р) тоже будет равен единице. Однако установлено значение числа d, при котором НОД(dр-1, р)=1 исключительно только для простых чисел р. И в случае использования таких значений числа d нет необходимости вычислять dр-1, так как исключительно только для любого простого числа р будет НОД(dр-1, р)=НОД(d, р)=1. Поэтому формулы для последовательного вычисления простых чисел на основе малой теоремы Ферма, могут быть модифицированы путем отказа от возведения в какую либо степень числа d и непосредственного использования алгоритма Евклида.
Таким образом, можно получить тривиальную рекуррентную формулу (17) для последовательного вычисления членов ряда (10), которая будет также более эффективна, чем формулы (13) и (16).
a1 = 0, an = n·0НОД(d, n)-1, (17)
где d = П1n-1(an-1+0^an-1) – данное выражение фактически представляет собой произведение всех простых членов an последовательности (10) от a2 = 2 до an-1 включительно.
Далее приведен пример вычисления при помощи формулы (17) по порядку всех членов последовательности (10) начиная со второго члена.
n = 2 d = 1·(0 + 00) = 1 НОД(1, 2)-1=0 a2 = 2·00 = 2
n = 3 d = 1·(2 + 02) = 2 НОД(2, 3)-1=0 a3 = 3·00 = 3
n = 4 d = 2·(3 + 03) = 6 НОД(6, 4)-1=1 a4 = 4·01 = 0
n = 5 d = 6·(0 + 00) = 6 НОД(6, 5)-1=0 a5 = 5·00 = 5
n = 6 d = 6·(5 + 05) = 30 НОД(30, 6)-1=5 a6 = 6·05 = 0
n = 7 d = 30·(0 + 00) = 30 НОД(30, 7)-1=0 a7 = 7·00 = 7
n = 8 d = 30·(7 + 07) = 210 НОД(210, 8)-1=1 a8 = 8·01 = 0
n = 9 d = 210·(0 + 00) = 210 НОД(210, 9)-1=2 a9 = 9·02 = 0
n = 10 d = 210·(0 + 00) = 210 НОД(210, 10)-1=9 a10 = 10·09 = 0
n = 11 d = 210·(0 + 00) = 210 НОД(210, 11)-1=0 a11 = 11·00 = 11
n = 12 d = 210·(11 + 011) = 2310 НОД(2310, 12)-1=5 a12 = 12·05 = 0
n = 13 d = 2310·(0 + 00) = 2310 НОД(2310, 13)-1=0 a13 = 13·00 = 13
n = 14 d = 2310·(13 + 013) = 30030 НОД(30030, 14)-1=13 a14 = 14·013 = 0
n = 15 d = 30030·(0 + 00) = 30030 НОД(30030, 15)-1=14 a15 = 15·014 = 0
n = 16 d = 30030·(0 + 00) = 30030 НОД(30030, 16)-1=1 a16 = 16·01 = 0
n = 17 d = 30030·(0 + 00) = 30030 НОД(30030, 17)-1=0 a17 = 17·00 = 17
n = 18 d = 30030·(17 + 017) = 510510 НОД(510510, 18)-1=5 a18 = 18·05 = 0
n = 19 d = 510510·(0 + 00) = 510510 НОД(510510, 19)-1=0 a19 = 19·00 = 19
n = 20 d = 510510·(19 + 019) = 9699690 НОД(9699690, 20)-1=9 a20 = 20·09 = 0
n = 21 d = 9699690·(0 + 00) = 9699690 НОД(9699690, 21)-1=20 a21 = 21·020 = 0
n = 22 d = 9699690·(0 + 00) = 9699690 НОД(9699690, 22)-1=21 a22 = 22·021 = 0
n = 23 d = 9699690·(0 + 00) = 9699690 НОД(9699690, 23)-1=0 a23 = 23·00 = 23
Очевидно, что продолжать вычисление по формуле (17) членов последовательности (10) можно бесконечно и при этом формула (17), как и формулы (13) и (16), всегда без ошибок будет возвращать простые числа, а вместо составных чисел – нули. Такой результат будет получаться всегда по тем же причинам, что и в формуле (13), но зато при выполнении существенно меньшего объема вычислений.
В целях дальнейшего сокращения объемов вычислений формулу (17) можно использовать совместно с арифметическими прогрессиями. При этом правила их совместного использования почти не будут отличаться от выше приведенных правил совместного использования формулы (13) и арифметических прогрессий.
Также необходимо обратить внимание на то, что все сказанное в настоящей статье относится к эффективности вычисления простых чисел на компьютере чисто числовыми методами. Однако существуют нечисловые методы тестирования чисел на простоту и выполнения факторизации чисел, у которых и эффективность будет иной, но чтобы не уходить в сторону от рассматриваемого в статье вопроса про них сейчас говориться не будет.
Таким образом, если в статье [5] было установлено наличие функциональной связи между числами натурального ряда и отдельными простыми числами, то формулы (13), (16) и (17) показали принципиальную возможность последовательного вычисления всех, без исключения, простых чисел в натуральном ряду. И тем самым преобразования последовательности натуральных чисел в последовательность чисел (10).
Кроме этого формулы (13), (16) и (17) позволяют непрерывно вычислять по порядку простые числа в течение неограниченного времени в отличие от алгоритмов просеивания простых чисел, которые делают это только до заранее выбранного максимального числа. А так же позволяют дополнительно вычислять произведение всех простых чисел d.
Октябрь 2022 года.
Литература:
1. В.А. Гусев, А.Г. Мордкович. Математика: Справ. материалы. - М.: Просвещение, 1988. – 416 с.
2. Р. Крэндалл, К. Померанс. Простые числа: Криптографические и вычислительные аспекты. Пер. с англ. / Под ред. В.Н.
Чубарикова. – М.: УРСС: Книжный дом «ЛИБРОКОМ», 2011. – 664 с. - ISBN 978-5-453-00016-6, ISBN 978-5-397-02060-2.
3. А.А. Бухштаб. Теория чисел. – М.: Просвещение, 1966. – 384 с.
4. О.Н. Василенко. Теоретико-числовые алгоритмы в криптографии. – М.: МЦНМО, 2003. – 328 с. - ISBN 5-94057-103-4.
5. А.М. Белов. Теория чисел: простые числа и универсальное уравнение [Электронный ресурс]. - Интернет адрес: http://stob2.narod.ru/2s.htm, 2003.
6. А.М. Белов. Детерминированный тест простоты Ферма и эффективный алгоритм факторизации больших чисел [Электронный ресурс]. - Интернет адрес: http://stob2.narod.ru/41s.htm, 2022.