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

[VAL]

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

Проще было исправить только nu[].

Я понимаю, что вместо укорачивания цикла можно было подправить n[u].
Но вопрос в быстродействии. Неполное разложение с помощью factor(n, 300000), конечно, гораздо быстрее, чем numdiv().
Но прохождение предыдущих фильтров и 6-и проверок с ограниченной факторизацией событие достаточно редкое.
И вполне вероятно, что выгоднее иногда зависать над numdiv(), чем ГОРАЗДО ЧАЩЕ тратить время на factor() c ограничениями.

[Dmitriy40]

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

И вполне вероятно, что выгоднее иногда зависать над numdiv(), чем ГОРАЗДО ЧАЩЕ тратить время на factor() c ограничениями.

Не согласен, счётчики же показывают что factor вызывается не столь уж чаще numdiv, а выполняется после трёх isprime достаточно быстро (тем более что я обычно делю диапазон на два или больше, до 3e4, потом до 3e5, потом до 16e6 (порог "больших" простых для PARI) - первый из них вообще моментально отрабатывает и отсеивает точно неподходящие). Ну а экономить секунды из многих часов я не намерен, это уже извращение (корректно называемое переоптимизацией).
Удлините nu[] до правильного и сравните время выполнения.

Я даже прямо скажу, добавление ЕЩЁ ОДНОГО цикла с factor(...,30000) перед циклом с factor(...,300000) УСКОРЯЕТ Вашу программу (во всяком случае M48n20, которая и тестировалась). Не говоря уж про оставление всё до numdiv.

[Yadryara]

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

Это сколько простых должно быть в разложении в позиции u[]. Начиная с nu[7] содержимое ошибочное. Правильное: nu=[3,3,3,4,3,3,4,3,3,4,3,3,4,4,3,3,4,3].

Ну то бишь оставшееся разложение имеется в виду, после обязательного и произвольного? То есть pqr --> 3, а pqrs --> 4? Но тогда, глядя на паттерн для 21-ки, который я опубликовал выше, получается другой nu=[3,3,3,4,3,3,4,3,3,3,3,3,4,4,3,3,4,3]. Как полагается, с 5-ю 4-ками.

[VAL]

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

Удлините nu[] до правильного и сравните время выполнения.

Вполне возможно, что так и сделаю. Когда и если вернусь к регулярному использованию этих программ.
Сейчас меня гораздо больше смущает вопрос, откуда вообще взялся странный хвост массива nu[].
Естественным объяснением кажется такое: переделывал nu[] из u[] и в этот момент меня что-то отвлекло.
Но я же потом растиражировал программку на 4 разных шаблона. И гонял несколько раз. И не заметил странного хвоста у nu[]?!

[Dmitriy40]

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

Но тогда, глядя на паттерн для 21-ки, который я опубликовал выше, получается другой nu=[3,3,3,4,3,3,4,3,3,3,3,3,4,4,3,3,4,3]. Как полагается, с 5-ю 4-ками.

Согласен, с местом +10 я ошибся, там лишь $pqr$. Руками же расставлял ...
А надо было вычислять: nu=[valuation(48/numdiv(M[t]),2) | t<-u]. Вообще константы - зло! Всё что можно вычислить - и надо вычислять!
И u=Vec(select(t->numdiv(t)<24,M,1)) тоже.

[VAL]

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

Ну так для неправильных мест не нашлось достаточно (сколько указано в nu[]) делителей до 300000, вот и срабатывало условие na<nu[j].

Там все хитрее. Условие накрученное и истинность na<nu[j] еще не гарантирует окончательного значения всего логического выражения. Насколько я понимаю, это может привести (а может и не привести) к потере перспективных кандидатур.

[Dmitriy40]

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

И вполне вероятно, что выгоднее иногда зависать над numdiv(), чем ГОРАЗДО ЧАЩЕ тратить время на factor() c ограничениями.

