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

[EUgeneUS]

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

Ускорителям не нужно /(7*37^2), они не перебирают простые ни на каком месте (ну или перебирают их все сразу). И 6* им тоже не нужно, это они и сами сделают внутри. Им достаточно n=p1+lcm(v)*i, из которых они перебирают только i (и неважно каким способом!), а p1 и m=lcm(v) им заранее известны и зависят только и исключительно от паттерна и больше ни от чего (как считаю и должно быть).
Так что про ускорители я Вас не понимаю.

Нужно всеми возможными способами снижать шаг $m$.

-- 13.10.2025, 16:42 --

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

Для программ VAL связь для любого перебираемого места:

Это я видел. Спасибо.

-- 13.10.2025, 16:44 --

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

А уж сколько там будет попыток/кандидатов/проверок - зависит от реализации и способа подсчёта их количества.

Нельзя забыть про количество попыток.

[Dmitriy40]

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

m= 1.93078E+24
[...]
Если искать 1.19E+14 кандидатов (до N = 7.98E+34), то есть 60% вероятности, что цепочка найдётся и рекорд обновится.

и опять не понимаю, откуда m=1.93078e24? А, это lcm(v)*6/37^2, но куда-то пропало /7 ... Непонятно.

И совсем непонятно почему что-то могло не найтись если проверено всё до n<1e38 по всем 46080 паттернам и частично и по другим тоже (с 41, 43, 47, ещё какими-то, а докуда-то и с вообще любыми).

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

Нужно всеми возможными способами снижать шаг $m$.

Это невозможно: m=lcm(v). Для сниженяи надо или ставить меньше простых в квадратах (что делалось!), или "шебуршить" расстановку 3,5,7,11,13 чтобы lcm(v) стал поменьше, но при этом что-то другое ухудшается (например проверяемых мест становится меньше и растёт количество мест $pq$, что приводит к снижению скорости ускорителей и ухудшению фильтрации, что уже приводит к замедлению и PARI программы).

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

Нельзя забыть про количество попыток.

Нельзя. Вопрос лишь что именно считать "попыткой". Например ускоритель M12-N2-31-123456.exe по паттерну [45, 578, 169, 12, 49, 50, 363, 32, 361, 18, 2645, 28, 2523, 1922, 1369] проверку по 2,3,41,43 за попытки не считает, эти проверки вообще не выполняются так как выполнены на этапе компиляции и генерации кода ускорителя, и соответственно вместо 2*3*41*43=10578 реально выполнит лишь 10578*1/2*1/3*30/41*32/43=960 проверок (столько i из каждых 10578 дойдёт до "длинного if"), понимаете, они просто тупо прямо перечислены в коде что только их и нужно проверить из всех 10578, а на остальные забить и игнорировать. А другой ускоритель может в принципе по другим модулям "не проверять" (точнее проверять на этапе своей компиляции) и соответственно делать другое количество проверок - и PARI программе на это плевать, она работает в терминах n=n0(v)+lcm(v)*i (n0 тоже разумеется зависит от v[], что и указал прямо как функцию от него), всё, остальное дело ускорителя. И сколько проверок и каких именно выполнит каждый ускоритель - вопрос весьма нетривиальный. Оперировать лучше лишь количеством i в формуле выше (без всяких оптимизаций типа 6* или длинного if) и соответственно временем проверки заданного количества i (нет, оно зависит от реализации).

-- 13.10.2025, 17:18 --

И насколько я помню, lcm(v)=4.4e26 как раз и есть минимальный при условиях отсутствия кубов (кроме 2) и расстановке наименьших доступных простых в квадратах и наличия 11 проверяемых мест. Дальше его снижать некуда, надо что-то менять в паттернах, что лишь ухудшало по тогдашним оценкам (в основном от VAL).

И никаким выбором что там перебирать (на каком месте простое) уменьшить этот m нельзя - в ускорителях нет /v[ip], они перебирают сразу синхронно все 11 простых на проверяемых местах.

[EUgeneUS]

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

Вопрос лишь что именно считать "попыткой".

