Исчисление простых чисел

[CherkasovMY]

Простыми числами называют такие натуральные числа, которые делятся только на единицу и само себя. И … других свойств простых чисел до сих пор не найдено. Правда, Евклид доказал, что множество таких чисел — бесконечно, а Эратосфен предложил способ нахождения простых чисел среди натуральных, известный как «решето Эратосфена». Но природа возникновения их так и остается непонятной. Их — то густо, то пусто, и даже сравнивают с сорной травой, которая растет, где хочет и как хочет, не подчиняясь ни какому закону распределения. Гаусс эмпирическим способом обнаружил, что соотношение вида: $ \frac{A_n} {n}$ : $ \frac{1} { \ln(n)}$ , где $A_n$ — число простых чисел, меньших $n$, стремится к $1$ при возрастании $n$. По сути, математики, отчаявшись найти формулу простых чисел, переключились на исследование распределения их в «среднем». Институт математики Клэя (США) даже в качестве одной из семи математических проблем третьего тысячелетия выдвинул вопрос о гипотезе Римана о количестве простых чисел.

Цитата:

«В итоге можно сказать, что поиски элементарных формул, дающих только простые числа, оказались тщетными. Ещё менее обнадеживающей следует считать задачу нахождения такой формулы, которая давала бы только простые числа и при том все простые числа» [Курант Р., Роббинс Г. Что такое математика? — 2001, с. 54].

Однако существует способ вычисления простых чисел, основанный на общеизвестном свойстве, которое гласит: если числа $B$ и $C$ не содержат общих множителей, то число $A = B+C $ будет простым по отношению к ним. Это свойство можно записать в более общем виде: $A = \abs(B \pm C)$, замена знака $«+»$ на $« \pm»$ не изменяет этого свойства и, если число $C$ превосходит число $B$, то рассматривается абсолютная величина. Теперь дадим более точную формулировку: «если числа $B$ и $C$ не содержат общих множителей, то числа вида $A = \abs(B \pm C)$ являются простыми по отношению ко всем множителям, входящим как в число $B$, так и в число $C$». Поэтому, если нам известны первые $n$ простых чисел $P_1, …, P_n$, то, представив число $B$ в виде произведения некоторых из них, а число $C$ как произведение остальных, тогда числа указанного вида будут простыми, при условии, что $A < (P_n+2)^2$. Возьмем пять первых простых числа $1, 2, 3, 5, 7$ — тогда: $abs(1\cdot2\cdot3\cdot5 \pm 7) = 37; 23$ — простые; $abs(3\cdot7 \pm 2\cdot5) = 31; 11$ также простые и т.д. Ограничение предназначено для исключения случаев, когда в результате вычислений получаются составные числа, содержащие множители, превосходящие $P_n$. Например, $abs(2\cdot3\cdot5\cdot7 \pm 1) = 211; 209$, но число $209 = 11\cdot19$ является составным.
Рассмотренный способ можно комбинировать с методом проверки, т.е. в вычислениях использовать только часть первых простых чисел, а результаты проверять на наличие в них, в качестве множителей, неиспользуемых простых чисел. Например, $abs(2\cdot5\cdot7 \pm 1) = 71; 69$, где $71$ — простое, а $69$ из рассмотрения исключается, т.к. содержит в качестве множителя простое число $3$.
Обратив особое внимание на то, что в свойстве говорится только о том, что числа $B$ и $C$ не должны содержать одинаковых множителей, приходим к выводу: в представлении числа $B$ любой множитель может входить многократно, это же относится и к числу $C$, т.е. их можно представлять в виде: $B = P_i^a \cdots P_j^b$, $C = P_k^c \cdots P_l^d$, где $a, b, c, d$ — натуральные числа. Например, $abs(2\cdot2\cdot2\cdot2\cdot3\cdot3 \pm 5\cdot7) = 107;37$, число $107$, хотя и является простым, из рассмотрения исключается в связи с ограничением.
Теперь, если найдены числа вида $abs(P_i^a\cdots P_j^b \pm 1)$, которые удовлетворяют указанному условию и не содержат множителей, не входящих в это представление, то такие числа называют простыми числами-близнецами, если вида $abs(P_i^a\cdots P_j^b \pm 2)$ — двоюродными простыми числами, $abs(P_i^a\cdots P_j^b \pm 3)$ — троюродными и т.д.
Фактически это объясняет природу простых чисел, которые появляются не сами по себе, а все предыдущие порождают последующие. Тем самым снимается актуальность проблемы поиска закона их распределения, ведь мало кого интересует вопрос о количестве чисел Фибоначчи, не превосходящих определенное число, т.к. есть формула их вычисления. Определенным недостатком рассмотренного способа является то, что при увеличении количества используемых первых простых чисел существенно возрастает объем вычислений, к тому же многие простые числа можно получать различными комбинациями.
Формула, используемая в вычислениях, позволила обнаружить, что все простые числа в той или иной степени являются "братьями".

