Итак, после допиливания удалось
на PARI посчитать паттерн 9-108 до конца, по 59#,
менее чем за 3 минуты, при том что программа переборов
на асме считала
1ч20м. Время распределилось по 29#-59# так: 1.6c, 7с, 17с, 25с, 28с, 31с, 35с, 38с. Уникальных вариантов комбинаций a[] после 59# осталось 546 тысяч (почти не росло уже с 37#, потому и время почти не росло).
Но считать надо всегда с самого начала, с 3#, переборы же могут считать любой праймориал.
Программа:
Код:
allocatemem(10^8);\\Память нужна, да
v=[0, 18, 24, 48, 54, 60, 84, 90, 108];\\9
a=setminus(vector(v[#v]/2,i,i*2),v); print("v=",v);
ww=vector(v[#v]/2,i,Map()); mapput(ww[#ww],2^#a-1,1);
{forprime(p=1,nextprime(v[#v]/2),
tz0=getwalltime();
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("",p,"#: ",strjoin(vc[1..vcmax],", "),", sum=",vecsum(vc),", time: ",strtime(getwalltime()-tz0));
);}
Принцип работы: работаем с битовыми масками наличия элементов в a[], инициализируем список всеми единичными битами с множителем 1, потом в порядке увеличения индекса vc[k] обрабатываем весь список уникальных комбинаций a[], для каждой (взятой в m) для каждого допустимого остатка удаляем его элементы из оставшихся a[] (делается bitand), вычисляем длину hy новой комбинации и обновляем её множитель в списке если есть или просто добавляем в список если такой там ещё нет. Сравнение y==и и пропуск модификации - если ничего не изменилось, то не будем вызывать много раз, а вызовем один раз в конце с увеличенным множителем количества. Так как проход по длине k идёт в сторону увеличения, а при обработке каждого остатка длина может или уменьшиться (тогда список ww сразу обновится) или остаться той же, то последние случаи накапливаются в новом списке rr и потом он перезаписывает обработанный в общем ww[k] (чтобы не менять текущий обрабатываемый список на лету).
Посчитать большие диаметры не получается, слишком быстро растёт количество уникальных комбинаций a[] (для простых примерно до четверти-трети диаметра, потом рост практически прекращается) и список их ww не влезает в память.
Зато смог посчитать правые 5 элементов в 19-252 до 127#:
Код:
61#: 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 4577709549962, 678625326646, 70209898488, 4365719848, 113480160, sum
67#: 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 135295969437234, 18878969508802, 1836531247768, 107619357728, 2666478240, sum
71#: 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 4613157466381520, 614389502603580, 57035296901788, 3194803761712, 76015820160, sum
73#: 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 163469887490363636, 20811088335231610, 1842711011866572, 98229862527152, 2225825159040, sum
79#: 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 6712529533063117932, 820634405591898460, 69651551721091256, 3557606996239392, 77458121798400, sum
83#: 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 295588436197324273224, 34763658542898459608, 2834250821896477544, 138942083362119936, 2905818137107200, sum
89#: 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 14788623264348306478398, 1687193291761313729988, 133497335364676741912, 6354086741865734784, 129246846208300800, sum
97#: 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 840804066512067515222744, 93048517713584964085964, 7141103807508254772636, 329920591582412971584, 6529000988722060800, sum
101#: 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 51618145822460787277758590, 5566629017220937449677844, 416310093193238409538376, 18746496499210476706368, 362224462774777344000, sum
103#: 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 3218267413612819577226083354, 337015942625338490947048616, 24465924058699731920786584, 1069813034763044135539968, 20109323045263947264000, sum
107#: 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 214036202732873586950402243044, 21866715832495639117111528096, 1548900465991827788951954720, 66139032710912104732002048, 1217030127904303663104000, sum
109#: 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 14543387499963069153193849853344, 1446051054386135437460983283016, 99652711658483082990715589360, 4140824467524594175759550976, 74238837802162523449344000, sum
113#: 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1056915263686593893844168443674496, 102892528884072156314253248592176, 6943611289142775998673865244208, 282684306303616742837495359488, 4974002132744889071106048000, sum
127#: 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 89445149902170647515706650093297424, 8528715955705842389417381362804080, 563686748014226965436196584961792, 22481280261968069356295314839552, 387972166354101347546271744000, sum
Начиная с 61# (меньшие ещё быстрее) все считались секунд по 16-35, всего хватило 7 минут.
Можно посчитать и 7 правых элементов, за десяток часов, но на большее не хватает памяти - ww слишком разрастается, для 7 правых элементов он уже больше 11млн элементов (для 5-ти хватило 357 тысяч).
На асме по идее под элемент списка хватает 32 байта (16 под маску и 16 под счётчик повторов qq в коде выше), значит в 8ГБ влезет 260млн элементов, это всего лишь 9 правых элементов в vc[] из 31. Беда.