Вероятность найти цепочку равна: $P(\text{win}) = 1 - e^{-nP_1(N)}$,
где $n$ - количество проверенных кандидатов после длинного ифа и без другой фильтрации,
$P_1(N)$ - вероятность найти цепочку за одну проверку около $N$.

Далее задаём желаемый уровень вероятности найти цепочку ($0.95, 0.99, 0,999 ...$), пусть задали $0.95$

Далее решаем уравнение $P(\text{win}) = 1 - e^{-nP_1(N)} = 0.95$
И получаем пресловутые "три сигма": $nP_1(N) = 3$

$P_1(N)$ - умеет считать "калькулятор шансов" для любого $N$, а толку, если $n$ неизвестно?
Нужно второе уравнение - зависимость $N(n)$.
И тогда: $nP_1(N(n)) = 3$, и всё решается относительно $n$

Для расчета шансов удобнее и правильнее пользоваться $n$ - количество проверенных кандидатов после длинного ифа и без другой фильтрации. Но это совсем не означает, что в программе должен быть именно длинный иф. Зная уровень фильтрации длинного ифа (а он зависит только от набора простых в паттерне и легко считается), можно привести $n$ к $i$ - количеству попыток до\без длинного ифа.

-- 13.10.2025, 17:30 --

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

И насколько я помню, lcm(v)=4.4e26 как раз и есть минимальный при условиях отсутствия кубов (кроме 2) и расстановке наименьших доступных простых в квадратах и наличия 11 проверяемых мест. Дальше его снижать некуда, надо что-то менять в паттернах, что лишь ухудшало по тогдашним оценкам (в основном от VAL).

это так.

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

И никаким выбором что там перебирать (на каком месте простое) уменьшить этот m нельзя - в ускорителях нет /v[ip], они перебирают сразу синхронно все 11 простых на проверяемых местах.

Не очень понимаю, что значит "перебирают сразу синхронно все 11 простых на проверяемых местах"
попробую позже сформулировать развернуый вопрос

-- 13.10.2025, 17:46 --

Запустил программу для расчета $p_1, m$ для программ VAL для одного из паттернов $D(12,15)$

v=[45, 98, 169, 12, 121, 50, 867, 32, 9583, 18, 1805, 4, 1587, 1682, 961]
m= 275825212808131388001600
d=0: [5, 5, 5, 1, 1, 1, 5, 5, 5, 1, 5, 5, 1, 5, 5] OK, p1=12621511795272816702191
d=1: [3, 5, 5, 1, 1, 1, 5, 2, 5, 5, 5, 5, 1, 5, 5]
d=2: [1, 5, 5, 1, 1, 1, 5, 5, 5, 3, 5, 5, 1, 5, 5]
d=3: [5, 5, 5, 1, 1, 1, 5, 2, 5, 1, 5, 5, 1, 5, 5]
d=4: [3, 5, 5, 1, 1, 1, 5, 5, 5, 5, 5, 5, 1, 5, 5]
d=5: [1, 5, 5, 1, 1, 1, 5, 2, 5, 3, 5, 5, 1, 5, 5]

Вопрос: будут ли ускорителем для этого паттерна проверены все (для любого $i$) цепочки вида
$12621511795272816702191 + 275825212808131388001600 \cdot i$
?

[EUgeneUS]

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

опять не понимаю, откуда m=1.93078e24? А, это lcm(v)*6/37^2, но куда-то пропало /7 ... Непонятно.

Понятно же. Опять промахнулся
Исправил, опять стало лучше:

N=   7,85E+34
p1=   12621511795272816702191
m=   275825212808131388001600
паттернов   2880
n=   8,20E+14
n на паттерн   2,85E+11
P(1)=   7,77057994721763E-015
P(win)=   0,998291049

То есть, если программами VAL искать до 7,85E+34 по 2880 паттернам с $7\cdot 37^2$, то рекорд обновится с вероятностью $99,8$ процентов.
Потребуется 8,20E+14 проверок после длинного ифа. Или 1,84E+15 проверок до\без длинного ифа.

[Dmitriy40]

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