[kotenok gav]

CherkasovMY в сообщении #1238311 писал(а):

простым по отношению к ним

Что это означает?

[worm2]

CherkasovMY писал(а):

все предыдущие порождают последующие

Это понятно и так: каждое простое число, большее 2, является минимальным из чисел, не делящихся ни на одно из множества предыдущих простых чисел.
Ваша идея понятна. Вы хотите по множеству первых $n$ простых чисел $P_n=\{2, 3, 5, \dots, p_n\}$ строить его продолжение по формуле $p_j=|B\pm C|$, где $B$ и $C$ являются всевозможными произведениями множителей из $P_n$, причём множители $B$ и $C$ не пересекаются. Если объединение этих множителей не составляет всё $P_n$ целиком, то предлагается дополнительно проверять делимость на отсутствующие простые. Ну и наконец предлагается из всевозможных таких сумм исключать те, которые будут равны 1, либо превышать $p_n^2$. Я ничего не пропустил?
Не скажу, что идея совсем уж тривиальна. Но, в общем, лежит на поверхности.
Вы утверждаете, что множество полученных таким образом чисел, будет в точности совпадать со множеством простых чисел, больших $p_n$, но меньших $p_n^2$. Или не утверждаете? Если нет, то в Вашем сообщении вообще есть какие-то содержательные утверждения? Если да, то это утверждение нуждается в доказательстве. Если вдруг получится его доказать, то я, пожалуй, готов признать это выдающимся достижением, а так... Попробуйте хотя бы для $p_{10}=29$ предъявить все формулы такого вида, выдающие все 136 простых чисел от 31 до 839. Возможно, эта попытка охладит Ваш энтузиазм.
Докладываю также, что известна формула, всегда дающая либо простые, либо отрицательные числа. Её можно найти, например, в статье Википедии "Простое число" в параграфе "Формулы для нахождения простых чисел": вот.

[atlakatl]

worm2 в сообщении #1238328 писал(а):

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

Только ни одного простого числа из этой формулы не известно. Так что формула чисто декоративная. Есть, конечно, у неё приложения, но генерация простых чисел не её конёк.

[Someone]

CherkasovMY в сообщении #1238311 писал(а):

Поэтому, если нам известны первые $n$ простых чисел $P_1, …, P_n$, то, представив число $B$ в виде произведения некоторых из них, а число $C$ как произведение остальных, тогда числа указанного вида будут простыми, при условии, что $A < (P_n+2)^2$.

Б. А. Кордемский. Математическая смекалка. Государственное издательство технико-теоретической литературы. Москва, 1957. (Четвёртое издание.)
369. Ещё один способ получения простых чисел.

Цитата:

Возьмём $1$ и любое количество $n$ первых простых чисел. Все эти числа произвольным образом распределим на $2$ группы. Перемножим числа каждой группы; образуется два произведения. Если сумма или разность этих произведений даст число $N$, меньшее, чем квадрат $(n+1)$-го простого числа, то $N$ — простое число.

Эта книжка предназначалась для школьников разного возраста. Я с ней познакомился, помнится, в четвёртом классе.

[atlakatl]

Someone
Повторение буквальное. На отличие фантазии не хватило. Всё уже украдено до нас. (c)

[CherkasovMY]

worm2 в сообщении #1238328 писал(а):

Попробуйте хотя бы для $p_{10}=29$ предъявить все формулы такого вида, выдающие все 136 простых чисел от 31 до 839. Возможно, эта попытка охладит Ваш энтузиазм.

