2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему На страницу Пред.  1 ... 34, 35, 36, 37, 38, 39, 40 ... 43  След.
 
 Re: кортежи последовательных простых. ключ к 19-252
Сообщение18.05.2024, 17:55 
Заслуженный участник


20/08/14
11329
Россия, Москва
Yadryara в сообщении #1639562 писал(а):
Вы и сами ведь расщеплением пока не занимаетесь?
Не занимаюсь.

Yadryara в сообщении #1639562 писал(а):
А это часом не те морковки, которые Ахиллесы пытались выкопать?
Не вполне уверен, я не в курсе что там считается. Скорее всего да, но там их посчитать нереально, да и морковки не совсем те (у меня гарантированно минимальные и только они, у НМ абы какие), вот и решил помочь.

 Профиль  
                  
 
 Re: кортежи последовательных простых. ключ к 19-252
Сообщение19.05.2024, 01:21 
Заслуженный участник


20/08/14
11329
Россия, Москва
Ещё одну редкую морковку выкопал:
1342053871456743509: [0, 18, 30, 60, 78, 84, 108, 114, 120, 122, 150, 168, 198, 210, 228], num13=8175, valids=14
Осталось найти три.

 Профиль  
                  
 
 Re: кортежи последовательных простых. ключ к 19-252
Сообщение19.05.2024, 02:30 
Заслуженный участник


20/08/14
11329
Россия, Москва
И ещё одна:
1380371357886098209: [0, 10, 30, 60, 78, 84, 108, 114, 120, 144, 150, 168, 198, 210, 228], num13=4095, valids=14

 Профиль  
                  
 
 Re: кортежи последовательных простых. ключ к 19-252
Сообщение19.05.2024, 04:57 
Аватара пользователя


29/04/13
7376
Богородский
Yadryara в сообщении #1639547 писал(а):
6 правых теперь считаются побыстрее: 1ч 40мин против 1ч 57мин для $67\# \to 79\#$ для 19-252.

А для $67\# \to 89\#$ 3ч 5мин против 3ч 40мин. Ну и за 7 с лишним часов корректно дошла до $113\#$.

Dmitriy40 в сообщении #1637098 писал(а):
Очень даже нужно: для 19-252 на PARI можно посчитать ww[] (а соответственно вероятно и ваши c1g1[] и g2[]) только для 41# или с большим трудом для 43#, не дальше,

Ну вот Вам и большой труд: даже у меня теперь за 5 минут(!!) посчитала до $43\#$.

 Профиль  
                  
 
 Re: кортежи последовательных простых. ключ к 19-252
Сообщение19.05.2024, 11:55 
Заслуженный участник


20/08/14
11329
Россия, Москва
gris
Досчитал все 100% таблицы num13, положил в тот же архив в облаке что и остальные.
Покажу только самые редкие valids=14, все 13шт в одном месте:
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
175301483404392739: [0, 18, 30, 60, 64, 84, 108, 114, 120, 144, 150, 168, 198, 210, 228], num13=7679, valids=14
460965104634828473: [0, 18, 30, 60, 78, 84, 108, 114, 120, 144, 150, 180, 198, 210, 228], num13=8187, valids=14
568075716637184849: [0, 18, 30, 60, 78, 84, 92, 114, 120, 144, 150, 168, 198, 210, 228], num13=8063, valids=14
1047761801315080993: [0, 18, 30, 60, 78, 84, 108, 114, 120, 144, 150, 168, 198, 204, 228], num13=8190, valids=14
1342053871456743509: [0, 18, 30, 60, 78, 84, 108, 114, 120, 122, 150, 168, 198, 210, 228], num13=8175, valids=14
1380371357886098209: [0, 10, 30, 60, 78, 84, 108, 114, 120, 144, 150, 168, 198, 210, 228], num13=4095, valids=14
1581918342960355339: [0, 18, 30, 60, 78, 84, 108, 114, 120, 144, 150, 168, 174, 210, 228], num13=8189, valids=14
1920480393994317703: [0, 18, 30, 60, 78, 84, 108, 118, 120, 144, 150, 168, 198, 210, 228], num13=8127, valids=14

