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

[Yadryara]

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

Если во время счета разрадность чисел не увеличичается, то будет линейно.
Если увеличивается, то будет расти время.
Это из-за роста времени на факторизацию и проверку простых.

Как понял, табличку вы внимательно не посмотрели.

Конечно же, при увеличении величины проверяемых чисел, время потихоньку растёт. Интервалы опять взяты по i:

  0 — 1e8         5min,  5,660 ms
1e8 — 2e8         5min,  7,940 ms
  0 — 1e9        50min, 49,609 ms
1e9 — 2e9        51min, 25,438 ms

Но, в некоторых случаях (см. таблицу выше) есть существенное ускорение при увеличении интервала, которое перекрывает замедление. Увеличиваешь интервал в 10 раз, время увеличивается сначала в 1.7 раза, а затем, когда ещё в 10 раз увеличиваешь, время увеличивается в 5 с лишним раз.

[Dmitriy40]

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

С другой стороны: уменьшение количества честных кандидатов приводит к
а) росту порядка чисел, в которых нужно будет делать isprime и factor/numdiv.
Грубо: во сколько раз уменьшили число кандидатов, во столько раз выросли числа. На самом деле - несколько больше выросли, но для грубой оценки можно так считать.

Это да, но насколько велик этот эффект? И не перекроется ли он улучшением фильтрации и соответственно на isprime/factor/numdiv будет оставаться меньше кандидатов и потому всё будет работать быстрее? Это вопрос. И ответ на него зависит от конкретной реализации фильтрации, и уж тем более делать её на PARI или ускорителями.

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

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

Опять таки, может быть лучше сделать больше более быстрых попыток, чем бороться за количество медленных. И тоже зависит от реализации.

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

Конечно, речь про проверку после всех быстрых проверок.

Вы не поняли мой вопрос: что выгоднее, сначала проверить все места на делители 5-128, потом все места на делители 128-32768, или сразу проверять все места на делители 5-32768? Мне первое видится намного более выгодным, с запасом перекрывающим разницу между порядком проверки $pqr$ или $pqrs$, и тогда этот порядок роли уже практически не играет.

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

Но сравнить в терминах: в каком порядке $N$ вероятность найти цепочку близка к 1? Сколько для этого потребуется кандидатов? А не в терминах времени.

А полезнее именно по времени. Что должно учитывать конкретную реализацию.
Например ускорители работали в терминах n=p1+i*m, m=lcm(M), p1%m, и коэффициент 6х считался уже фильтрацией по 2 и 3 и выполнялся самим ускорителем, снаружи (в PARI) он не присутствовал. И я считаю это правильным - как именно ускорять фильтрацию (и в частности по какому простому перебирать) дело ускорителя, а не внешней программы, её дело работать с n.
Заметьте, тут вообще не присутствует "перебираемое простое", перебор идёт сразу в области n, можно сказать перебираются сразу одновременно все три (или сколько их там будет) простых.
Ещё, ускорителям глубоко пофиг на величину чисел n - они работают в арифметике по модулю (ну может за исключением короткой инициализации) и этим они принципиально отличаются от PARI, где ограниченный factor должен зависеть от величины чисел. А до полной проверки с factor/numdiv должно доходить достаточно мало чисел чтобы на общую скорость это влияло мало - именно для этого нужно много проверяемых мест $p$, чтобы улучшить быструю фильтрацию в ускорителях и оставить PARI меньше медленной работы.

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

Добавление простых будет уменьшать вероятность найти цепочку в 4-6 раз на каждое место.
Это приведет к росту необходимого количества проверок на порядок. А размер чисел увеличится на 1-2 порядка.

На каждое какое место? Которое преобразуется к виду $p$? А не пофиг ли если они проверяются существенно быстрее и дополнительно улучшают фильтрацию и значит общая скорость должна вырасти, даже при увеличении количества проверок? Опять зависимость от реализации, а не просто теоретическая оценка вероятности.

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

Но в любом случае нужно понять на сколько потоков можно рассчитывать.

Я могу запустить 20-25 эквивалентных потока (4 обычных плюс 64 более медленных). Медленные сейчас заняты другим, но то можно и бросить.

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

Комп(ы) довольно старенькие - тактовая частота не очень высокая. Но оба поддерживают AVX.

