Поиск простого числа по новому

[Dmitriy40]

Спасибо Someone за формулу для $M_n$, теперь оказалось возможным подсчитать средний выигрыш от использования формулы $p_n\#/2\pm2^m$ для поиска простых вместо последовательной проверки. Выигрыш есть и медленно растёт с увеличением $n$. Например для $n=2975$ с 11718 цифр до нахождения первого простого в среднем надо проверить 1470 чисел вместо 26980 (которые сократятся в лучшем случае до 5 тысяч исключением проверки кратных малым простым). А для $n=899769$ с количеством цифр уже более 6 млн, проверить надо почти 470 тысяч вместо почти 14 млн (сокращаемых лишь до 2.2 млн). О времени проверки даже одного числа умолчу.

[Побережный Александр]

Someone в сообщении #1318912 писал(а):

Можно оценить ожидаемое количество простых чисел в вашем методе. Как обычно, $p_n$ обозначает $n$-ое простое число.
При большом $n$ почти все числа вида $p_n\#/2\pm 2^m$, где $2^m<p_n\#/2$, расположены вблизи числа $p_n\#/2$.
Плотность множества простых чисел вблизи большого числа $A=p_n\#/2$ оценивается выражением $\frac 1{\ln A}$. Количество проверяемых Вами чисел оценивается выражением $2\log_2A$.
Все проверяемые числа лежат в множестве чисел, взаимно простых с $p_n\#$; плотность этого множества можно оценить как $d_n=\prod\limits_{k=1}^n\left(1-\frac 1{p_k}\right)$. Например, получаем $d_{1404}\approx 0{,}0599066$, $d_{2585}\approx 0{,}0558193$, $d_{3707}\approx 0{,}0536692$.
Поэтому ожидаемое количество простых чисел можно оценить выражением

$$M_n=\frac{2\log_2A}{d_n\ln A}=\frac 2{d_n\ln 2}.$$

Например, $M_{1404}\approx 48$, $M_{2585}\approx 52$, $M_{3707}\approx 54$ (результаты округлены до ближайшего целого).

Попробую оценить снизу количество простых.
По неравенству Чебышёва $0,92(\frac{A}{\ln(A)})<\pi(A)<1,11(\frac{A}{\ln(A)})$
Максимальная плотность простых чисел вблизи числа $A=p_n\#/2$ оценивается выражением $\frac{1,11}{\ln(A)}$
Отклонение от ожидаемого выражения оценивается выражением $\log_2A$
Максимальное отклонение от ожидаемого будет выражаться $\Delta M_n=\frac{1,11}{d_n\ln{2}}$
Следовательно, ожидаемое количество простых чисел будет лежать в интервале $[M_n-\Delta M_n;M_n+\Delta M_n]$
Другими словами $[\frac{2-1,11}{d_n\ln{2}};\frac{2+1,11}{d_n\ln{2}}]$
Нижняя граница всегда больше единицы. Соответственно, в праймориале простое число вида $p_n\#/2\pm2^m$ всегда найдется.

[Someone]

Побережный Александр в сообщении #1319598 писал(а):

Максимальное отклонение от ожидаемого будет выражаться $\Delta M_n=\frac{1,11}{d_n\ln{2}}$

Не пройдёт. Если бы такие вещи доказывались подобными рассуждениями…

[Someone]

Затратив примерно $100$ часов, программа OpenPFGW закончила проверку $n=2585$, $1\leqslant m\leqslant 33222$. Найдено $55$ кандидатов в простые числа (прогнозировалось $52$). Файл со списком прилагается.

Dmitriy40 в сообщении #1318564 писал(а):

Для $n=3707$ проверены $m<1130$ за 9.5ч, ничего не найдено, надоело, закрыл.

Запустил проверку для $n=3707$. Спустя примерно $11{,}5$ часов было найдено псевдопростое число (по основанию $3$): $34703\#/2-2^{1420}$. Полная проверка для данного $n$, как ожидается, займёт примерно $400$ часов.

[Побережный Александр]

Someone, я вас поздравляю!
Вы попутно установили рекордный результат среди праймориальных простых чисел (7 место) и рекордный результат среди факториальных (12 место).

[Someone]

