кортежи последовательных простых. ключ к 19-252

[Dmitriy40]

vicvolf
Читайте и цитируйте правильно (полно), тогда и цитируемое будет верно. Я говорил об "интересующих нас цепочках", т.е. симметричных (и нечётной длины), а не об абы каких.

[vicvolf]

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

vicvolf
Читайте и цитируйте правильно (полно), тогда и цитируемое будет верно. Я говорил об "интересующих нас цепочках", т.е. симметричных (и нечётной длины), а не об абы каких.

Больше того. Это справедливо для любой бесконечной цепочки простых $k$- кортежей при $k>2$.

[Dmitriy40]

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

а до 1e15 оценка соответственно около 30 млрд шт.

Это я погорячился, рост далеко не линейный, а примерно как корень (например до 1e12 их не 40млн, а всего 13.8млн), так что до 1e15 количество будет порядка 400млн.

vicvolf
Повторю, нас интересуют симметричные цепочки нечётной длины и именно про них я и говорил (и это чётко указано в изначальном моём сообщении), а таковые могут быть только на одной (но любой) последовательности $6n\pm1$.
А для чётной длины - нет, числа могут быть сразу на обеих последовательностях. Потому такие и искать легче, и длиннее найдены, и могут состоять из близнецов. Примеры:
5179852391836338871: 0 12 18 28 46 76 78 120 186 210 226 232 238 300 306 312 328 352 418 460 462 492 510 520 526 538
2640138520272677: 0 2 12 14 30 32 54 56 90 92 114 116 132 134 144 146
789795449254776509: 0 2 18 20 42 44 72 74 108 110 138 140 240 242 252 254 270 272 318 320 360 362

[Yadryara]

Вроде бы я научился оценивать сразу количество чистых цепочек. Правда, пока только для троек 6-6, коих в искомой 19-ке три. Столбцы:

Степень 10-ки, Средняя ожидаемая частотность, Факт.

2        1         1
3        8        13
4       53        58
5      315       322
6     2035      1929
7    13761     12313
8    96491     83446
9   703548    595279

Некоторые значения можно проверить по A047948.

[vicvolf]

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

Повторю, нас интересуют симметричные цепочки нечётной длины и именно про них я и говорил (и это чётко указано в изначальном моём сообщении), а таковые могут быть только на одной (но любой) последовательности $6n\pm1$.

Согласен. Кстати, несимметричные цепочки кортежей нечетной длины могут располагаться на обеих последовательностях. Пример, при $k=3$ кортеж простых чисел $(0,2,4)$:$(5,7,11),(11,13,17),(17,19,23),(41,43,47),...$.

[Yadryara]

Вижу, Вы пока с обозначениями не разобрались.

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

кортеж простых чисел $(0,2,4)$:

Этот кортеж обозначается $(0, 2, 6)$. Или тройка 2-4.

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

для троек 6-6

А этот $(0, 6, 12)$

[vicvolf]

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

Этот кортеж обозначается $(0, 2, 6)$. Или тройка 2-4.

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

[Dmitriy40]

Да, в виде интервалов лучше видны симметрии. Однако тогда возникает путаница в голове про длину кортежа, ведь она на 1 больше количества интервалов. Можно конечно просто помнить это, но всё же менее удобно. И ещё из списка интервалов совсем не видно диаметра кортежа (не каждый может в уме просуммировать больше десятка чисел).

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

-- 13.03.2024, 14:42 --

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

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

а до 1e15 оценка соответственно около 30 млрд шт.

Это я погорячился, рост далеко не линейный, а примерно как корень (например до 1e12 их не 40млн, а всего 13.8млн), так что до 1e15 количество будет порядка 400млн.

Да, до 1e13 было 47.5млн, до 3.3e13 было 91.3млн. Всего на несколько процентов быстрее корня. Так что до 1e15 таки порядка 500млн, никаких миллиардов.

[Yadryara]

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

Вроде бы я научился оценивать сразу количество чистых цепочек.

И формулы получаются жутко красивые. Покажу позже.

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

Правда, пока только для троек 6-6, коих в искомой 19-ке три. Столбцы:

Степень 10-ки, Средняя ожидаемая частотность, Факт.

2        1         1
3        8        13
4       53        58
5      315       322
6     2035      1929
7    13761     12313
8    96491     83446
9   703548    595279

Теперь уже и для четвёрок 6-6-18:

 3       0.105         0
 4       2.107         4
 5      19.072        22
 6     143.503       135
 7    1031.313       908
 8    7349.267      6229          1.180
 9   53175.750     44576          1.193

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

