Симметричные кортежи из последовательных простых чисел

[Yadryara]

Средневзвешенная длина сократилась с 24 до 3.28. Если это регулярное сокращение, то самой перспективной группой будет 19+21.

[Dmitriy40]

Группа 19+21 занимает 12.8% общего объёма, т.е. если суметь перебирать только в ней, можно найти решение раз в 8 быстрее, если оно в ней.
Если же перебирать вместе с соседней 19+20, занимающей 18% объёма, то выигрыш уже не более 3.3 раз.
Три группы 19+19, 19+20, 19+21 покрывают практически 50% объёма, максимальный выигрыш два раза.
Но я не понимаю как можно заставить быстро перебирать несколько простых только внутри соседних групп, каждое же простое может уменьшить номер группы от 0 до 2. А уменьшит или нет зависит не только от самих остатков по этим вот перебираемым простым, но и от входного числа (вектора, как там распределились пока имеющиеся позиции).
Вот моя программа перебирает 5e8 вариантов в секунду в одном потоке, чтобы её имело смысл вызывать надо чтобы она работала хотя бы секунд 20, в 4 потока это 4e10 вариантов на вызов, столько вариантов можно набрать лишь простыми 41...67, целых 7 штук, и они могут уменьшить номер группы аж на 14! Даже подав числа строго из группы 19+30 перебираться могут группы вплоть до 19+16, а это более 95% всего объёма, т.е. выигрыш вероятности фактически отсутствует. Можно ли так выбрать комбинации остатков по простым 31...67 (да, их понадобится больше чтобы набрать порядка 4e10 вариантов) чтобы максимальное уменьшение группы было поменьше я не знаю, сомневаюсь что получится менее 10 возможного уменьшения, что всё равно перекроет все самые объёмные группы.
В общем идея интересная, но как её реализовать я без понятия.

-- 12.08.2024, 22:17 --

Ещё статистика по группам 19+6 и 19+7.
Из 6792018 в группе 19+6 проходят проверку по простым 71...256 лишь следующие кортежи длиной не менее 13:
40099080399210918331067: [ 0, 6, 12, +30, +42, +72, 90, +96,-104,+120,-122, 126, 132,+156, 162,+180, 210, 222, 240,+246, 252], len=13, valids=11
2924325186879153792738931: [ +0, +6, +12, 30, 42, +72, -88, 90, 96, 120, 126,-130,+132,+156,+162, 180,+210, 222, 240, 246, 252], len=13, valids=11
2470093966477821920391977: [ +0, 6, +12, 30, +42, 72, +90, 96, 120,-122,+126,+132,+156, 162, 180,-194, 210,+222,-236,+240, 246, 252], len=13, valids=10

Из 49611630 из группы 19+7 (далеко не все, да) проверку по простым 71...256 прошли 26 кортежей длиной не менее 13, из них длиннее всего лишь 4шт:
3170229632314035637602077: [ 0, 6, +12, -26, +30, +42, -44, 72, +90, 96,+120, 126,+132,-134, 156,+162,-174, 180,-194,+210, 222, 240, 246,+252], len=15, valids=10
306095594166258362289751: [ +0, +6, 12, +30, 42, +72, -76, +90, +96,-118,+120,+126,+132,-148,+156, 162,-166, 180, 210, 222,-226, 240, 246, 252], len=14, valids=9
1103179835691860937196007: [ 0, +6, +12, +30, +42, 72, 90, 96, 120, 126,+132,+156,+162,-164,-170,+180,-182,-194,-206,+210, 222, 240, 246,+252], len=14, valids=9
7589724038957044583754977: [ +0, +6, +12, -20, +30, 42, 72, 90, -92, 96,-104,+120,+126, 132,+156, 162, 180,-194,-206,+210, 222,+240,+246, 252], len=14, valids=9
При этом были и такие два кортежа:
5533503550107886583025617: [ 0, 6, +12, 30, +42, -56, 72, +90, +96, 120, 126, 132,+156, 162, 180,+210, 222, 240, 246,+252], len=13, valids=12
5709788001614924924692817: [ 0, +6, 12, +30, +42, 72, 90, 96,+120, 126,+132, 156, 162,-170,+180, 210,+222, 240, 246, 252], len=13, valids=12
Это максимальный valids для указанных условий отбора.

-- 12.08.2024, 22:24 --

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

В общем идея интересная, но как её реализовать я без понятия.