Исходный код выполнил 10млн итераций за 54.065с, счётчики s,t при этом 326,3.
Укорочение nu[] до 6 замедлило до 92.477c, счётчики 326,27. Вот такая Ваша коррекция программы ...
Удлинение nu[] до правильного ускорило до 53.541с, счётчики 326,0.
Т.е. быстрая (относительно numdiv) проверка мест u[] ВЫГОДНА. В данном тесте она исключила вообще все проверки numdiv (1% кандидатов после всех isprime). И разница в скорости как раз похожа на 1%.
И кстати можно легко проверять что не встретилось не только слишком много простых в первой степени до 3e5, но и вообще любых неподходящих вариантов разложений, это ещё исключит сколько-то кандидатов (и вероятно не 1-2).

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

Там все хитрее. Условие накрученное и истинность na<nu[j] еще не гарантирует окончательного значения всего логического выражения. Насколько я понимаю, это может привести (а может и не привести) к потере перспективных кандидатур.

Вижу. Но равенство na числам выше 7 слишком редко (а выше 15 и вообще невероятно) чтобы учитывать, я же выше приводил табличку где конечно и 10 чисел в первой степени были, но сколько их там было то, сотые процента, причём для чисел порядка 1e98, а не 1e38, в этих столь много делителей невероятнее.

[EUgeneUS]

Анализ перспектив поиска D(48,21) по паттерну

M =  [3698, 3971, 12, 49, 50, 5043, 362024, 529, 18, 4805, 28, 4107, 242, 841, 480, 289, 4418, 63, 4, 845, 320226]

отсюда.

Расчет в предположении "эффективной предварительной фильтрации" (все заведомо "бракованные" цепочки выкидываются, все "не бракованные" - не выкидываются).

1. С учетом приведенных в коде m, p1, i1, i2 поиск производится в районе $N \approx 2.77 \cdot 10^{50}$. При этом, на диапазоне $i_1, i_1+i_2$ разрядность $N$ не меняется.
2. Для $N \approx 2.77 \cdot 10^{50}$ "базовые вероятности" (без поправочных коэффциентов):

Для $p$: $[0.00863775,0.009582335]$
Для $pqr$: $[0.097512059,0.103502185]$
Для $pqrs$: $[0.15444672,0.160353878]$

3. Поправочный коэффициент для простых: $b_1 = 7.599514588$

4. Вероятности найти простое (только для мест, где нужны простые):
$i=7, \hat{p}_7=0.072821096$
$i=15, \hat{p}_{15}=0.068474101$
$i=21, \hat{p}_{21}=0.072735597$

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

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

Пока выглядит безнадёжным.
Более-менее перспективный путь - набирать миллионы-десятки миллионов "похожих" шаблонов (за счет перестановок простых и симметричных) и снижать $i$ на 6-7 порядков.

-- 09.10.2025, 12:12 --

Будет ли этот путь перспективным:
а) а сколько вообще реально сделать проверок за разумное время?
Если $10^{14} ... 10^{15}$ - реально,
б) то будет нужно посмотреть на рассчитанные по статистике $b_3, b_4$

Если сделать $10^{14} ... 10^{15}$ проверок нереально, то тема бесперспективна.

[VAL]

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

Исходный код выполнил 10млн итераций за 54.065с, счётчики s,t при этом 326,3.
Укорочение nu[] до 6 замедлило до 92.477c, счётчики 326,27. Вот такая Ваша коррекция программы ...
Удлинение nu[] до правильного ускорило до 53.541с, счётчики 326,0.

У меня тоже завершилось сравнительное тестирование.
Самое поразительное, что результат по времени тоже оказался не в пользу усеченного фильтра nu[]

На заключительную проверку при усеченном nu[] было допущено 1374 цепочки против 22 при полном.

[Dmitriy40]

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

Самое поразительное, что результат по времени тоже оказался не в пользу усеченного фильтра nu[]

Не вижу в этом ничего поразительного, так и должно быть: чем больше кандидатов отбрасываются как можно раньше, до долгих проверок, тем быстрее работает.

VAL
А замена if(ispseudoprime(x), ...) на if(!ispseudoprime(x,1),next) во всех трёх местах даёт ускорение с 52.5с до 45.5с. Вообще просто. Но придётся в самом конце (перед numdiv или прямо им же) допроверить эти места до точно простых.

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

а) а сколько вообще реально сделать проверок за разумное время?
Если $10^{14} ... 10^{15}$ - реально,
б) то будет нужно посмотреть на рассчитанные по статистике $b_3, b_4$

