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

[Yadryara]

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

Раз для вычисления всех ваших массивов достаточно знать vc[] для некоего другого паттерна и раз для cg[] паттерн удлиняется лишь на 1 элемент и потому вычисление cg[] занимает больше всего времени - надо каждый паттерн в первых двух циклах тоже разбить на ещё более длинные.

1. Достаточно знать vc[] для каждого из некой совокупности других паттернов. Для cg[] для 19-252 для вычисления 71# таких паттернов 8 штук.

2. Двигаться надо от наибольшего известного, то есть от 67# к 71#. И цикл вычисления cg[] нужен только один. Это хорошая новость.

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

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

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

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

[Dmitriy40]

gris
Ещё редкость:
568075716637184849: [0, 18, 30, 60, 78, 84, 92, 114, 120, 144, 150, 168, 198, 210, 228], num13=8063, valids=14
Их осталось найти 5 ...

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

Сколько у Вас было посчитано до 113# ? 7 правых?

Они все есть в выложенном в облако файле, да, 7 правых (для них #ww[] уже был в десятки миллионов и дальше памяти мало).

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

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

Вдвое это не смертельно.

[Dmitriy40]

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

1. Достаточно знать vc[] для каждого из некой совокупности других паттернов. Для cg[] для 19-252 для вычисления 71# таких паттернов 8 штук.
2. Двигаться надо от наибольшего известного, то есть от 67# к 71#. И цикл вычисления cg[] нужен только один. Это хорошая новость.

Заценил скорость одного первого паттерна. Считается примерно раз в 15 быстрее 19-252, все 8 паттернов будут считаться где-то вдвое быстрее 19-252. Но их надо считать на шаг меньше, значит скорость будет в итоге раз в 30 выше и на 67# (для проверки) хватит часов 6, а на 71# дня 4. Но на 73# надо уже месяца два ... Не вариант. Надо сильнее забивать/удлинять паттерны чтобы считались ещё намного быстрее.

Кстати мои программы уже с конца марта не используют удвоения (включая и обе недавно упомянутые на PARI), считают любые паттерны прямо как есть.

[Yadryara]

Давайте сразу же сверим часы.

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

Заценил скорость одного первого паттерна.

Вот этого?

v0=[0,6,12,30,42,72,90, 96, 120, 126, 132,142,156, 162, 180, 210, 222, 240, 246, 252];

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

Но их надо считать на шаг меньше, значит скорость будет в итоге раз в 30 выше и на 67# (для проверки) хватит часов 6,

Уже посчитано?

Другие 7:

v0=[0,6,12,30,42,72,90, 96, 120, 126, 132,148,156, 162, 180, 210, 222, 240, 246, 252];
v0=[0,6,12,30,42,72,90, 96, 120, 126, 132,154,156, 162, 180, 210, 222, 240, 246, 252];
v0=[0,6,12,30,42,72,90, 96, 120, 126, 132,156, 162,172, 180, 210, 222, 240, 246, 252];
v0=[0,6,12,30,42,72,90, 96, 120, 126, 132,156, 162, 180,184, 210, 222, 240, 246, 252];
v0=[0,6,12,30,42,72,90, 96, 120, 126, 132,156, 162, 180, 210,214, 222, 240, 246, 252];
v0=[0,6,12,30,42,72,90, 96, 120, 126, 132,156, 162, 180, 210, 222,232, 240, 246, 252];
v0=[0,6,12,30,42,72,90, 96, 120, 126, 132,156, 162, 180, 210, 222,238, 240, 246, 252];

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

Но на 73# надо уже месяца два

Нет, 73# для этого паттерна, как и для других семи считать не надо.

Каждый паттерн нужен, что называется здесь и сейчас, и для 73# будут свои паттерны. Ведь я делал схему для того, чтобы это было понятно. Могу ещё сделать, именно для 19-252.

[Yadryara]

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

Эти 5 неизвестных — 5 массивов, которые нынче обозначаю c1, cg, g2, g1, g0. И вот, при расщеплении 1-го паттерна из тех 52-х, уже появился 6-й массив — c2.

Формула пока усложнилась несильно, совпадения состоялись при добавлении всего одного слагаемого c2[i] в 4-ю строку:

rp = pn-#v0+1;

for(i=1,#vco-1,

vc[i] =

(rp-i)*vco[i] + i*vco[i+1]
+       cg[i] -    cg[i+1]
+       g2[i] - 2* g2[i+1] + g2[i+2]
+       c2[i]
);

Ну, это я перемудрил. Не надо никакого 6-го массива. Рабочий множитель rp просто надо увеличить на единичку: rp = pn-#v0+2

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

Надо сильнее забивать/удлинять паттерны чтобы считались ещё намного быстрее.

Не нравится слово расщеплять? Показываю схему дальнейшего забивания паттерна по линии cg :

[0,6,12,30,42,72,90,96,120,126,132,156,162,180,210,222,240,246,252];

1-й шаг:

[0,6,12,30,42,72,90,96,120,126,132,142,156,162,180,210,222,240,246,252];

2-й шаг:

[0,6,12,14,30,42,72,90,96,120,126,132,142,156,162,180,210,222,240,246,252];
[0,6,12,20,30,42,72,90,96,120,126,132,142,156,162,180,210,222,240,246,252];
[0,6,12,30,38,42,72,90,96,120,126,132,142,156,162,180,210,222,240,246,252];
[0,6,12,30,42,68,72,90,96,120,126,132,142,156,162,180,210,222,240,246,252];
[0,6,12,30,42,72,80,90,96,120,126,132,142,156,162,180,210,222,240,246,252];
[0,6,12,30,42,72,90,96,98,120,126,132,142,156,162,180,210,222,240,246,252];
[0,6,12,30,42,72,90,96,104,120,126,132,142,156,162,180,210,222,240,246,252];
[0,6,12,30,42,72,90,96,110,120,126,132,142,156,162,180,210,222,240,246,252];[0,6,12,30,42,72,90,96,120,126,132,142,148,156,162,180,210,222,240,246,252];
[0,6,12,30,42,72,90,96,120,126,132,142,154,156,162,180,210,222,240,246,252];
[0,6,12,30,42,72,90,96,120,126,132,142,156,162,172,180,210,222,240,246,252];
[0,6,12,30,42,72,90,96,120,126,132,142,156,162,180,184,210,222,240,246,252];[0,6,12,30,42,72,90,96,120,126,132,142,156,162,180,210,214,222,240,246,252];
[0,6,12,30,42,72,90,96,120,126,132,142,156,162,180,210,222,232,240,246,252];
[0,6,12,30,42,72,90,96,120,126,132,142,156,162,180,210,222,238,240,246,252];

Комбинаторный взрыв. И так по 15 вариантов на каждый из 8.

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

[Yadryara]

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

И так по 15 вариантов на каждый из 8.

Можно конечно и не 120 считать, а 92, ибо повторы.

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

Кстати мои программы уже с конца марта не используют удвоения (включая и обе недавно упомянутые на PARI), считают любые паттерны прямо как есть.

А почему?

[Dmitriy40]

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

Вот этого?
v0=[0,6,12,30,42,72,90, 96, 120, 126, 132,142,156, 162, 180, 210, 222, 240, 246, 252];

Нет, я взял переход 61#->>67# (для сверки), Ваша программа выдала паттерны:
[0, 6, 12, 30, 42, 72, 90, 96, 120, 126, 132, 134, 156, 162, 180, 210, 222, 240, 246, 252]
[0, 6, 12, 30, 42, 72, 90, 96, 120, 126, 132, 140, 156, 162, 180, 210, 222, 240, 246, 252]
[0, 6, 12, 30, 42, 72, 90, 96, 120, 126, 132, 146, 156, 162, 180, 210, 222, 240, 246, 252]
[0, 6, 12, 30, 42, 72, 90, 96, 120, 126, 132, 156, 162, 164, 180, 210, 222, 240, 246, 252]
[0, 6, 12, 30, 42, 72, 90, 96, 120, 126, 132, 156, 162, 176, 180, 210, 222, 240, 246, 252]
[0, 6, 12, 30, 42, 72, 90, 96, 120, 126, 132, 156, 162, 180, 206, 210, 222, 240, 246, 252]
[0, 6, 12, 30, 42, 72, 90, 96, 120, 126, 132, 156, 162, 180, 210, 222, 224, 240, 246, 252]
[0, 6, 12, 30, 42, 72, 90, 96, 120, 126, 132, 156, 162, 180, 210, 222, 230, 240, 246, 252]
Я взял первый.
И кстати они все уже не симметричные, так что удваивать я сразу не буду даже пытаться. Но и трогать формулу cg[]=2*vc[] тоже не буду конечно.

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

Уже посчитано?

Нет, у меня программа после начала счёта выдаёт текущую оценку требуемого времени (вначале ошибается раза в 2, но это учитываю), запустил и посмотрел, там для 61# типа часа, но ждать не стал, всё равно сравнивать не с чем.

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

Нет, 73# для этого паттерна, как и для других семи считать не надо.

Это уже понятно, каждый паттерн считаем только до одного числа. Я тут уже про оценку общего времени на все паттерны. Конечно для 71# и 73# паттерны будут другими, но понадеялся что скорость их счёта сильно не изменится (хотя можно и выборочно проверить).

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

Не нравится слово расщеплять?

Нравится. Просто ещё не привык, не запомнилось.

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

Комбинаторный взрыв. И так по 15 вариантов на каждый из 8.

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

Можно конечно и не 120 считать, а 92, ибо повторы.

У нас и так комбинаторный взрыв, просто он спрятан в процедуре Calc() в моей программе или в размере ww[] в последней программе (и в ней взрыв взрывается не до конца, а лишь до трети диаметра, дальше останавливается, почему она собственно и вообще считает за разумное время, главное чтобы памяти хватило).
92 вместо 120 это тоже прекрасно, это как раз похоже на вот ту остановку взрыва. Думаю следующая итерация расщепления тоже даст не в 15 раз больше, а раз в 10. И следующая. И скоро вообще места в паттерне закончатся и взрыв остановится. А если ещё при этом удастся впихнуть в память весь ww[], то общие паттерны можно будет считать лишь один раз, а не для каждого простого с самого начала. Сколько паттернов получится и как их результаты скомпоновать в итог - ещё вопрос конечно, но это наиболее перспективное направление, остальные два с половиной (или перебор, или тянуть ww[], или сначала второе, потом досчитывать первым) упираются в память или время.

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

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

Кстати мои программы уже с конца марта не используют удвоения (включая и обе недавно упомянутые на PARI), считают любые паттерны прямо как есть.

А почему?

Да наткнулся пару раз что не срабатывало (ещё на программе с Calc()), плюнул. Плюс заманался каждый раз помнить где что подправить (2 на 1 и обратно) для каждого паттерна (они ведь и несимметричные считались). Плюс выигрыш вдвое при комбинаторном взрыве роли не играет - пока времена менее чем в днях (тогда плевать) или более чем в месяцах (это по любому не посчитать).


Кстати, если в вашей последней программе не считать последнюю итерацию (p==pfin) в ww[], а сразу увеличивать vc[], то памяти нужно раз в 10 меньше (ww[] только для предыдущего простого перед pfin), а считается впятеро быстрее. И для 41#-->43# для 19-252 с 4-мя циклами хватает примерно 1млн элементов в ww[] и считается 3м15с вместо 17м26с. Но 47# посчитать снова не получится, надо до 9.5млн элементов ww[] (а у меня видимо не получится посчитать 53#).

Если же считать лишь правые элементы, то зря взяли лишь три, можно и 5 (раз считались 4 правых для 19-252, то тут должно хватить минимум на 1 больше), там в правых ww[k] размеры маленькие. И для этого в первых двух циклах надо считать на 1 левее желаемого (т.е. 6 правых элементов для получения правильных 5 правых), а в 3 и 4 на 2 левее желаемого (что не страшно, ведь в них паттерны длиннее на 2 и соответственно размеры ww[] меньше). У меня так получилось посчитать 7 правых 41#-->61# за 2ч, у Вас должно получиться 5 правых (и заметно быстрее). Всё же чем длиннее сравнение тем надёжнее отсутствие ошибок.

[Yadryara]

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

И кстати они все уже не симметричные, так что удваивать я сразу не буду даже пытаться. Но и трогать формулу cg[]=2*vc[] тоже не буду конечно.

Вы про вот эту? cg[ll+1]+=2*vc[ll]

Вот как раз отсюда 2-ку конечно же надо убирать для несимметричных.

И отсюда тоже: g2[ll+2]+=2*vc[ll]

Об остальном позже...

[Yadryara]

Чтоб было лучше понятно, о чём я говорю. Вот обсчёт несимметричного паттерна (1-го из 52-х) для 11-144:

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

(PARI)

{print(); tz0=getwalltime();

v0=[0, 12, 30, 42, 54, 72, 2*37, 90, 102, 114, 132, 144];

vco = [0, 0, 0, 0, 0, 1, 60, 1887, 20681, 116158, 406627,  945186, 1545939, 1821693, 1517572,  892686,  347097,   75059,   7314,   280, 0];

forprime(pfin=31, 31,

pn=nextprime(pfin+1);

tz1=getwalltime();

cg=vector(#vco);

v=[0, 12, 30, 42, 54, 72, 2*37, 12 + 2*pn, 90, 102, 114, 132, 144];

o=2;
while(v0[o]+2*pn < v0[#v0],

v[8]=v0[o]+2*pn;

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

ww=vector(v[#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--);

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

for(ll=1,#cg-1,cg[ll+1]+=vc[ll]);
\\print();print();
o++;);
print();



o=#v0;
while(v0[o]-2*pn > v0[1],

v[8]=v0[o]-2*pn;

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

ww=vector(v[#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--);

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

for(ll=1,#cg-1,cg[ll+1]+=vc[ll]);
\\print();print();
o--;);
print();



print(#cg,"  cg = ",cg, "    ",vecsum(cg));
print();
print("time: ",strtime(getwalltime()-tz1));
print();print();



print(); tz2=getwalltime();

g2=vector(#vco+1);

do=setminus(vector((v0[#v0]-2-2*pn)/2,i,i*2),Set(v0));
do=setminus(Set(do),Set(vector(#v0,i,v0[#v0+1-i]-2*pn)));

print();
print(#do,"  do = ",do);
print();

for(o=1,#do,

v=[0, 12, 30, 42, 54, 72, 2*37, 90, 102, 114, 132, 144, 2, 2+2*pn];

v[#v-1]=do[o];
v[#v]=do[o]+2*pn;

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

ww=vector(v[#v-2]/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--);

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

for(ll=1,#g2-2,g2[ll+2]+=vc[ll]);
\\print();print();
);


print();print(#g2,"  g2 = ",g2, "    ",vecsum(g2));
print();
print("time: ",strtime(getwalltime()-tz2));
print();


rp = pn-#v0+2;

for(i=1,#vco-1,

vc[i] =

(rp-i)*vco[i] + i*vco[i+1]
+       cg[i] -    cg[i+1]
+       g2[i] - 2* g2[i+1] + g2[i+2]
);

vc  = vc[1..#vco];
vco = vc;

print();
print("vc  -->  ",pn,"# : ",vc,"      ",vecsum(vc));
print();
print();
print("time: ",strtime(getwalltime()-tz0));
print();
print();
);
print();

}quit;

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

И скоро вообще места в паттерне закончатся и взрыв остановится.

И не только поэтому. Вилка ведь расширяется. Для 79# будет не 15, а 13 вариантов, а затем всё меньше и меньше. На схеме это видно.

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

у Вас должно получиться 5 правых (и заметно быстрее).

Да я это понимал. Просто хотел побыстрее дойти до 113# и убедиться, что всё чётко.

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

Кстати, если в вашей последней программе не считать последнюю итерацию (p==pfin) в ww[], а сразу увеличивать vc[], то памяти нужно раз в 10 меньше (ww[] только для предыдущего простого перед pfin), а считается впятеро быстрее.

Последняя ww[] не нужна? Пока не понял, почему.

Уже давно понятно, что теперь можно 11-156 посчитать. А вдруг и 13-168...

[Dmitriy40]

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

Последняя ww[] не нужна? Пока не понял, почему.

Не последняя ww[], а все массивы ww[] для p=pfin. Посмотрим что делается с ww[] и vc[] на последней итерации, когда p=pfin: перебираются все ww[] от предыдущего простого, для каждого перебираются допустимые остатки, для каждого вычисляется новое hy (будущее k) и соответствующий элемент ww[hy] увеличивается (или добавляется если такого не было). По окончании все ww[k=1..#ww] суммируются в vc[k]. Но значения ключей (y) при суммировании не нужны, нужно только hy (которое фактически новое k) и без разницы новый это элемент ww[hy] или такой уже был - их сумма от этого не изменится. Потому вместо добавления командой mapput можно просто добавить значение сразу к vc[]. Т.е. на последнем проходе (для pfin) вместо обновления ww[] можно сразу считать vc[] (независимо новый это элемент или такой уже встретился). Это чуть сокращает код (что для PARI тоже важно) и сильно сокращает размер ww[] (примерно раз в 10, до размера ww[] для precprime(pfin), ведь потом он уже не обновляется) и главное вместо модификации огромной структуры Map командой mapput (что очевидно совсем не быстро) можно сделать простое и быстрое vc[hy]+=qq.
Плюс это надо делать не для каждого p как у Вас, а лишь после окончания цикла по p, ведь для промежуточных p массив vc[] нам не нужен, нужен ww[].

В итоге инициализация vc=vector(#ww); выносится перед forprime(p=2,pfin,, вычисление for(k=1,#ww, foreach(ww[k],x, vc[k]+=x[1][2]; ); ); удаляется, перед циклом foreach(am,x, добавляется другой вариант перебора для последней итерации if(p==pfin, foreach(am,x, vc[hammingweight(bitand(x,b))+1]+=qq; ); next; ); (можно if и внутрь цикла по am сунуть, но PARI такой, ему чем меньше команд тем лучше и потому добавлять лишнюю команду внутрь самого глубокого цикла не есть хорошо, лучше продублировать чуть кода) - и вуаля, вместо обновления ww[] для p=pfin будет считаться сразу vc[]. С которым после выхода из цикла forprime(p=2,pfin, уже делаете что и прежде.
Единственная задача или фича - последней итерацией при p=pfin весь массив ww[] обнуляется, что в принципе и неплохо (память освобождается), но не позволяет показать его размеры в print. Решается командой wk=sum(k=1,#ww,#ww[k]); сразу по входу в цикл forprime(p=2,pfin, и показом в print числа из wk.

[Yadryara]

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

Не последняя ww[], а все массивы ww[] для p=pfin.

Ну так fin от слова финиш. Последняя итерация массивов.

Да, вроде верно. Я в Вашу часть проги пока по-новой не вникал.

Вы где сейчас копаете? Есть ли трудности?

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

у Вас должно получиться 5 правых (и заметно быстрее).

Я сразу 6 правых сейчас считаю. Даже без последнего улучшения по ww[].

Составные части cg[] значительно более регулярны чем составные части g2[]. Вот они на переходе $67\# \to 71\#$ для 19-252:

cg           26               27              28             29            30          31

 576223355569886, 112154584135474, 16236102874212, 1656286833424, 103008559808, 2666478240
 195212742516854,  30989684123230,  3416514444664,  236416758352,   7621135200
 433623711479106,  92090161630168, 14446636277546, 1553585004440,  98988895712, 2666478240
 170881506383746,  28314007267602,  3122007613882,  204731284716,   6014064960
 471266906399904,  96003376413834, 14533258767384, 1536464867320,  98179060448, 2666478240
 144242578987880,  21780563612244,  2206523406438,  135634339616,   3883279680
 575275598188934, 113749554115066, 16655665580292, 1691856478792, 103096155008, 2666478240
 147287385432644,  25108200150588,  2926747782744,  208993022656,   6767503200
__________________________________________________________________________________________
2714013784958954, 520190131448206, 73543456747162, 7223968589316, 427558654016,10665912960


g2            26               27              28             29            30          31

  89596004992770,  15413516412626,  1887975565538,  149162596932,   5490349920
   8094000168146,    785094117240,    34276608000
  58972855004592,   9892425840882,  1106197959932,   73498372348,   2130785280
 270086640043998,   65128394361876, 11310469539510, 1330376968332,  92155178240, 2666478240
  83584240302522,  19586865799904,  3474971669154,  449469147780,  37224519696, 1354429440
  21038170451812,   2352299651784,   135695727216,    2868341760
   7820860750046,    751891352064,    30686343000
  63841998167760,  12540982614702,  1724030228998,  145801120332,   5490349920
   6472216553842,    515634561152,    19197384640
  26325366399724,   3161867654732,   210628320004,    5663538176
 303796887358472,   68347890434416, 11515887614892, 1349740609468,  93555034496, 2666478240
__________________________________________________________________________________________
 939629240193684,  198476862801378, 31450016960884, 3506580695128, 236046217552, 6687385920

[Dmitriy40]

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

Вы где сейчас копаете?

Копаю я пока другой участок, у gris.

Но буквально только что пришла ещё одна идея ускорения счёта: поделить ww[] на два по некоторому p<pfin и считать их рекурсивно. Будет больше итераций, зато сильно меньше требования к памяти. Думаю как бы это попроще оценить, будет ли заметный выигрыш.
Плюс можно не одну последнюю итерацию считать сразу vc[], а несколько, тоже может быть выигрыш (а может и не быть, проверять надо).

[Yadryara]

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

Я сразу 6 правых сейчас считаю. Даже без последнего улучшения по ww[].

Сделал улучшение как рекомендовано. На 7 правых памяти всё равно не хватило. 6 правых теперь считаются побыстрее: 1ч 40мин против 1ч 57мин для $67\# \to 79\#$ для 19-252.

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

Это чуть сокращает код (что для PARI тоже важно) и сильно сокращает размер ww[] (примерно раз в 10,

Что-то я сокращения толком и не заметил.

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

Решается командой wk=sum(k=1,#ww,#ww[k]); сразу по входу в цикл forprime(p=2,pfin, и показом в print числа из wk.

А может надо wk=sum(k=1,#ww-1,#ww[k]); ?

[Dmitriy40]

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

А может надо wk=sum(k=1,#ww-1,#ww[k]); ?

1. Почему?
2. Какая разница?

Учтите что я обычно вообще делаю и vc[] и ww[] размером v[#v] (и в обоих там справа больше 200 нулевых элементов), без всяких уменьшений размера тютелька-в-тютельку ибо не вижу смысла париться об точных размерах если разница в единицах КБ и миллисекундах.

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

Что-то я сокращения толком и не заметил.

Не знаю почему, для исходного 19-252 размеры #ww[] известны: 2.8млн для 37# и 31млн для 41#, сокращение более чем в 10 раз.
Ну и вот кусочек лога двух запусков вашей проги, до и после доработки:
o = 1 --> 43# : 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 2, 62, 978, 9166, 63284, 318312, 1217964, 3554848, 7817902, 12749554, 15353100, 13657622, 8949344, 4296066, 1503078, 382032, 68312, 7490, 324, sum = 69949440, #ww[]=6395682, time cg: 48,414 ms
o = 2 --> 43# : 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 4, 370, 7454, 83302, 554110, 2343658, 6886820, 14717472, 23017668, 26256274, 21794666, 13070360, 5636184, 1753162, 393784, 60966, 5918, 228, sum = 116582400, #ww[]=10856982, time cg: 2min, 18,866 ms
vs
o = 1 --> 43# : 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 2, 62, 978, 9166, 63284, 318312, 1217964, 3554848, 7817902, 12749554, 15353100, 13657622, 8949344, 4296066, 1503078, 382032, 68312, 7490, 324, sum = 69949440, #ww[]=606404, time cg : 9,750 ms
o = 2 --> 43# : 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 4, 370, 7454, 83302, 554110, 2343658, 6886820, 14717472, 23017668, 26256274, 21794666, 13070360, 5636184, 1753162, 393784, 60966, 5918, 228, sum = 116582400, #ww[]=1034672, time cg : 26,465 ms
Обратите внимание на разницу в #ww[].

Но конечно если считать только правые элементы, то разницы почти не будет - к 41# (не говоря уж про 61#) они уже почти устаканились, выведите не только сумму #ww[k] по всем k, но и сам массив vector(#ww,k,#ww[k])[25..32] и посмотрите как распределяется количество уникальных элементов по k.

-- 18.05.2024, 14:30 --

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

Копаю я пока другой участок, у gris.

И выкопал ещё одну редкую морковку:
1047761801315080993: [0, 18, 30, 60, 78, 84, 108, 114, 120, 144, 150, 168, 198, 204, 228], num13=8190, valids=14
Осталось найти ещё 4 морковки (из 13-ти), а проверено уже половина интервала до 15-228.

[Yadryara]

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

1. Почему?
2. Какая разница?

Учтите что я обычно вообще делаю и vc[] и ww[] размером v[#v] (и в обоих там справа больше 200 нулевых элементов),

Ну так как раз потому, что я воспринимаю Вашу повторяющуюся часть как чёрный ящик, в который загоняешь паттерн, а на выходе получаешь vc[].

Мне пока так проще, ибо вопрос с расщеплением сложный и отвлекаться на ww[] не хочется. Вот я и забыл что он такой длиннющий. Вы и сами ведь расщеплением пока не занимаетесь?

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

Но конечно если считать только правые элементы, то разницы почти не будет - к 41# (не говоря уж про 61#) они уже почти устаканились, выведите не только сумму #ww[k]

Ну так о чём и речь. Я-то считал сумму #ww[k] для переходов к 71# и дальше.

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

Осталось найти ещё 4 морковки (из 13-ти), а проверено уже половина интервала до 15-228.

А это часом не те морковки, которые Ахиллесы пытались выкопать?