Какое же начало, спросите вы, ведь в конце уже целый миллиард брался. Ну а что такое ярд по сравнению с громаднейшим числом 31607# ...

[Yadryara]

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

И формулы получаются жутко красивые. Покажу позже.

А вот не буду пока показывать.

vicvolf, хотели задачку по математике?

Вот задача, для центральной пятёрки 24-6-6-24 найти формулы, которые позволят сколь угодно заполнять вот эту таблицу вниз:

p#    5    6     7      8       9      10      11      12      13     14    15        Sum

07#                                                                    4     4          8       

11#                                                     4      20     20     4         48

13#                                     2      32     108     164     70     8        384

17#                            10     188     886    1790    1352    354    28       4608

19#                    56    1252    7256   18488   22662   12112   2522   164      64512

23#            210   5714   50874  196672  373354  353058  153098  26760  1476    1161216

29#      372 19964 307062 1946818 5908748 9195112 7301150 2741054 427520 21384   27869184

То бишь центральную пятёрку диаметром 60 можно загрязнить ещё максимум 10-ю простыми числами. И нужно суметь посчитать все количества от 5 до 15 для дальнейших интервалов 31#, 37#, 41#, ...

[Yadryara]

И чего все молчат? Даже ТС.

Это же не оффтоп, изучая более простые паттерны, разумеется, есть прицел на то, чтобы оценить количества чистых 19-к для 19-252.

Например

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

То бишь центральную пятёрку диаметром 60 можно загрязнить ещё максимум 10-ю простыми числами.

А паттерн 19-252 можно загрязнить ещё максимум 30-ю простыми числами. То есть максимум $len=49$ для $valids=19$.

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

нужно суметь посчитать все количества от 5 до 15 для дальнейших интервалов 31#, 37#, 41#, ...

Предполагая, что устаканивание произойдёт уже на следующем шаге, я посчитал по формулам:

