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

[Yadryara]

Нет, не риторические. Предлагаю идти от простого к сложному.

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

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

Мы неоднократно считали оценку для полупростых для определённых паттернов для интересующего интервала. В теме это есть. И нашли что она равна $0.24-0.25$. Разделил её на 4, чтобы узнать оценку VAL.

[Yadryara]

Хорошо, кое-что объясню по новой:

Во-первых, VAL на первой же странице даёт сбывшийся прогноз:

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

У меня оценка - $10^{15} - 10^{16}$ цепочек.

Во-вторых, VAL уже на второй странице называет шаг:

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

Отмечу, что каждая программа перебирает цепочки с одним и тем же шагом $2^63^3\prod_{i=3}^{12}p_i^2$.

Во-третьих, шаг этот в 6 раз больше чем вот этот:

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

До $10^{38}$ должно быть выполнено проверок (если правильно понимаю):
$(10^{38}/440538835723387181869888800)\cdot 46080 \approx 10^{16}$

Не вполне правильно. Потому что проверок по комплекту КМК37-11 было сделано

$$\frac{10^{38}\cdot46080}{440538835723387181869888800\cdot6}\approx 1.7\cdot 10^{15}$$

И в-четвёртых, проверки эти делали не втроём, а впятером.

[Yadryara]

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

Кстати, возможно, Ваша программа упростится, если на входе будут не только векторы v[], но и начальное значение, вычисленное с помощью chinese и даже список "терапевтических" исключений (по одному на каждое p от 5 до 37).

Кстати, эти терапевтические исключения не такой пустяк, особенно для 21-ки. Из-за них выбрасывается почти 60% кандидатов в 21-ки:

{dro=1.0;forprime(p=5,59,dro*=(p-1)/p;print(p,"  ",dro));}

5   0.800
7   0.685
11  0.623
13  0.575
17  0.541
19  0.513
23  0.490
29  0.473
31  0.458
37  0.446
41  0.435
43  0.425
47  0.416
53  0.408
59  0.401

И часть ускорения достигнута в том числе и благодаря более быстрой фильтрации по этим исключениям.

[EUgeneUS]

По построению оценки вероятности найти цепочку по паттерну.

Кратко:
Вероятности найти удачное число в каждом месте считаются независимыми.
Оцениваются так:

1. Известны функции $\pi_k(N)$ - (асимптотически) количество чисел, свободных от квадратов, с ровно $k$ множителями. Берем от них производную по $N$ - получаем плотности вероятности, найти число с ровно $k$ множителями, для случайно выбранного N.
Обозначим их $P_k(N)$ и назовём "базовыми" вероятностями.

2. В базовые вероятности нужно подставлять не само число $N$ - в районе которого ищем цепочку, а число $N/a_i$, где $a_i$ произведение всех множителей, заданных шаблоном:
$P_{k_i}(N/a_i)$ - базовая вероятность для i-го места в шаблоне. $k_i$ - количество простых множителей:
$k_i=1$, для $p$
$k_i=2$, для $pq$
$k_i=3$, для $pqr$
и т.д.

3. Далее нужно рассчитать поправочные коэффициенты к вероятностям. (Этот шаг был пропущен в прошлой оценке и именно в этом была ошибка).
Смысл этих коэффициентов в том, что применяя шаблоны, мы гарантируем, что ни одно неизвестное число $p, pq, pqr, pqrs...$ не делится на простые числа, которые используются в шаблоне.
Это факт изменяет базовые вероятности, причем разным образом - в зависимости от того, сколько множителей содержит неизвестное число.
а) для неизвестных простых. Все числа, которые "вычеркнуты" шаблоном - "плохие". Очевидно, если число делится на небольшое простое, оно не может быть большим простым
Тогда считаем долю оставшихся чисел, после "вычеркивания", как в этом сообщении.
Обратное число и будет поправочный коэффициент для вероятности найти простое, обозначим его $b_1$:

$$\tilde{P}_{1_i}=b_1 P_{1}(N/a_i)$$

где $\tilde{P}_{1_i}$ - уже "настоящая вероятность", найти на i-м месте неизвестное простое.
б) для неизвестных $pq$. Точного расчета у меня нет. Приблизительный такой:
если число делится (как минимум) на два простых из шаблона, то оно уже не может быть большим $pq$, доля таких чисел:
- считаем долю чисел, которые делятся на каждую пару: $\frac{1}{a_i a_j}, a_i \ne a_j$
- потом суммируем. Отнимаем от единицы - это и будет поправочный коэффициент $b_2$:

$$\tilde{P}_{2_i}=b_2 P_{2}(N/a_i)$$

где $\tilde{P}_{2_i}$ - уже оценка "настоящей вероятность", найти на i-м месте неизвестное $pq$.

Про поправочные коэффициенты можно сказать, что они зависят от шаблона, но не от $N$.

4. После чего перемножаем вероятности для каждой позиции и получаем вероятность успеха при однократной проверке по данном шаблону в районе заданного $N$.

Далее расскажу, про применение этой модели к шаблону для пентадекатлона.