Последняя нашлась прямо перед valids=15, но хорошо хоть не после.

 Профиль  
                  
 
 Re: кортежи последовательных простых. ключ к 19-252
Сообщение19.05.2024, 12:05 
Заслуженный участник
Аватара пользователя


13/08/08
14477
Прямо подарок! Чувствую себя пионером. Видел их сегодня на линейке у Мальчиша-Кибальчиша :-) .

 Профиль  
                  
 
 Re: кортежи последовательных простых. ключ к 19-252
Сообщение19.05.2024, 12:48 
Аватара пользователя


29/04/13
7376
Богородский
Dmitriy40 в сообщении #1639401 писал(а):
Но 47# посчитать снова не получится, надо до 9.5млн элементов ww[]

Это для $o=11$ только в первом цикле? С 6.8 млн справляется. Сколько раз встречается более длинный ww[] ?

$o=11$ я расщепил и посчитал отдельно. Очень не хотелось мне с двумя вилками(2p и 4p) возиться, но решил, что надо попробовать. Удалось и сошлось. Правда процедуру так и не сделал, а сделал 6 циклов:

(6 циклов)

Код:
{print(); tz0=getwalltime();

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

print();print(v0);print();

vco = [0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 46, 819, 9513, 86961, 666700, 3879368, 161926
26, 49107041, 111348972, 191311822, 247761038, 239234341, 170780294, 89844745, 3
4830936, 9970388, 2131036, 333276, 32863, 1374, 0];

forprime(pfin = 43, 43, \\ precprime(precprime(v0[#v0]/2)-1),

tz1=getwalltime();

pn=nextprime(pfin+1);

cg=vector(#vco);

v=[0,6,12,30,42,72,90,96,120,126,132, 156, 162, 180, 210, 222,226, 240, 246, 2*pn, 252];

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

if(o<>11, v[#v-1]=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);

vc=vector(#ww);

forprime(p=2, pfin,
wk=sum(k=1,#ww,#ww[k]);

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;
if(p==pfin, foreach(am,x, vc[hammingweight(bitand(x,b))+1]+=qq; ); next; );
         foreach(am,x,
            y=bitand(x,b);
            if(y==b, qn+=qq; next);
            hy=hammingweight(y)+1; nn=0;
\\if(hy<24, next);
            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;
   );
   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),
", time cg : ",strtime(getwalltime()-tz1),"  memory:    ", wk);
);
);
for(ll=1,#cg-1,cg[ll+1]+=vc[ll]);
print();print();
);o++);



v=[0,6,12,30,42,72,90,96,120,126,132, 156, 162, 180, 210, 222,226, 240, 246, 2*pn, 252];

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

if(o<>17,v[#v-1]=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);
vc=vector(#ww);

forprime(p=2, pfin,
wk=sum(k=1,#ww,#ww[k]);
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;
if(p==pfin, foreach(am,x, vc[hammingweight(bitand(x,b))+1]+=qq; ); next; );
         foreach(am,x,
            y=bitand(x,b);
            if(y==b, qn+=qq; next);
            hy=hammingweight(y)+1; nn=0;
\\if(hy<24, next);
            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;
   );
   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),
", time cg : ",strtime(getwalltime()-tz1),"  memory:    ", wk);
);
);
for(ll=1,#cg-1,cg[ll+1]+=vc[ll]);
print();print();
);o--);





v=[0,6,12,30,42,72,90,96,120,126,132, 156, 162, 180, 210, 222,226, 240, 246, 4*pn, 252];

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

v[#v-1]=v0[o]+4*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);

vc=vector(#ww);

forprime(p=2, pfin,
wk=sum(k=1,#ww,#ww[k]);

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;
if(p==pfin, foreach(am,x, vc[hammingweight(bitand(x,b))+1]+=qq; ); next; );
         foreach(am,x,
            y=bitand(x,b);
            if(y==b, qn+=qq; next);
            hy=hammingweight(y)+1; nn=0;
\\if(hy<24, next);
            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;
   );
   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),
", time cg : ",strtime(getwalltime()-tz1),"  memory:    ", wk);
);
);
for(ll=1,#cg-1,cg[ll+1]+=vc[ll]);
print();print();
o++;);


v=[0,6,12,30,42,72,90,96,120,126,132, 156, 162, 180, 210, 222,226, 240, 246, 4*pn, 252];

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

v[#v-1]=v0[o]-4*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);
vc=vector(#ww);

forprime(p=2, pfin,
wk=sum(k=1,#ww,#ww[k]);

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;
if(p==pfin, foreach(am,x, vc[hammingweight(bitand(x,b))+1]+=qq; ); next; );
         foreach(am,x,
            y=bitand(x,b);
            if(y==b, qn+=qq; next);
            hy=hammingweight(y)+1; nn=0;
\\if(hy<24, next);
            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;
   );
   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),
", time cg : ",strtime(getwalltime()-tz1),"  memory:    ", wk);
);
);
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(#ddo," ddo = ",ddo);
print();

for(o=1,#do,

v=[0,6,12,30,42,72,90,96,120,126, 132, 156, 162, 180, 210, 222,226, 240, 246, 252, 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);
vc=vector(#ww);

forprime(p=2, pfin,
wk=sum(k=1,#ww,#ww[k]);

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;
if(p==pfin, foreach(am,x, vc[hammingweight(bitand(x,b))+1]+=qq; ); next; );
         foreach(am,x,
            y=bitand(x,b);
            if(y==b, qn+=qq; next);
            hy=hammingweight(y)+1; nn=0;
\\if(hy<23, next);
            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;
   );
   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),
" time g2 : ",strtime(getwalltime()-tz2),"  memory:    ", wk);
);
);
for(ll=1,#g2-2,g2[ll+2]+=vc[ll]);
print();print();
);





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

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

for(o=1,#do,

v=[0,6,12,30,42,72,90,96,120,126, 132, 156, 162, 180, 210, 222,226, 240, 246, 252, 2, 2+4*pn];

v[#v-1]=do[o];
v[#v  ]=do[o]+4*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);
vc=vector(#ww);

forprime(p=2, pfin,
wk=sum(k=1,#ww,#ww[k]);

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;
if(p==pfin, foreach(am,x, vc[hammingweight(bitand(x,b))+1]+=qq; ); next; );
         foreach(am,x,
            y=bitand(x,b);
            if(y==b, qn+=qq; next);
            hy=hammingweight(y)+1; nn=0;
\\if(hy<23, next);
            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;
   );
   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),
" time g2 : ",strtime(getwalltime()-tz2),"  memory:    ", wk);
);
);
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[1..31],"      ",vecsum(vc));
print();
print();
print("time: ",strtime(getwalltime()-tz0));
print();
print();
);
print();

}quit;

 Профиль  
                  
 
 Re: кортежи последовательных простых. ключ к 19-252
Сообщение19.05.2024, 13:52 
Заслуженный участник


20/08/14
11329
Россия, Москва
Yadryara в сообщении #1639607 писал(а):
Это для $o=11$ только в первом цикле? С 6.8 млн справляется. Сколько раз встречается более длинный ww[] ?
Вот список размеров ww[] для 47# (конечно с оптимизацией последней итерации p=pfin):
o = 1 : #ww[]=3025266
o = 2 : #ww[]=5922993
o = 3 : #ww[]=6434247
o = 4 : #ww[]=2659555
o = 5 : #ww[]=6310685
o = 6 : #ww[]=6395682
o = 7 : #ww[]=6891855
o = 8 : #ww[]=2774664
o = 9 : #ww[]=3592478
o = 10 : #ww[]=2819459
o = 11 : #ww[]=9595253
o = 12 : #ww[]=8832776
o = 1 : #ww[]=5760324
o = 2 : #ww[]=2879012
o = 3 : #ww[]=6032087
o = 4 : #ww[]=3104091
o = 5 : #ww[]=10078929
o = 2 : #ww[]=480954
o = 6 : #ww[]=550540
o = 7 : #ww[]=1853448
o = 12 : #ww[]=605006
o = 16 : #ww[]=3632729
o = 17 : #ww[]=1088104
o = 20 : #ww[]=1320592
o = 22 : #ww[]=977562
o = 24 : #ww[]=2226015
o = 28 : #ww[]=984631
o = 4 : #ww[]=967987
o = 6 : #ww[]=1824593
o = 9 : #ww[]=1294251
o = 11 : #ww[]=1175125
Как видите для следующего o=12 тоже надо больше 6.8млн, и потом ещё для o=5 во втором цикле.

Но не мучайтесь с расщеплением, я таки сделал свою идею с разделением ww[] на два этапа, вот что получилось для первых двух итераций первого цикла, было:
o = 1 --> 47# : 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 46, 1924, 38946, 436496, 2912218, 12145728, 33883832, 68872388, 109483440, 140243220, 144385066, 117790748, 74383220, 35367736, 12539770, 3295202, 601922, 64630, 2748, sum = 756449280, #ww[]=3025266, time cg: 1min, 732 ms
o = 2 --> 47# : 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 8, 330, 6926, 86970, 738242, 4362312, 18595380, 58131040, 134709640, 231640358, 296001158, 281617158, 199538934, 105753564, 42195270, 12722686, 2861426, 447266, 40168, 1404, sum = 1389450240, #ww[]=5922993, time cg: 3min, 5,056 ms
Стало для лучшего варианта по скорости:
o = 1 --> 47# : 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 46, 1924, 38946, 436496, 2912218, 12145728, 33883832, 68872388, 109483440, 140243220, 144385066, 117790748, 74383220, 35367736, 12539770, 3295202, 601922, 64630, 2748, sum = 756449280, #ww[]=239+24074, time cg: 43,867 ms
o = 2 --> 47# : 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 8, 330, 6926, 86970, 738242, 4362312, 18595380, 58131040, 134709640, 231640358, 296001158, 281617158, 199538934, 105753564, 42195270, 12722686, 2861426, 447266, 40168, 1404, sum = 1389450240, #ww[]=480+23577, time cg: 2min, 7,886 ms
Здесь после значка плюс показано максимальное количество элементов в ww[], потому что для каждого элемента из первого количества ww[] перестраивается полностью с нуля (но не с простого 2, а с простого 29 и далее, по простое 23 построен первый массив).
Обратите внимание не на скорость (она не кардинально уменьшилась), а на снижение требований к памяти.
Код покажу чуть позже (кстати уже с функцией расчёта vc[]), запустил просчёт всего 47# для сравнения, вдруг не совпадёт ...

 Профиль  
                  
 
 Re: кортежи последовательных простых. ключ к 19-252
Сообщение19.05.2024, 14:07 
Аватара пользователя


29/04/13
7376
Богородский
Dmitriy40 в сообщении #1639613 писал(а):
Но не мучайтесь с расщеплением,

Ну как не мучиться. На будущее-то пригодится. Соображение в том, чтобы расщеплять только самые объёмные.

Ваша новая придумка ведь не решает всех проблем. Или решает?

Dmitriy40 в сообщении #1639613 писал(а):
Обратите внимание не на скорость (она не кардинально уменьшилась), а на снижение требований к памяти.

Вижу. Шикарное снижение!

 Профиль  
                  
 
 Re: кортежи последовательных простых. ключ к 19-252
Сообщение19.05.2024, 14:18 
Заслуженный участник


20/08/14
11329
Россия, Москва
Совпало.
Время уменьшилось с 38м до 27м, но это не главное.
Зато требования к памяти снизились с 10млн до 476+24688, в 400 раз! Вот это да ...

Yadryara в сообщении #1639616 писал(а):
Ваша новая придумка ведь не решает всех проблем. Или решает?
Пока не знаю. Я ж её только реализовал, ещё не анализировал как для больших простых себя поведёт. Вот для 47# очень нравится, сейчас буду запускать для следующих простых.
А потом видимо придётся второй цикл переписывать на асме, он частично уже есть, но лишь на 2/3.
Плюс хочу проверить улучшит ли картину оптимизация не одной последней итерации, а нескольких, но это надо уже в асме проверять, PARI тут не помощник (совершенно не факт что эффект унаследуется с PARI в асм).
И кстати может оказаться что и расщепление не понадобится ... Конечно очень вряд ли, слишком глубок перебор (его придётся делать видимо с 43# по 113# или докуда хватит терпения), но вдруг.

 Профиль  
                  
 
 Re: кортежи последовательных простых. ключ к 19-252
Сообщение19.05.2024, 14:26 
Аватара пользователя


29/04/13
7376
Богородский
Dmitriy40 в сообщении #1639618 писал(а):
Зато требования к памяти снизились с 10млн до 476+24688, в 400 раз! Вот это да ...

Да, это очень круто. Проздравляю :!:

Dmitriy40 в сообщении #1639613 писал(а):
Код покажу чуть позже (кстати уже с функцией расчёта vc[]),

Попробую запустить. Ведь много что считать нужно, не только 19-252.

 Профиль  
                  
 
 Re: кортежи последовательных простых. ключ к 19-252
Сообщение19.05.2024, 15:17 
Заслуженный участник


20/08/14
11329
Россия, Москва
Код с функцией и двумя оптимизациями, памяти и скорости (последней итерации):
Код:
{CalcVC()=my(cc,p,m,am,k,rr,b,qq,qn,x,y,hy,nn,ww,wm,kk,mm);
cc=vector(v[#v]); wk=wkm=0; wm=vector(v[#v],i,Map()); mapput(wm[#wm],2^#a-1,1);
forprime(p=2,pmid,
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,#wm, rr=Map();
foreach(wm[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(wm[hy],y,&nn), nn+=qq , nn=qq); mapput(wm[hy],y,nn); );
if(qn>0, mapput(rr,b,qn); );
); wm[k]=rr;); ); wkm=sum(k=1,#wm,#wm[k]);
for(kk=1,#wm, foreach(wm[kk],mm,
ww=vector(v[#v],i,Map()); mapput(ww[kk],mm[1][1],mm[1][2]);\\Помещаем обрабатываемый элемент из первого массива
forprime(p=pmid+1,pfin,
wk=max(wk,sum(k=1,#ww,#ww[k]));\\Для второго массива подсчитваем тоьлко максимальное количество элементов
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;
if(p==pfin, foreach(am,x, cc[hammingweight(bitand(x,b))+1]+=qq; ); next; );\\Оптимизация последней итерации, оставить или это или строку с комментом ниже
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; ););););
\\wk=0; for(k=1,#ww, wk+=#ww[k]; foreach(ww[k],x, cc[k]+=x[1][2]; ); );\\Оставить или это или строку с комментом выше
return(cc);
}

\\Первый цикл, остальные аналогично
pmid=23;\\Можно глобально, можно для каждого цикла или даже каждого паттерна отдельно, можно указать pmid=1 (или 0) и тогда оптимизации памяти не будет
while(v0[o]+2*pn < v0[#v0],
v[2]=v0[o]+2*pn;
a=setminus(vector(v[#v]/2,i,i*2),Set(v));
vc=CalcVC();\\Всё остальное вычисление убрано в функцию
for(ll=1,#cg-1, cg[ll+1]+=2*vc[ll]; );
vcmax=#vc; while(vcmax>1&&vc[vcmax]==0, vcmax--);
print("o=",o," --> ",pn,"#: ",2*vc[1..vcmax],", sum=",2*vecsum(vc),", #ww[]=",wkm,"+",wk,", time cg: ",strtime(getwalltime()-tz1));\\Формат на свой вкус
o++;);
Значения pmid пока подбираю руками от фонаря, для больших простых и 19-252 придётся видимо ставить pmid=37 или 41 (сколько влезет в память), для проверки можно второй цикл в функции не запускать (заменить kk=1,#wm на kk=1,-#wm), а ограничиться первым и проверить каковы получаются размеры первого wm[] (они будут равны размерам ww[] предыдущей программы).
При завышенном pmid начинается резкое торможение, даже в разы медленнее чем без него вообще, уже при pmid на два шага больше оптимального, аккуратнее его увеличивать!

 Профиль  
                  
 
 Re: кортежи последовательных простых. ключ к 19-252
Сообщение19.05.2024, 17:44 
Аватара пользователя


29/04/13
7376
Богородский
Dmitriy40, ну это высший пилотаж!

Поправлю добавки и a[] тоже внутрь функции засуну.

 Профиль  
                  
 
 Re: кортежи последовательных простых. ключ к 19-252
Сообщение19.05.2024, 17:57 
Заслуженный участник


20/08/14
11329
Россия, Москва
Yadryara в сообщении #1639647 писал(а):
Поправлю добавки и a[] тоже внутрь функции засуну.
А вот это я специально делать не стал - у Вас он чуть по разному вычисляется, то как v[#v]/2, то как v[#v-2]/2. Я разбираться не стал и оставил снаружи.

 Профиль  
                  
 
 Re: кортежи последовательных простых. ключ к 19-252
Сообщение20.05.2024, 16:45 
Заслуженный участник


20/08/14
11329
Россия, Москва
Решил посчитать и дальше 47# по новой технологии (только первую итерацию первого цикла, чисто для оценки времён):
Код:
o = 1  --> 53# : 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 146, 8460, 203224, 2697872, 23103316, 138349770, 592360310, 1828419190, 4101908536, 6745504470, 8193836292, 7375194824, 4911017062, 2420209734, 892528614, 251237826, 53962188, 8219646, 743840, 27480, sum = 37539532800, #ww[]=479+244070, time cg: 17min, 23,701 ms
o = 1  --> 59# : 0, 0, 0, 0, 0, 0, 0, 52, 7962, 221916, 3201390, 31334234, 227783596, 1251104314, 5212591726, 16641883168, 41279989156, 80289911650, 122384890388, 144847974412, 131372896230, 89973052818, 45744068524, 16924170166, 4445986626, 801279468, 94232106, 6635458, 210816, sum = 701533426176, #ww[]=27239+43799, time cg: 2h, 12min, 52,446 ms
Дальше терпения не хватило.
На PARI считать по прежнему нереально.

Для сравнения расчёт 59# на асме по почти той же технологии (таблица по 31# как и на PARI и потом перебор 31#->53#, правда уже без исключения дубликатов через Map, почти полный):
Код:
53#: 0, 0, 0, 0, 0, 0, 0, 26, 3981, 110958, 1600695, 15667117, 113891798, 625552157, 2606295863, 8320941584, 20639994578, 40144955825, 61192445194, 72423987206, 65686448115, 44986526409, 22872034262, 8462085083, 2222993313, 400639734, 47116053, 3317729, 105408, sum=350766713088, time: 61.712s
Числа не удвоены, как и должно быть.
В 130 раз быстрее. Подобрав параметры (размер первой таблицы Map) можно наверное и ещё ускорить. И реализовав вторую таблицу с исключением дублей тоже должно стать побыстрее, особенно для больших простых.

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 639 ]  На страницу Пред.  1 ... 34, 35, 36, 37, 38, 39, 40 ... 43  След.

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group