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

[Someone]

Можно оценить ожидаемое количество простых чисел в вашем методе. Как обычно, $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$ (результаты округлены до ближайшего целого).

Аналогично можно получить оценку количества простых чисел вида $p_n\#/2\pm P\cdot 2^m$, где $P$ — число, взаимно простое с $p_n\#/2$. Если обозначим $d'_P=\prod\limits_{p|P,p>2}\left(1-\frac 1p\right)$, где произведение берётся по всем простым делителям числа $P$, бо́льшим $2$ (а так как $P$ взаимно просто с $p_n\#/2$, то $p>p_n$), то оценку можно записать в виде

$$M_{n,P}=\frac 2{d_nd'_P\ln 2}\left(1-\frac{\ln P}{\ln(p_n\#/2)}\right).$$

Вчера написал скрипт для программы OpenPFGW, также известной как PrimeForm, для проверки чисел вида $p_n\#/2\pm 2^m$. Файл скрипта прилагается. Файл Data.txt должен содержать три числа $n$, $0$, $0$ по одному в каждой строчке. В процессе счёта этот файл используется для сохранения текущего состояния и нужен для возобновления расчётов в случае прерывания работы программы.
Как раз сейчас программа закончила проверку $n=1404$. Затраты времени — около 12 часов. Начало отчёта о тестировании выглядит так:

Цитата:

11699#/2-2^1 is composite: RES64: [217F4DB3F4E017F1] (1.3637s+0.0258s)
11699#/2+2^1 is composite: RES64: [F46EC537E9CA4FFB] (1.3061s+0.0092s)
11699#/2-2^2 is composite: RES64: [802633D72444380E] (1.7244s+0.0093s)
11699#/2+2^2 is composite: RES64: [B55A2979791690E2] (1.3070s+0.0094s)
11699#/2-2^3 is composite: RES64: [5411525AA66BAC78] (1.3076s+0.0093s)
11699#/2+2^3 is composite: RES64: [5B7F734CFD4AACE1] (1.3093s+0.0088s)
11699#/2-2^4 is composite: RES64: [EAFFA414F9CBBF6E] (1.3091s+0.0095s)
11699#/2+2^4 is composite: RES64: [78750E728B5326E2] (1.3172s+0.0092s)
11699#/2-2^5 is composite: RES64: [678DF03C29FB6474] (1.3059s+0.0091s)
11699#/2+2^5 is composite: RES64: [FD776A99E7C58331] (1.3085s+0.0090s)
…
11699#/2-2^36 is composite: RES64: [04E786736606B7FA] (1.3088s+0.0095s)
11699#/2+2^36 is composite: RES64: [C001C3D14B1E353C] (1.3135s+0.0124s)
11699#/2-2^37 is composite: RES64: [F06235679380B2F3] (1.3102s+0.0110s)
11699#/2+2^37 is 3-PRP! (1.3085s+0.0087s)
11699#/2-2^38 is composite: RES64: [1D91AEE3A6C3CA90] (1.3046s+0.0388s)
11699#/2+2^38 is composite: RES64: [83FF4D0F0DE43325] (1.3065s+0.0088s)

Объём файла — $2\,502\,907$ байт. Всего проверено $2\cdot 16621=33242$ числа. Обнаружено $43$ кандидата в простые числа. Список — в прилагаемом файле.

Добавление. 10/VII-2018 заменил файл Prim-pm-Exp.txt, так как обнаружил в нём две ошибки, которые, впрочем, не повлияли на результаты вычислений.

[Dmitriy40]

Хм, интересно сравнить скорость с PARI/GP для $n=1404$ (заодно проверил разницу в скорости двух разных тестов на простоту):

Используется синтаксис Text

? ispseudoprime(p+2^37)
%2 = 1
  ***   last result computed in 3,151 ms.
? ispseudoprime(p+2^37,1)
%3 = 1
  ***   last result computed in 890 ms.
? ispseudoprime(p+2^33)
%4 = 0
  ***   last result computed in 953 ms.
? ispseudoprime(p+2^33,1)
%5 = 0
  ***   last result computed in 905 ms.
? ?ispseudoprime
ispseudoprime(x,{flag}): true(1) if x is a strong pseudoprime, false(0) if not. If flag is 0 or omitted, use BPSW test, otherwise use strong Rabin-Miller test for flag randomly chosen bases.

Почему-то BPSW втрое медленнее, но лишь на простых ...
Выходит OpenPFGW на четверть быстрее BPSW и Rabin-Miller (с одним основанием) на составных числах (которых большинство).

Someone
Спасибо за оценку вероятностей.
Примечательно что $M_n$ растёт неадекватно длине чисел, т.е. среднее время проверки до первого простого растёт с ростом $n$ почти пропорционально $\ln p_n\#$.
Но ещё более примечательно и почти постоянство и величина $d_n$, это же получается уже с $p_n\#/2>25\cdot10^6\Rightarrow n>8$ такие числа будут встречаться чаще чем обычные с их $1/\ln(p_n\#/2)$? Тогда это очень даже интересно.

[Someone]

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

Выходит OpenPFGW на четверть быстрее BPSW и Rabin-Miller (с одним основанием) на составных числах (которых большинство).

Ну, OpenPFGW, всё-таки, специализированная программа, предназначенная для поиска чрезвычайно больших простых чисел (сотни тысяч и миллионы десятичных цифр). Там алгоритм умножения с помощью быстрого преобразования Фурье вылизывается уже много лет…

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

интересно сравнить скорость с PARI/GP

Кстати, у меня ваша программа не заработала. Точнее, она просто зациклилась. После прерывания значение переменной $m$ посмотреть не могу.

(Оффтоп)

Вложение:

PARI-1.gif [ 31.9 Кб | Просмотров: 0 ]

[Dmitriy40]

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

Кстати, у меня ваша программа не заработала.

Даже и не знаю что сказать. У меня работает (код вставил через буфер прямо из своего сообщения), даже проверил именно 2.6.1 x86 версию (вторая картинка):

Предлагаю проверить содержимое gprc.txt и временно переименовать его в что-нибудь левое чтобы он не подгружался при старте (у меня не подгружается ничего).

Сравнил скорость 2.9.5 (только что обновлённую) x86 и x64, с 2.9.3 x64 и с 2.6.1 x86 на следующем тестовом коде (время получал командой ## после завершения счёта):

p=10^15001+1;for(m=1,5,ispseudoprime(p+2^m))
2.9.5 x64: 29s
2.9.3 x64: 29s
2.9.5 x32: 98s
2.6.1 x32: 102s

Во всех случаях выполнение оставалось однопоточным. Любая x86/x32 версия страшно тормозная.

-- 12.06.2018, 00:05 --

Для более автоматизированного измерения времени можно поправить код до такого (нужно именно два вызова):

gettime();p=10^15001+1;for(m=1,5,ispseudoprime(p+2^m));gettime()

Время будет выведено в мс.

-- 12.06.2018, 00:11 --

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

После прерывания значение переменной $m$ посмотреть не могу.

Код у меня не слишком дружелюбный пользователю, удобнее смотреть сразу logint(m,2) - т.е. степень двойки. Стрелкой вверх команда после первого раза легко вызывается из истории.

[Someone]

У меня версия 2.6.1. Ваш тестовый код отработал нормально: " *** last result computed in 4min, 31,219 ms."
Чувствую, надо обновить.
С предыдущим кодом пока не разобрался. Он у меня работать не хочет. Если учесть, что до сих пор я использовал PARI/GP как калькулятор для подсчёта квартплаты, ничего удивительного в этом нет.

[Andrey A]

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

$p_n\#/2\pm2^m$

Я извиняюсь, почему такое избирательное отношение к двойке? Почему не $p_n\#/3\pm3^m$ ? И вообще, если пара вз. простых $a,b$ такова, что в каноническом разложении $ab$ содержатся все простые от $p_1=2$ до $p_n$, то $ab$ и $c=\left | a \pm b \right |$ также вз. просты. Если при этом $c<(p_n+2)^2$, то $c$ простое. Тема проигрывает, как только возникает необходимость проверок (ИМХО). Попутный вопрос: могут ли быть получены таким способом все простые $<(p_n+2)^2$ ? В случае $n=2$ могут:
$2+3=5,\ 2^2+3=7,\ 2+3^2=11,\ 2^2+3^2=13,\ 2^3+3^2=17, 2^4+3=19,\ \left | 2^2-3^3 \right |=23$. Исключив сам $(p_n+2)^2$, можно повысить потолок до $(p_n+3)^2-1$ :
$2+3^3=29,\ 2^2+3^3=31.$

[Andrey A]

(Оффтоп)

$n=3$
$2^2\cdot 3+5^2=37,\ 2^2\cdot 3^2+5=41,\ 2\cdot 3^2+5^2=43, 2^5+3\cdot 5=47,\ 2\cdot 5^2+3=53,\ 2\cdot 5^2+3^2=59,\ 2^2\cdot 3^2+5^2=61.$

$n=4$
$2^2\cdot 3\cdot 5+7=67,\ 2^2\cdot 3^2+5\cdot 7=71,\ 3^2\cdot 5+2^2\cdot 7=73,$ $2\cdot 3\cdot 5 +7^2=79,\ 2^2\cdot 5+3^2\cdot 7=83,\ 3\cdot 5^2+2\cdot 7=89,\ 2\cdot 3^2\cdot 5+7=97.$

[vorvalm]

Andrey A
Вы открываете "Америку". Давно известно, что вычеты ПСВ (приведенная система вычетов)
определяются по формуле

$a_x=\mid\prod p_t^{\alpha_t}\pm\prod p_s^{\beta_s}\mid<p_r\#=\prod p_t\cdot\prod p_s$

[Andrey A]

(Оффтоп)

Я тут не претендую на открытие. Давайте воздержимся от off topic.

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

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

Поэтому ожидаемое количество простых чисел можно оценить выражением

$$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$ (результаты округлены до ближайшего целого).

Уважаемый Someone, спасибо за приведенную оценку! Интересно, по вашей оценке с увеличением праймориала будет расти и количество простых. Можно ли утверждать на основании этого, что в любом праймориале всегда будут простые вида $p_n\#/2\pm2^m$?

Andrey A в сообщении #1319210 писал(а):

Я извиняюсь, почему такое избирательное отношение к двойке? Почему не $p_n\#/3\pm3^m$ ?

Никто не мешает рассматривать и такие комбинации. Но я исходил из того, что все числа взаимно простые с праймориалом расположены симметрично относительно середины праймориала. Если праймориал это $p_n\#$, то середина праймориала будет $p_n\#/2$. Вот почему появляется двойка.

[Someone]

Andrey A в сообщении #1319210 писал(а):

Я извиняюсь, почему такое избирательное отношение к двойке? Почему не $p_n\#/3\pm3^m$ ?

Ну, видите ли, Побережный Александр заинтересовался именно этим выражением, а не вашим. Ведь можно запросто придумать тьму всяких выражений и искать простые числа соответствующего вида.
Примеры.
1) Зададим целое число $a_0$ и рассмотрим последовательность, определяемую рекуррентной формулой $a_n=n!-a_{n-1}$.
При $a_0=0$ получается знакочередующаяся сумма факториалов. В пределах $n<6305$ простые числа получаются при $n\in\{3,4,5,6,7,8,10,15,19,41,59,61,105,160,661,2653,3069,3943,4053,4998\}$ (последние $5$ не проверены; десятичная запись $a_{2653}$ имеет $7934$ цифры). Эта проверка возможна, если использовать программу PRIMO, но требует очень много времени.

2) Рассмотреть простые числа видов $(186624n^8-1)^9-(559872n^9-6n)^8$ и $(186624n^8+1)^9-(559872n^9+6n)^8$. Эти формы имеют то преимущество, что если известно полное разложение числа $n$ на простые множители, то программа OpenPFGW может проверить простоту этих чисел за приемлемое время (во много раз быстрее, чем PRIMO). Самое большое известное мне простое число такого вида равно $(186624(1766!/1457!)^8 - 1)^9 - (559872(1766!/1457!)^9 - 6(1766!/1457!))^8$ ($71391$ цифр в десятичной записи). Поиск таких простых чисел затруднён тем, что никто не удосужился написать эффективную просеивающую программу для таких чисел.

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