Это Вы про что? Подробнее, пожалуйста. Со ссылками, если таковые имеются.

[Побережный Александр]

http://primes.utm.edu/top20/page.php?id=5 - рекорды по праймориальным простым числам.
http://primes.utm.edu/top20/page.php?id=30 - рекорды по факториальным простым числам.

-- Пн июн 18, 2018 12:04:44 --

Ваше "скорее всего" простое число имеет $15000$ десятичных знаков.

[SpiderHulk]

(Оффтоп)

Разрешите задать вопрос: каково сейчас наибольшее простое число такое, что все простые числа меньшие его найдены?

[Someone]

Побережный Александр в сообщении #1320766 писал(а):

Ваше "скорее всего" простое число имеет $15000$ десятичных знаков.

Это: $34703\#/2-2^{1420}$? $15004$. Но оно не праймориальное и не факториальное. Первые имеют вид $n\#\pm 1$, вторые — вид $n!\pm 1$. Кроме того, имеющихся у меня вычислительных ресурсов не хватит, чтобы доказать, что оно простое, а не только псевдопростое (для праймориальных и факториальных чисел хватило бы, поскольку для таких чисел существуют эффективные тесты).

-- Пн июн 18, 2018 13:41:17 --

SpiderHulk в сообщении #1320768 писал(а):

(Оффтоп)

Разрешите задать вопрос: каково сейчас наибольшее простое число такое, что все простые числа меньшие его найдены?

Понятия не имею. И в каком смысле "известны"? Имеется полный список в печатном виде или в виде набора файлов на каком-нибудь компьютерном носителе?
И для чего Вы хотите это знать? Чтобы взять самое большое число в этом списке и, запустив какой-нибудь пакет компьютерной математики, за ничтожную долю секунды побить этот рекорд? Например, Wolfram Mathematica:

Timing[NextPrime[10^50]]
{0.015600, 100000000000000000000000000000000000000000000000151}

Потом запустить PRIMO и за $0{,}02$ с получить сертификат простого числа. Файлы сюда не загрузились, поэтому их содержимое приведу в тексте.

(Входной файл: 10^50.in)

[Candidate]
N=100000000000000000000000000000000000000000000000151

(Отчёт о выполнении задачи: primo-B3E5F02D7CC7C.tr)

[PRIMO - Task Report]
Version=3.0.9
WebSite=http://www.ellipsa.eu/
Task=Certification
ID=B3E5F02D7CC7C
Created=06.18.2018 01:14:57 PM

[Common]
Path=D:\D\Programming\Primo 3.0.9\work\
Selected=1
Processed=1
Certified=1
Candidate #1=Certified, 0.02s