А вот мне помнится что-то на них не поддерживалось, типа AVX2, и потому приходилось использовать SSE версию (чтобы не плодить третий вариант с AVX кроме AVX2+SSE). Но что именно уже не помню. Проверьте снова, запустив первый попавшийся старый ускоритель в тестовом режиме (на 0.1с):
C:\>M12-N2-31-123456.exe 0 1000000
[290322,506436,621570,856092]
Если вылетит с ошибкой - чего-то таки не хватает.
У меня он работает со скоростью 2e9/с разных i (до абсолютно всех предпроверок) в один поток.

[EUgeneUS]

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

Вы не поняли мой вопрос: что выгоднее, сначала проверить все места на делители 5-128, потом все места на делители 128-32768, или сразу проверять все места на делители 5-32768? Мне первое видится намного более выгодным, с запасом перекрывающим разницу между порядком проверки $pqr$ или $pqrs$, и тогда этот порядок роли уже практически не играет.

Насколько понимаю, после проверок всех чисел на делители 5-32768, кандидаты уходят на (долгую) факторизацию.
И вот там будет выгоднее делать долгую факторизацию с начиная с тех мест, где вероятность успеха минимальна. А значит с $pqrs$.

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

А полезнее именно по времени. Что должно учитывать конкретную реализацию.

"Калькулятор шансов" считает вероятности.
Далее, конечно, с учётом реализации и ожидаемой скорости проверки, нужно выбрать оптимум.

Для любых шаблонов могу посчитать вероятности, но нужно выбрать- по каким и собрать статистику, как делали на днях. Чтобы обсуждать, уже имея конкретные числа.