Можно ли утверждать на основании этого, что в любом праймориале всегда будут простые вида $p_n\#/2\pm2^m$?

К сожалению, нельзя. Это не оценка снизу. Это оценка ожидаемого количества. Но при каком-нибудь $n$ может крупно не повезти. Например, при $n=1404$ получилось $M_{1404}\approx 48$, а фактически таких простых чисел оказалось $43$.

[Dmitriy40]

График количества простых в зависимости от $n=2..200$:

Рост конечно заметен, но очень медленный, да и разброс тоже вроде бы растёт. Так что пока не вижу причин иметь ненулевое минимальное значение где-то дальше.
Сами данные:

Используется синтаксис Text

n=2, m=1..1: 1
n=3, m=1..3: 6
n=4, m=1..6: 10
n=5, m=1..10: 12
n=6, m=1..13: 12
n=7, m=1..17: 16
n=8, m=1..22: 13
n=9, m=1..26: 18
n=10, m=1..31: 20
n=11, m=1..36: 23
n=12, m=1..41: 22
n=13, m=1..47: 30
n=14, m=1..52: 16
n=15, m=1..58: 28
n=16, m=1..63: 21
n=17, m=1..69: 26
n=18, m=1..75: 22
n=19, m=1..81: 19
n=20, m=1..87: 14
n=21, m=1..94: 18
n=22, m=1..100: 17
n=23, m=1..106: 20
n=24, m=1..113: 21
n=25, m=1..119: 25
n=26, m=1..126: 25
n=27, m=1..133: 23
n=28, m=1..139: 23
n=29, m=1..146: 27
n=30, m=1..153: 22
n=31, m=1..160: 29
n=32, m=1..167: 24
n=33, m=1..174: 30
n=34, m=1..181: 23
n=35, m=1..188: 24
n=36, m=1..196: 30
n=37, m=1..203: 26
n=38, m=1..210: 34
n=39, m=1..218: 33
n=40, m=1..225: 27
n=41, m=1..233: 25
n=42, m=1..240: 30
n=43, m=1..248: 21
n=44, m=1..255: 24
n=45, m=1..263: 36
n=46, m=1..271: 21
n=47, m=1..278: 30
n=48, m=1..286: 32
n=49, m=1..294: 21
n=50, m=1..302: 23
n=51, m=1..310: 26
n=52, m=1..317: 33
n=53, m=1..325: 35
n=54, m=1..333: 30
n=55, m=1..341: 22
n=56, m=1..349: 25
n=57, m=1..357: 37
n=58, m=1..366: 31
n=59, m=1..374: 27
n=60, m=1..382: 25
n=61, m=1..390: 28
n=62, m=1..398: 27
n=63, m=1..406: 29
n=64, m=1..415: 25
n=65, m=1..423: 25
n=66, m=1..431: 34
n=67, m=1..440: 36
n=68, m=1..448: 32
n=69, m=1..457: 36
n=70, m=1..465: 31
n=71, m=1..473: 34
n=72, m=1..482: 30
n=73, m=1..490: 32
n=74, m=1..499: 25
n=75, m=1..508: 41
n=76, m=1..516: 34
n=77, m=1..525: 35
n=78, m=1..533: 26
n=79, m=1..542: 23
n=80, m=1..551: 28
n=81, m=1..559: 37
n=82, m=1..568: 35
n=83, m=1..577: 38
n=84, m=1..586: 32
n=85, m=1..594: 32
n=86, m=1..603: 27
n=87, m=1..612: 37
n=88, m=1..621: 40
n=89, m=1..630: 35
n=90, m=1..639: 26
n=91, m=1..647: 35
n=92, m=1..656: 31
n=93, m=1..665: 40
n=94, m=1..674: 34
n=95, m=1..683: 28
n=96, m=1..692: 33
n=97, m=1..701: 25
n=98, m=1..710: 30
n=99, m=1..719: 42
n=100, m=1..728: 35
n=101, m=1..737: 22
n=102, m=1..746: 32
n=103, m=1..756: 32
n=104, m=1..765: 27
n=105, m=1..774: 31
n=106, m=1..783: 27
n=107, m=1..792: 30
n=108, m=1..801: 39
n=109, m=1..811: 41
n=110, m=1..820: 34
n=111, m=1..829: 22
n=112, m=1..838: 36
n=113, m=1..848: 32
n=114, m=1..857: 33
n=115, m=1..866: 29
n=116, m=1..876: 24
n=117, m=1..885: 34
n=118, m=1..894: 32
n=119, m=1..904: 28
n=120, m=1..913: 35
n=121, m=1..922: 41
n=122, m=1..932: 32
n=123, m=1..941: 35
n=124, m=1..951: 26
n=125, m=1..960: 28
n=126, m=1..969: 39
n=127, m=1..979: 29
n=128, m=1..988: 38
n=129, m=1..998: 40
n=130, m=1..1007: 28
n=131, m=1..1017: 31
n=132, m=1..1027: 35
n=133, m=1..1036: 39
n=134, m=1..1046: 43
n=135, m=1..1055: 35
n=136, m=1..1065: 40
n=137, m=1..1074: 38
n=138, m=1..1084: 48
n=139, m=1..1094: 26
n=140, m=1..1103: 39
n=141, m=1..1113: 24
n=142, m=1..1123: 48
n=143, m=1..1132: 39
n=144, m=1..1142: 41
n=145, m=1..1152: 39
n=146, m=1..1161: 33
n=147, m=1..1171: 30
n=148, m=1..1181: 40
n=149, m=1..1191: 31
n=150, m=1..1200: 35
n=151, m=1..1210: 30
n=152, m=1..1220: 30
n=153, m=1..1230: 38
n=154, m=1..1240: 26
n=155, m=1..1249: 33
n=156, m=1..1259: 33
n=157, m=1..1269: 39
n=158, m=1..1279: 42
n=159, m=1..1289: 34
n=160, m=1..1299: 28
n=161, m=1..1309: 40
n=162, m=1..1318: 37
n=163, m=1..1328: 39
n=164, m=1..1338: 46
n=165, m=1..1348: 45
n=166, m=1..1358: 45
n=167, m=1..1368: 33
n=168, m=1..1378: 45
n=169, m=1..1388: 30
n=170, m=1..1398: 42
n=171, m=1..1408: 34
n=172, m=1..1418: 46
n=173, m=1..1428: 34
n=174, m=1..1438: 48
n=175, m=1..1448: 39
n=176, m=1..1458: 26
n=177, m=1..1468: 24
n=178, m=1..1478: 32
n=179, m=1..1488: 29
n=180, m=1..1498: 22
n=181, m=1..1508: 40
n=182, m=1..1518: 45
n=183, m=1..1529: 32
n=184, m=1..1539: 33
n=185, m=1..1549: 36
n=186, m=1..1559: 35
n=187, m=1..1569: 34
n=188, m=1..1579: 34
n=189, m=1..1589: 34
n=190, m=1..1599: 39
n=191, m=1..1610: 45
n=192, m=1..1620: 41
n=193, m=1..1630: 38
n=194, m=1..1640: 44
n=195, m=1..1650: 38
n=196, m=1..1661: 36
n=197, m=1..1671: 39
n=198, m=1..1681: 29
n=199, m=1..1691: 28
n=200, m=1..1702: 51

[Someone]

Сравнение опыта с предсказаниями. Линия показывает график $M_n=\frac 2{d_n\ln 2}$.

Вложение:

PA250.gif [ 4.83 Кб | Просмотров: 2906 ]

[Dmitriy40]

Да, показательно. Теория - сила!

[grizzly]

(Оффтоп)

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

Да, показательно.

Логарифмически