Для того, чтобы найти комбинацию простых чисел, дающую какое-нибудь заданное простое, можно вместо строгого выражения $\left\lvert A=B\pm C\right\rvert$ использовать менее строгое: $\left\lvert A=B+/-C\right\rvert$. Тогда, взяв два произвольных числа, сумма или разность которых равна этому простому, и разложив их на простые множители, получим требуемую комбинацию. Здесь следует отметить тот факт, что количество вариантов представления в виде суммы двух — ограничено, а в виде разности — безгранично.
Теперь приведу по одному примеру комбинации простых для каждого простого от $31$ до $839$. Перед каждой группой примеров указывается совокупность используемых простых чисел.
$\{1;2;3;5\}$

$ 1. (31;29)=2\cdot3\cdot5\pm 1$
$ 2. (37;13)=5\cdot5\pm 2\cdot2\cdot3$
$ 3. (41;31)=2\cdot2\cdot3\cdot3\pm 5$
$ 4. (43;37)=2\cdot2\cdot2\cdot5\pm 3$
$ 5. (47;17)=2\cdot2\cdot2\cdot2\cdot2\pm 3\cdot5$

$\{1;2;3;5;7\}$

$ 6. (53;17)=5\cdot7\pm 23\cdot3$
$ 7. (59;31)=3\cdot3\cdot5\pm 2\cdot7$
$ 8. (61;19)=2\cdot2\cdot2\cdot5\pm 3\cdot7$
$ 9. (67;53)=2\cdot2\cdot3\cdot5\pm 7$
$10. (71;41)=2\cdot2\cdot2\cdot7\pm 3\cdot5$
$11. (73;67)=2\cdot5\cdot7\pm 3$
$12. (79;61)=2\cdot5\cdot7\pm 3$
$13. (83;43)=3\cdot3\cdot7\pm 2\cdot2\cdot5$
$14. (89;79)=2\cdot2\cdot3\cdot7\pm 5$
$15. (97;43)=2\cdot5\cdot7\pm 3\cdot3\cdot3$
$16. (101;59)=2\cdot2\cdot2\cdot2\cdot5\pm 3\cdot7$
$17. (103;47)=3\cdot5\cdot5\pm 2\cdot2\cdot7$
$18. (107;37)=2\cdot2\cdot2\cdot3\cdot3\pm 5\cdot7$
$19. (109;101)=3\cdot5\cdot7\pm 2\cdot2$
$20. (113;97)=3\cdot5\cdot7\pm 2\cdot2\cdot2$

$\{1;2;3;5;7;11\}$

$21. (127;83)=3\cdot5\cdot7\pm 2\cdot11$
$22. (131;89)=2\cdot5\cdot11\pm 3\cdot7$
$23. (137;17)=7\cdot11\pm 2\cdot2\cdot3\cdot5$
$24. (139;29)=2\cdot2\cdot3\cdot7\pm 5\cdot11$
$25. (149;61)=3\cdot5\cdot7\pm 2\cdot2\cdot11$
$26. (151;101)=2\cdot3\cdot3\cdot7\pm 5\cdot5$
$27. (157;67)=2\cdot2\cdot2\cdot2\cdot7\pm 3\cdot3\cdot5$
$28. (163;107)=3\cdot3\cdot3\cdot5\pm 2\cdot2\cdot7$
$29. (167;127)=3\cdot7\cdot7\pm 2\cdot2\cdot5$

$\{1;2;3;5;7;11;13\}$

$30. (173;163)=2\cdot3\cdot3\cdot3\cdot3\pm 5$
$31. (173;103)=2\cdot2\cdot5\cdot7\pm 3\cdot11$
$32. (179;101)=2\cdot2\cdot5\cdot7\pm 3\cdot13$
$33. (181;71)=2\cdot3\cdot3\cdot7\pm 5\cdot11$

$\cdots$
Полагаю, что продолжать далее список примеров не имеет смысла, т.к. задача нахождения подобных комбинаций решается легко. Легко, если обратить внимание на заключительные слова темы:

CherkasovMY в сообщении #1238311 писал(а):

все простые числа в той или иной степени являются "братьями"

