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

[Dmitriy40]

EUgeneUS
Конкретно $m$ не снизит конечно, зато остальные числа станут поменьше - и это и даст выигрыш скорости, ровно как и снижение $m$. Цель ведь не снижение $m$, а уменьшение перебираемых простых $p=p_1+m\cdot i$ (за счёт снижения $m$). Я же предлагаю снижать не только перебираемое простое, но и остальные проверяемые простые на местах $p$.

-- 12.10.2025, 20:52 --

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

Можно ли сделать паттерны для $D(48,21)$ вида "3-0-13-5 (9)" и "4-0-12-5 (9)" такие, чтобы на месте с неизвестным простым стояло $19^2 \cdot 13 \cdot 11 \cdot 7 = 6865859$?

И чисто в принципе можно же и $59^2\cdot19\cdot17\cdot13=14616719$ сделать, наверное ...
Или вообще $2^{23}=8388608$, но это уже изврат.

[EUgeneUS]

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

Цель ведь не снижение $m$, а уменьшение перебираемых простых $p=p_1+m\cdot i$ (за счёт снижения $m$).

Цель - снизить $N$

Вероятность найти цепочку (за одну проверку) с ростом $N$ падает как $1/(\ln(N))^k$, где $k$ - длина цепочки.
Чуть медленнее, там ещё в числителе будет $\ln(\ln(N))$ в какой-то степени, но для грубых оценок можно так считать.
Логарифм, конечно, медленная функция, но в 21-й степени она перестаёт быть медленной, а вечер перестаёт быть томным.
Снижение $m$ на $n$ порядков даёт такой же эффект, как увеличение количества паттернов на $n$ порядков.

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

И чисто в принципе можно же и $59^2\cdot19\cdot17\cdot13=14616719$ сделать, наверное ...

Можно. Но если будем "размножать" паттерны перестановкой необязательных простых, то там будут простые от $23$ до $59$. Оценку, наверное, надо будет сделать для наихудшего с $23^2$.

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

Или вообще $2^{23}=8388608$, но это уже изврат.

А так не получится. Ибо $2^{23}$ раздует LCM.

[Yadryara]

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

Примеры для разных паттернов:

Ну вот я пока взял знаменитый паттерн для D(6,5) :

M = [49, 2, 9, 4, 25]     a = 2     m = 132300

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

Только эти остатки, если пересчитать их по модулю 22050, дают один и тот же остаток 5611 и он не совпадают ни с одним из тех 8-ми, что в статье, а остатки там верные, цепочки по ним находятся.

Соответственно, в результате подстановки в программу этих остатков, ни одного решения не находится. Может, я где-то ошибся.

Согласно терминологии Дмитрия, перебираемое место здесь n+1, что указано как a=2.

Да, я брал не только 6-кратный шаг, но и 1, 2, 3-х кратный. Остаток, если он существует, всё равно 5611 (mod 22050).

[Dmitriy40]

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

Только эти остатки, если пересчитать их по модулю 22050, дают один и тот же остаток 5611 и он не совпадают ни с одним из тех 8-ми, что в статье, а остатки там верные, цепочки по ним находятся.

А то что там перебираемое простое в квадрате Вас конечно не смутило? И формула
$n=a(p=p_1+m\cdot i)^2-1$
ну совсем не похода на формулу
$n=a(p=p_1+m\cdot i)-20$
в части перехода от $n$ к $i$?
Разумеется в таком случае приведённое вычисление остатков по модулю $m$ работать не будет.

[EUgeneUS]

Поиск оптимального паттерна на примере $D(36,15)$.
У меня нашлась в архиве полная система паттернов для $D(36,15)$, построенная pcoul.

1. Минимальное количество неизвестных простых? 10 (и пять $pq$). Дальше ищем среди таких паттернов.
2. Минимизируем $LCM$
2.1. Минимальное количество квадратов необязательных простых - 19.
Оно получается при таких максимальных степенях обязательных простых: $2^8, 3^8, 5^2, 7^2, 11^2, 13^2$
2.2. $3^8$ менять на $3^2$ не выгодно, а с другой стороны, менять $5^2$ на $5^8$ тоже не выгодно.
2.3. $3^8$ должно стоять близко к краю, чтобы влезло два $3^2$.
Далее ищем среди таких.

3. Чтобы в какой-то позиции стояли $11$ или $13$ - нет.
4. Поэтому выбираем, тот, где имеется $7$.