Вопрос: будут ли ускорителем для этого паттерна проверены все (для любого $i$) цепочки вида
$12621511795272816702191 + 275825212808131388001600 \cdot i$
?

Да, ускорителем M12-N9-21-162345 с параметрами
v=[45,98,169,12,121,50,867,32,9583,18,1805,4,1587,1682,961]; pp=Mod(120951947534099402457096345, 440538835723387181869888800);

Только цепочки будут другими, Вы написали выражение для $p$, а цепочки $n$ будут
$n=9583 \cdot (12621511795272816702191 + 275825212808131388001600 \cdot i)-8$
и для ускорителя они будут считаться как
$120951947534099402457096345 + 440538835723387181869888800 \cdot j$
(фактически просто раскрытие скобок) для возможно немного другого $j$ (но почти с тем же количеством, разница не более сотен, их VAL зачем-то приплюсовывал к своему p1 и потому j=i-const).

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

Не очень понимаю, что значит "перебирают сразу синхронно все 11 простых на проверяемых местах"

Дело в том что ускорители не проверяют простоту чисел. Вот просто совсем. Они проверяют отсутствие у 11 чисел делителей менее 4096 (и ещё дополнительно условие длинного if).
А для проверки отсутствия делителей вовсе не надо выполнять isprime(), достаточно проверить остатки каждого из чисел по модулю соответствующего простого. Т.е. чтобы для всех 11 чисел одновременно выполнялись выражения $\left(n_{k,p}=\frac{n+k-1}{v[k]}\right) \ne 0 \pmod p$ для всех простых $p=[2\ldots4096]$ и для всех 11 разных $k$ (проверяемые места паттерна).
Подставив сюда формулу для $n=n_0 + m \cdot i$ из ускорителей получим выражения $n_{k,p,i}=\frac{n_0 + m \cdot i+k-1}{v[k]} \ne 0 \pmod p$.
В которых для каждых конкретных $k$ и $p$ при изменении i меняется только часть $\frac{m}{v[k]}\cdot i \pmod p$.
А если мы $i$ считаем строго последовательно, $i=i+1$, как ускоритель внутри и делает, то выражения для $n_{k,p,i}$ можно переписать в виде $n_{k,p,i+1}=n_{k,p,i}+\frac{m}{v[k]} \pmod p$, в котором для получения каждого следующего $n_{k,p,i+1}$ достаточно сделать операцию сложения по модулю, ведь в формулах одни константы (вычисляемые на этапе компиляции ускорителя) и предыдущие посчитанные числа. А операцию сложения по не слишком большому модулю я умею делать быстро, очень быстро, на SSE/AVX2.
В итоге, ускоритель считает одновременно все 11 таких выражений для каждого простого 2-4096 (за некоторыми исключениями) (итого порядка 6000 формул) и проверяет не стало ли любое из них нулём - значит число в соответствующей позиции $k$ кратно соответствующему простому $p$, т.е. такой $n$ не подходит.
Всё.
Все i что не отбросились возвращаем в PARI и пусть мучается с полной факторизацией.

Заметьте, тут сразу 11 делений на v[] (и не в программе, а при компиляции, в программе это просто константы), а не одно, как в программах VAL (которое у него заменено умножением перебираемого простого на v[ip] чтобы получить n, ускоритель же наоборот, из n получает 11 разных p, ну учитывая что реально этого не делает, см.выше), потому делить m=lcm(v) на что-то нет никакого смысла, ведь перебирается не одно число в какой-то позиции, а сразу все 11 чисел по модулям 550 простых 47-4096 (ну или примерно, зависит от реализации).

-- 13.10.2025, 18:53 --

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

То есть, если программами VAL искать до 7,85E+34 по 2880 паттернам с $7\cdot 37^2$, то рекорд обновится с вероятностью $99,8$ процентов.
Потребуется 8,20E+14 проверок после длинного ифа. Или 1,84E+15 проверок до\без длинного ифа.

И опять не понимаю: я же уже сказал что среди 46080 есть 2880 паттернов с $7\cdot37^2$, они все проверены до 1e38 - а Вы снова про какие-то будущие находки ниже 1e35, как так?!

