Пентадекатлон мечты

[EUgeneUS]

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

которые дают степень размещённых простых более квадрата (кроме двойки и тройки),

Спасибо!
Написал в ЛС. Но тут тоже пусть будет (лучше тут ответить)
1. Вот это я называю "предварительной фильтрацией.
2. А почему, кроме двойки и тройки?

-- 09.10.2025, 16:48 --

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

Если считаете что проверки h[4..6] лишние,

Для "боевого" расчета скорее всего - не лишние, раз ускоряют работу.
А вот для оценок вероятностей, похоже, все проверки h[1..6] лишние. Поразбираюсь с этим на выходных.

[Dmitriy40]

EUgeneUS в сообщении #1705157 писал(а):

2. А почему, кроме двойки и тройки?

Сам не понимаю.
Вероятно они уже учтены в p1 и m, потому m и в 6 раз больше lcm(M). Но не уверен.
VAL?

-- 09.10.2025, 17:40 --

EUgeneUS в сообщении #1705157 писал(а):

1. Вот это я называю "предварительной фильтрацией.

А то что простые 61...523 могут попадать на места $p$ - это не предварительная фильтрация? Не очень понятно.

[EUgeneUS]

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

А то что простые 61...523 могут попадать на места $p$ - это не предварительная фильтрация? Не очень понятно.

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

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

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

[Dmitriy40]

Ну тогда вот статистика только с одним длинным if, разлагаются все места, и с ожидаемым $p$ тоже (они же теперь не проверяются), интервал 1e2 считался 1м33с, в нём обработано 39 кандидатов:

[ 1, 5, 1, 0, 1, 5, 3, 2, 0, 2, 4, 2, 1, 5, 3, 1, 3, 1, 2, 1, 4], sum=47, pows=[1]
[10, 7,14,13,11, 6, 7, 7, 8, 9, 5, 8, 9,10, 9, 7,10, 8, 6,12,11], sum=187, pows=[1,1]
[13,16, 6,11,12, 9,13, 9,15, 9, 9,15,10, 6, 8,11,10,11,14, 7,13], sum=227, pows=[1,1,1]
[10, 4,11, 9, 8,12, 9,13, 7,11,11,10, 8, 4,12,12, 9, 9, 8,13, 5], sum=195, pows=[1,1,1,1]
[ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], sum=0, pows=[3,1]
[ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], sum=0, pows=[3,1,1]

Интервал 1e3 за 15м15с обработано 394 кандидата:

[ 25, 28, 23, 19, 25, 27, 27, 25, 24, 24, 37, 28, 19, 26, 27, 18, 26, 22, 24, 27, 30], sum=531, pows=[1]
[ 81, 80, 75, 93, 81, 75, 86, 80, 98, 84, 81, 88, 83, 97, 84, 79, 89, 92, 94, 98, 84], sum=1802, pows=[1,1]
[116,125,113,124,113,109,124,132,125,120,115,115,135, 99,131,122,116,123,114,112,117], sum=2500, pows=[1,1,1]
[ 94, 84, 94, 87, 96, 87, 90, 86, 73, 92, 95, 88, 72, 87, 86, 98, 77, 92, 82, 86, 93], sum=1839, pows=[1,1,1,1]
[  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0], sum=0, pows=[3,1]
[  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0], sum=0, pows=[3,1,1]

[VAL]

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

EUgeneUS в сообщении #1705157

писал(а):
2. А почему, кроме двойки и тройки? Сам не понимаю.
Вероятно они уже учтены в p1 и m, потому m и в 6 раз больше lcm(M). Но не уверен.
VAL?

Подтверждаю.

[EUgeneUS]

VAL
а какой модуль для тройки нужно исключать?
(умножать на 6 не очень эффективно)

Dmitriy40
Правильно понимаю, что у Вас на 6 не умножалось?

      p=p1+i*m; \\h[1]++;\\Не считается ради ускорения

[Dmitriy40]

EUgeneUS в сообщении #1705184 писал(а):

Правильно понимаю, что у Вас на 6 не умножалось?

Умножалось, я же взял данные VAL. Сравните a*m=1774... и lcm(M)=2957..., первое ровно в 6 раз больше.

Кстати, могу код и здесь показать, он сильно упростился:

i1=round(1e8); i2=i1+round(1e2);\\Интервал счёта, справа не включая