Вот такой, например (в нотации Хуго):

b18483:   3^8   2.7^2   13^2   2^2.3   5   2.11^2   3   2^8   7   2.3^2.5^2   .   2^2   3   2   5

Далее в позицию с $7$ прибиваем гвоздями $89^2 \cdot 97^2$, остальные квадраты необязательных простых как-то расставляем.

5. Получили такое:

6561   675122   1054729   63948   7284245   1086338   4029843   256   521700823   450   1841449   4   7087107   4245698   11506445

<del> ошибся - пропустил квадрат простого в 4-й позиции с конца.
сейчас пересчитаю.

-- 13.10.2025, 12:37 --

Поправил:

6561   675122   1054729   63948   7284245   1086338   4029843   256   521700823   450   1841449   7396   7087107   4245698   11506445

LCM = 3.23028E+45
m = 6*LCM/vp = 6.19183E+36

Для 1 паттерна:
Для кандидатов: 1.00E+14
Вероятность найти 15: 0.60908989
Вероятность найти 14: 0.97990636
N в районе: 6.19E+50

Для 50 000 паттернов
Для кандидатов: 1.00E+14
Вероятность найти 15: 0.987390863
Вероятность найти 14: 0.999999944
N в районе: 1.24E+46

-- 13.10.2025, 12:46 --

Оценка грубая, для более точной, нужно собирать статистику.
"Кандидаты" - это уже после фильтрации Длинным Ифом.

[Yadryara]

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

А то что там перебираемое простое в квадрате Вас конечно не смутило?

А чего там смущаться, бери, да подставляй И ведь не избавиться от квадрата этого вроде. Ну ладно, хоть и не хотелось, но взял вместо пяти три числа подряд по 6 делителей, те которые правее.

Пока посчитал остаток по наибольшему квадрату, то есть по 25 и перебор сделал по нему же. D(6,3) комп находит исправно:

Pattern = [9, 4, 25]

a =     25
m =     36
p1 =    17

T= [[1, 4, 6], [3, 8, 9], [2, 6, 10], [0, 15, 16], [2, 10, 18], [4, 12, 20]]

bad = [3]

start: 0   finish: 1005

1   4923   666
2   58923   666
3   499923   666
4   118323   666
5   469323   666
6   132723   666

2 ms

[EUgeneUS]

Чудные дела происходят...

Попытался сделать анализ для $D(12,15)$

1. Минимальное количество простых - 11. Всего таких паттернов - 64. Все из них требуют подстановки 6 необязательных простых в квадрате. И по всем ним мы и искали пентадекатлон с ускорителями.

2. Выбираем из них паттерны, у которых есть $7$ без других множителей. Всего таких паттернов - 24.
3. Прибиваем к семерке гвоздями $37^2$, остальные пять необязательных простых в квадрате будем перебирать. Итого: $24 \cdot 5! = 2880$. Причем для них ускорители уже есть.
4.

LCM=1.22128E+17
m = 6*LCM/(7 * 37^2) = 5.35256E+14

5. Подставляем в калькулятор "шансов".

Для 1 паттерна:
Для кандидатов: 3.00E+13 (на два-три порядка меньше, чем оценки выполненных проверок!)
Вероятность найти 15: 0.997002749
Вероятность найти 14: 0.999999998
N в районе: 1.61E+28 (на шесть (!) порядков меньше текущего рекорда!)

Для 2880 паттернов:
Для кандидатов: 2.00E+12 (!!!!)
Вероятность найти 15: 0.997571719
Вероятность найти 14: 0.999999982
N в районе: 3.72E+23 (на 11 порядков меньше текущего рекорда!)

Никто не хочет улучшить по-быстрому $D(12,15), D(12,14)$ ?

-- 13.10.2025, 14:22 --

Вот 24 паттерна с семеркой (в нотации Хуго):

(Оффтоп)

