29/04/13
8145
Богородский
|
Скорее потому что тогда такой кортеж был бы найден поиском 19-252. Это уже говорилось. И я специально сказал о том же самом другими словами. После отдыха вернулся к задаче. Решил перепроверить и по-новому вычислить 11-144. Объединил все вычисления в одну программу (PARI)
Код: allocatemem(2^26);
{print(); tz0=getwalltime();
v0=[0, 12, 30, 42, 54, 72, 90, 102, 114, 132, 144];
vco = [0, 0, 0, 0, 0, 0, 10, 396, 6868, 69358, 387838, 1378512, 3278384, 5495890, 6620352, 5617466, 3288286, 1227208, 252110, 24342, 980, 0];
forprime(pfin=31,precprime(v0[#v0]/2),
tz1=getwalltime();
\\print();
\\print(pfin," ", v0[#v0]);
pn=nextprime(pfin+1); \\37*2 = 74
cg=vector(#vco);
v=[0, 12, 30, 42, 54, 72, 2*pn, 90, 102, 114, 132, 144];
o=1;
while(v0[o]+2*pn < v0[#v0],
\\print();
\\print(v0[o]+2*pn," ", v0[#v0]);
v[7]=v[o]+2*pn;
a=setminus(vector(v[#v]/2,i,i*2),Set(v));
\\a=a[1..60];
ww=vector(v[#v]/2+3-#v,i,Map()); mapput(ww[#ww],2^#a-1,1);
\\print(#a," a = ",a);
\\print();
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(2*vc[1..vcmax],", "),", sum = ",2*vecsum(vc),", time cg : ",strtime(getwalltime()-tz1));
);
);
for(ll=1,#cg-1,cg[ll+1]+=2*vc[ll]);
print();print();
o++;);
print();print(#cg," cg = ",cg, " ",vecsum(cg));
print();
print("time: ",strtime(getwalltime()-tz1));
print();print();
print(); tz2=getwalltime();
\\pfin=31; pn=nextprime(pfin+1); \\37*2 = 74
g2=vector(#vco+1);
\\ 2-76 ... 14-88 18-92 ... 26-100 32-106 34-108 \\ 36-110
\\do=[2,4,6,8,10,14,18,20,22,24,26,32,34];
do=setminus(vector((v0[#v0]-2-2*pn)/4,i,i*2),Set(v0));
do=setminus(Set(do),Set(vector(11,i,v0[12-i]-2*pn)));
print();
print(#do," do = ",do);
\\print(#ddo," ddo = ",ddo);
print();
for(o=1,#do,
v=[0, 12, 30, 42, 54, 72, 90, 102, 114, 132, 144, 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));
\\a=a[1..60];
ww=vector(v[#v-2]/2+3-#v+2,i,Map()); mapput(ww[#ww],2^#a-1,1);
\\print(#a," a = ",a);
\\print();
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(2*vc[1..vcmax],", "),", sum = ",2*vecsum(vc)", time g2: ",strtime(getwalltime()-tz2));
);
);
for(ll=1,#g2-2,g2[ll+2]+=2*vc[ll]);
print();print();
);
print();print(#g2," g2 = ",g2, " ",vecsum(g2));
print();
print("time: ",strtime(getwalltime()-tz2));
print();
\\ sum = 27648000
\\print();
\\print(#vco," ",vco);
\\print();
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]);
vc = vc[1..#vco];
vco = vc;
print();
print("vc --> ",pn,"# : ",vc," ",vecsum(vc));
print();
print();
print("time: ",strtime(getwalltime()-tz0));
print();
print();
);
print();
}quit; Да, демонстративно мало памяти взял. И, тем не менее считается всё, а не только 8 правых, как тогда. У меня считалась 5 часов 22 минуты от 31# до 71#. Предлагаю Вам запустить и сравнить времена со старыми: 31#: 15,624 ms
37#: 1min, 50,439 ms
41#: 6min, 36,976 ms
43#: 15min, 24,531 ms
47#: 24min, 4,339 ms
53#: 30min, 33,017 ms
59#: 34min, 37,949 ms
61#: 35min, 28,376 ms
67#: 37min, 26,759 ms
71#: 37min, 24,168 ms
73#: 37min, 54,155 ms
Общее время 4ч22м Потенциально можно ещё больше экономить память, переходя от одних паттернов к другим, более длинным. Но есть опасность лавинообразного нарастания их количества и нарастания времени обсчёта. Схема обсчёта только через vc[]. Третья строка сокращена. Код: vc31
2*(vc[+2*37] + vc[+12+2*37] + vc[+30+2*37] + vc[+42+2*37] + vc[+54+2*37])
2*(vc[+4]+vc[+6]+vc[+10]+vc[+18]+vc[+22]+vc[+24]+vc[+13])
=
vc37
2*(vc[+2*41] + vc[+12+2*41] + vc[+30+2*41] + vc[+42+2*41] + vc[+54+2*41])
2*(vc[+2,+2+2*41]+vc[+14,+14+2*41]+vc[+18,+18+2*41])
=
vc41
2*(vc[+2*43] + vc[+12+2*43] + vc[+30+2*43] + vc[+42+2*43] + vc[+54+2*43])
2*(vc[+6,+6+2*43]+vc[+10,+10+2*43]+vc[+24,+24+2*43])
=
vc43
2*(vc[+2*47] + vc[+12+2*47] + vc[+30+2*47] + vc[+42+2*47])
2*(vc[+2,+2+2*47]+vc[+6,+6+2*47]+vc[+14,+14+2*47]+vc[+18,+18+2*47]+vc[+24,+24+2*47])
=
vc47
2*(vc[+2*53] + vc[+12+2*53] + vc[+30+2*53])
2*(vc[+2,+2+2*53]+vc[+6,+6+2*53])
=
vc53
2*(vc[+2*59] + vc[+12+2*59])
2*(vc[+2,+2+2*59]+vc[+6,+6+2*59])
=
vc59
2*(vc[+2*61] + vc[+12+2*61])
2* vc[+4,4+2*61]
=
vc61
2* vc[+2*67]
2* vc[+4,4+2*67]
=
vc67
2* vc[+2*71]
2*0
=
vc71
2*0
2*0
=
vc73 OK
|
|
Я не заметил, честно. Потом посмотрел внимательнее 
Но я же правильно написал 
, так что пусть и не первая, но вторая-третья цепочка обязательно найдутся, не могут они все попасть ровно в ошибку (если оная вообще осталась в коде), это ещё на много порядков менее вероятно. А решения попрут валом после первого, все примеры других цепочек говорят об этом.
. Затем посчитать для нового паттерна vc[] для 53#,
. Затем посчитать уже для этого нового паттерна vc[] для 53#.
. Затем посчитать уже для этого нового паттерна vc[] для 53#.
диаметра, либо пытаться считать от четверти диаметра тот же 19-252. Ведь vc-шки есть и для 61# и для 67#. То есть удлинять ещё больше паттерны и смотреть будут ли работать какие-нибудь формулы.