m =  554159729309947409007752567806326895200;
a =  320226;
p1 = 30475766721704852566432501877740394775491;
M =  [3698, 3971, 12, 49, 50, 5043, 362024, 529, 18, 4805, 28, 4107, 242, 841, 480, 289, 4418, 63, 4, 845, 320226];
pows=[[1], [1,1], [1,1,1], [1,1,1,1], [3,1], [3,1,1]];\\По каким разложениям набирать статистику (степени сортировать по убыванию), можно указывать много разных, почти не замедляет
npr=matrix(#M,#pows); h=0;
{for(i=i1,i2-1,
if(i%5!=4 && i%7!=3 && i%11!=3 && i%13!=6 && i%17!=11 && i%19!=15 && i%23!=17 && i%29!=1 && i%31!=18 && i%37!=19 && i%41!=21 && i%43!=22 && i%47!=3 && i%53!=23 && i%59!=27,
p=p1+i*m; n=a*p-20;
foreach([1..#M],k, f=vecsort(factor((n+k-1)/M[k])[,2]~,,4); j=select(t->t==f,pows,1); if(#j>0, npr[k,j[1]]++); );
));}
print("h=",h);
for(i=1,#pows, printf("%2u, sum=%u, pows=%u\n",npr[,i]~,vecsum(npr[,i]),pows[i]); );

[VAL]

EUgeneUS в сообщении #1705184 писал(а):

VAL
а какой модуль для тройки нужно исключать?
(умножать на 6 не очень эффективно)

Надо найти исходники на maple/
А по памяти, вроде бы, делал из каждого шаблона две программки с шагом 6m.

[EUgeneUS]

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

Кстати, могу код и здесь показать, он сильно упростился:

Спасибо!

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

Интервал 1e3 за 15м15с обработано 394 кандидата:

пока всё указывает на то, что в вилку с грубой оценкой попал:

EUgeneUS в сообщении #1705107 писал(а):

а) среднее геометрическое вероятности для всех мест, отличных от простых: $0.3$ (это завышено)
Вероятность найти цепочку: $\hat{p} = 1.40512 \cdot 10^{-13}$

б) среднее геометрическое вероятности для всех мест, отличных от простых: $0.2$ (это ближе к правде, но всё равно завышено)
Вероятность найти цепочку: $\hat{p} = 9.50759 \cdot 10^{-17}$

Будет чуть лучше, чем в пункте б), но не намного.

-- 09.10.2025, 19:41 --

VAL в сообщении #1705186 писал(а):

А по памяти, вроде бы, делал из каждого шаблона две программки с шагом 6m.

OK. Понятно.
Для оценки вероятностей пока можно умножать на 6.

[EUgeneUS]

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

p=p1+i*m; n=a*p-20;

Я же правильно понимаю, что цепочка ищется в районе $n$, а не в районе $p$?

[Dmitriy40]

EUgeneUS в сообщении #1705197 писал(а):

Я же правильно понимаю, что цепочка ищется в районе $n$, а не в районе $p$?

Конечно.
$p$ это перебираемое большое простое на +20 месте. Просто перебирается оно не подряд, а с огромным шагом m начиная с p1 потому что все остальные по модулю m - точно не подходят.

-- 09.10.2025, 20:52 --

Можно конечно и прямо n перебирать, с шагом a*m, но тогда придётся проверять что (n+20)/320226 является простым, а умножение чуть дешевле (быстрее) деления (даже на константу). Тем более разрядность i всего десяток цифр, а разрядность n может достигать тысяч и миллионов. Так что перебирать i удобнее и быстрее чем p или n.

[EUgeneUS]

Dmitriy40
Понятно. Значит я на 5 порядков ошибся, в оценке $N$.
Завтра посмотрю, как это на оценки вероятностей повлияет. Повлияет, конечно, в худшую сторону, но насколько.

[Dmitriy40]

За 2ч32м посчитался интервал 1e4, обнаружено 4005 кандидатов:

[ 265, 265, 258, 235, 244, 257, 271, 278, 252, 277, 247, 257, 234, 275, 258, 244, 254, 269, 271, 267, 268], sum=5446, pows=[1]
[ 827, 878, 837, 846, 834, 884, 882, 879, 866, 817, 799, 864, 810, 861, 861, 844, 890, 860, 853, 876, 900], sum=17968, pows=[1,1]
[1258,1198,1195,1192,1156,1158,1267,1215,1185,1164,1227,1192,1258,1195,1207,1228,1190,1173,1199,1187,1213], sum=25257, pows=[1,1,1]
[ 891, 940, 908, 952, 985, 965, 920, 902, 946, 977, 962, 947, 962, 923, 960, 942, 934, 957, 892, 924, 930], sum=19719, pows=[1,1,1,1]
[   0,   0,   0,   0,   0,   0,   0,   0,   0,   0,   0,   0,   0,   0,   0,   0,   0,   0,   0,   0,   0], sum=0, pows=[3,1]
[   0,   0,   0,   0,   0,   0,   0,   0,   0,   1,   0,   0,   0,   0,   1,   0,   0,   0,   0,   0,   0], sum=2, pows=[3,1,1]

Два раза попался вариант $p^3rs$, на разных местах паттерна.

Явно выделенных мест паттерна не наблюдаю, везде равномерно. Разброс значений для $pqr$ составил менее 5%.

[EUgeneUS]

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

За 2ч32м посчитался интервал 1e4, обнаружено 4005 кандидатов:

О!

А у меня еще считается. При этом я $i$ понизил до $10^6$

-- 09.10.2025, 22:07 --

Dmitriy40
Ещё, скажите, пожалуйста, в каких числах $n$ начинался расчет, и в каких закончился.

[Dmitriy40]

Все мои начинались с $i=10^8$, и кончались на $i=10^8+10^{[2,3,4]}-1$.
В n (начало цепочки) они пересчитываются по формулам

m =  554159729309947409007752567806326895200;
a =  320226;
p1 = 30475766721704852566432501877740394775491;
p=p1+i*m; n=a*p-20;

-- 09.10.2025, 22:39 --

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

При этом я $i$ понизил до $10^6$

Прекрасно, это отдельно будет полезно сравнить, зависимость от величины $n$.