ID   1   2   3   4   5   6   7   8   9   10   11   12   13   14   15
b561:   .   2   3.13^2   2^2   5.11^2   2.3^2   7   2^5   3   2.5^2   .   2^2.3   .   2.7^2   3^2.5
b564:   .   2   3   2^2   5.11^2   2.3^2   7   2^5   3.13^2   2.5^2   .   2^2.3   .   2.7^2   3^2.5
b565:   .   2   3   2^2   5.11^2   2.3^2   7   2^5   3   2.5^2   13^2   2^2.3   .   2.7^2   3^2.5
b568:   .   2   3   2^2   5.11^2   2.3^2   7   2^5   3   2.5^2   .   2^2.3   13^2   2.7^2   3^2.5
b583:   .   2   3.13^2   2^2   5   2.3^2   7   2^5   3.11^2   2.5^2   .   2^2.3   .   2.7^2   3^2.5
b585:   .   2   3   2^2   5.13^2   2.3^2   7   2^5   3.11^2   2.5^2   .   2^2.3   .   2.7^2   3^2.5
b587:   .   2   3   2^2   5   2.3^2   7   2^5   3.11^2   2.5^2   13^2   2^2.3   .   2.7^2   3^2.5
b590:   .   2   3   2^2   5   2.3^2   7   2^5   3.11^2   2.5^2   .   2^2.3   13^2   2.7^2   3^2.5
b593:   .   2   3.13^2   2^2   5   2.3^2   7   2^5   3   2.5^2   11^2   2^2.3   .   2.7^2   3^2.5
b595:   .   2   3   2^2   5.13^2   2.3^2   7   2^5   3   2.5^2   11^2   2^2.3   .   2.7^2   3^2.5
b597:   .   2   3   2^2   5   2.3^2   7   2^5   3.13^2   2.5^2   11^2   2^2.3   .   2.7^2   3^2.5
b599:   .   2   3   2^2   5   2.3^2   7   2^5   3   2.5^2   11^2   2^2.3   13^2   2.7^2   3^2.5
b62:   3^2.5   2.7^2   13^2   2^2.3   11^2   2.5^2   3   2^5   7   2.3^2   5   2^2   3   2   .
b66:   3^2.5   2.7^2   .   2^2.3   11^2   2.5^2   3.13^2   2^5   7   2.3^2   5   2^2   3   2   .
b68:   3^2.5   2.7^2   .   2^2.3   11^2   2.5^2   3   2^5   7   2.3^2   5.13^2   2^2   3   2   .
b70:   3^2.5   2.7^2   .   2^2.3   11^2   2.5^2   3   2^5   7   2.3^2   5   2^2   3.13^2   2   .
b88:   3^2.5   2.7^2   13^2   2^2.3   .   2.5^2   3.11^2   2^5   7   2.3^2   5   2^2   3   2   .
b91:   3^2.5   2.7^2   .   2^2.3   13^2   2.5^2   3.11^2   2^5   7   2.3^2   5   2^2   3   2   .
b95:   3^2.5   2.7^2   .   2^2.3   .   2.5^2   3.11^2   2^5   7   2.3^2   5.13^2   2^2   3   2   .
b97:   3^2.5   2.7^2   .   2^2.3   .   2.5^2   3.11^2   2^5   7   2.3^2   5   2^2   3.13^2   2   .
b108:   3^2.5   2.7^2   13^2   2^2.3   .   2.5^2   3   2^5   7   2.3^2   5.11^2   2^2   3   2   .
b111:   3^2.5   2.7^2   .   2^2.3   13^2   2.5^2   3   2^5   7   2.3^2   5.11^2   2^2   3   2   .
b114:   3^2.5   2.7^2   .   2^2.3   .   2.5^2   3.13^2   2^5   7   2.3^2   5.11^2   2^2   3   2   .
b117:   3^2.5   2.7^2   .   2^2.3   .   2.5^2   3   2^5   7   2.3^2   5.11^2   2^2   3.13^2   2   .

Проверьте, пожалуйста, я в расчете $m$ не накосячил?
И с каким $m$ искали пентадекатлон?

-- 13.10.2025, 15:14 --

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

первый поиск проверил не менее 66387422053662391209161093722597723545 / 440538835723387181869888800 = 1.5е11 кандидатов для каждого из 46080 паттерна;

Я же правильно понимаю, что шаг поиска был 440538835723387181869888800?

[Dmitriy40]

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

И с каким $m$ искали пентадекатлон?

А Вы какое $m$ имеете в виду, то что у VAL или то что у меня в ускорителях? Проги VAL работают в пространстве p и у него m=lcm(v)*6/v[ip] и зависят от выбора перебираемого места, мои ускорители работают в пространстве n и m=lcm(v) независимо от того что перебирается (да и перебирается сразу n), у него m домножается на 6, у меня это спрятано в ускорителе.
Вот почему я и говорил что сравнивать удобнее только по n, сколько там разных вариантов надо перебрать и в каком диапазоне, а не по p и m, которые зависят от выбора какое место перебирать.

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