Единственное что вроде бы могу сделать, так это перебирать варианты из скажем 31# (или максимум 37#) в порядке увеличения грязноты, в надежде что программа будет уменьшать грязноту, но при этом не вылетит вверх за группы 19+15, 19+16, 19+17, и т.д., т.е. эти группы переберутся первыми. Правда пока не получается подобрать корректные константы, но это наверняка возможно без заметных тормозов счёта.

[Yadryara]

Самым простым способом определить самую перспективную группу пока представляется анализ длины.

Вот есть самая крошечная группа 19+5 длиной 24. Которая после окончательной проверки (а не до 256) превратилась в такие длины:

12       2
11       4
10      31
9      118
8      474
7     1342
6     3484
5     6675
4    10848
3    12935
2    11301
1     5995
0     1551
__________
     54760

Считаем средневзвешенную длину:

$\frac{12 \cdot 2 + 11 \cdot 4 + 10 \cdot 31 + 9 \cdot 118+ 8 \cdot 474+ 7 \cdot 1342+ 6 \cdot 3484+ 5 \cdot 6675+ 4 \cdot 10848+ 3 \cdot 12935+ 2 \cdot 11301+ 1 \cdot 5995+ 0 \cdot 1551}{54760}\approx 3.28$

Но по представленным результатам для групп 19+6 и 19+7 такой расчёт выполнить нельзя — не все длины показаны. Ну и отдельный интерес представляет группа 19+30. Как изменяется длина 49? Для каждого из 6 вариантов расстановки?

[Yadryara]

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

Средневзвешенная длина сократилась с 24 до 3.28. Если это регулярное сокращение, то самой перспективной группой будет 19+21.

А с чего вдруг надо было вычитать из 24-х 3.28 ? Делить же надо. Ведь по каждому малопростому из 24-х надо проводить дальнейшую проверку на простоту. И поскольку $\dfrac{24}{3.28}\approx 7.3$ , эту дальнейшую проверку, грубо говоря, проходит только каждое 7-е число.

Значит, если средневзвешенная длина была 49, то станет всего лишь $\dfrac{49}{7.3}\approx 6.7$.

И тогда самая перспективная группа как раз самая грязная, 19+30 ! А она крошечная: меньше одной стомиллионной от общего количества.

Так что порядок проверки групп нужен строго обратный первоначально предложенному, то есть такой: $19+30, 19+29, 19+ 28, ...$

И тогда, кстати, если искать не минимальную, а хоть какую-нибудь чистую 19-252, могут пригодиться и те самые посчитанные правые числа. Например, для $71\#$ это $76015820160$ . То есть не 2.6 ярда кандидатов в самой грязной группе, а гораздо больше — 76 ярдов. Для $73\#$ их уже больше 2-х триллионов, а именно $2225825159040$. И т. д.

[Yadryara]

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

Так что порядок проверки групп нужен строго обратный первоначально предложенному

Хотя нет, более тщательный анализ показывает, что первоначальное предположение справедливо и вероятность найти 19+0 для 19+5 выше чем вероятность для 19+30 аж в 38 раз:

19+ 5   1.658853263169199247842288359 E-17
19+30   4.291919161372029244999614640 E-19

{print();

t0=getwalltime();

p=0.136;
s=0;
l=24;

forstep(i=l,19,-1,

ver=(p^i*(1-p)^(l-i)); \\*binomial(l)[i+1];

print(i,"   ",ver,"   ",binomial(l)[i+1]);

s=s+ver;
);

print();
\\print(s);
print();
print(strtime(getwalltime()-t0));
print();

quit;}

[Dmitriy40]

Отбор по модулям простых 71...256 связан с тем что такая проверка в десятки раз быстрее получения списка простых в интервале [x...x+252]. Плюс это отбрасывает приличную часть точно не 19-252 цепочек (я же решение пытаюсь найти, а не полную статистику, как выше для группы 19+5, 8МБ лога кстати).
А ограничение длины снизу (минимум 13) ради сокращения размера лога.

