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

[Yadryara]

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

И подождать пока оформится следующая гениальная идея

О самоиронии пока что не забываю.

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

hy=hammingweight(y)+2;

Скажите, а почему +2? У меня было +1.

Я тем самым вроде нейтрализовывал чрезмерное уменьшение vcmax. Бывает, что он ниже 21 падает:

 vcmax=#vc; while(vcmax>1&&vc[vcmax]==0, vcmax--);

И сейчас не сходится именно из-за этого. Вы все правые нули отрезаете. Для vc[] это правильно, а для cg[] не всегда.

[Dmitriy40]

Про гениальность я не в шутку, а серьёзно. Всё равно не до конца понимаю почему работает.

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

Вы все правые нули отрезаете. Для vc[] это правильно, а для cg[] не всегда.

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

[Yadryara]

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

я отрезаю только при показе на экран

Ну так я же привёл команду. А она выше принта.

Мне просто не следовало ориентироваться на этот vcmax, а учесть вот такую штуковину:

v=[0, 12, 30, 42, 54, 72, 90, 94, 102, 114, 132, 144]
47#: 0, 0, 2721, 334512, 13466775, 249891747, 2546863249, 16086138868, 68747348769, 210614244485, 476468642077, 801226962815, 990558859063, 879984534441, 544295721235, 224443431125, 57914676023, 8545288327, 641392168, 22041600, sum=4282359840000,
time: 5 min, 58,641 ms

v=[0, 12, 30, 42, 54, 72, 90, 102, 106, 114, 132, 144]
47#: 0, 375, 55430, 2541932, 53948912, 640577503, 4714583698, 22748531163, 74378658193, 168051308889, 264021171000, 285601694869, 206596796023, 94670748763, 25066420072, 3221766878, 124116300,
sum=1149892920000, time: 14,209 ms

Длинные кортежи труднее загрязнять, поэтому стандартный максимум длины массива vc[] при добавлении одного простого равен не 22 и не 21, а 20.

Но вот встретился и аномально чистый паттерн с максимумом vc[] лишь 17 , который посчитался в 25 раз быстрее!

Я понял как исправить.

[Yadryara]

Выкладываю. Проверен пока только правый край.

(11-144-1)

v=[0, 12, 30, 42, 54, 72, 90, 102, 114, 132, 144];   31# -------> 73#

lmax = 31

31#                                                   

vc =               1227208,               252110,               24342,               980 ]
                                                                                       *
--> 37#                                                                     37 - 31 =  6
                                                                                       +
cg =               2608364,               574980,               59710,              2660 ]
                                                                                       +
g2 =               1138406,               263552,               30854,              1540 ]
                                                                                       =
vc =              18258392,              3198032,              274818,             10080 ]
                                                                                       *
--> 41#                                                                     41 - 31 = 10
                                                                                       +
cg =              53004854,              9936014,              913552,             36960 ]    
                                                                                       +
g2 =              14670430,              2842404,              218938,              3360 ]
                                                                                       =
vc =             347197072,             55028276,             4313408,            141120 ]
                                                                                       *
--> 43#                                                                     43 - 31 = 12
                                                                                       +
cg =             830604596,            138129734,            11554920,            423360 ]
                                                                                       +
g2 =             211535540,             36256118,             2943724,             87360 ]
                                                                                       =
vc =            7032906938,           1009381460,            72797268,           2204160 ]
                                                                                       *
--> 47#                                                                     47 - 31 = 16
                                                                                       +
cg =           12769496464,           1955561568,           151761316,           5214720
                                                                                       +
g2 =            7158935508,           1233689554,           104441880,           3601920 ]
                                                                                       =
vc =          167404031278,          22384222338,          1525421392,          44083200
                                                                                       *
--> 53#                                                                     53 - 31 = 22
                                                                                       +
cg =          132207060984,          18703368358,          1366253920,          44083200 ]
                                                                                       +
g2 =          169411750632,          27693913256,          2380585640,          88166400 ]
                                                                                       =
vc =         4817924986420,         606562365374,         39492779576,        1102080000 ]
                                                                                       *
--> 59#                                                                     59 - 31 = 28
                                                                                       +
cg =         6912920608914,         915512898482,         62096336320,        1800960000 ]
                                                                                       +
g2 =         3971047262956,         588232346186,         44863949672,        1505280000 ]
                                                                                       =
