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

[Dmitriy40]

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

Самое главное что именно количество делителей ведь интересует, а не то как именно они соберутся.

Не скажите, второе тоже интересует: стоит ли размещать в паттерн кубы и более старшие степени, ради скорости isprime против factor.
В общем инструменты есть, можно развлекаться.

[VAL]

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

А докуда проверено по этой программе? И какова вообще история поиска 21-ки (очковтирательства ) ? То есть как долго длился поиск, по каким паттернам, что найдено за это время?

Историю поиска помню плохо: много воды утекло.
Всего у меня 4 программки (при поиске 20-ки использовалось полсотни одновременно, а всего больше 100).
Одна из них, судя по протоколам запускалась многожды, остальные - пару тройку раз. Успехи не впечатляют. Больше 18 из 21 позиции не совпали ни разу. Вот наиболее близкие промахи:

90715763859608616730714175556209422588238079327693680146
# [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 0, 0] 18
85214054718602387929373909199904790013177732572016804946
# [1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0] 18
29825395661688231658603848650736899419196053570174356946
# [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 0, 0] 18

Приведены лишь те позиции, где выполнялась факторизация. До этого в еще трех позициях сработал ispseudoprime().
То, что в последних позициях везде нули, говорит лишь о том, что после второго промаха поиск прекращался.

[Yadryara]

Благодарю.

Удобно действовать по аналогии. Как видим на примере паттерна из единственной показанной здесь программы для поиска 21-к, он тоже построен согласно Концепции Минимальных Квадратов (КМК). Только для поиска D(12,15) была КМК37-11, а здесь КМК59-3.

Для D(12,15) — 6 обязательных чисел и 6 произвольных.
Для D(48,21) — 8 обязательных чисел и 9 произвольных.

Для D(12,15) — комплект состоит из $64\cdot 6! = 46080$ паттернов.
Для D(48,21) — комплект состоит из $x\cdot 9!$ паттернов.

То есть речь идёт, видимо, о миллионах паттернов в одном только комплекте КМК59-3.

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

Но. Впс два года занимался кортежами. Был придуман приём, который я назвал "разбиение по чистоте". И мы с Демисом тщательно проверили реальный эффект от него, попутно найдя весьма немало кортежей.

Можно ли его применить здесь? Хочется сказать: да, конечно. Ведь здесь тоже задача сводится к поиску простых чисел, будь то одиночные $p$, парные $pq$ или тройные-четверные $pqr$-$pqrs$. Как понял, для 48 делителей одиночных простых — от 3-х до 7.

[Yadryara]

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

Больше 18 из 21 позиции не совпали ни разу.

Не согласен. Один раз 48 делителей было у 19-ти чисел из 21-го. Для полноты картины я проверял сплошную полосу шириной в 31 число:

      1112222222222333333333344444444    H21   ML     ALL
e53   7890123456789012345678901234567

852    1111111 1111111111 11               2   10      19

907    1111111111111111 1  1     1         3   16      19
298    111111111111111 11  1     1         3   15      19
1073   1 1111111111111  1111               3   13      18

1119   111 111111111111   11               4   12      17

1124   111111111111 11   1 1               5   12      16

H21 — это как раз важнейший критерий, количество пропусков (Hole) в полосе паттерна шириной 21.
ML — MaxLen, наибольшая подрядность.
АLL — общее количество чисел по 48 делителей в полосе шириной 31.

Пока нет путаницы: 56-значные найдены Вами, 57-значные — Макаровой по Вашей программе.

[EUgeneUS]

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

Самое главное что именно количество делителей ведь интересует, а не то как именно они соберутся.

Для моих целей интересует именно количество делителей.

-- 08.10.2025, 08:14 --

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

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

Но. Впс два года занимался кортежами. Был придуман приём, который я назвал "разбиение по чистоте". И мы с Демисом тщательно проверили реальный эффект от него, попутно найдя весьма немало кортежей.

Именно для оценки "качества" паттернов (и не только) решалась задача по оценке вероятности найти цепочку по паттерну за один раз.

В целом она решена. Хотя и требует вычислительных экспериментов для каждого паттерна.

Ниже опишу пошаговую "инструкцию". Чтобы в одном месте было.

