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

[Dmitriy40]

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

Нет?

Подписан массив счётчиков количества простых, как и у VAL, а не исходный вектор паттерна.

[Yadryara]

Dmitriy40
Не знаю, для поиска 21-ки вроде пока не надо строить иерархию паттернов, как мы это делали для 12 делителей. Или лучше всё-таки попытаться построить?

[Dmitriy40]

Yadryara
Вопрос не ко мне, а к тем кто собрался её искать.
И/или к VAL, по чьим паттернам её скорее всего будут искать.

[EUgeneUS]

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

Подписан массив счётчиков количества простых, как и у VAL, а не исходный вектор паттерна.

Сорри, не заметил, что нумерация $n[]$ не совпадает с нумерацией $v[]$.
Интересно, что вероятности для всех позиций совпали с результатом VAL, кроме позиции с большой степенью тройки.
Я правильно понимаю, что поиск производился в районе $10^{9+11}$ и было $5 \cdot 10^5$ попыток?

[Dmitriy40]

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

Я правильно понимаю, что поиск производился в районе $10^{9+11}$ и было $5 \cdot 10^5$ попыток?

Нет, попыток было конечно $5\cdot10^5$, как и у VAL, только цепочки были в интервале $[1.47288808\cdot10^{98},1.47362452\cdot10^{98}]$ так как модуль p0.mod весьма велик, $2.455\cdot10^{88}$, а перебор идёт с шестикратным шагом и начинается с числа в 6 миллиардов раз больше модуля (примерно, плюс начальное смещение).
Вообще, вот чему равен p0:

(Оффтоп)