vc =       169110651386440,       20300660062168,       1269480973696,       34164480000 ]
                                                                                       *
--> 61#                                                                     61 - 31 = 30
                                                                                       +
cg =       149430997676128,       19023101799684,       1252148620672,       34164480000 ]
                                                                                       +
g2 =        31231995132872,        4507049914088,        359833275072,       12499200000 ] 
                                                                                       =
vc =      6099049001327756,      695312096232556,      41590018800320,     1071598080000 ]
                                                                                       *
--> 67#                                                                     67 - 31 = 36
                                                                                       +
cg =      5433790367705256,      655736779432460,      40724036527808,     1071598080000 ]
                                                                                       +
g2 =      2937061682841968,      383970835611104,      25229957421056,      671623680000 ]   
                                                                                       =
vc =    256717864016301348,    28105273260147940,    1621985204433024,    40320752640000 ]
                                                                                       *
--> 71#                                                                     71 - 31 = 40
                                                                                       +
cg =    228603839329213948,    26491815964165156,    1587739450409088,    40320752640000 ]
                                                                                       +
g2 =                     0,                    0,                   0,                 0 ]
                                                                                       =
vc =  11746875094748669676,  1236143272324197004,   68855227132323072,  1653150858240000 ]
                                                                                       *
--> 73#                                                                     73 - 31 = 42
                                                                                       +
cg =                     0,                    0,                   0,                 0 ]
                                                                                       +
g2 =                     0,                    0,                   0,                 0 ]
                                                                                       =
vc = 550859958165525681492, 55698553297778806544, 2993837783854692096, 69432336046080000 ]

Dmitriy40, если vc-шки совпали, жду обновления облака

[Dmitriy40]

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

Dmitriy40, если vc-шки совпали, жду обновления облака

Хм, а сами разве не сравнили? У Вас же 8 правых есть ...
Разумеется совпало. Так что файл в облаке обновил. Только уже не помню там ещё нового кроме 11-144.

[Yadryara]

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

Так что файл в облаке обновил.

Обсчитал все 11-144. Закономерности вновь подтвердились.

(Я бы это сделал ещё вчера, но 8 часов без света...)

(Подробная статистика)

1. [0, 12, 30, 42, 54, 72, 90, 102, 114, 132, 144]

1     E13      1.612     2.7 %        3

1     E14      1.506     3.6 %       19

1     E15      1.750     4.6 %       98

1     E16      1.953     5.7 %      534

1     E17      1.986     6.8 %     3244

1     E18      2.086     8.0 %    19388

2.148 E18      2.125     8.4 %    35139



2. [0, 12, 30, 42, 60, 72, 84, 102, 114, 132, 144]

1     E13      1.304     2.9 %        2

1     E14      2.559     3.8 %        6

1     E15      1.949     4.9 %       47

1     E16      1.954     6.0 %      284

1     E17      2.024     7.2 %     1688

1     E18      2.096     8.5 %    10194

2.148 E18      2.110     8.9 %    18677



3. [0, 12, 30, 54, 60, 72, 84, 90, 114, 132, 144]

1     E13      1.879     2.6 %        2

1     E14      2.028     3.5 %       11

1     E15      2.271     4.5 %       59

1     E16      1.968     5.5 %      415

1     E17      1.985     6.7 %     2547

1     E18      2.074     7.9 %    15313

2.148 E18      2.092     8.3 %    28040



4. [0, 12, 42, 54, 60, 72, 84, 90, 102, 132, 144]

1     E13      1.048     2.7 %        3

1     E14      2.067     3.6 %        9

1     E15      1.858     4.6 %       60

1     E16      2.005     5.7 %      338

1     E17      2.018     6.9 %     2074

1     E18      2.069     8.1 %    12691

2.148 E18      2.097     8.5 %    23106

Сводная статистика для диапазона $0-2.148\cdot 10^{18}$ по всем кортежам 11-144:

1. [0, 12, 30, 42, 54, 72, 90, 102, 114, 132, 144]    2.125     8.4 %    35139
2. [0, 12, 30, 42, 60, 72, 84, 102, 114, 132, 144]    2.110     8.9 %    18677
3. [0, 12, 30, 54, 60, 72, 84,  90, 114, 132, 144]    2.092     8.3 %    28040
4. [0, 12, 42, 54, 60, 72, 84,  90, 102, 132, 144]    2.097     8.5 %    23106

