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

[Yadryara]

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

Я правильно помню, что для M12n15 в шаблонах было 11 $p$ и 4 $pq$?

Нет, в паттернах по которым считали, как правило было 11 $p$ и 4 $qr$

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

удалось достичь 38-процентного ускорения именно на PARI.

Теперь уже 303 секунды на 100млн и 44% ускорения. Кстати, вот такая забавная конструкция позволяет сбросить 5 секунд:

if(bittest(0X57FBBF7DEFEDFF3FF3FEDFDEFBF77FAFFDFF, i%143) &&

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

[Yadryara]

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

Кстати, стоит ли показать как на PARI вычислить константы для длинного if и для T[]?

Конечно. Раньше ведь chinese был в самой проге. Это облегчит ту самую адаптацию.

[EUgeneUS]

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

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

писал(а):
Я правильно помню, что для M12n15 в шаблонах было 11 $p$ и 4 $pq$? Да.

тогда у меня вероятности не сходятся на 5-8 порядков.

Оценка 1.
Мы тогда втроем проверили почти всё до $10^{38}$ и нашли 3 пентадекатлона в $(1..10) \cdot 10^{37}$
До $10^{38}$ должно быть выполнено проверок (если правильно понимаю):
$(10^{38}/440538835723387181869888800)\cdot 46080 \approx 10^{16}$
И оценка вероятности найти пентадекатлон за одну проверку: $3/10^{16} = 3 \cdot 10^{-16}$

Оценка 2.
Забываем про четыре места с $pq$ (они ещё уменьшат вероятность на 3-4 порядка) и просто считаем вероятность найти 11 простых:
$(\frac{1}{\ln(10^{38})})^{11} \approx 4.3 \cdot 10^{-22}$
это заниженная оценка, так как простые ищутся не в районе $10^{38}$
скидываем 5 порядков (с запасом):
$(\frac{1}{\ln(10^{33})})^{11} \approx 2.1 \cdot 10^{-21}$
Это уже завышенная оценка.

И это никак не бьётся с $3 \cdot 10^{-16}$ из "Оценка 1".

Не могу понять, ЧЯДНТ

[Yadryara]

Ну во-первых, я вот только-только приводил частотности. Возводим в степень и перемножаем:

$$0.06^{11}\cdot0.25^4 \approx 1.4\cdot 10^{16}$$

[Dmitriy40]

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

тогда у меня вероятности не сходятся на 5-8 порядков.

Скорее всего из-за не учёта взаимозависимости простых. Например цепочку из 19 простых n19d252 мы нашли около $9.4\cdot10^{24}$ за менее $6\cdot10^{17}$ проверок, хотя наивная вероятность $\frac{1}{\ln^{19}(10^{25})} \approx 3.6\cdot10^{-34}$.

Yadryara
Минус в показателе потеряли.

[EUgeneUS]

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

$$0.06^{11}\cdot0.25^4 \approx 1.4\cdot 10^{16}$$

И откуда у Вас $0.6$, если даже для 33-значных чисел $P(N=p) = \frac{1}{\ln{10^{33}}} \approx 0.013$?

-- 02.10.2025, 19:11 --

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

Скорее всего из-за не учёта взаимозависимости простых.

Всё указывает на то. Но тогда это ставит под сильное сомнение вот это

Цитата:

In mathematics, Probabilistic number theory is a subfield of number theory, which explicitly uses probability to answer questions about the integers and integer-valued functions. One basic idea underlying it is that different prime numbers are, in some serious sense, like independent random variables. This however is not an idea that has a unique useful formal expression.

И совершенно не понятно, как бы это можно было использовать....

-- 02.10.2025, 19:15 --

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

хотя наивная вероятность $\frac{1}{\ln^{19}(10^{25})} \approx 3.6\cdot10^{-34}$.

В оценке $10^{25}$ нужно уменьшать на несколько порядков, так как простые ищутся не в числах цепочки, а на несколько порядков меньше. Но это не спасает. Различие вероятностей оказывается всё равно гигантским.

[Yadryara]

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

И откуда у Вас $0.6$

Ну что, всё по-новой?

Во-первых, не $0.6$, а $0.06$

Во-вторых, вот, например, оценка:

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

Паттерны, в которых нужна простота 11 чисел, перспективнее. Конечно, проверка на простоту быстрее, но вероятность, что число из интересующего нас диапазона окажется произведением двух простых в 4 с лишним раза выше.

$0.25$ как раз в 4 с лишним раза больше чем $0.06$.

[EUgeneUS]

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

Ну что, всё по-новой?

ОМГ!
Есть две оценки.
1. "На реальных данных".
2. Теоретическая, в предположении, что вероятность найти подходящее число в разных местах цепочки независима.

И эти оценки вероятности "не бьются" на много порядков. Вот в чём вопрос.
А не в том, что вероятность попасть $pq$ в четыре раза больше, чем в вероятность попасть в $p$.

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

$0.25$ как раз в 4 с лишним раза больше чем $0.06$.

Грубая оценка (без учёта, что $pq$ не содержит малых простых, которые уже есть в шаблоне), вероятность попасть в $pq$ больше чем вероятность попасть в $p$: $\ln(\ln(N))$. Что на диапазоне $10^{20}...10^{40}$ даёт $3.8 ... 4.5$

[Dmitriy40]

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

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

Кстати, стоит ли показать как на PARI вычислить константы для длинного if и для T[]?

Конечно. Раньше ведь chinese был в самой проге. Это облегчит ту самую адаптацию.

Вот что получилось на примере выложенной M48n21:

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

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]]," && "),",");