(31#)

372 49228 1400322 14849698 72373736 179254380 235010290 160650282 53186652 7481680 342144 ; sum = 724598784

(37#)

61132 4326712 86558754 720136186 2922736508 6249930000 7234819514 4441750266 1343814768 175500080 7527168 ; sum = 23187161088

Для 31# можно посчитать и перебором, программно. Первоначальная оценка была около 90 часов. Сейчас удалось достичь оценки в 26-27 часов. Собственно, вот прога для 29# уложилась в час с небольшим:

(PARI)

{print();vc=vector(15);a=vector(29-3);  f=29;mor=1;
forprime(p=2,f,mor=mor*p);

v=[0,24,30,36,60];

forstep(i=2,v[#v]-2,2,
for(j=2,#v-1,
if(i==v[j],next(2)));
k++;a[k]=i);

print();

kp=0;k3=0;k5=0;k7=0;k9=0;
start=0*10^11;fin=mor;

ko=1;m=vector(f,i,[]);
forprime(p=2,#m, m[p]=setminus(vector(p,i,i-1),Set(-v%p));
printf("%d: x %d: %d\n",p,#m[p],m[p]);
ko=ko*#m[p]);

print();
print(mor);print();
print(ko);

x0=Mod(1,2);
foreach(m[29],m29,    
foreach(m[23],m23,
foreach(m[19],m19,
foreach(m[17],m17,
foreach(m[13],m13,
foreach(m[11],m11,
foreach(m[7],m7,
foreach(m[5],m5,
foreach(m[3],m3,
kan=lift(chinese([Mod(m29,29),Mod(m23,23),Mod(m19,19),Mod(m17,17),Mod(m13,13),
Mod(m11,11),Mod(m7,7),Mod(m5,5),Mod(m3,3),x0]));
kps=5;  

for(j=1,#a,
kon=1;
forprime(p=3,f,kon=kon*(kan+a[j])%p);

if(kon>0, kps++));

vc[kps]++;

)))))))));

print(vecsum(vc));print();
print(vc);
print();

}quit;

[Dmitriy40]

Замена внутреннего цикла

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

for(j=1,#a,
kon=1;
forprime(p=3,f,kon=kon*(kan+a[j])%p);
if(kon>0, kps++));

на вот такой

foreach(a+vector(#a,i,kan),j,
   forprime(p=3,f, if(j%p==0, next(2)); );
   kps++;
);

ускоряет вычисления в 3.7 раза.

PS. А молчат все видимо потому что ждут оценки для 19-252 сразу для 67# ...
И я вообще не представляю как Вы собрались её считать, ведь внешние циклы должны перебрать все 293e15 вариантов kan, но тогда проще не считать внутренний цикл, а сразу проверить kan на кортеж.
Можно ли из чисел для 6-30 получить оценку для 19-252 я не знаю, но в этом и смысла нет, ведь количество kan для 6-30 составляет 1.2e22 для 67# (вместо 293e15 для 19-252), т.е. перебирать внешними циклами придётся на 5 порядков больше! Да ещё и вместо 19шт простых ispseudoprime() для каждого из 1.2e22 kan надо выполнять внутренний цикл ... Либо я чего-то недопонял, как Вы собрались оценивать 19-252 для 67#.

-- 17.03.2024, 15:37 --

Очень меня смущает этот внутренний цикл, такое ощущение что он вычисляет в kps что-то довольно простое, что можно вычислить почти без циклов ...
Во всяком случае chinese точно вычислять не нужно, остатки kan по всем нужным простым и так известны из внешних циклов, осталось лишь их аккуратно скомбинировать с a[].

Кстати a[] можно вычислить проще:
a=setminus(vector(v[#v]/2,i,i*2),v);

[Yadryara]

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

ускоряет вычисления в 3.7 раза.

Благодарю. Да, там перемножение для kon было медленным местом.

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

А молчат все видимо потому что ждут оценки для 19-252 сразу для 67#

Ну, цели-то гораздо выше. Помните, если оценивать количество 19-к до тысячи, надо брать 31#, если до 10 тысяч, то 97#, до миллиарда — 31607#. Недавно писал:

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

Ну а что такое ярд по сравнению с громаднейшим числом 31607# ...

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

Либо я чего-то недопонял, как Вы собрались оценивать 19-252 для 67#.

Похоже, пока не поняли. По формулам, которые я пока не показал. Для нескольких меньших паттернов это удалось. Вот-вот получится и для 5-60. Я ведь уже вычислил для 31# и 37#, теперь надо проверить.

Устаканивание для суммы для 19-252 происходит раньше, на 43#. Да Вы сами писали:

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

Запрещённых остатков ровно 19 для всех простых с 43 и далее.

Большое Спасибо, продолжу рассказ.

[Dmitriy40]

Да, я был прав, весь этот внутренний цикл вообще не нужен, можно сразу вычислять kps прямо в самих внешних циклах, это даёт ускорение ещё в 10 раз, общее становится 35 раз (и даже 41 раза). Но правда это если внешние циклы делать в порядке увеличения простого, в обратном порядке (как сейчас у Вас в программе) вдвое-втрое медленнее.

Принцип следующий: перед внешними циклами делаем a2=a;, потом в каждом foreach делаем a29=select(t->(t+m29)%29>0,a23); (меняя соответственно имена переменных и простое число и беря вектор от более верхнего цикла, в самом верхнем берём a2), это оставляет только ненулевые по модулю простого элементы, в самом внутреннем kps=#v+#a3; (ну или какой foreach получится самым внутренним). Всё, внутренний цикл вообще не нужен, как и КТО.

(Ладно, приведу и готовый код)

Весь блок с циклами foreach заменяется на:

a2=a;
foreach(m[3],m3, a3=select(t->(t+m3)%3>0,a2);
foreach(m[5],m5, a5=select(t->(t+m5)%5>0,a3);
foreach(m[7],m7, a7=select(t->(t+m7)%7>0,a5);
foreach(m[11],m11, a11=select(t->(t+m11)%11>0,a7);
foreach(m[13],m13, a13=select(t->(t+m13)%13>0,a11);
foreach(m[17],m17, a17=select(t->(t+m17)%17>0,a13);
foreach(m[19],m19, a19=select(t->(t+m19)%19>0,a17);
foreach(m[23],m23, a23=select(t->(t+m23)%23>0,a19);
foreach(m[29],m29, a29=select(t->(t+m29)%29>0,a23);
   vc[#v+#a29]++;
);););););););););

Здесь даже проверять на пустоту векторов не надо, в таком случае уже следующий foreach просто не будет выполняться.

[Yadryara]

Это гениально!! Для 29# меньше полутора минут хватило И ни черта-то я не понял пока.

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

Можно ли из чисел для 6-30 получить оценку для 19-252 я не знаю, но в этом и смысла нет, ведь количество kan для 6-30

А что за 6-30 ? Я говорил про 5-60.