Проверил часть групп 19+7 и 19+8, 318872706 и 1820850596 вместо полных 325858198, 8732689082 (97.9% и 20.9%), тоже с указанным отбором. Суммарно по ним, самые длинные:
2646941926452971682625171: [ +0, +6, 12, 30, +42, 72, -82, 90, 96,-118, 120, 126,+132,-148, 156, 162, 180,-190, 210,+222,+240,+246, 252], len=16, valids=12
3957064735267138948226701: [ +0, +6, 12, -28, 30, +42, -58, 72, +90, 96,-118, 120, 126,-130, 132, 156,+162, 180, 210,+222, 240,+246, 252], len=16, valids=12
6117838779406400224068257: [ +0, 6, 12, -20, 30, +42, -44, 72, +90, +96, 120, 126, 132,+156, 162,-164, 180,-182, 210, 222, 240,+246,+252], len=16, valids=12
4527180549437276115218761: [ 0, 6, +12, -28, 30, 42, +72, -82, 90, +96,-118, 120, 126,+132, 156,+162,+180,-196, 210,+222,-228, 240,+246, 252], len=16, valids=11
6763738198997598839664571: [ +0, 6, 12, 30, +42, -58, +72, -88, 90, +96, 120, 126,+132, 156, 162,-166, 180,-208, 210,+222,-228,+240,+246, 252], len=16, valids=11
263923260402499407515627: [ 0, 6, 12, 30, 42, 72, -84, 90, +96, 120,+126, 132, 156, 162, 180,+210,+222, 240,+246, 252], len=15, valids=14
5729306415679395249220447: [ 0, 6, 12, 30, 42, +72, 90, +96,+120,-124, 126, 132, 156, 162,+180, 210,+222, 240, 246, 252], len=15, valids=14
Последние дали и максимальный valids.
С valids=13 нашлись 10шт длиной 15, 9шт длиной 14 и 3шт длиной 13.

[Yadryara]

Dmitriy40, понятно. Зато есть важное число: 0.136.

Проверил: да, при расчёте с вероятностью $p=0.136$ пройти все проверки по простым выше 67, получается примерно то же количество кортежей с длиной 3. Вот по этой проге 12944, а по факту 12935.

{print();

t0=getwalltime();

p=0.136;
s=0;

for(l=24,24,

forstep(i=l,3,-1,

ver=(p^i*(1-p)^(l-i))*binomial(l)[i+1];

if(i==3,print(l,"   ",54760*ver));

));

print();
print(strtime(getwalltime()-t0));
print();

quit;}

Какой отсюда вывод. Предпочтительный порядок проверки понятен.

Но сомнения опять вызывает диапазон. Если в $0-67\#$ искомого кортежа нет, то что в лоб, что по лбу — он не найдётся при любом способе проверки.

А вот для $0-71\#$, где предположительно 11 искомых кортежей, порядок проверки очень даже важен. Кстати, а вероятность для этого диапазона пройти все проверки по простым выше 71-го меньше чем 0.136 ?

-- 13.08.2024, 10:42 --

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

я же решение пытаюсь найти, а не полную статистику, как выше для группы 19+5, 8МБ лога кстати

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

Для 71# насколько сложно посчитать такие же таблички для групп 19+4 и 19+5 ?

[Dmitriy40]

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

Кстати, а вероятность для этого диапазона пройти все проверки по простым выше 71-го меньше чем 0.136 ?