Уточнение: Все, кроме $2$.
Число $(P_j-P_i)$ лежит строго посредине между ними и определяет степень их «родства». Поэтому, числа $P_j$ и $P_i$ можно представить в виде: $[P_i+(P_j-P_i)/2]\pm [(P_j-P_i)/2]$ и, разложив числа $P_i+(P_j-P_i)/2$ и $(P_j-P_i)/2$ на простые множители, получим искомую комбинацию.
Таким образом, имея число $P_n$, можно его рассматривать попарно с каждым простым, не превосходящим его, получая $(n-)$ вариантов.
Рассмотрим, например, $P_1_5=47$, получив при этом $14$ вариантов:

$1. (47;1)=2\cdot2\cdot2\cdot3\pm 23$
$2. (47;3)=3\cdot3\cdot3\pm 5\cdot5$
$3. (47;5)=2\cdot13\pm 3\cdot7$
$4. (47;7)=3\cdot3\cdot3\pm 2\cdot2\cdot5$
$5. (47;11)=29\pm 2\cdot3\cdot3$
$6. (47;13)=2\cdot3\cdot5\pm 17$
$7. (47;17)=2\cdot2\cdot2\cdot2\cdot2\pm 3\cdot5$
$8. (47;19)=3\cdot11\pm 2\cdot7$
$9. (47;23)=5\cdot7\pm 2\cdot2\cdot3$
$10. (47;29)=2\cdot19\pm 3\cdot3$
$11. (47;31)=3\cdot19\pm 2\cdot2\cdot2$
$12. (47;37)=2\cdot3\cdot7\pm 5$
$13. (47;41)=2\cdot2\cdot11\pm 3$
$14. (47;43)=3\cdot3\cdot5\pm 2$

Если рассматривать число $P_n$ попарно с каждым простым, превосходящим его, получим бесконечное количество вариантов.

[Andrey A]

CherkasovMY в сообщении #1240495 писал(а):

все простые числа в той или иной степени являются "братьями"

$41$ и $43$ братья? Ведь они близнецы, но $\dfrac{41+43}{2}=2\cdot 3\cdot 7.$ Пятерка отсутствует, или это не важно? Тогда конечно братья, но подлость в том, что и для пары составных полусумма и полуразность имеет свои канонические разложения. Тогда все составные - сёстры.

[vorvalm]

CherkasovMY в сообщении #1240495 писал(а):

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

На каком основании такое заключение7

[worm2]

CherkasovMY в сообщении #1240495 писал(а):

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

Моя ошибка, слишком лёгкую задачу задал, вот из-за этого замечания:

я в сообщении #1238328 писал(а):

Если объединение этих множителей не составляет всё $P_n$ целиком, то предлагается дополнительно проверять делимость на отсутствующие простые.

Так, действительно, любое число, большее 23 (не только простое), легко получить, подобрав его как сумму слагаемых, не имеющих в разложении простых, больших квадратного корня из него. На это даже задача была, вот: http://dxdy.ru/post1013350.html. Но в типичном случае разложение (не только суммы, а, конечно, и разности тоже) будет содержать очень немного сомножителей, и придётся проверять делимость на остальные (почти все) простые вручную. В такой постановке ничего интересного нет.
Интереснее, когда мы требуем, чтобы объединение этих множителей составляло всё $P_n$ целиком. Я писал программу, перебирающие $|A-B| < 31^2$, где $A$ и $B$ — взаимно простые числа, делители которых в совокупности дают все простые числа от 2 до 29. Например: $5\cdot 7^2\cdot 13\cdot 19\cdot 29-2^3\cdot 3\cdot 11\cdot 17^2\cdot 23 = 127$. Понятно, что таких вариантов бесконечное множество, и в программе мне как-то пришлось ограничивать круг поиска. Так вот, за полчаса перебора разных вариантов нашлось несколько простых, но ни одного, меньшего 100. Каким будет множество таких чисел, если рассмотреть все (бесконечное множество) варианты — это очень непростой вопрос, я подозреваю, что на сегодняшний момент это открытая проблема. Если же ещё увеличить простое число $p$ (например, до 101), то проблемой будет найти даже одну подходящую разность (меньшую $103^2$.)

[Someone]

Весь смысл затеи — в том, что если число $A<p_{n+1}^2$ представлено в виде $A=\lvert B\pm C\rvert$, где числа $B$ и $C$ взаимно простые, а их произведение $BC$ делится на все простые числа $2,3,\ldots,p_n$, то число $A$ простое, и никаких дополнительных проверок не требуется. Если $BC$ делится не на все простые, меньшие $p_{n+1}$, то $A$ не обязано быть простым, и затея теряет смысл.