-- 08.10.2025, 08:34 --

1. Шаг 1.
Считаем "базовые" вероятности $P^{(k)}(N)$ для нахождения чисел, свободных от квадратов, с $k$ простыми различными делителями.
Для этого берем:

vicvolf в сообщении #1703438 писал(а):

Асимптотическая формула для количества $k$-почти простых чисел $\pi_k(x)$, при фиксированном $x$:

$\pi_k(x) \sim \frac{x}{\log x} \cdot \frac{(\log \log x)^{k-1}}{(k-1)!}$

И дифференцируем:
$P^{(k)}(N) = \frac{d \pi_k(N)}{d N}$

"Базовые вероятности" для каждого $k$ зависят только от $N$.
Можно брать с точностью до $O(\frac{1}{(\ln(N))^2})$. Я в своих экспериментах брал полную производную.

2. Шаг 2. Считаем "базовые" вероятности $P_i^{(k_i)}(N_i)$ - для каждого места в шаблоне.
Для каждого i-го места в шаблоне считаем
а) $a_i$ - произведение всех множителей, заданных шаблоном
б) $N_i = N/a_i$ - число, где ищем неизвестные с учетом, что оно меньше, чем $N$
в) подставляем $N_i$ в "базовые вероятности": $P_i^{(k_i)}(N_i)$. $k_i$ - тоже задаётся шаблоном, это необходимое количество простых множителей в неизвестном числе.

"Базовые" вероятности $P_i^{(k_i)}(N_i)$ для каждого места в шаблоне зависят от $N$ и от самого шаблона. Но не от способа "запуска шаблона".

3. Шаг3. Фильтрация при запуске расчета по шаблону и поправочные коэффициенты.

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

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

Поправочный коэффициент для неизвестных простых легко рассчитывается аналитически: $\frac{1}{b_1} = \prod\limits_{p_l}^{}(1 - 1/p_l)$, где произведение считается по всем простым, которые используются в шаблоне в любой степени (в расчете используется первая степень для всех простых!).
Для бОльшего количество простых множителей у меня нет аналитического выражения для поправочных коэффициентов (для $b_k, k>1$), их нужно рассчитывать численно. Об этом ниже.

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

4. Шаг 4. Финальный.
Умножаем базовые вероятности для каждого места в шаблоне на поправочный коэффициент, и получаем вероятность найти подходящее неизвестное число для каждого места в шаблоне: $\hat{P_i (N)} = b_{k_i}P_i^{(k_i)}(N_i)$
Можно эти вероятности перемножить и получить вероятность найти цепочку за одну проверку для данного шаблона, если искать в районе числа $N$.

[EUgeneUS]

3.1. Шаг 3.1. Дополнительный.
Расчет $b_k, k>1$

а) Нужно выбрать количество испытаний $n$ - чтобы собрать статистику, достаточную для оценки $b_k$ с точностью до 3-го значащего знака.
несколько сотен тысяч, может быть - миллион, представляется достаточным.
б) Исходя из $n$ и известного шага нужно выбрать $N$ - размерность чисел, где будет осуществляться расчет.
Порядок $N$ не должен сильно изменяться при проведении $n$.
Неизменность десятичного порядка выглядит обязательной. Но лучше бы все $n$ укладывались в $[N, 2N]$.
в) провести расчет, получить оценки вероятностей для $\hat{P_i (N)}$.
г) зная $N$ и экспериментальные оценки $\hat{P_i (N)}$, расcчитываем оценки для $b_k$.
д) если в шаблоне несколько мест с одинаковым $k$, то по ним можно усреднить, для повышения точности оценки $b_k$
е) проверяем, что оценка $b_1$ (для неизвестных простых) совпадает со значением, полученным аналитически. Если не совпадает, то это указывает, скорее всего на некорректную "предварительную фильтрацию" (см. Шаг 3).

Собственно говоря, всё.
Позже напишу, что со всем этим можно делать.

-- 08.10.2025, 09:48 --

Что со всем этим можно делать.