Сбор статистики смогу запустить у себя, конечно. А вот "плохие" остатки для большого ифа рассчитать не смогу :(

(Оффтоп)

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

А вот мне помнится что-то на них не поддерживалось, типа AVX2, и потому приходилось использовать SSE версию (чтобы не плодить третий вариант с AVX кроме AVX2+SSE). Но что именно уже не помню. Проверьте снова, запустив первый попавшийся старый ускоритель
в тестовом режиме (на 0.1с):
C:\>M12-N2-31-123456.exe 0 1000000
[290322,506436,621570,856092]
Если вылетит с ошибкой - чего-то таки не хватает.
У меня он работает со скоростью 2e9/с разных i (до абсолютно всех предпроверок) в один поток.

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

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

[Dmitriy40]

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

А вот "плохие" остатки для большого ифа рассчитать не смогу :(

Я показывал этот расчёт (последняя строка):
m=554159729309947409007752567806326895200;
p1=30475766721704852566432501877740394775491;
pr2=primes([5,59]);
zapr=[(lift(Mod(20-(select(x->x%pr2[j]^2==0,M,1)[1]-1), pr2[j]^3))/320226-p1)/m)%pr2[j] | j<-[1..#pr2]];
Получается массив запрещённых остатков размером #pr2.
И заменить длинный if можно циклом for(j=1,#pr2, if(i%pr2[j]==zapr[j], next(2)); );.

Он откровенно подбирался под числа VAL, мне проще работать с m=lcm(M) и p1%m=lift(chinese([Mod(-j+1, M[j]) | j<-[1..#M]])) и n=p1+m*i. Да, тут i будет пробегать лишь значения i=6k+5, остальные 5 запрещены, ну и что, это тоже фильтрация (в ускорителях - бесплатная). И эти i не совсем те что у VAL (у него чуть смещены в плюс непонятно зафига), зато понятнее. Из расчёта zapr уйдут 20-, -1, /320226-p1, /m, и вообще он переместится в ускорители, где всё иначе.

[EUgeneUS]

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

А вот мне помнится что-то на них не поддерживалось, типа AVX2,

Да, на компе, который сейчас в наличии AVX - есть, а AVX2 - нет .

Про вероятности успеха.
Если вероятность успеха в одном испытании $p$, то вероятность успеха (хотя бы одного) при $n$ испытаниях:
$P(\text{win}) = 1 - (1-p)^n$
Если $p \ll 1, n \gg1$, то $P(\text{win}) \approx 1 - (1/e)^{np}$

Далее для разных количеств паттернов типа "3-0-13-5 (9)" подбирались с точностью 10% необходимые количества испытаний, чтобы получить вероятность 0.95 и 0.99.

Получилось вот так.

UPD: заменил картинку. На прошлой неточно показывались значения в колонке $i$

-- 11.10.2025, 15:28 --

$i$ - количество проверок на 1 паттерн до длинного ифа.;
$n=0.4 i$ - количество проверок на 1 паттерн после длинного ифа.
"Всего проверок" - общее количество проверок после длинного ифа, чтобы получить заданную вероятность успеха. Чтобы перейти к количеству проверок до длинного ифа нужно умножить на $2.4$
$N$ - максимальное число, до которого проверяется.
$P(1)$ - вероятность успеха за одну проверку (в районе максимального числа)
$P(\text{win})$ - вероятность успеха при этих условиях.

[Yadryara]

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

Проверьте снова, запустив первый попавшийся старый ускоритель в тестовом режиме (на 0.1с):
C:\>M12-N2-31-123456.exe 0 1000000
[290322,506436,621570,856092]
Если вылетит с ошибкой - чего-то таки не хватает.

У меня нормально отработал.

Антивир ругался, я нажал "выполнить в любом случае". Потом догадался запустить из консоли.

Статистику собрал для первых 564 ярдов по i или, что примерно то же самое, в интервале $0 - 10^{54}$ по n.

Valids    8     9    10    11    12    13    14    15    16    17    18    19    20
Цепочек   2     3     2     7     7     5     8     4     1                              39

Полагаю, надо собрать ещё по другим паттернам и смотреть хвост, начиная с 14-ти.

[EUgeneUS]

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

Я показывал этот расчёт
(последняя строка):

Спасибо!
Остаётся построить\найти паттерны для четырёх и пяти простых.
Могу для обоих расчеты сделать.

-- 11.10.2025, 16:03 --

Нашелся у меня паттерн для $D(48,21)$ вида "4-0-12-5 (9)".
То есть на 4 простых.
Попробую подготовить и рассчитать статистику для него.

-- 11.10.2025, 16:20 --

Dmitriy40
ещё вопрос, в качестве:

a =  320226;

какое число брать для нового паттерна?

[Dmitriy40]

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

какое число брать для нового паттерна?

То, которое стоит в паттерне на месте перебираемого простого. Это же просто коэффициент пересчёта от p к n: n=a*p-20, здесь -20 это переход от места +20 (в котором и перебирается простое по p=p1+m*i) к месту +0 (начало цепочки).

-- 11.10.2025, 16:56 --

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

Да, на компе, который сейчас в наличии AVX - есть, а AVX2 - нет .

Проблема в том что ускорители очень активно используют операцию "сложение по модулю простого", реализованную как сложение, вычитание простого и взятие минимума из двух - и вот взятие минимума в AVX работает только с регистрами xmm (т.е. фактически в режиме SSE) вместо вдвое более длинных ymm в AVX2. Вот такой урезанный функционал работы с целыми в AVX, там делали упор на плавающую точку (кодеки и всё такое). Реализовать выбор минимального значения из двух можно и без vpminub, но тогда почти пропадает преимущество AVX и код становится почти совместим с SSE4.1 (только без трёхадресных команд и соответственно с лишними mov), т.е. применение AVX не даёт существенно выигрыша от более распространённого SSE4.1, под который и компились варианты. Навскидку, точного анализа не проводилось, акцент всегда смещён на AVX2. К тому же мне не на чём проверять код для AVX и SSE (ну то есть извратиться наверное можно, но это куча гемора).

[EUgeneUS]

Dmitriy40
Спасибо! Почти получилось, но только почти

(Оффтоп)

Подставляю паттерн в первую программу:

\\      +0      +1      +2      +3      +4      +5      +6      +7      +8      +9      +10     +11     +12     +13     +14     +15     +16     +17     +18     +19     +20
\\      2       11      3               2       3       2^3*13          2       5       7       3       2               3*5             2       7               5       2*3*19
\\      43^2    19^2    2^2     7^2     5^2     41^2    59^2    23^2    3^2     31^2    2^2     37^2    11^2    29^2    2^5     17^2    47^2    3^2     2^2     13^2    53^2
\\      pqr     pqr     pqr     pqrs    pqr     pqr     p       pqrs    pqr     pqr     pqrs    pqr     pqr     pqrs    p       pqrs    pqr     pqr     pqrs    pqr     p
\\ v=[     3698,   3971,   12,     49,     50,     5043,   362024, 529,    18,     4805,   28,     4107,   242,    841,    480,    289,    4418,   63,     4,      845,    320226  ];
\\    p   pqrs   pqr   pqr   pqr   pqr   p   pqrs   pqr   pqrs   pqr   pqr   pqr   pqr   p   pqr   pqr   pqr   pqrs   pqrs   p
v=[   54910,   529,   12,   1573,   2738,   75,   194936,   841,   18,   961,   20,   5043,   3698,   15463,   1056,   14045,   338,   153,   4,   361,   1470];

nd=48;\\Количество делителей
pr2=primes([5,59]);\\Эти квадраты размещены
P=primes([61,523]);\\По этим простым будем проверять
ip=20;\\Перебирать будем по месту +20

vp=v[ip+1];
print("m= ",m=lcm(v)*6/vp);
print("p1=",p1=(lift((chinese([Mod(-j+1, v[j]) | j<-[1..#v]])))+ip)/vp+5/6*m+54*m);
print("P= ",P);
plt=select(x->numdiv(x)==nd/2,v,1);
print("T= ",[Set([((lift(Mod(ip-(plt[k]-1), P[j]))/vp-p1)/m)%P[j] | k<-[1..#plt]]) | j<-[1..#P]]);
print("if(",strjoin([strprintf("i%%%u!=%u", pr2[j], ((lift(Mod(ip-(select(x->x%pr2[j]^2==0,v,1)[1]-1), pr2[j]^3))/vp-p1)/m)%pr2[j]) | j<-[1..#pr2]]," && "),",");

Получаю:

parisize = 8000000, primelimit = 1048576, factorlimit = 1048576
m= 120718607808168176188378621617924378464160
p1=6635499368845584484761886884147377300780797
P= [61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509, 521, 523]
T= [[4, 28, 46, 47], [3, 4, 50, 51], [8, 19, 33, 44], [2, 11, 36, 50], [27, 29, 65, 70], [4, 15, 44, 58], [18, 28, 35, 45], [4, 22, 46, 64], [47, 55, 62, 70], [24, 29, 85, 90], [28, 43, 81, 97], [36, 53, 93, 105], [29, 36, 83, 90], [16, 71, 96, 118], [27, 50, 93, 116], [16, 87, 106, 134], [32, 59, 114, 116], [53, 90, 101, 138], [38, 62, 113, 137], [36, 53, 96, 113], [44, 62, 86, 104], [81, 106, 134, 159], [87, 99, 156, 168], [60, 79, 103, 122], [14, 40, 85, 150], [48, 88, 147, 187], [43, 77, 144, 169], [58, 83, 125, 150], [52, 84, 151, 183], [18, 20, 154, 156], [90, 129, 137, 176], [69, 131, 138, 200], [55, 88, 139, 172], [6, 72, 119, 192], [95, 134, 180, 219], [79, 83, 150, 154], [17, 102, 124, 209], [19, 151, 177, 250], [78, 115, 167, 204], [4, 34, 116, 191], [15, 24, 76, 234], [73, 131, 177, 235], [122, 165, 209, 252], [2, 35, 110, 210], [63, 141, 174, 252], [47, 50, 140, 264], [51, 82, 242, 273], [70, 120, 162, 212], [211, 236, 267, 292], [201, 226, 253, 278], [114, 208, 221, 315], [31, 45, 114, 128], [15, 22, 97, 289], [14, 23, 111, 120], [17, 41, 320, 344], [118, 183, 211, 276], [177, 192, 212, 227], [181, 206, 300, 325], [83, 95, 111, 123], [50, 73, 363, 386], [20, 27, 301, 308], [74, 164, 284, 374], [76, 212, 257, 393], [200, 268, 289, 357], [9, 244, 315, 359], [88, 166, 315, 370], [214, 227, 328, 341], [34, 68, 333, 367], [55, 163, 244, 417], [20, 101, 209, 290], [372, 393, 421, 442], [24, 158, 230, 364], [247, 292, 360, 405], [38, 331, 402, 434], [162, 227, 421, 447], [16, 282, 388, 397], [160, 231, 340, 411], [83, 123, 314, 354], [227, 237, 471, 496], [69, 245, 377, 446], [308, 328, 435, 455], [26, 67, 126, 490]]
if(i%5!=4 && i%7!=4 && i%11!=7 && i%13!=0 && i%17!=15 && i%19!=15 && i%23!=14 && i%29!=10 && i%31!=29 && i%37!=7 && i%41!=9 && i%43!=5 && i%47!=2 && i%53!=14 && i%59!=29,
(21:08)

Подставляю всё во вторую программу:

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

\\ 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];

m = 120718607808168176188378621617924378464160
a = 1470
p1 = 6635499368845584484761886884147377300780797
M=[   54910,   529,   12,   1573,   2738,   75,   194936,   841,   18,   961,   20,   5043,   3698,   15463,   1056,   14045,   338,   153,   4,   361,   1470];

pows=[[1], [1,1], [1,1,1], [1,1,1,1], [1,1,1,1,1], [1,1,1,1,1,1], [3,1], [2,1], [2,1,1], [3,1,1]];\\По каким разложениям набирать статистику (степени сортировать по убыванию), можно указывать много разных, почти не замедляет
npr=matrix(#M,#pows); h=0; l=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,
if(i%5!=4 && i%7!=4 && i%11!=7 && i%13!=0 && i%17!=15 && i%19!=15 && i%23!=14 && i%29!=10 && i%31!=29 && i%37!=7 && i%41!=9 && i%43!=5 && i%47!=2 && i%53!=14 && i%59!=29,

p=p1+i*m; n=a*p-20;
l++;
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]]++); );
if(l%10==0, print("l=",l);print("i=",i);print("n=",n);for(i=1,#pows, printf("%2u, sum=%u, pows=%u\n",npr[,i]~,vecsum(npr[,i]),pows[i]); ););\\прогресс
));}
print("h=",h);
print("i=",i);      
print("a=",a);      
print("n=",n);      
print("p=",p);      
print("l=",l);      
for(i=1,#pows, printf("%2u, sum=%u, pows=%u\n",npr[,i]~,vecsum(npr[,i]),pows[i]); );

И получаю в начале расчета:

l=160
i=1000387
n=177534783270875410799860980466120753986611823753970
[11,14,13, 6,12, 9,15, 9, 0,13,10,12,16,13, 0,14,17,17, 9,11,11], sum=232, pows=[1]
[46,41,40,31,35,28,31,39,12,33,33,33,34,38, 6,38,39,34,30,39,37], sum=697, pows=[1,1]
[47,36,47,52,49,41,56,48,16,44,48,47,49,55,21,48,46,49,46,45,47], sum=937, pows=[1,1,1]
[33,38,33,48,34,53,33,39,35,37,42,45,41,31,23,33,31,42,50,32,36], sum=789, pows=[1,1,1,1]
[11,24,21,17,24,18,18,14,25,24,20,16,14,17,18,20,19,11,16,26,20], sum=393, pows=[1,1,1,1,1]
[11, 3, 3, 4, 4,10, 6, 7,13, 5, 3, 6, 6, 2, 8, 6, 4, 6, 5, 5, 5], sum=122, pows=[1,1,1,1,1,1]
[ 0, 0, 0, 0, 0, 0, 0, 0, 2, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0], sum=3, pows=[3,1]
[ 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 2, 0, 0, 0, 0, 0, 0], sum=3, pows=[2,1]
[ 0, 0, 0, 0, 0, 1, 0, 0, 6, 1, 0, 0, 0, 0, 9, 0, 0, 0, 0, 0, 0], sum=17, pows=[2,1,1]
[ 0, 0, 0, 0, 0, 0, 0, 0, 3, 0, 0, 0, 0, 0, 4, 0, 0, 0, 0, 0, 0], sum=7, pows=[3,1,1]

На 9 и 15 месте не бывает простых, но там повышенное количество квадратов и кубов

[EUgeneUS]

Пока предварительно, до расчёта статистики (а с ней проблемы - см. выше): переход от паттерна "3-0-13-5 (9)" к паттерну "4-0-12-5 (9)" требует увеличения количества проверок в $1.34$ раза.

Что вряд ли окупится
Так как, даже если проверка простых будет "бесплатной", выигрываем одну факторизацию (из 18-и).

[Dmitriy40]

EUgeneUS
Множитель 5/6*m в расчёте p1 надо поменять на 4/6*m (откровенно подобрал чтобы все простые на местах $p$ были $\pm1\pmod6$, расчёт додумаю потом). А +54*m вообще убрать как пережиток прошлого.
Константы посчитаются такие:

m= 120718607808168176188378621617924378464160
p1=96574779236474941224711546509806800638797
if(i%5!=4 && i%7!=1 && i%11!=8 && i%13!=0 && i%17!=4 && i%19!=9 && i%23!=3 && i%29!=11 && i%31!=16 && i%37!=18 && i%41!=29 && i%43!=9 && i%47!=17 && i%53!=24 && i%59!=34,

Массивы T[],P[] не используются и вычислять не нужно.
Подставив этот if в программу получим вроде адекватную статистику (401 кандидат на интервале 1e3 за 15 минут, дольше ждать влом):

[  21,  18,  19,  22,  32,  23,  29,  33,  31,  24,  37,  34,  31,  28,  22,  31,  27,  21,  17,  34,  24], sum=558, pows=[1]
[  82,  77,  85,  89,  77,  88,  79,  69,  80,  84,  82,  87, 100,  93,  78,  82,  86, 100,  87,  78,  78], sum=1761, pows=[1,1]
[ 130, 111, 117, 127, 130, 122, 126, 129, 117, 125, 117, 119,  99, 110, 132, 134, 117, 107, 106, 119, 131], sum=2525, pows=[1,1,1]
[ 105, 119,  96,  80,  89,  89,  88,  88, 104,  99,  88,  97, 107, 104,  85,  88,  92, 100,  98,  92,  99], sum=2007, pows=[1,1,1,1]
[  42,  52,  67,  61,  45,  52,  48,  58,  47,  46,  49,  44,  42,  46,  54,  46,  58,  45,  58,  48,  46], sum=1054, pows=[1,1,1,1,1]
[  15,  19,  15,  15,  22,  18,  21,  15,  16,  17,  21,  14,  13,  15,  24,  13,  16,  14,  25,  23,  20], sum=371, pows=[1,1,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=[2,1]
[   0,   0,   0,   0,   0,   0,   1,   0,   0,   0,   0,   0,   0,   0,   0,   0,   0,   0,   1,   0,   0], sum=2, pows=[2,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,1]

[EUgeneUS]

Dmitriy40
Спасибо!
Запустил расчет на ночь.

[Dmitriy40]

Может стоит сделать многопоточный вариант и запускать файлом gppthread64-2-17-2.exe вместо gp64-2-17-2.exe? Но многопоточный PARI/GP только под х64 винду! А SSE версии ускорителей приходилось компилить под х32/х86 винду ...

[EUgeneUS]

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

Может стоит сделать многопоточный вариант и запускать файлом gppthread64-2-17-2.exe вместо gp64-2-17-2.exe? Но многопоточный PARI/GP только под х64 винду! А SSE версии ускорителей приходилось компилить под х32/х86 винду ...

Это про расчет или сбор статистики? Если про сбор статистики - завтра видно будет. Если за ночь будет собираться для одного паттерна (где-нибудь до $1...4 \cdot 10^4$ кандидатов), то и ладно.

Кстати,
может быть и окупится переход на четыре простых.
а) после условно бесплатной проверки простого дальше уйдет $0.07$ кандидатов
б) а после долгой факторизации (ожидаем $pqr$) дальше уйдет $0.3$ кандидатов, что в $4.29$ раз больше.

[Dmitriy40]

Про сбор статистики конечно.

-- 11.10.2025, 20:25 --

Хотя у меня на 4 потоках ускоряет с 1м25с до 37с, ну совсем не в 4 раза, хотя заняты на 100% все 4 ядра.

-- 11.10.2025, 20:36 --

Параллельная программа:

i1=round(1e8); i2=i1+round(1e2);\\Интервал счёта, справа не включая
\\default(nbthreads,1);\\Убрать комментарий для запуска в одном потоке даже под gpp.exe

{t0=getwalltime();
\\   +0   +1   +2   +3   +4   +5   +6   +7   +8   +9   +10   +11   +12   +13   +14   +15   +16   +17   +18   +19   +20
\\v=[   3698,   3971,   12,   49,   50,   5043,   362024,   529,   18,   4805,   28,   4107,   242,   841,   480,   289,   4418,   63,   4,   845,   320226   ];
\\   pqr   pqr   pqr   pqrs   pqr   pqr   p   pqrs   pqr   pqr   pqr   pqr   pqr   pqrs   p   pqrs   pqr   pqr   pqrs   pqr   p

v=[   54910,   529,   12,   1573,   2738,   75,   194936,   841,   18,   961,   20,   5043,   3698,   15463,   1056,   14045,   338,   153,   4,   361,   1470   ];
\\   p   pqrs   pqr   pqr   pqr   pqr   p   pqrs   pqr   pqrs   pqr   pqr   pqr   pqr   p   pqr   pqr   pqr   pqrs   pqrs   p

nd=48;\\Количество делителей
pr2=primes([5,59]);\\Эти квадраты размещены
ip=20;\\Перебирать будем по месту +20

vp=v[ip+1];
print("m= ",m=lcm(v)*6/vp);
print("p1=",p1=(lift((chinese([Mod(-j+1, v[j]) | j<-[1..#v]])))+ip)/vp+4/6*m);\\Для первого паттерна надо 5/6*m вместо 4/6*m
\\print("if(",strjoin([strprintf("i%%%u!=%u", pr2[j], ((lift(Mod(ip-(select(x->x%pr2[j]^2==0,v,1)[1]-1), pr2[j]^3))/vp-p1)/m)%pr2[j]) | j<-[1..#pr2]]," && "),",");
bad=[((lift(Mod(ip-(select(x->x%pr2[j]^2==0,v,1)[1]-1), pr2[j]^3))/vp-p1)/m)%pr2[j] | j<-[1..#pr2]];\\Это недопустимые остатки для длинного if

pows=[[1], [1,1], [1,1,1], [1,1,1,1], [1,1,1,1,1], [1,1,1,1,1,1], [3,1], [2,1], [2,1,1], [3,1,1]];\\По каким разложениям набирать статистику (степени сортировать по убыванию), можно указывать много разных, почти не замедляет
npr=matrix(#v,#pows); h=0;
nth=default(nbthreads); export(nth,th,v,i1,i2,pows,p1,m,vp,npr,t0);
parfor(th=0,nth-1,
   my(hh=0,p,n,f,i,j,nprth);
   nprth=matrix(#v,#pows);
   forstep(i=i1+th,i2-1,nth,
      \\if(i%5!=4 && i%7!=1 && i%11!=8 && i%13!=0 && i%17!=4 && i%19!=9 && i%23!=3 && i%29!=11 && i%31!=16 && i%37!=18 && i%41!=29 && i%43!=9 && i%47!=17 && i%53!=24 && i%59!=34,
      for(j=1,#pr2, if(i%pr2[j]==bad[j], next(2)); );\\Замена длинному if, немного медленнее, у меня на 15%
         p=p1+i*m; n=vp*p-ip; hh++;
      \\   print("i=",i,", p=",p,", n=",n);\\Показ найденных кандидатов если надо
         foreach([1..#v],k, f=vecsort(factor((n+k-1)/v[k])[,2]~,,4); j=select(t->t==f,pows,1); if(#j>0, nprth[k,j[1]]++); );
         if(th==0, printf("%u, %0.3f%%, ETA: %s\t\t\t\t%c",hh*nth,100.0*(i+1-i1)/(i2-i1),strtime(round((i2-i-1)/(i+1-i1)*(getwalltime()-t0))),13););\\Показ прогресса, можно и убрать
      \\);
   );
   [hh,nprth]
,r, h+=r[1]; npr+=r[2]);
print("h=",h,"\t\t\t\t\t");
for(i=1,#pows, printf("%4u, sum=%u, pows=%u\n",npr[,i]~,vecsum(npr[,i]),pows[i]); );
print(strtime(getwalltime()-t0));}

В процессе многопоточной работы выводит примерное количество кандидатов (в один поток - точное), точное будет указано после завершения.