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

[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$.

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

-- 04.10.2025, 21:13 --

Вот, что получилось для взятого наугад шаблона для пентадекатлона:


Параметр модели - число $N$, тут $10^{37}$

$a_i$ - произведения всех чисел в столбце шаблона
$N_i = N/a_i$
$\ln (N_i)$ и $\ln(\ln (N_i))$ - используются для расчёта "базовых вероятностей" $P_i$
Поправки к вероятностям рассчитывались, как описано выше.

Результат, оценка вероятности найти цепочку за один раз - строка 22 ($P$)

Видно, что вероятности для простых вроде бы похожи на правду. А вероятности для $pq$ выглядят заниженными, видимо из-за ошибки в расчете поправки для них....

-- 04.10.2025, 21:19 --

Тут всё тоже самое, но для $N=10^{38}$:


В общем,
1. Скорее всего имеются ошибки в расчете поправочных коэффициентов. Для $pq$ - точно имеются.
2. Скорее всего они устранимы.
3. Когда\если их устранить, то будет способ оценивать вероятность найти цепочку в заданной размерности при известном шаблоне.
4. Так как промежуточным результатом являются вероятности по каждой позиции шаблона - можно будет навешивать туда веса для оценки скорости вычислений и сравнения шаблонов уже по этому критерию.

[VAL]

После некоторой паузы (удачно совпавшей с моей загруженностью другими делами) нашлось некоторое количество перспективных кандидатур.

Самая перспективная эта:

(2 prime factors wanted)

1333401164884342191362652252579505933409163456046203884330678826542919483592953731718836518733790256578836971646812287941080692080294389337741328644132777 (154 digits) = pq?

Если с первой не срастется, можно попытать счастья с другой:

(2 prime factors wanted)

56739571521274155156164052199283682238087620340161926881293062246801978007475397005263228681951233704051958044152427111317131311032820305428387217330868643512924778357 (167 digits) = pq?

Она нацелена на то же значение $k$. И в случае успеха с первой интереса не представляет.

Для того же $k$ есть и еще несколько кандидатур, но там надо факторизовать по 2 числа, хотя бы одно из которых больше второго из приведенных здесь.
У меня в работе еще несколько $k$, но там более чем за неделю счета хороших кандидатур не появилось. Возможно стоит бросить эти $k$ и переключиться на поиск более длинных цепочек.

-- 05 окт 2025, 08:00 --

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

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

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

Там точно есть зависимости. Чем они объясняются, пока не понял, но наблюдаются настолько устойчиво, что случайными быть не могут.

Возьмем хотя бы случай, когда дополнительный к фиксированному множитель в какой-то позиции нашего шаблона обязан быть простым.
Я давно заметил, что его вероятность оказаться простым резко уменьшается, если фиксированный множитель делится на большую степень тройки и наоборот увеличивается, если он делится на большую степень двойки. Это наблюдается настолько явно, что в последнее время я стараюсь учитывать это обстоятельство при построении шаблона.

Провел небольшой эксперимент. Построил шаблон для нахождения восьмерки последовательных чисел с близкими по размеру фиксированными множителями (для этого показатели фиксированных простых пришлось сделать разными). Фиксированные множители в шаблоне были степенями чисел 2, 3, 5, 7, 11, 13, 17 и 31. Одинаковое количество делителей у возникающих чисел не требовалось. Вот этот шаблон

[2^2*31^7, 17^9, 2*3^23, 5^16, 2^37, 3*7^13, 2*11^11, 13^10]

Далее перебирались полмиллиона подходящих цепочек и фиксировалась частота появления простых. Количества простых для каждого из фиксированных множителей таковы:

   2     3     5       7     11     13     17    31    
14843, 9789, 11903, 12739, 13282, 13616, 13899, 14404

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

[Yadryara]

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

Возможно стоит бросить эти $k$ и переключиться на поиск более длинных цепочек.

Конечно. Тогда уже не будет ощущения как раньше: кто во что горазд.

Как уже говорил, Вашу прогу для D(48,20) ускорили на 46%. Это на моём компе в один поток. У Вас может быть как меньше так и больше. Так что если Дмитрий не против, передадим Вам одну из последних версий. Тестируйте на здоровье, адаптируйте хоть для D(48,21), хоть для D(24,19)...

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

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

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

[Dmitriy40]

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

Так что если Дмитрий не против

Конечно не против. Можно даже просто здесь опубликовать.

[EUgeneUS]

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

Там точно есть зависимости. Чем они объясняются, пока не понял, но наблюдаются настолько устойчиво, что случайными быть не могут.
...
Провел небольшой эксперимент.
...

Эксперимент, конечно, убедительный.

Не думаю, что вероятности найти простое в разных позициях зависимы.
Скорее всего они просто оказываются разными. А вот почему они оказываются разными - это вопрос, конечно.

[VAL]

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

Не думаю, что вероятности найти простое в разных позициях зависимы.
Скорее всего они просто оказываются разными. А вот почему они оказываются разными - это вопрос, конечно.

То есть, вероятность того, что в числе $2^{37}n$ множитель $n$ будет прост в полтора раза выше, чем вероятность его простоты в числе $3^{37}n$ ?
При том же самом $n$?! Странное утверждение!

[Yadryara]

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

Можно даже просто здесь опубликовать.

Пока желающих не видно. Если найдутся, опубликую.

А я пока посмотрел имеющиеся паттерны в программах для 48 делителей.

D(48,21)
     |               |               |
     |               |               |
     |1112222222222333333333344444444|
     | 890123456789012345678         |
   2   1 2 1 3 1 2 1 5 1 2 1
   3     1  1  2  1  1  2  1
   5       2    1    1    1 
   7      2      1      1   
  11    1          2        
  13         1            2 
  17                  2     
  19    2                  1
  ____________________________________
  23          2             
  29                2       
  31            2           
  37              2         
  41        2               
  43   2                    
  47                   2    
  53                       2
  59         2              
  ____________________________________
       ppppppppppppppppppppp
       qqqqqq qqqqqqq qqqqq 
       rrrrrr rrrrrrr rrrrr 
          s   s     s s  s  

Если я ничего не напутал, то в этом паттерне как раз есть легендарная $32p$-шка.

[Dmitriy40]

Легендарная (чем?) $32p$-шка есть почти в любом паттерне длиной более 7. Кроме извращённых с большими степенями. Это принцип такой, класть в паттерн простые в наименьших подходящих степенях.

-- 06.10.2025, 13:16 --

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

Далее перебирались полмиллиона подходящих цепочек

А что именно Вы называете "подходящими цепочками"? Потому что у меня картина другая, по крайней мере для 3:

v=[   4*31^7,   17^9,   2*3^23,   5^16,   2^37,   3*7^13,   2*11^11,13^10   ];
{p0=chinese([Mod(-j+1,v[j]) | j<-[1..#v]]); n=vector(8);
for(i=10^9,10^9+5e5-1,
   x=lift(p0)+(6*i+5)*p0.mod;
   ispseudoprime((x+0)/v[1]) && n[8]++;
   ispseudoprime((x+1)/v[2]) && n[7]++;
   ispseudoprime((x+2)/v[3]) && n[2]++;
   ispseudoprime((x+3)/v[4]) && n[3]++;
   ispseudoprime((x+4)/v[5]) && n[1]++;
   ispseudoprime((x+5)/v[6]) && n[4]++;
   ispseudoprime((x+6)/v[7]) && n[5]++;
   ispseudoprime((x+7)/v[8]) && n[6]++;
); print(n);}

   2      3      5      7     11     13     17     31
[14387, 14163, 11536, 12156, 13294, 13214, 13568, 13936]

При том что отклонения до $\sqrt{5\cdot10^5}\approx707$ (или даже вдвое больше) можно считать случайными.

[Yadryara]

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

Легендарная (чем?)

Шуткую. Легендарная в смысле многократно упоминаемая. Вспомнилось знаменитое grisовское "без $32p$ нет даже десятки".

Да, я же не объяснил обозначения. Места, как и для 12 делителей, нумеруются согласно остаткам по модулю 64. И $32p$ находится как раз в центре легальной зоны из 31-го числа, ограниченного | . Далее идут 8 простых (и их степени) из обязательной программы, а под чертой 9 простых (и их степени, точнее именно квадраты) из произвольной.

Хочется делить паттерны на левые и правые относительно $32p$. Этот — левый, почти вплотную прижался к левому краю.

[EUgeneUS]

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

То есть, вероятность того, что в числе $2^{37}n$ множитель $n$ будет прост в полтора раза выше, чем вероятность его простоты в числе $3^{37}n$ ?
При том же самом $n$?! Странное утверждение!

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

По сути, мы задаёмся следующим вопросом (ищем только простые): какая вероятность найти неизвестное простое при следующих условиях:
1. Ищем с применением заданного шаблона
2. На i-м месте шаблона.

Шаблон же не только снижает размер искомого проcтого на $a_i$ - произведение всех множителей в шаблоне на на i-м месте,
но и поиск простого производится не на всех числах в районе $N/a_i$, а на множестве числах после фильтрации.

[Dmitriy40]

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

Хочется делить паттерны на левые и правые относительно $32p$. Этот — левый, почти вплотную прижался к левому краю.

А симметричные относительно $32p$? Они тоже бывают левыми и правыми.

[EUgeneUS]

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

Потому что у меня картина другая, по крайней мере для 3:

Хм.
Большая степень двойки стоит на первом (нумерация с 1) месте шаблона, и там $14387$
Большая степень тройки стоит на третьем (нумерация с 1) месте шаблона, и там $11536$. Но сверху почему-то подписано как $5$
Нет?