В самую общую таблицу добавились две строчки:

Паттерн      От 0 до   Kпревыш.   Чистых    Кортежей

   9- 84    1     E16    1.894    25.3 %      81588
   9- 96    1     E16    1.826    17.5 %      87501
   9-108    1     E16    1.788    12.8 %      87326
   9-120    1     E16    1.735     9.0 %     442966
   9-132    1     E16    1.675     5.9 %     488223
  11-132    1     E16    1.961     8.2 %        962
  11-144    1     E16    1.970     5.7 %       1571

  11-132    2.148 E18    2.166    11.6 %      59143
  11-144    2.148 E18    2.106     8.5 %     104962

Доля чистых вновь упала с ростом длины. И вновь падение кэфа с ростом диаметра.

Невыполнение последнего для 0—1е16 отношу к флуктуации, связанной с малым числом кортежей.

[Yadryara]

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

Невыполнение последнего для 0—1е16 отношу к флуктуации, связанной с малым числом кортежей.

Всё-таки решил сравнить семейства 11-к и в других диапазонах. Да, так и есть: для большего диаметра кэф меньше.

Паттерн      От 0 до   Kпревыш.   Чистых    Кортежей

  11-132    1     E16    1.961     8.2 %        962
  11-144    1     E16    1.970     5.7 %       1571

  11-132    1     E17    2.079     9.7 %       5470
  11-144    1     E17    2.003     6.9 %       9553

  11-132    1     E18    2.147    11.1 %      32528
  11-144    1     E18    2.081     8.1 %      57586

  11-132    2.148 E18    2.166    11.6 %      59143
  11-144    2.148 E18    2.106     8.5 %     104962

[Yadryara]

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

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

Можно ведь и g2[] и g0[] тоже считать через vc[] для более длинных паттернов.

А вот уже не помню как именно хотел сделать.

Хорошие новости. Уже посчитал максимальный g2[] для 11-144 не более чем за 16 минут. То бишь для $(\frac{d}{2}-5)\# = 67\#$

Пока умею считать только для таких паттернов. Для которых есть простое на 5 меньше радиуса.

Идея ускорения ещё и в том, что строка vc[] нужна только предокейная. Промежуточные считать вроде необязательно. Зная сg[] и g2[], можно по формуле вычислить и g1[]. Можно ли затем уже по другим формулам посчитать g0[] и vc[] — не уверен. Попытаюсь.

[Yadryara]

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

Можно ли затем уже по другим формулам посчитать g0[] и vc[] — не уверен. Попытаюсь.

Да, получилось. Теперь попробую замахнуться на Вильяма нашего Шекспира — рекордный кортеж 11-156.

[Yadryara]

Есть такие соображения.

Начиная с какого-то момента от $\frac16$ до $\frac12$ диаметра vc[] можно считать по старой формуле, а отклонение, которое как раз и определяется по нижней части новой формулы, считать отдельно. Потом сложить и получить сразу vc[] для предокейной строки.

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

На примере 11-144. Дошли, к примеру, до 53#, вычислив vc[] перебором. А дальше, до предокейной 71#, мгновенно вычисляем предварительный vc[] по первой строчке формулы:

vc[l]=

(p-l)*vc[l] + (l-lmin+1)*vc[l+1]
+     cg[l] -            cg[l+1]
+     g2[l] -          2*g2[l+1] + g2[l+2]

Затем считаем массивы cg[] и g2[] от 59# до 71# и 67# соответственно. И, используя 2-ю и третью строчки формулы, получаем отклонение. Которое суммируем с предварительным vc[] до 71#. Точное значение получено. И дальше, как обычно.

[Dmitriy40]

gris
Нашёл Вам несколько самых редких (с наибольшим valids) паттернов для num13:
33059484194640583: [0, 18, 58, 60, 78, 84, 108, 114, 120, 144, 150, 168, 198, 210, 228], num13=6143, valids=14
41956342214813189: [0, 18, 30, 60, 78, 104, 108, 114, 120, 144, 150, 168, 198, 210, 228], num13=7935, valids=14
49859575758966199: [0, 18, 30, 58, 78, 84, 108, 114, 120, 144, 150, 168, 198, 210, 228], num13=7167, valids=14
54161791237928599: [0, 18, 30, 60, 78, 84, 108, 114, 120, 144, 154, 168, 198, 210, 228], num13=8183, valids=14
79752455921818619: [0, 18, 30, 60, 78, 84, 108, 114, 140, 144, 150, 168, 198, 210, 228], num13=8159, valids=14
Плюс перепроверил и известную с valids=15:
2079914861571286679: [0, 18, 30, 60, 78, 84, 108, 114, 120, 144, 150, 168, 198, 210, 228], num13=8191, valids=15
Плюс нашёл 64 из 78 цепочек с valids=13 и 283 из 286 с valids=12 (эти все пока не показываю).