-- 13.10.2025, 19:05 --

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

А если мы $i$ считаем строго последовательно, $i=i+1$, как ускоритель внутри и делает,

И даже не если не строго последовательно, но всегда с постоянным шагом $d$ (например так любимый $d=6$), $i_{t+1}=i_t+d$, то формула не усложняется, усложняется лишь константа, вместо $\frac{m}{v[k]}$ станет $\frac{m d}{v[k]}$, что для ускорителя будет всё той же константой, а $i_0$ будет учтено в начальном значении $n_{k,p,i=0}$, которое разумеется тоже константа (так как от $i$ уже не зависит).
Но это всё внутри ускорителя! Снаружи $i$ видны лишь как множители при lcm(v).

[EUgeneUS]

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

Только цепочки будут другими, Вы написали выражение для $p$, а цепочки $n$ будут
$n=9583 \cdot (12621511795272816702191 + 275825212808131388001600 \cdot i)-8$
и для ускорителя они будут считаться как
$120951947534099402457096345 + 440538835723387181869888800 \cdot j$
(фактически просто раскрытие скобок) для возможно немного другого $j$ (но почти с тем же количеством, разница не более сотен, их VAL зачем-то приплюсовывал к своему p1 и потому j=i-const).

Спасибо за разъяснения. Понял, осознал.
Ошибка была в том, что сегодня для $D(12,15)$ и $D(36,15;14)$ не умножил на $v[ip]$
Вот и разгадка всех чудес.

[Yadryara]

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

Да, конечно, в данном случае согласен с Дмитрием по всем пунктам. Теперь ловить минималки для 12 делителей о-о-очень сложно.

А я тем временем, протестировав нововведения, перешёл уже к счёту. Сделал болванку:

bolv = [2,3971,12,49,50,3,104,1,18,5,28,3,242,1,480,289,2,63,4,845,114];

Паттерн пока ещё обозначаю M, хотя v мне больше нравится. И дальше, формирую уже готовый паттерн с расстановкой квадратов 123456789:

M = bolv;
mdkv = [1,6,7,8,10,12,14,17,21];
r=primes([23,59]);
rass = [1,2,3,4,5,6,7,8,9];
for(i=1,#mdkv, M[mdkv[i]]*=r[rass[i]]^2);

Вроде ошибок пока не замечаю. И уже пара приближений с valids 9 и 10 нашлась. И это весь улов до 1e53.

M = [1058, 3971, 12, 49, 50, 2523, 99944, 1369, 18, 8405, 28, 5547, 242,
 2209, 480, 289, 5618, 63, 4, 845, 396834]

m = 447180315895329581126910934492379272800     a = 396834

d = 0: [5, 1, 1, 1, 1, 5, 5, 5, 5, 5, 5, 1, 5, 5, 5, 1, 1, 5, 1, 1, 5]
p1 = 44247351766878945595325330060830383299
d = 1: [5, 1, 1, 1, 1, 5, 5, 5, 3, 5, 5, 1, 5, 5, 2, 1, 1, 1, 1, 1, 5]
d = 2: [5, 1, 1, 1, 1, 5, 5, 5, 1, 5, 5, 1, 5, 5, 5, 1, 1, 3, 1, 1, 5]
d = 3: [5, 1, 1, 1, 1, 5, 5, 5, 5, 5, 5, 1, 5, 5, 2, 1, 1, 5, 1, 1, 5]
d = 4: [5, 1, 1, 1, 1, 5, 5, 5, 3, 5, 5, 1, 5, 5, 5, 1, 1, 1, 1, 1, 5]
d = 5: [5, 1, 1, 1, 1, 5, 5, 5, 1, 5, 5, 1, 5, 5, 2, 1, 1, 3, 1, 1, 5]

bad = [2, 5, 3, 4, 1, 18, 6, 27, 25, 9, 20, 9, 34, 37, 29]

499     1 1 1  1    11 1 11                9
379    1  1 11 1  1111     1              10