p0 = chinese([Mod(-j+1,v[j]) | j<-[1..#v]]) = Mod(12338794247178490886529300275819881792885639393379268380866795707426742143740081787109372, 24548134647125423862256054695427899033555331092583693503660556964478320640000000000000000)

А шаг перебора ещё в 6 раз больше, что явно видно в выражении x=lift(p0)+(6*i+5)*p0.mod. Подставив в него i=[1e9..1e9+5e5-1] и получим указанный интервал.

[EUgeneUS]

Dmitriy40
Спасибо!
А из каких соображений выбран шестикратный шаг?

Рассчитал вероятности найти простое в каждой позиции для этого случая:
1. "Теоретическая", рассчитывалась, как описано выше (upd: но с небольшим исправлением): $0.0285 ... 0.0288$
2. "Экспериментальная: $0.0231 ... 0.0288$. Максимальная и самая близкая к "теоретической" - на месте с $2^{37}$

-- 06.10.2025, 20:03 --

Кстати! Применил это исправление для шаблона от пентадекатлона.
И попал с точностью до порядка!

-- 06.10.2025, 20:07 --

Вот картинка с расчетом:


Исправленные клетки - розовой заливкой. Если простые в шаблоне в степени более 1, то при расчете поправки их всё равно нужно брать с первой степени.

Результат,
вероятность найти цепочку в районе $N=10^{38}$ - $1.131 \cdot 10^{-16}$ (на картинке)
вероятность найти цепочку в районе $N=10^{37}$ - $1.6857 \cdot 10^{-16}$

[Dmitriy40]

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

А из каких соображений выбран шестикратный шаг?

По инерции, помню же что для пентадекатлона и аналогичных ему паттернов 5 вариантов из 6 давали составное число на месте искомого простого в одной из позиций цепочки. Здесь же похоже разрешены два из 6, вот остатки по модулю 6 искомых простых чисел на местах паттерна :

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]]);
for(d=0,5, x=lift(p0)+d*p0.mod; print(d,": ",[((x+j-1)/v[j])%6 | j<-[1..#v]]); );
0: [1, 1, 5, 1, 4, 1, 1, 5]
1: [1, 1, 3, 1, 1, 1, 1, 5]
2: [1, 1, 1, 1, 4, 1, 1, 5]
3: [1, 1, 5, 1, 1, 1, 1, 5]
4: [1, 1, 3, 1, 4, 1, 1, 5]
5: [1, 1, 1, 1, 1, 1, 1, 5]

Видно что чётные запрещены на месте +4 (дают чётное число вместо простого), 1 и 4 запрещены на месте +2 (дают кратное 3 вместо простого), из всех остаются только 3 и 5.

Запуск счёта для 5e5 попыток с разрешёнными 3 и 5 по модулю 6 даёт:
[14564, 14518, 11476, 12325, 13114, 13561, 13365, 13804]
Т.е. по сути ничего собственно и не изменилось.

-- 06.10.2025, 22:05 --

EUgeneUS
Да, это такой кривой паттерн VAL сделал, что у него два разрешённых остатка по модулю 6.

[EUgeneUS]

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

Видно что чётные запрещены на месте +4 (дают чётное число вместо простого), 1 и 4 запрещены на месте +2 (дают кратное 3 вместо простого), из всех остаются только 3 и 5.

тут где-то лежит причина расхождения "теоретической" вероятности и практической.

При расчете "теоретической вероятности", считаю, что применение шаблона гарантирует, что ни в каком месте не может быть чисел, кратных простым из шаблона.
А тут получается, что если шаблон применять "в лоб", то могут быть четные числа, или кратные трём на некоторых местах.
По модулю 6, хорошо, подобрали параметры запуска "руками".
А по другим модулям, с простыми множителями больше $3$? Если на каких-то позициях нет-нет, а проскакивают числа, которые могут делитьcя на $5, 7, 11, 17, 31$, то для таких позиций "теоретическая" вероятность будет больше практической (будет завышена).

Кстати, если запускать "в лоб", то минимальная вероятность и будет на позиции с тройкой в большой степени, так как там четные будут проскакивать.

[Dmitriy40]

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

Если на каких-то позициях нет-нет, а проскакивают числа, которые могут делитьcя на $5, 7, 11, 17, 31$, то для таких позиций "теоретическая" вероятность будет больше практической (будет завышена).

Проверим это, скорректируем счётчики 5-31 из последних показанных мной:
? n=[14564, 14518, 11476, 12325, 13114, 13561, 13365, 13804];
? k=[1, 1, 5/4, 7/6, 11/10, 13/12, 17/16, 31/30];
? [round(n[j]*k[j]) | j<-[1..#n]]
%1 = [14564, 14518, 14345, 14379, 14425, 14691, 14200, 14264]
И получили равномерное распределение с точностью до случайных флуктуаций. Как и должно быть.

Если так же скорректировать и значение 9789 для 3 из данных VAL, получим 9789*3/2=14684, без всяких аномалий.
Т.е. аномалии получились из-за дополнительной фильтрации кандидатов, а вовсе не присутствуют в изначальном ряду. Потому я и спрашивал что именно считал VAL как "подходящие цепочки".

-- 06.10.2025, 23:01 --

И если быть совсем честными, надо даже и 6х шаг не использовать, это тоже уже фильтрация. И тогда получается как и должно быть, вероятности по числам начала цепочек одинаковы, а после деления на числа паттерна разные:

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=0,5e5-1,
   x=lift(p0)+(10^9+i)*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);}
k=[2/1, 3/2, 5/4, 7/6, 11/10, 13/12, 17/16, 31/30]; for(j=1,#k, n[j]=round(n[j]*k[j])); print(n);

[7282, 9545, 11556, 12245, 13024, 13264, 13479, 14054]
[14564, 14318, 14445, 14286, 14326, 14369, 14321, 14522]

Первым показаны делённые, потом скорректированные, видно что вторые практически равномерные.

[VAL]

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

Я правильно понимаю, что поиск производился в районе $10^{9+11}$ и было $5 \cdot 10^5$ попыток?

Размер исследуемых чисел 90-100 знаков. (Я же приводил пример шаблона, там НОК порядка 90 знаков.)
А попыток было десяток раз по 50 тыщ и 3 раза по полмиллиона. Менялся порядок чисел в шаблоне и диапазон параметра цикла.
Я привел статистику только для одного запуска, поскольку для остальных она идентична.

-- 06 окт 2025, 23:30 --

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

Т.е. аномалии получились из-за дополнительной фильтрации кандидатов, а вовсе не присутствуют в изначальном ряду.

Все верно! Объяснение именно такое.
А жаль, я думал мы на пороге великого открытия

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

[EUgeneUS]

Итого,
1. Мы умеем считать вероятность появления неизвестного простого в любом месте любого шаблона.
Если используются такая предварительная фильтрация:

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

Зато каждое 3-е делится на лишнюю степень тройки, каждое 5-е - на лишнюю степень пятерки и т. д. Этот момент я давно учитываю с помощью предварительной фильтрации.

то сразу.
А если не используется или используется частично, то известно как это учитывать.

2. С расчетом поправочных коэффициентов для $pq, pqr, pqrs ... $ пока сложности: для $pq$ скорее всего ошибка, для большего количества простых множителей пока даже не брался.

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

Dmitriy40
Можно ли доработать Ваш скрипт для "учебного шаблона" так чтобы:
а) он применял предварительную фильтрацию, как описал VAL, для исключения
каждое 3-е делится на лишнюю степень тройки, каждое 5-е - на лишнюю степень пятерки и т. д.
б) чтобы для каждой позиции подсчитывал не только количество $p$, но и $pq, pqr, pqrs, pqrst$?
Или большое время факторизации по сравнением с проверкой на простоту убьёт эту затею на "учебном шаблоне"?

[Yadryara]

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

Или большое время факторизации по сравнением с проверкой на простоту убьёт эту затею на "учебном шаблоне"?

Пока что убивает. Потому что напрашивающийся numdiv гораздо медленнее ispseudoprime.

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

{t0=getwalltime();print;
v=[   4*31^3,   17^3,   2*3^7,   5^6,   2^10,   3*7^3,   2*11^3,  13^4   ];
p0=chinese([Mod(-j+1,v[j]) | j<-[1..#v]]); n=vector(8);
x=lift(p0)+(10^9+10000)*p0.mod;
print(x); print(p0.mod);print;
for(i=0,1e4-1,
   x=lift(p0)+(10^9+i)*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);
k=[2/1, 3/2, 5/4, 7/6, 11/10, 13/12, 17/16, 31/30];
for(j=1,#k, n[j]=round(n[j]*k[j])); print(n);
print;print(strtime(getwalltime()-t0));print;
}quit;


66780634200201351588197234940267109372
66779966380109412397968000000

[353, 449, 596, 618, 698, 667, 665, 758]
[706, 674, 745, 721, 768, 723, 707, 783]

314 ms

Заменив 8 проверок по ispseudoprime на

   numdiv((x+0)/v[1]) == 4 && n[8]++;
   numdiv((x+1)/v[2]) == 4 && n[7]++;
   numdiv((x+2)/v[3]) == 4 && n[2]++;
   numdiv((x+3)/v[4]) == 4 && n[3]++;
   numdiv((x+4)/v[5]) == 4 && n[1]++;
   numdiv((x+5)/v[6]) == 4 && n[4]++;
   numdiv((x+6)/v[7]) == 4 && n[5]++;
   numdiv((x+7)/v[8]) == 4 && n[6]++;

Получим в сотни раз дольше работающую прогу, выдающую результат:

[1339, 1682, 1951, 1985, 2117, 2167, 2206, 2314]
[2678, 2523, 2439, 2316, 2329, 2348, 2344, 2391]

2min, 26,678 ms

По этим данным видно, что значения частотностей пока скорее всё-таки 0.07 и 0.24 для простых и полупростых соответственно.

Если проделать ту же операцию для количества делителей равных 8 и 16, основное представление для которых pqr и pqrs соответственно, а затем взять нижние вектора, получим табличку:

   2   p     [ 706,  674,  745,  721,  768,  723,  707,  783]
   4   pq    [2678, 2523, 2439, 2316, 2329, 2348, 2344, 2391]
   8   pqr   [4172, 3941, 3516, 3372, 3155, 3252, 3203, 3136]
  16   pqrs  [4034, 3344, 2923, 2743, 2609, 2546, 2463, 2279]

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

[Yadryara]

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

А это одна из программ, тщетно пытавшихся набрать очко

Всё не покидает ощущение, что эта прога заточена на запуск из PARI: плотные длиннющие строки. Сложнее разобраться.

Не пробовали запускать из консоли? Для длинных программ это намного удобнее.

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

Например, та самая программа при i=605102169583 находит цепочку из 11-ти последовательных чисел с 48 делителями, начиная с числа 107379224505589048964595089898468182968439621246614942548

Вы её уже ранее находили?

[Dmitriy40]

Чтобы не ждать для каждого значения numdiv объявляем n как матрицу n=matrix(8,33000) (в надежде что более 33000 делителей не встретится) и в цикле её обновляем просто как n[8,numdiv((x+0)/v[1])]++ безо всяких условий.
Потом накопленную инфу уже можно анализировать как угодно, например вывести только комбинации из 1..15 простых в первой степени:
k=[2, 3, 5, 7, 11, 13, 17, 31];
for(np=1,15, print(np,": ",n[,2^np]~," : ",[round(n[j,2^np]*k[j]/(k[j]-1)) | j<-[1..#k]]); );

Для паттерна v=[4*31^3,17^3,2*3^7,5^6,2^10,3*7^3,2*11^3,13^4] и 1e4 кандидатов за минуты 4 выдаст следующее:

1: [353, 449, 596, 618, 698, 667, 665, 758] : [706, 674, 745, 721, 768, 723, 707, 783]
2: [1339, 1682, 1951, 1985, 2117, 2167, 2206, 2314] : [2678, 2523, 2439, 2316, 2329, 2348, 2344, 2391]
3: [2086, 2627, 2813, 2890, 2868, 3002, 3015, 3035] : [4172, 3941, 3516, 3372, 3155, 3252, 3203, 3136]
4: [2017, 2229, 2338, 2351, 2372, 2350, 2318, 2205] : [4034, 3344, 2923, 2743, 2609, 2546, 2463, 2279]
5: [1386, 1300, 1242, 1282, 1208, 1148, 1141, 1113] : [2772, 1950, 1553, 1496, 1329, 1244, 1212, 1150]
6: [622, 545, 453, 443, 431, 369, 407, 355] : [1244, 818, 566, 517, 474, 400, 432, 367]
7: [194, 161, 121, 110, 93, 101, 94, 77] : [388, 242, 151, 128, 102, 109, 100, 80]
8: [56, 35, 30, 16, 19, 22, 11, 17] : [112, 53, 38, 19, 21, 24, 12, 18]
9: [10, 6, 4, 8, 1, 2, 1, 3] : [20, 9, 5, 9, 1, 2, 1, 3]
10: [3, 0, 1, 0, 0, 0, 0, 0] : [6, 0, 1, 0, 0, 0, 0, 0]
11: [0, 0, 0, 0, 0, 0, 0, 0] : [0, 0, 0, 0, 0, 0, 0, 0]
12: [0, 0, 0, 0, 0, 0, 0, 0] : [0, 0, 0, 0, 0, 0, 0, 0]
13: [0, 0, 0, 0, 0, 0, 0, 0] : [0, 0, 0, 0, 0, 0, 0, 0]
14: [0, 0, 0, 0, 0, 0, 0, 0] : [0, 0, 0, 0, 0, 0, 0, 0]
15: [0, 0, 0, 0, 0, 0, 0, 0] : [0, 0, 0, 0, 0, 0, 0, 0]

Видно что более 10 простых в первых степенях не встретилось.

Для вывода например комбинаций $p^2qrst\ldots$ надо 2^np заменить на 3*2^np (и уменьшить предел для np до 13 чтобы не вылететь за пределы матрицы). Если подумать об этом сразу и добавить в прогу, то снова ждать не придётся, в матрице n уже всё будет накоплено.

Правда так не различить комбинации $p^3rs$ и $pqrs$, т.е. наличие именно куба простого. Как и 7-й степени, и 15-й, и 31-й, и некоторые другие комбинации. Но они сильно менее вероятны и потому дают лишь мелкую поправку.

-- 07.10.2025, 12:04 --

Если же таки хочется точного анализа, то объявляем вектор с желаемыми разложениями, например (указываются степени простых по убыванию):
pows=[[1], [1,1], [1,1,1], [2], [2,1], [2,1,1], [3], [3,1], [3,1,1]];
Матрицу объявляем как n=matrix(8,#pows).
В цикле команды заменяем на
f=vecsort(factor((x+7)/v[8])[,2]~,,4); j=select(t->t==f,pows,1); if(#j>0, n[6,j[1]]++);\\Будет учитывать первое совпадающее разложение
Вывод например так:
p=[31, 17, 3, 5, 2, 7, 11, 13]; foreach(Vec(vecsort(p,,1)),j, print(p[j],":\t",n[j,]); );

Для предыдущего паттерна и 1e4 кандидатов и указанных выше комбинаций степеней за те же 4 минуты выведет:

2:      [698, 2117, 2868, 0, 16, 42, 0, 0, 5]
3:      [596, 1951, 2805, 0, 28, 96, 0, 8, 14]
5:      [618, 1985, 2886, 0, 21, 64, 0, 4, 4]
7:      [667, 2167, 3002, 0, 16, 50, 0, 0, 3]
11:     [665, 2206, 3015, 0, 11, 30, 0, 0, 1]
13:     [758, 2314, 3035, 0, 13, 23, 0, 0, 1]
17:     [449, 1682, 2610, 0, 66, 193, 0, 17, 56]
31:     [353, 1339, 2034, 0, 80, 338, 0, 52, 133]

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

Что и как и зачем здесь корректировать мне думать уже лень.

-- 07.10.2025, 12:12 --

И да, анализ лишь по numdiv ошибается, например для 31 и $pqr$ (numdiv=8) в первом выводе указано число 2086, но в последнем видно что оно набрано как 2034+52, т.е. $pqr$ и $p^3r$ соответственно.

[Yadryara]

Здорово. Так удобней.

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

И да, анализ лишь по numdiv ошибается, например для 31 и $pqr$ (numdiv=8) в первом выводе указано число 2086, но в последнем видно что оно набрано как 2034+52, т.е. $pqr$ и $p^3r$ соответственно.

Не ошибается. Я же написал, что $pqr$ это основное представление:

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

Если проделать ту же операцию для количества делителей равных 8 и 16, основное представление для которых pqr и pqrs соответственно,

Но основное не значит единственное.

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

Мы откатали обязательную и произвольную программы и нам нужно добрать недостающее количество делителей. То есть нас в первую очередь интересует именно частотность 2086 из 10000, то бишь вероятность примерно 0.21, а не то как именно будут получены 8 делителей. Поэтому в паттерне упрощённо написано $pqr$, для наглядности, на самом деле-то можно 8 делителей написать.

Людям скорее всего это и так понятно, это я на всякий случай проговорил явно.