Плюс полностью (т.е. 100% всех кодов!) посчитал все меньшие num11,9,7,5,3,1, буквально за день (c num7 и менее вообще прямо на PARI), выложил в том же файле в облаке что и num15,17 - https://cloud.mail.ru/public/cXJz/js19fzTi7

Забавно что для num11 максимально заполненная цепочка num11=2047, valids=13 встретилась раньше менее заполненных:
2479672831189511: [0, 12, 42, 60, 66, 90, 96, 102, 126, 132, 150, 180, 192], num11=2047, valids=13
4427240114012827: [0, 12, 42, 60, 66, 70, 96, 102, 126, 132, 150, 180, 192], num11=1983, valids=12
17947479917069477: [0, 12, 42, 60, 66, 90, 92, 102, 126, 132, 150, 180, 192], num11=2015, valids=12
Смотрите насколько дальше менее заполненные цепочки ...
Впрочем такое случается и для меньших num, но не так сильно:
1056281: [0, 6, 30, 36, 42, 66, 72], num5=31, valids=7
1172461: [0, 6, 30, 36, 42, 70, 72], num5=30, valids=6
1191571: [0, 6, 30, 40, 42, 66, 72], num5=27, valids=6
1602281: [0, 2, 30, 36, 42, 66, 72], num5=15, valids=6
47: [0, 6, 12], num1=1, valids=3
89: [0, 8, 12], num1=0, valids=2
Но если вдруг аналогичное случится и с num17, то заполнить всю таблицу num17 будет намного сложнее чем найти 19-252.

[Yadryara]

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

Теперь попробую замахнуться на Вильяма нашего Шекспира — рекордный кортеж 11-156.

Приступил. g2[] для 59# посчитался удивительно быстро. Но не с чем сравнивать.

g2 = [0, 0, 0, 19276, 4243822, 204652524, 4349711070, 50778295938, 361404234
214, 1659576229550, 5070471802218, 10452741569846, 14579842540782, 1371122718278
0, 8650318679458, 3652157411880, 1030597330522, 191938626330, 22713162298, 15794
26212, 47900160]    sumg2 = 59439953018880

time: 17min, 20,096 ms

Памяти намного меньше требует!

allocatemem(2^28);