Если сделать $10^{14} ... 10^{15}$ проверок нереально, то тема бесперспективна.

На PARI - можно, но долго: вот же 10млн за примерно полминуты (если применить все методы ускорения), значит 1e14 за 1e14/1e7*30с=3e8 секунд или лет 10 в один поток. Набрав полсотни потоков можно справиться за разумное время в пару месяцев.
С ускорителями - вопрос, три проверяемых места им маловато, выигрыш будет всего в разы, не сотни и не десятки. Но плюс время компиляции, считаем по 10с (с запасом) на вариант, 9! даёт сразу полтора месяца в один поток.

[VAL]

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

Не вижу в этом ничего поразительного

А смайлик видите?

[EUgeneUS]

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

вот же 10млн за примерно полминуты (если применить все методы ускорения),

Значит имеет смысл оценить $b_3, b_4$

Для этого нужна программа, которая:
1. Пробегает, скажем, миллион цепочек, не увеличивая разрядность чисел.
2. Ещё можно уменьшить разрядность, чтобы факторизация быстрее считалась.
В терминах программы из этого поста можно выбрать:

i1=10^8; i2=10^6

тогда числа будут вблизи $(5.54 ... 5.6) \cdot 10^{46}$
3. Предварительная фильтрация должна быть максимально эффективна и выполняться так, как предполагается при "боевом" запуске.
4. В каждой проверке для каждого места в паттерне проверяются попадания в $p, pq, pqr, pqrs, p^3r, p^3rs$ (остальные не интересны).
5. Результат: для каждого места в паттерне выводятся количества попаданий в $p, pq, pqr, pqrs, p^3r, p^3rs$.

Могу попробовать собрать из того, что Вы размещали на прошлой странице. Но у меня это будет не быстро, и скорее всего с ошибками
(основные проблемы будут, скорее всего с пунктом 3).
Запустить у себя, конечно, смогу.

[Dmitriy40]

EUgeneUS
На интервале 1e5 после фильтрации по одиночным простым за 0.5с остаётся 13 цепочек, которые потом раскладываются за 27с, можно считать в среднем по 2с на цепочку.
На интервале 1e6 остаётся 127 цепочек, на интервале 1e7 за 49с (без разложения) остаётся 1275 цепочек.

Добавка отсева по простым до 3e5 для интервалов 1e5, 1e6, 1e7 ускоряет до 0.4с, 4с, 40с, не оставляя для разложения ничего.

Проверка интервала 1e8 занимает 432с и оставляет после фильтрации 5 кандидатов (на разложение которых потрачено 17с). Можно считать в среднем по 86с на кандидата на 2e7 интервала.
Статистика по ним:

i=114541278, p=63474194087062156045389257456820216802374841091, n=20326087275723565981790820358367710745757285863206546
i=123701835, p=68550605874510499952607088296106439286487467491, n=21951686316770999357823557456708980626954735764772946
i=155548262, p=86198613240319500487411622880813178892610917891, n=27603037123494552363081874348631281024065223792563346
i=194266133, p=107654498153136963286158024801057296604795037091, n=34473769325586437205273239649943373862567095547502546
i=199271017, p=110428003315804650114342381503630097181351193891, n=35361917789806859887515403459381451499995367414939346
h=[0, 0, 5, 5, 5, 5, 5]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], sum=0, pows=[1]
[1, 0, 2, 1, 0, 2, 0, 2, 2, 2, 1, 2, 2, 0, 0, 1, 1, 1, 0, 0, 0], sum=20, pows=[1, 1]
[3, 5, 0, 2, 5, 3, 0, 1, 2, 2, 2, 3, 2, 2, 0, 1, 4, 2, 3, 3, 0], sum=45, pows=[1, 1, 1]
[1, 0, 3, 1, 0, 0, 0, 1, 0, 0, 1, 0, 1, 2, 0, 3, 0, 2, 1, 2, 0], sum=18, 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]

Т.е. есть 20 вариантов pq, 45 вариантов pqr и 18 вариантов pqrs, других среди этих 5 кандидатов не встретилось.