Я же правильно понимаю, что шаг поиска был 440538835723387181869888800?

Смотря что Вы понимаете под шагом поиска. Это lcm(v). Но разумеется проверялись только каждый шестой i в формуле n=n0+m*i. Но это было спрятано в ускорителе и PARI программа об этом не знала и выдавала диапазон по i именно с таким m невзирая на это уменьшение перебора, просто ускоритель работал вшестеро быстрее.

[EUgeneUS]

А вот для $D(12,15)$ для $m=440538835723387181869888800$

m= 440538835723387181869888800
патернов= 46080
кандидатов 2.00E+15
N= 1.91E+37
P(1) 2.87885E-15
P(win) 0.996841653

С учётом того, что было найдено больше одной цепочки до $10^{38}$, а так же того, что число кандидатов - это количество проверок после Длинного Ифа (нужно умножить на 2 - 2.5), всё оказалось очень похоже на правду.
А значит и предыдущие расчеты близки к правде и можно быстро и сильно улучшить $D(12,15), D(12,14)$

-- 13.10.2025, 15:25 --

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

А Вы какое $m$ имеете в виду, то что у VAL или то что у меня в ускорителях?

То, с которым искали пентадекатлон до успеха.

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

мои ускорители работают в пространстве n и m=lcm(v) независимо от того что перебирается (да и перебирается сразу n), у него m домножается на 6, у меня это спрятано в ускорителе.

Тогда для быстрого улучшения $D(12,15), D(12,14)$ нужно будет переделать ускорители так, что бы m=6*lcm(v)/(7*37^2). Для 2880 паттернов.
И цепочка найдется в 100-1000 раз быстрее И сильно короче имеющегося рекорда.

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

Вот почему я и говорил что сравнивать удобнее только по n, сколько там разных вариантов надо перебрать и в каком диапазоне, а не по p и m, которые зависят от выбора какое место перебирать.

В калькуляторе шансов, всё очень сильно зависит от $N$, а $N$ рассчитывается через $p_1, m, i$.
В общем нужна связь между $N, p_1, m, i$.

[Dmitriy40]

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

LCM=1.22128E+17
m = 6*LCM/(7 * 37^2) = 5.35256E+14

Как это у Вас получилось?
lcm(v)=440538835723387181869888800
lcm(v)*6=2643233014340323091219332800
lcm(v)/(31*29*23*19*17)^2=9876523456800
lcm(v)/(31*29*23*19*17*37)^2=7214407200
lcm(v)/7/37^2*6=275825212808131388001600

[EUgeneUS]

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

Как это у Вас получилось?

Промахнулся ячейкой в Экселе.
Сейчас пересчитаю.

-- 13.10.2025, 15:49 --

Да, всё стало не так радужно

m= 1.93078E+24
патернов = 2880
кандидатов 1.00E+15 (всего в 10 раз меньше)
N= 6.70E+35 (что уже почти в 10 раз больше имеющегося рекорда)
P(1) 2.87885E-15
P(win) 0.996841653

То есть ускорение есть. И хорошее (за счет уменьшения количества проверок примерно на порядок).
Но рекорд уже вряд ли обновится.

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

-- 13.10.2025, 15:49 --

Dmitriy40
Спасибо за внимательность. Вот не зря попросил расчет проверить

[Dmitriy40]

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

В общем нужна связь между $N, p_1, m, i$.

Для программ VAL или для ускорителей? Если первое, то с каким перебираемым местом из 11 для M12n15?
Для ускорителей p1 и m указаны прямо в exe файле, если его открыть блокнотом (или FAR), то почти в конце будет табличка типа такой:

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

============================================================================================================================
        n+0     n+1     n+2     n+3     n+4     n+5     n+6     n+7     n+8     n+9     n+10    n+11    n+12    n+13    n+14
        45      722     841     12      49      50      507     32      961     18      605     28      867     1058    1369
p=Mod(438957010505237256671215545,440538835723387181869888800)
Decycle: 2 3 41 43 - repeats=10578
Check by index: 5 7 11 13 17 19 23 29 31 37
Numbers: 11
Primes up to 4093
============================================================================================================================