{print(); tz0=getwalltime();

pfin=53; pn=nextprime(pfin+1);

g2=vector(23);

\\ 4-122 10-128 12-130 14-132 16-134 18-136 \\ 20-138

do=[4,10,12,14,16,18];

for (o=1,#do,

v=[0, 6, 30, 36, 66, 78, 90, 120, 126, 150, 156, 2, 2+2*pn];

v[12]=do[o];
v[13]=do[o]+2*pn;

a=setminus(vector(v[#v-2]/2,i,i*2),Set(v)); 

ww=vector(v[#v-2]/2+3-#v+2,i,Map()); mapput(ww[#ww],2^#a-1,1);

forprime(p=2, pfin, 

m=setminus(vector(p,i,i-1),Set(-v%p));
am=vecextract(vector(p-1,i,fromdigits(Vecrev(apply(t->(t+i)%p>0,a)),2)),m);

   for(k=1,#ww,
      rr=Map();
      foreach(ww[k],m,
         b=m[1][1]; qq=m[1][2]; qn=0;
         foreach(am,x,
            y=bitand(x,b);
            if(y==b, qn+=qq; next);
            hy=hammingweight(y)+1; nn=0;
            if(mapisdefined(ww[hy],y,&nn), nn+=qq , nn=qq);
            mapput(ww[hy],y,nn);
         );
         if(qn>0, mapput(rr,b,qn); );
      );
      ww[k]=rr;
   );
   vc=vector(#ww); for(k=1,#ww, foreach(ww[k],x, vc[k]+=x[1][2]; ); );
   vcmax=#vc; while(vcmax>1&&vc[vcmax]==0, vcmax--);

\\print();print("vcmax = ",vcmax);print();

if(p==pfin,   print("o = ",o,"  --> ",nextprime(p+1),"# : ",strjoin(vc[1..vcmax],", "),", sum = ",vecsum(vc));
);
);

for(ll=1,#g2,g2[ll]+=2*vc[ll]);
print();print();
);
print();print(#g2,"  g2 = ",g2, "    ",vecsum(g2));
print();
print("time: ",strtime(getwalltime()-tz0));
print();

}quit;

[Dmitriy40]

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

На примере 11-144. Дошли, к примеру, до 53#, вычислив vc[] перебором. А дальше, до предокейной 71#, мгновенно вычисляем предварительный vc[] по первой строчке формулы:

vc[l]=
(p-l)*vc[l] + (l-lmin+1)*vc[l+1]
+     cg[l] -            cg[l+1]
+     g2[l] -          2*g2[l+1] + g2[l+2]

Затем считаем массивы cg[] и g2[] от 59# до 71# и 67# соответственно. И, используя 2-ю и третью строчки формулы, получаем отклонение. Которое суммируем с предварительным vc[] до 71#. Точное значение получено. И дальше, как обычно.

Так разумеется не получится: посчитанный только по первой строке vc[] для 67# из 53# отличается от правильного vc[] для 67# и потому имея правильные cg[] и g2[] для 67# правильный vc[] для 71# не получим. Но это и не принципиально: имея правильный vc[] для некоторого p, можно, посчитав cg[] и g2[] для того же p, посчитать правильный vc[] для следующего p прямо вот по этой формуле, считать отдельно vc[] (по первой строке) не нужно, это микросекунды и на скорость не влияет.
Проблема всё та же: как получать cg[] и g2[] для следующего p из данных для предыдущего p без полного перебора с самого начала (и без полного ww[], который как я выяснил в память точно не лезет, а скорее всего даже и на диск). Я пока не пойму насколько Вы её решили. Считать больше паттернов, но более длинных - очень интересно, но пока непонятно будет ли во первых выигрыш, во вторых влезут ли они каждый тоже в память чтобы отказаться от полного перебора.

[gris]

Dmitriy40, спасибо! Надо обдумать. Этак Вы и 19-ку найдёте. Торопиться не надо
Да, Вы меня коварно опередили Я только вчера начал искать все 184 паттерна для валидс14. И как раз взял средний по количеству формул
111111 number from
111111 number to
[0,18,30,60,78,84,108,114,120,144,154,168,198,210,228]
search in 22284476618834430 (2.2 E16) - 22284677179324560 (2.2 E16) L=2.01 E11
prove by 31#942480 formulae
time = 18,284 ms.
А Ваш кортеж посмотрел только что:
270052 number from
270052 number to
[0,18,30,60,78,84,108,114,120,144,154,168,198,210,228]
search in 54161761480586760 (5.4 E16) - 54161962041076890 (5.4 E16) L=2.01 E11
prove by 31#

54161791237928599: [0, 18, 30, 60, 78, 84, 108, 114, 120, 144, 154, 168, 198, 210, 228]
time = 18,127 ms.
Я бы и сам его нашёл. Всего полторы сотни тысяч периодов осталось по 18 сек. Нашёл бы!

[Yadryara]

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

Так разумеется не получится: посчитанный только по первой строке vc[] для 67# из 53# отличается от правильного vc[] для 67# и потому имея правильные cg[] и g2[] для 67# правильный vc[] для 71# не получим.

А я написал

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

Затем считаем массивы cg[] и g2[] от 59# до 71# и 67# соответственно.

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

Проблема всё та же: как получать cg[] и g2[] для следующего p из данных для предыдущего p без полного перебора с самого начала (и без полного ww[], который как я выяснил в память точно не лезет, а скорее всего даже и на диск). Я пока не пойму насколько Вы её решили.

Ни насколько. Вы же видели программу: считается для каждого p с самого начала. Правда памяти жрёт гораздо меньше и скорость порой радует.

А вопрос Ваш вроде эквивалентен вот этому:

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

Можно ли досконально рассчитать по формулам кортеж малопростых по чистоте, начиная за шаг до четверти диаметра?

По формулам — скорее нет, чем да.

Остаётся надеяться на всякие ухищрения и комбинаторные тождества. Вот, удлинил паттерн на два, сэкономил память.