1. Совпадение аналитической вероятности с экспериментальной оценкой для неизвестных простых - индикатор, что "предварительная фильтрация" эффективна.
В частности, для пентадекатлона:
аналитическая вероятность для простых в районе $N=10^{38}$: от $0.078$ до $0.084$ (для разных позиций первого попавшегося шаблона, который сохранился у меня в архивах),
а экспериментальная - около $0.06$
Это указывает, что "предварительная фильтрация" путем умножения шага на $6$ - неэффективна.
К тому же такая "предварительная фильтрация" выкидывает из проверки половину не "бракованных" цепочек.

2. Можно сравнивать, какие шаблоны "лучше", "какие" хуже, а какие примерно одинаковы.
В частности, легко получить ответ - есть ли лучшие или худшие шаблоны, если переставлять необязательные простые в квадратах?
Предварительно, такие перестановки влияют только на $N_i$, и то в очень ограниченном виде. А значит шаблоны с перестановкой необязательных простых в квадратах примено одинаковы.
Но у желающих появился способ это проверить.

3. Можно прогнозировать, в каком порядке $N$ найдётся цепочка.

4. Если известны оценки (хотя бы в попугаях) времени проверки на $p, pq,$ и т.д. - можно оценивать ожидаемое время нахождения цепочки.

5. С учетом п.4. можно сравнивать шаблоны по ожидаемому времени нахождения цепочек. Только нужно не забывать, что для разных шаблонов - разный шаг и по разному растёт $N$

[Yadryara]

Я вот выше писал, что мол адаптируйте и считайте. Гладко было на бумаге.

Сам попытался адаптировать быструю программу для D(48,20) для счёта D(48,21). И подзапутался, ибо старая для D(48,20) и менее старая для D(48,21) не просто разные, они отличаются сильнее чем поначалу казалось.

Понятно что массив M это старый MM,
массив u это старый uu, только нумерация позиций не с 0, а с 1-цы.

А вот nu больше похож на u чем на старый u2.

[EUgeneUS]

И ещё пара комментариев

i. $pqr$ и $p^3r$

При экспериментальном расчёте $b_3$ (для $pqr$) нужно учитывать "попадания" именно в $pqr$, но не в $p^3r$.
Дело в том, что вероятность попасть в $pqr$ зависит сильно другим образом от $N$, чем вероятность попасть в $p^3r$.
При "боевом" расчете $N$ будет гораздо больше, чем при оценке $b_3$, и вероятность попасть в $p^3r$ улетит в ноль. А рассчитанный $b_3$ окажется завышенным. Не сильно завышенным, но всё равно неприятно.

Аналогично и для подобных случаев ($pqrs$, $p^8s$ и $p^3rs$, и т.д.)

ii. Расчет $b_k$ в случае "неэффективной предварительной фильтрации".

В случае "неэффективной предварительной фильтрации" оценки $b_k$ всё также не будут зависеть от $N$, и вся методика будет работать.
Конечно, при условии, что "предварительная фильтрация" будет такой же, как для оценки $b_k$, так и для собственно поиска цепочек.
Но это не отменяет того, что на эффективность "предварительной фильтрации" нужно обращать внимание. Всё таки иметь вероятность от $0.078$ до $0.084$ в 11 позициях, гораздо приятнее, чем $0.06$

[EUgeneUS]

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

Для моих целей интересует именно количество делителей.

Тут неправильно написал. Интересуют именно, как соберутся.
Более подробно в комментарии i. в сообщении выше.

[Yadryara]

VAL, по поводу nu это же в первую очередь к Вам вопрос. Это у Вас в программе:

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

А это одна из программ, тщетно пытавшихся набрать очко
[..]
u = [1, 2, 3, 4, 5, 6, 8, 9,10,11,12,13,14,16,17,18,19,20];
nu = [3, 3, 3, 4, 3, 3, 8, 9,10,11,12,13,14,16,17,18,19,20];

Понятно что записано в массиве u — перечислены все номера мест паттерна, где нет одиночных $p$. Я его и переименовал в bezp для наглядности.

Но что такое nu ? Он точно такой же как u, только в нём в начале куча 3-к. Что сие значит?

[Yadryara]

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

Тут неправильно написал.

Вот и я подумал, что ровно наоборот. Хотел уже спросить.

Насчёт оформления таблицы приближений к D(48,21). 48 делителей редко собираются сами собой на 10 внепаттерных позициях. По таблице видно, что это случилось лишь 2 раза из 70.