[Candidate #1]
Input=10^50.in
Report=primo-B3E5F02D7CC7C-001.cr
Output=primo-B3E5F02D7CC7C-001.out
Status=Candidate certified prime

(Отчёт о сертификации: primo-B3E5F02D7CC7C-001.cr)

[PRIMO - Certification Report]
Version=3.0.9
WebSite=http://www.ellipsa.eu/
ID=B3E5F02D7CC7C
Created=06.18.2018 01:14:57 PM
Certificate=D:\D\Programming\Primo 3.0.9\work\primo-B3E5F02D7CC7C-001.out
TestCount=8

[Backtrack]
Count=0

[1]
Type=1
Run=1
Gain=32

[2]
Type=3
Run=1
Gain=16
D=-3
H=1
G=1

[3]
Type=3
Run=1
Gain=20
D=-4
H=1
G=1

[4]
Type=1
Run=1
Gain=30

[5]
Type=1
Run=1
Gain=14

[6]
Type=1
Run=1
Gain=4

[7]
Type=3
Run=1
Gain=15
D=-3
H=1
G=1

[8]
Type=0
Run=1
Gain=36

(Сертификат: primo-B3E5F02D7CC7C-001.out)

[PRIMO - Primality Certificate]
Version=3.0.9
WebSite=http://www.ellipsa.eu/
Format=3
ID=B3E5F02D7CC7C
Created=06.18.2018 01:14:57 PM
TestCount=8
Status=Candidate certified prime

[Comments]
No comment in the input file

[Running Times]
Initialization=0.00s
1stPhase=0.01s
2ndPhase=0.01s
Total=0.02s

[Candidate]
File=D:\D\Programming\Primo 3.0.9\work\10^50.in
N$=446C3B15F9926687D2C40534FDB564000000000097
HexadecimalSize=42
DecimalSize=51
BinarySize=167

[1]
Type=1
S$=E0346076
R$=4E20481A8728DF37D5933642A6D1B6FF31
B$=2

[2]
Type=3
S$=106B1
R$=4C22D3141D8F14CDA9DED5997D3F85
A$=0
B$=-13881206A1CA37CDF564CD90A9B46DBFAD
T$=3

[3]
Type=3
S$=F02D2
R$=5126F45C0B8E726787E7BB981
A$=2
B$=0
T$=1

[4]
Type=1
S$=369AAE80
R$=17C76D7D644EA5C30F
B$=2

[5]
Type=1
S$=5D36
R$=414EDE905D3185
B$=2

[6]
Type=1
S$=C
R$=5713D36B26ECB
B$=2

[7]
Type=3
S$=8DC9
R$=9D38F973F
A$=0
B$=10
T$=2

[8]
Type=0

[Signature]
1$=6782DA2102C31C70770ACB0AA87BF9463205A4A7
2$=A495D6CC53173CE0A2E2ABE11C9E0AF0231DDF3D

[Dmitriy40]

SpiderHulk в сообщении #1320768 писал(а):

каково сейчас наибольшее простое число такое, что все простые числа меньшие его найдены?

Тут надо смотреть научные результаты, мне немного лень, потому опишу простой способ получить оценку снизу: посмотреть в вики интервалы между простыми, докуда они проверены и известны, значит все числа меньшие уже определены. В английской вики приведено число 15 570 628 755 536 096 243, плюс я где-то видел что проверены все числа до $2^{64}\approx 2\cdot10^{19}$. Ещё где-то видел о проверке всех простых до $10^{22}$ (но интервалы при этом не проверялись и в вики не вошли, тут кажется проверяли аппроксимацию функции количества простых), но совсем не уверен в точности цифры.
Если нужна более точная оценка - надо искать научные публикации.

Напомню, полный список нигде в интернете не получить (вероятно, я могу не знать как именно выкладывали результаты научные группы), он слишком велик (порядка 400 миллионов миллиардов простых чисел до $2^{64}$) и жалко места на серверах и трафика по сети. Ну и обычно быстрее его насчитать заново чем откуда-то скачивать. Для оценки скорости можно взять данные самой быстрой программы, она выдаёт простые числа около $10^{19}$ со скоростью миллиард простых чисел за 150 секунд (на 3.7ГГц процессоре в один поток). Перекачать по сети этот список надо скорость 20ГБ/150с, т.е. примерно гигабит в секунду, инет пока ещё почти у всех медленнее, а вот многопоточные (многоядерные) процессоры есть уже у всех, а уж про видеокарты совсем молчу.

[SpiderHulk]

Someone в сообщении #1320783 писал(а):

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

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

Dmitriy40 в сообщении #1320836 писал(а):

Ещё где-то видел о проверке всех простых до $10^{22}$

Спасибо

[Yadryara]

SpiderHulk
Можно действовать и по-другому. Есть способы находить Prime counting function($pi(n)$) аналитически. Значения $pi(n)$ уже найдены до $n=10^{27}$ включительно. Например, посмотрите ссылки к A006880.

Сможете найти $pi(n)$ для $n=10^{27}-100$ ? Если количество будет отличаться ровно на единицу, значит в этой сотне ровно одно простое число.

[Dmitriy40]

Yadryara в сообщении #1320854 писал(а):

Есть способы находить Prime counting function($pi(n)$) аналитически. Значения $pi(n)$ уже найдены до $n=10^{27}$ включительно.

Вот спасибо, значит я таки ошибся с порядком цифры, он не 22, а 27 (до $pi(n)$ в вики не добрался по ссылкам).

[ozheredov]

Someone в сообщении #1320783 писал(а):

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

А это противозаконно?

[Someone]

ozheredov в сообщении #1321017 писал(а):

А это противозаконно?

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

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