Чтобы набрать статистику хотя бы 1e4 кандидатов надо 2e11 интервал и 1e4*86с=86e4c или 10 дней. Ну пусть 1e11 интервал и 5 дней. Ну пусть даже в 4 моих потока, чуть больше суток. Неохота, предлагаю запустить Вам, готовую программу пришлю личкой.

-- 09.10.2025, 15:50 --

Ошибся, фильтрация ещё лучше указанной выше, там я не учёл фильтрацию по $pqrs$, только по $pqr$.
Т.е. ждать статистики ещё дольше.

[EUgeneUS]

Dmitriy40
Что-то жуткая какая-то фильтрация.
Видимо, под "предварительной фильтрацией" мы понимаем разное.

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

Неохота, предлагаю запустить Вам, готовую программу пришлю личкой.

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

-- 09.10.2025, 16:27 --

А не замахнуться ли нам на Уильяма, нашего, Шекспира? (с)

Взял первый попавшийся паттерн для D(36,15) с пятью $pq$ (больше не бывает) и десятью $p$, и прокрутил его через эту методу.

Текущая цепочка длиной 13 найдена в районе $1.04 \cdot 10^{72}$
Поэтому для оценки добавил ещё 6 порядков, до $N=10^{78}$

Для простых (с эффективной предварительной фильтрацией) вероятность попасть получается от $0.049$ до $0.053$. Что очень неплохо.
Для $pq$ оценку вероятности взял от фонаря - $0.15$. Примерно в три раза больше, чем для $p$ - грубо, но вроде бы адекватно.

Оценивал вероятности, как найти 15-шку, так и для 14 (не попали в края).
Получилось:
Для 15-шки, вероятность найти за один раз: 1.16675E-17. Это требует 8.57083E+16 проверок.
Для 14-шки, вероятность найти за один раз: 2.97782E-16. Это требует 3.35816E+15 проверок.

С учетом того, что
а) для пентадекатлона выполнили порядка $10^{16}$ проверок.
б) имеется 10 простых - ускорители будут эффективны. (это не 11 простых, как для пентадекатлона, но всё таки).
в) имеются знания, как запускать проверки более эффективно.
всё это выглядит вполне перспективным, при 20-30 потоков.

[Dmitriy40]

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

Что-то жуткая какая-то фильтрация.
Видимо, под "предварительной фильтрацией" мы понимаем разное.

Поясню как там у VAL всё устроено (рассказ по присланному моему коду, но он весьма близок к его):
сначала отфильтровываем такие i, которые дают степень размещённых простых более квадрата (кроме двойки и тройки), это длинный if;
потом отфильтровываем такие i что простое 61...523 попадает на проверяемые места, где должно быть очень большое простое, это цикл по массивам T[],P[] с setsearch у VAL и bittest у меня с Yadryara, количество оставшихся подсчитывается в h[1];
потом отфильтровываем если перебираемое число точно составное (но не обязательно иначе точно простое), количество оставшихся подсчитывается в h[2];
потом отфильтровываем если другие два простых числа точно составные (любое из, и не обязательно иначе точно простое), количество оставшихся подсчитывается в h[3];
потом отбрасываем кандидаты при частичном разложении которых обнаружены делители до 3e4 и при этом они не могут дать 48 делителей даже если доразложить до конца (да, factor(,30000) оказалось быстрее ispseudoprime, VAL, Вам на заметку), количество оставшихся подсчитывается в h[4];
потом отбрасываем если на любом месте $pqr$ или $pqrs$ оказалось $p$ (потому что ispseudoprime быстрее factor(,300000)), количество оставшихся подсчитывается в h[5];
потом отбрасываем если на любом месте $pqr$ или $pqrs$ при частичном разложении (с делителями до 3e5) уже точно не даст 48 делителей, количество оставшихся подсчитывается в h[6];
потом отбрасываем кандидата если на трёх проверяемых местах оказалось таки не простое, количество оставшихся подсчитывается в h[7];
и только после этого начинается полное разложение кандидата.

Если считаете что проверки h[4..6] лишние, то можно убрать всё между n=a*p-20 и h[6]++ (h[7] проверка фактически дублирует h[2] и h[3] проверки, просто те немного быстрее, но иногда ошибаются на составных числах считая их простыми, что в h[2] и h[3] проверках никак не мешает ведь они срабатывают лишь на точно составные числа).