Нашел статью с оценкой вероятности, что число полупростое.
Например, тут.
Там даётся такая оценка:
Я сравнил вероятности, что число простое (
), и что число полупростое для разных порядков числа. Получилось, что отношение вероятностей изменяется от
при десятичном порядке числа
, до
при десятичном порядке числа
.
С учетом применения ускорителей, отношение не очень большое. Ускорители ускоряют больше. Так и подмывает заменить в паттернах
на
, путём прибития гвоздями
. Но это плохой путь. Так как резко снижает вероятность нахождения цепочки (для 15-ки на 36 делителей - примерно на четыре порядка). А значит искать придется в бОльших числах, что опять же снизит вероятность нахождения цепочки
Поэтому предложение следующее:
1. Не уменьшать искусственно число позиций
за счёт увеличения позиций
.
2. Числа в позициях
тоже "пропустить через ускорители" по следующей схеме:
а) если число разделилось ровно на одно среднее простое - отправить остаток в
isprimeб) если число разделилось более чем на одно среднее простое - отправить всю цепочку в треш.
в) если число не разделилось ни на какое среднее простое, то тут вопрос, что с этим делать. Может просто в лог сложить (если цепочка не выкинулась по другим причинам).
Кстати, в упомянутой работе есть оценка вероятности того, что число - "сильно полупростое", то есть такое, которое будет факторизоваться тяжело.
-- 20.06.2022, 18:05 --И ещё некоторые соображения по поиску длинных цепочек с количеством делителей
Ранее я заявлял, что
по наблюдениям применение ускорителей позволит улучшить цепочки на 1-2 позиции.
Но эти наблюдения были сделаны по цепочкам с
, где
-
нечетное.
Такие цепочки характеризуются "дефицитом" простых (в первой степени), в результате в них
а) относительно много позиций, где нужно искать
.
б) в остальных позициях нужно искать
.
За счёт пункта "а" ускорители оказываются весьма эффективны.
Если же
- четное, то наблюдается "избыток" простых (в первой степени), в результате в таких цепочках:
а) относительно мало позиций, где нужно искать
.
б) имеются, но опять же их немного, позиции, где нужно искать
.
в) в остальных позициях
или даже
.
За счет того, что ускорители не применяются к позициям
,
или
их эффект оказывается снижен. И получается соревнование мощностей в "голом" PARI/GP", а у уважаемого
VAL их больше
Возможно, применение ускорителей к
по схеме, как описано выше, сможет как-то улучшить ситуацию.