Есть проблема: никак не соображу как автоматически вычислить 5/6*m для p1, т.е. когда он нужен именно 5%6, а когда 1%6. Вроде откуда берётся понятно, но вот формулой задать дял произвольного v[] что-то не получается, позабыл уже всё ...
Ещё непонятно почему не меняются T и if при смене ip (перебираемого места), вроде должны же (ip в формулы входит), ан нет ... Или я где-то ошибся, или формулы можно упростить исключив ip.
И мелкая неясность почему пропускаются первые 54 значения i (в p1 стоит +54*m), вероятно они были проверены отдельно. Это можно безопасно грохнуть, правда константы могут измениться.

[Yadryara]

Dmitriy40, вот поэтому я и начал вспоминать расклады для маленьких количеств делителей. Чтоб проще было разобраться.

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

И эти оценки вероятности "не бьются" на много порядков.

Значит как минимум одна из них неверна.

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

А не в том, что вероятность попасть $pq$ в четыре раза больше, чем в вероятность попасть в $p$.

Не надо голову морочить. Я отвечаю на вопросы. Меня спросили откуда взялась оценка, я ответил. И не голословно, а на основании цитаты VAL на 6-й странице. Человек давно в теме и знает что говорит.

Если по-прежнему непонятно, то поскольку вопрос уже обсуждался и обсчитывался неоднократно, можно ещё поискать цитаты. Поэтому я и сказал "по новой".

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

Есть две оценки.
1. "На реальных данных".
2. Теоретическая, в предположении, что вероятность найти подходящее число в разных местах цепочки независима.

И эти оценки вероятности "не бьются" на много порядков.

Когда появились эти оценки? Почему раньше оценки сходились, а сейчас вдруг не сходятся?

Раньше-то они у вас сходились?

У меня сходились с точностью до порядка и, скорее всего, об этом написано в теме.

Мне нужно по новой рассказывать, потому что кое-кто не может или не хочет внимательно перечитать тему?

[EUgeneUS]

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

Мне нужно по новой рассказывать, потому что кое-кто не может или не хочет внимательно перечитать тему?

Перечитать внимательно тему на 230+ страниц? Серьёзно?

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

Если по-прежнему непонятно, то поскольку вопрос уже обсуждался и обсчитывался неоднократно, можно ещё поискать цитаты. Поэтому я и сказал "по новой".

...

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

Когда появились эти оценки? Почему раньше оценки сходились, а сейчас вдруг не сходятся?

Раньше-то они у вас сходились?

У меня сходились с точностью до порядка и, скорее всего, об этом написано в теме.

Вопрос о вероятностях поднимался неоднократно, но никогда не был не решён до конца. А именно: нет ответа на вопрос, как рассчитать вероятность найти цепочку при однократной проверки по известному паттерну?
Поэтому, не знаю, что и куда у Вас "сходилось".

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

Не надо голову морочить. Я отвечаю на вопросы.

Вы отвечаете на вопросы, которые не задавались, а на которые задавались - не отвечаете. Так что, да, не надо голову морочить.

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

И не голословно, а на основании цитаты VAL на 6-й странице. Человек давно в теме и знает что говорит.

Уважаемый VAL, конечно, "в теме" и знает что говорит. Вот только на 6-й странице темы он не приводит оценку вероятность найти простое в виде $0.06$.

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

Значит как минимум одна из них неверна.

Да, ладно. Не может такого быть.

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

[Yadryara]

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

Перечитать внимательно тему на 230+ страниц? Серьёзно?

Серьёзно. Я недавно перечитывал.

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

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

Вопрос о вероятностях поднимался неоднократно, но никогда не был не решён до конца.

Однако же с точностью до порядка он был решён.

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

А именно: нет ответа на вопрос, как рассчитать вероятность найти цепочку при однократной проверки по известному паттерну? Поэтому, не знаю, что и куда у Вас "сходилось".

А я знаю.

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

Вы отвечаете на вопросы, которые не задавались, а на которые задавались - не отвечаете.

На какие вопросы я не ответил?

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

Уважаемый VAL, конечно, "в теме" и знает что говорит. Вот только на 6-й странице темы он не приводит оценку вероятность найти простое в виде $0.06$.

А оценку $0.24$ VAL в теме приводил? $0.06$ в 4 раза меньше чем $0.24$?

[EUgeneUS]

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

А оценку $0.24$ VAL в теме приводил? $0.06$ в 4 раза меньше чем $0.24$?

Третий раз повторяю. Не интересует $0.24$, с этим числом всё понятно. Интересует откуда взялось $0.06$
Вот я и говорю:

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

Вы отвечаете на вопросы, которые не задавались, а на которые задавались - не отвечаете. Так что, да, не надо голову морочить.

[Yadryara]

Ещё раз спрашиваю: на какие вопросы я не ответил?

Вы пока что не ответили на вроде бы простые вопросы:

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

А оценку $0.24$ VAL в теме приводил? $0.06$ в 4 раза меньше чем $0.24$?

[EUgeneUS]

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

Ещё раз спрашиваю: на какие вопросы я не ответил?

Откуда Вы взяли вероятность найти неизвестное простое, как $0.06$.

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

Вы пока что не ответили на вроде бы простые вопросы:

Это риторические вопросы, потому и не ответил.