Так что пишу пока valids именно по паттерну (по полосе шириной 21) и maxlen. Сортировка тоже идёт по этим двум параметрам. Если оба совпадут, тогда выше поставлю цепочку, меньшую по величине начального числа, примерное значение которого указано в крайне левом столбце. Например, наш нынешний лидер указан как 852e53, а точное значение было опубликовано выше.

e53   1112222222222333333333344444444   Valids   MaxLen   Found
      7890123456789012345678901234567

852    1111111 1111111111 11                19       10     VAL

907    1111111111111111 1  1     1          18       16     VAL
298    111111111111111 11  1     1          18       15     VAL
1073   1 1111111111111  1111                18       13      NM

1325   111111111111111 1   1                17       15      NM
1119   111 111111111111   11                17       12      NM

1124   111111111111 11   1 1                16       12      NM

Ссылку на блог NM пока не даю, вроде люди и так знают. Впрочем, дам ссылку если будет найдено приближение не хуже наилучшего, то есть с $valids\geqslant 19$.

[VAL]

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

VAL, по поводу nu это же в первую очередь к Вам вопрос. Это у Вас в программе:

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

А это одна из программ, тщетно пытавшихся набрать очко
[..]
u = [1, 2, 3, 4, 5, 6, 8, 9,10,11,12,13,14,16,17,18,19,20];
nu = [3, 3, 3, 4, 3, 3, 8, 9,10,11,12,13,14,16,17,18,19,20];

Понятно что записано в массиве u — перечислены все номера мест паттерна, где нет одиночных $p$. Я его и переименовал в bezp для наглядности.

Но что такое nu ? Он точно такой же как u, только в нём в начале куча 3-к. Что сие значит?

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

Что означают эти тройки и четверка в первых шести позициях n[] понятно. Они бракуют цепочки, у которых в этих позициях встречается число, у которого не 48 делителей.
А вот, что и зачем проверяется, начиная с 7-го шага цикла...
Какая-то кривая (с исключениями) выбраковка цепочек, где хотя бы одно из интересующих нас чисел имеет более двух простых множителей, больших 300000. Зачем? Почему? И главное - как при этом еще что-то нашлось?

-- 09 окт 2025, 08:16 --

PS:

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

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

Забыл наиболее реалистичное объяснение: инопланетяне взломали мой комп и внесли изменения в текст программы

[Yadryara]

Ну здесь такой простой рецепт. Перепишите этот непонятный кусок кода заново.

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

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

[VAL]

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

Ну здесь такой простой рецепт. Перепишите этот непонятный кусок кода заново.

Уже тестирую.

-- 09 окт 2025, 10:19 --

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

(Оффтоп)

 
\l  e:\VAL\math\projects\equidivisible_numbers\PARI\res21\res21tau48n_3-0-13-5__II_1
allocatemem(2^28)

m =  554159729309947409007752567806326895200
p1 = 30475766721704852566432501877740394775491
a = 320226
     
M =  [3698, 3971, 12, 49, 50, 5043, 362024, 529, 18, 4805, 28, 4107, 242, 841, 480, 289, 4418, 63, 4, 845, 320226]
u  = [1, 2, 3, 4, 5, 6, 8, 9,10,11,12,13,14,16,17,18,19,20];
nu = [3, 3, 3, 4, 3, 3]; 

i1 =       480000000000
i2 =   i1+  50000000000