Подбирать такого рода представления вида $A=B\pm C$, где $BC$ делится на все заданные простые в заданных степенях, для выбранного числа $A$, не очень трудно. Пусть $\mathscr P=\{P_1,P_2,\ldots,P_n\}$ — множество тех (попарно различных) простых в требуемых степенях, на которые должно делиться произведение $BC$. Выберем любое подмножество $\mathscr Q\subseteq\mathscr P$ и положим $Q=\prod\mathscr Q$ и $R=\prod(\mathscr P\setminus\mathscr Q)$ (имеются в виду произведения всех элементов указанных множеств; если множество пустое, произведение считаем равным $1$). Так как числа $Q$ и $R$ взаимно простые, диофантово уравнение $Qx+Ry=A$ имеет бесконечное множество решений. Обозначая $B$ то из чисел $Qx$ и $Ry$, которое положительно, а $C$ — модуль оставшегося, получим $A=B\pm C$.

Например, взяв $Q=5\cdot 7\cdot 13\cdot 19\cdot 29$ и $R=2\cdot 3\cdot 11\cdot 17\cdot 23$, для $A=127$ найдём $x=7+25806t$ и $y=-68-250705t$, где $t$ — любое целое число. При $t=0$ получим $B=(5\cdot 7\cdot 13\cdot 19\cdot 29)\cdot 7=5\cdot 7^2\cdot 13\cdot 19\cdot 29$ и $C=(2\cdot 3\cdot 11\cdot 17\cdot 23)\cdot 68=2^3\cdot 3\cdot 11\cdot 17^2\cdot 23$, что даёт $127=5\cdot 7^2\cdot 13\cdot 19\cdot 29-2^3\cdot 3\cdot 11\cdot 17^2\cdot 23$.

Аналогично при тех же $Q$ и $R$ для $A=53$ находим $x=20729+25806t$ и $y=-201382-250705t$, что при $t=-1$ даёт $53=2\cdot 3^2\cdot 11\cdot 17\cdot 23\cdot 41\cdot 401-5\cdot 7\cdot 13\cdot 19\cdot 29\cdot 5077$.

Проблемой же является нахождение таких $B$ и $C$, произведение которых полностью разлагается в произведение заданных простых с условием, что все они входят в разложение.

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

[CherkasovMY]

Как говаривал профессор Али Иванович Кокорин (в 1970-х — 1980-х годах преподавал логику на матфаке Иркутского госуниверситета): "Не будем "засерать" доказательство". Основная цель темы: показать, что простые числа не "выскакивают как черт из табакерки", а подчиняются определенной закономерности, суть которой отражается выражением $A=\left\lvert B\pm C\right\rvert$. Поэтому, обсуждать следует только один вопрос: существует ли простое число $P_?\ne \left\lvert B\pm C\right\rvert$?

[vorvalm]

vorvalm в сообщении #1240520 писал(а):

CherkasovMY в сообщении #1240495 писал(а):

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

На каком основании такое заключение ?

Повторно.

[Someone]

CherkasovMY в сообщении #1240704 писал(а):

Поэтому, обсуждать следует только один вопрос: существует ли простое число $P_?\ne \left\lvert B\pm C\right\rvert$?

А я именно это и обсуждаю. Вы не заметили?
Ответ на ваш вопрос может существенно зависеть от ограничений на $P$, $B$, $C$. Эти ограничения у Вас меняются по ходу дела. Когда Вы точно сформулируете все ограничения, обсуждение сможет принять более конкретный вид.

[Dmitriy40]

А мне вот дополнительно интересна и сложность алгоритма. Пока что для проверки одного единственного числа $A$ на простоту никакого выигрыша не вижу: что число $A$ проверять на остатки на $2,3,\dots,p_n$, что произведение $BC$ проверять на те же самые $2,3,\dots,p_n$ (это даже и хуже - числа длиннее). Это даже если не брать более быстрые методы.

Для генерации всех простых в некотором диапазоне $(<p_{n+1}^2)$ сложность вообще непонятна, не понял сложность решения диофантового уравнения и даже его составления, как бы там не вылезла квадратичность из-за перебора (степеней) по списку простых ...