Тут указан конкретный паттерн, p1 и m в форме Mod(p1,m), "разворачиваемые" простые (проверки по которым время не тратят так как берутся напрямую из таблицы, как видите здесь всегда есть 2 и 3), список простых проверяемых по индексу (длинный if), количество проверяемых мест, по каким простым производится фильтрация.

-- 13.10.2025, 15:56 --

EUgeneUS
Про обновление рекорда тоже не понял. Вы говорите это можно сделать с уже готовыми ускорителями, так? Но ведь ими проверено тотально всё до n<1e38! По всем 46080 паттернам. И ничего нового до n<1e38 найдено быть не может. Про какое тогда обновление рекорда Вы?

-- 13.10.2025, 15:59 --

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

В общем нужна связь между $N, p_1, m, i$.

Так ведь для программ VAL я много раз только что её показывал: N=v[ip]*(p1+m*i)-ip, m=lcm(v)*6/v[ip], где ip индекс (с нуля) в паттерне перебираемого простого. p1 у него в коде обычно другой, но это мелочи и его личные тараканы, идеологически формулы должны быть такими. В скобках это фактически перебираемое простое, которое проверяется на простоту ещё до вычисления N.
А для ускорителей всё проще: N=p1+m*i, m=lcm(v) (и ускоритель не проверяет 5 из каждых 6 i, но это его личное дело и не надо к нему лезть) и никаких простых он не перебирает, ну или перебирает сразу все 11 простых что тоже самое, и выдаёт из себя лишь те N (в виде соответствующих i) в которых все 11 проверяемых чисел псевдопростые (не имеют делителей меньше 4094).

[Yadryara]

EUgeneUS
Лень мне пока по новой вникать так подробно в 12 делителей. Но совет, которому сам стараюсь следовать, банален: идти от простого к сложному. Я же не зря вернулся опять к всего лишь 6 делителям. Это помогло разобраться. Ни Длинного Ифа нет, ни порой даже короткого

А ведь и к 4-м делителям недавно возвращался. В общем надо нащупать твёрдую почву под ногами, чтоб разные методы оценки одного и того же сходились, а для этого неплохо бы упростить расчёт.

[EUgeneUS]

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

Для программ VAL или для ускорителей?

Для любого способа, который хотим оценить с помощью "калькулятора шансов".

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

Если первое, то с каким перебираемым местом из 11 для M12n15?

В том варианте, в котором оценивал - для места с $7 \cdot 37^2$

-- 13.10.2025, 16:11 --

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

Вы говорите это можно сделать с уже готовыми ускорителями, так?

Уже нет. Я не знал некоторых деталей про ускорители.

После всех уточнений и исправлений ошибок, про обновление рекорда:

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

То есть ускорение есть. И хорошее (за счет уменьшения количества проверок примерно на порядок).
Но рекорд уже вряд ли обновится.

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

И будут нужны новые ускорители для 2880 паттернов с $m = 6 \cdot lcm/(7 \cdot 37^2)$

[Dmitriy40]

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

И будут нужны новые ускорители для 2880 паттернов с $m = 6 \cdot lcm/(7 \cdot 37^2)$

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

-- 13.10.2025, 16:17 --

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

В том варианте, в котором оценивал - для места с $7 \cdot 37^2$

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

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

Так ведь для программ VAL я много раз только что её показывал: N=v[ip]*(p1+m*i)-ip, m=lcm(v)*6/v[ip], где ip индекс (с нуля) в паттерне перебираемого простого. p1 у него в коде обычно другой, но это мелочи и его личные тараканы, идеологически формулы должны быть такими. В скобках это фактически перебираемое простое, которое проверяется на простоту ещё до вычисления N.

-- 13.10.2025, 16:28 --

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

И будут нужны новые ускорители для 2880 паттернов с $m = 6 \cdot lcm/(7 \cdot 37^2)$

Ускорителей с числом в паттерне 7*37^2=9583 уже было сделано 2880шт (среди 46080). Зачем новые? И чем новые отличаются от этих? И что новые должны дать?

-- 13.10.2025, 16:33 --

EUgeneUS
Мне кажется у Вас путаница с N и m в расчётах. Делайте расчёт всегда по N, забудьте про m, так разночтений не должно быть. А уж сколько там будет попыток/кандидатов/проверок - зависит от реализации и способа подсчёта их количества.