P=[61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509, 521, 523];
T={[
Set([16, 35, 59]), Set([0, 46, 47]), Set([19, 30, 44]), Set([21, 30, 55]), Set([13, 49, 51]), Set([40, 51, 80]), Set([5, 15, 87]), Set([15, 39, 57]), Set([63, 71, 86]), Set([51, 93, 98]), Set([47, 85, 100]), Set([19, 36, 88]), Set([32, 39, 98]), Set([70, 95, 117]), Set([16, 39, 82]), Set([16, 63, 134]), Set([50, 107, 134]), Set([60, 108, 145]), Set([57, 108, 132]), Set([21, 38, 118]), Set([6, 24, 48]), Set([65, 118, 143]), Set([45, 57, 126]), Set([67, 110, 129]), Set([104, 130, 175]), Set([34, 74, 166]), Set([51, 76, 143]), Set([97, 139, 164]), Set([82, 149, 181]), Set([91, 93, 166]), Set([16, 153, 192]), Set([142, 149, 211]), Set([18, 51, 163]), Set([86, 133, 206]), Set([39, 78, 124]), Set([9, 80, 84]), Set([56, 141, 248]), Set([42, 141, 167]), Set([6, 43, 180]), Set([21, 178, 208]), Set([1, 53, 62]), Set([68, 126, 172]), Set([13, 56, 207]), Set([44, 152, 227]), Set([43, 147, 225]), Set([36, 126, 250]), Set([94, 125, 245]), Set([112, 204, 254]), Set([154, 185, 210]), Set([220, 245, 297]), Set([190, 203, 297]), Set([124, 138, 221]), Set([24, 99, 106]), Set([78, 87, 334]), Set([263, 287, 319]), Set([80, 145, 238]), Set([14, 29, 367]), Set([153, 247, 272]), Set([187, 199, 215]), Set([58, 348, 371]), Set([163, 170, 286]), Set([12, 102, 293]), Set([173, 218, 354]), Set([244, 312, 333]), Set([45, 280, 351]), Set([117, 266, 321]), Set([140, 153, 267]), Set([1, 300, 334]), Set([62, 143, 397]), Set([26, 286, 394]), Set([241, 269, 290]), Set([155, 276, 410]), Set([56, 101, 214]), Set([27, 320, 391]), Set([167, 193, 452]), Set([88, 97, 469]), Set([151, 222, 462]), Set([182, 222, 413]), Set([139, 373, 383]), Set([108, 284, 485]), Set([351, 371, 498]), Set([41, 82, 141])
]}
s=0;t=0;
{for(i=i1,i2,
if(i%5!=4 && i%7!=3 && i%11!=3 && i%13!=6 && i%17!=11 && i%19!=15 && i%23!=17 && i%29!=1 && i%31!=18 && i%37!=19 && i%41!=21 && i%43!=22 && i%47!=3 && i%53!=23 && i%59!=27, 
tf=1;for(j=1,82, if(setsearch(T[j],i%P[j]),tf=0;break));if(tf, p=p1+i*m;
if(ispseudoprime(p),n=a*p-20; if(ispseudoprime((n+6)/M[7]) && ispseudoprime((n+14)/M[15]),
tf1=1; for(j=1,18,if(ispseudoprime((n+u[j]-1)/M[u[j]]), tf1=0; break)); 
if(tf1, s=s+1; tf2=1; for(j=1,6, ng=(n+u[j]-1)/M[u[j]]; g=factor(ng,300000); na=matsize(g)[1];
 if(!((na==nu[j] && ispseudoprime(g[na,1])) || (na<nu[j] && !ispseudoprime(g[na,1]))), tf2=0; break));
 if(tf2, tf3=1; E=[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0];ss=0;t=t+1; for(j=1,18,if(numdiv(n+u[j]-1)==48,E[j]=1;ss=ss+1);
 if(j>ss+1, if(j>10,printf("%.4g",(i-i1)/(i2-i1)*100.); printf(" ")); break)); 
 if(ss>11, print(); print(n); print("# ",E," ",ss+3);if(ss==18,print(n," YES!!! ");break)))))))));
 print(s," ",t)};"res21tau48n_3-0-13-5__II_1"

[Dmitriy40]

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

Но что такое nu ?

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

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

И главное - как при этом еще что-то нашлось?

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

-- 09.10.2025, 10:21 --

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

-- 09.10.2025, 10:25 --

Yadryara
Код для M48n21 практически не отличается от кода для M48n20, отличия чисто косметические (в величине констант).
То что вместо 3 стоит nu[j] в цикле проверки разложения это уже мелочи, попытка оптимизации, учесть заодно и вариант $pqrs$ в той же проверке.
Соответственно и все ускорения применимы ровно так же, только объединить два цикла проверки разложений для 3 (u2[]) и 4 ([4,6,9,12,17]) из M48n20 в один с nu[] и u[] (который вместо u2[] и константного вектора),