Не знаю откуда взялась 0.136, но по идее чем по меньшему количеству простых проверяем кортеж, тем выше вероятность пройти проверку. Значит ответ - чуть больше, если только по простым до 256. А если до $\sqrt{71\#}$ или $\sqrt{67\#}$, то тогда будет valids=19 и сколько их таких никто не знает, вероятность же посчитать сложнее - надо сравнить $\frac{52}{71}$ и $\prod\limits_{p=\sqrt{67\#}}^{\sqrt{71\#}}\frac{p-19}{p}$, а это до 5 суток счёта на PARI.
Другое дело что такие кортежи уже 100% прошли проверку по 71, т.е. их уже меньше чем было для 67# (не в штуках, а в плотности).

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

Для 71# насколько сложно посчитать такие же таблички для групп 19+4 и 19+5 ?

19-4 для 71# в разы сложнее потому что надо иметь точные 19+5 и 19+6 для 67#, соответственно нужна точная 19+8 для 61# и так далее по +2 на каждое простое 61...43 и +3 на 41...29.
Для 19+5 для 71# ещё в разы сложнее потому что нужны будут точные 19+7 для 67# (325млн), 19+9 для 61# (938млн), 19+11 для 59# (1млрд) и так далее. Столько на PARI обрабатывать, да ещё и перебором по остаткам, морока. Но как сделать получение сразу скажем 325млн кортежей для 67# (группы 19+5, 19+6, 19+7) не перебирая 48 остатка по модулю 67 для всех 938млн кортежей для 61# не знаю. Т.е. выходит что надо перебрать 325e6*52+938e6*48+1e9*42+658e6*40+256e6*34+...=1.4e11 кортежей.
Для сравнения, для получения группы 19+5 для 67# достаточно иметь группы по 19+7 для 61# (1.2млн), 19+9 для 59# (5млн), 19+11 для 53# (7.1млн), 19+13 для 47# (5.6млн), т.е. перебрать всего 1.2e6*48+5e6*42+7.1e6*40+5.6e6*34+...=742млн, почти в 200 раз меньше. Вероятно и перебор для 19+5 на 71# будет в 200 раз дольше 9 минут, т.е. больше суток.
Получение 19+4 на 71# потребует 19+6 на 67# (6.8млн), 19+8 на 61# (43.5млн), 19+10 на 59# (86.5млн), 19+12 на 53# (79млн), 19+14 на 47# (44млн), всего 6.8e6*52+43.5e6*48+86.5e6*42+79e6*40+44e6*34+...=1e10, в 14 раз больше 19+5 на 67# за 9 минут или 2ч.
Проверю корректность оценки сравнением 96м для 19+6 на 67# против 9.7м для 19+5 на 67#: 43.5e6*48+86.5e6*42+79e6*40+44e6*34+...=1e10, тоже в 14 раз больше 742e6 вместо 96/9.7=10, почти в полтора раза завышает. Ну хоть не на порядок.
В принципе используя такой метод оценки (суммируя количество кортежей в нужных группах по каждому простому) Вы тоже можете прикинуть относительную трудность подсчёта.

-- 13.08.2024, 12:34 --

Перебор группы 19+30 для 67# идёт уже 3ч (и далёк от завершения) и лучшее по valids из пока найденного (длина минимум 19 и проверка по простым до 256):
352472214626473083051577: [ 0, +6, 12, -16, -22, -24, +30, -40, 42, -70, +72, 90, 96, 120, 126,+132,-136, 156, 162, 180, 210, 222,+240, 246, 252], len=20, valids=14
7820172587153217956775191: [ 0, 6, +12, 30, 42, -60, +72, 90, +96,-116, 120, 126, 132,+156, 162,-168,-176,+180,-182,-198, 210, 222,-228, 240, 246, 252], len=21, valids=14
1374651560483745975521171: [ 0, +6, 12, -20, +30, 42, -60, +72, +90, -92, 96, 120, 126, 132, 156,+162,-170, 180,-198,-200, 210,+222,-236, 240, 246, 252], len=20, valids=13
2897685964720053287190491: [ +0, +6, 12, 30, -32, 42, -68, 72, -86, +90, 96, 120, 126, 132,+156, 162,-168, 180, 210, 222,-236,+240,-242,+246, 252], len=19, valids=13
Самые длинные 5шт len=22 с valids=11,11,9,8,5.

-- 13.08.2024, 12:49 --

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

Кстати, а вероятность для этого диапазона пройти все проверки по простым выше 71-го меньше чем 0.136 ?

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

А если до $\sqrt{71\#}$ или $\sqrt{67\#}$, то тогда будет valids=19 и сколько их таких никто не знает, вероятность же посчитать сложнее - надо сравнить $\frac{52}{71}$ и $\prod\limits_{p=\sqrt{67\#}}^{\sqrt{71\#}}\frac{p-19}{p}$, а это до 5 суток счёта на PARI.

Оценил по другому, взял произведение лишь 1/10009 части в конце интервала в 10009-й степени (получилась оценка сверху), оно уже оказалось меньше:

? 52/71.
%1 = 0.73239436619718309859154929577464788732
? k=sqrt(vecprod(primes([2,71]))); s=1.0; forprime(p=k-2.08e9,k, s*=(p-19)/p); s^10009
%2 = 0.58052983480847360131840581561133844714

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

[Yadryara]

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

Не знаю откуда взялась 0.136,

Да попросту перевернул 7.3 и округлил в пол, чтоб не обольщаться:

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

И поскольку $\dfrac{24}{3.28}\approx 7.3$ ,

$$\lfloor{\dfrac{3.28}{24}}\rfloor = 0.136$$

Кстати, другим способом посчитал, получилось $0.137$. И этим же способом посчитал для 71# :

Diapazon     p1       p2

0 - 67#    0.130    0.137
0 - 71#    0.128    0.129

Занятно, вероятность, что произвольно взятое число из диапазона $0 - 71\#$ пройдёт проверку по простым до 71 включительно, почти такая же, как и та, что оно пройдёт и остальную проверку уже до корня.

{print();

t0=getwalltime();

w=71;

period=vecprod(primes(primepi(w)));

print("     ",period);
print();

for(i=1,10^7,

kan=random(period);

forprime(j=2,w,

if(kan%j==0, next(2));

);

kkan++;

if(ispseudoprime(kan), kpod++;

));

print(kpod,"    ",kkan,"    ",kpod/kkan*1.0);
print();
print(strtime(getwalltime()-t0));
print();

quit;}

[Yadryara]

Попытался посчитать матожидание количества кортежей для 67# уже 3-м способом. По HL-1 было 0.51 кортежа. Однако у меня получается 0.51 только если взять $p=0.134$. Для $p=0.137$ получается уже 0.72 кортежа.

{print();

t0=getwalltime();

vc=[0, 0, 0, 0, 0, 54760, 6792018, 325858198, 8732689082, 153606059908, 
1913747177340, 17483063702860, 119249071095310, 615440511892708, 
2432725989818718, 7447022885574328, 17813512167763926, 33491264807265158, 49603797522180000, 57819061781785358, 52856050981018074, 37699907542234036, 20848732917709526, 8879811423403526, 2895245491002764, 719253136438230, 135295969437234, 18878969508802, 1836531247768, 107619357728, 2666478240];

p=0.134; i=19;
kkor=0;

for(l=24,49,

ver=(p^i*(1-p)^(l-i));

kkor+=vc[l-18]*ver;

print(l,"   ",vc[l-18]*ver,"   ",kkor);
);

print();
print(strtime(getwalltime()-t0));
print();

quit;}

[Dmitriy40]

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

Перебор группы 19+30 для 67# идёт уже 3ч (и далёк от завершения)

Однако завершился за 4ч. Ничего лучше показанного не найдено.

[Yadryara]

Если сможете посчитать vc[] для 71#, то таким же способом смогу посчитать после какого количества обсчитанных кандидатов матожидание превысит 1-цу. Может тоже стоит 3 тысячных сбросить до 0.126.

[Yadryara]

В принципе, прикинуть можно и по нынешнему раскладу. В среднем, если проверять кортежи безыдейно, то для нахождения $\frac1{11}$ всех кортежей нужно проверить ту же долю, то есть 9.1% кандидатов. Если проверять от чистых к грязным, то 5.2%.

Допустим, этот же процент необходимой проверки сохранится и для 71#. Значит до 1-го кортежа проверить нужно будет в среднем почти 800 квадриллионов кандидатов. Что конечно гораздо больше чем все 293 квадрика в нынешнем 67#.

[Dmitriy40]

Для 71# vc[19+4]=240396. И считалось оно 1.75ч, без проверки кортежей (впрочем 240К проверить быстро), только перебор с подсчётом.
Запустил с проверкой кортежей, 19+4 все, а 19+5 и 19+6 только часть от всех и с отбором по простым до 256 и длиной не менее 15.

[Dmitriy40]

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

а 19+5 и 19+6 только часть от всех и с отбором по простым до 256 и длиной не менее 15.

Погорячился, из 38034460 (группа 19+5) + 317757600 (группа 19+6) (оба количества сильно занижены от реальных!) ни одного кортежа с указанными условиями не нашлось.

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

Если сможете посчитать vc[] для 71#,

Статистика по всей группе 19+4 (len\valids: штук):

Используется синтаксис Text

        10      9       8       7       6       5       4       3       2       1       0       =
12              1                                                                               1
11      7       4       1                                                                       12
10      4       20      26      7                                                               57
9               30      122     95      45      3                                               295
8                       176     442     333     123     7                                       1081
7                               810     1627    1132    234     16                              3819
6                                       2842    4992    2424    381     19                      10658
5                                               8322    10935   4220    484     17              23978
4                                                       18873   18656   4929    357     9       42824
3                                                               31458   22510   3712    117     57797
2                                                                       37747   16553   1313    55613
1                                                                               28391   5931    34322
0                                                                                       9939    9939
=       11      55      325     1354    4847    14572   32473   54731   65689   49030   17309   240396

На всё про всё хватило 2.1ч.