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

[Yadryara]

Может формула сложнее для сложных паттернов...

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

Очень интересно как это у Вас та же программа досчитала до 71# всего за час.

Она не совсем та же. Сейчас я приведу её в божеский вид и опубликую. Запустите у себя и сверите.

allocatemem(2^30);

{print();

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

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

a=setminus(vector(v[#v]/2,i,i*2),v); 
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, \\nextprime(v[#v]/2),

tz0=getwalltime();

print();

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(); kvar=0;
      foreach(ww[k],m,
         b=m[1][1]; qq=m[1][2]; qn=0; kvar++;
         foreach(am,x,
            y=bitand(x,b);
            if(y==b, qn+=qq; next);
            hy=hammingweight(y)+2; 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;
if(ww[k] <> Map([;]),
);
   );
   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("--> ",nextprime(p+1),"# : ",strjoin(2*vc[1..vcmax],", "),", sum = ",2*vecsum(vc),", time: ",strtime(getwalltime()-tz0));
print();
);
print();
}quit;

-- 05.05.2024, 20:15 --

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

Пару ошибок у себя нашёл, одну исправил, со 2-й разбираюсь...

Понял, где ошибка. cg для маленьких $p$ считаются сложнее даже если $p$ больше четверти диаметра.

[Dmitriy40]

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

pfin=67; pn=nextprime(pfin+1);
v=[0, 12, 30, 42, 54, 72, 90, 102, 114, 132, 2*pn, 144];

И что это должно значить? С чего вдруг v[] стал длиной 12?! И не симметричным?

А в коде дальше не вижу никаких изменений кроме косметических.

И да, с таким паттерном программа работает примерно вчетверо быстрее, наверняка за час справится. Ну так это другой паттерн!

-- 05.05.2024, 20:56 --

ww[k] <> Map([;]) упрощается до #ww[k]>0.

-- 05.05.2024, 21:16 --

kvar в итоге тоже равна просто #ww[k] до цикла обработки ww[k], её не обязательно обнулять и потом увеличивать.

[Yadryara]

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

И что это должно значить?

Это означает, что найден способ правильно и быстро вычислять cg[] для $p$ близких к половине диаметра.

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

С чего вдруг v[] стал длиной 12?!

Я далеко не сразу к этому пришёл. Соответственно и рассказать в двух словах не получится.

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

И не симметричным?

Симметрия учитывается, умножаю на 2:

print("--> ",nextprime(p+1),"# : ",strjoin(2*vc[1..vcmax],", "),", sum = ",2*vecsum(vc),", time: ",strtime(getwalltime()-tz0));

Но можно не умножать, а ещё час считать симметричный паттерн

v=[0, 144-2*pn, 12, 30, 42, 54, 72, 90, 102, 114, 132, 144]; с ровно таким же результатом.

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

И да, с таким паттерном программа работает примерно вчетверо быстрее, наверняка за час справится. Ну так это другой паттерн!

Ну так в этом и красота идеи — быстрее считать нужный массив для того самого паттерна через другой паттерн.

Проверить, кстати можете и сами, ибо я пока не умею так высоко вычислять g2. Формулы, надеюсь, по-прежнему работают:

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]

$p=71, lmin=11, lmax=31$

[Dmitriy40]

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

Ну так в этом и красота идеи — быстрее считать нужный массив для того самого паттерна через другой паттерн.

Могли прямо об этом сказать, я бы не ломал голову чего у меня PARI такой тормозной.
Красиво, согласен.

-- 05.05.2024, 22:38 --

А с 19-252 фокус не проходит ... Или я его не понимаю.

[Yadryara]

Сразу сказал:

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

То есть до 71# я добрался примерно за 2 с половиной часа, перезапуская прогу каждый раз для всех финальных значений 37#, 41#, ... , 71# , с различными включениями в паттерн.

Для 37#, например, нужно 5 включений:

pfin=31; pn=nextprime(pfin+1);
cg=vector(31);
for (o=1,5,
v=[0, 12, 30, 42, 54, 72, 2*pn, 90, 102, 114, 132, 144];
v[7]=v[o]+2*pn;

И тогда должно сойтись то, что не сходилось в примере. Но пока не доделал.

-- 05.05.2024, 22:54 --

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

А с 19-252 фокус не проходит ... Или я его не понимаю (добавление 226 в паттерн).

Потому что нужно добавить ещё и $232 (6+226)$ и $238 (12+226)$. И все 3 включения отдельно обсчитать.

Вы ещё 40 способов придумаете как ускорить

[Yadryara]

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

Ну вот в этом месте уже можно сверить. Пока не устранённое расхождение:

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

И тогда должно сойтись то, что не сходилось в примере. Но пока не доделал.

Доделал. Вроде сошлось. Теперь так:

v=[0, 12, 30, 42, 54, 72, 90, 102, 114, 132, 144];

lmax = 31

31# --> 37#                                                           Sum

vc = [   5617466,  3288286,  1227208,  252110,  24342,   980 ]   27648000
                                                           *
                                                           6
                                                           +
cg = [  10460054,  6497630,  2608364,  574980,  59710,  2660 ]   49631616
                                                           +
g2 = [   4423660,  2784734,  1138406,  263552,  30854,  1540 ]   19258752
                                                           =
vc = [ 118359724, 58406136, 18258392, 3198032, 274818, 10080 ]  718848000

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

ww[k] <> Map([;]) упрощается до #ww[k]>0.

-- 05.05.2024, 21:16 --

kvar в итоге тоже равна просто #ww[k] до цикла обработки ww[k], её не обязательно обнулять и потом увеличивать.

Прошу прощения, это я ещё не все отладочные вещи удалил. Я даже не поменял обозначения в той проге: просто помнил, что считается не vc[], a cg[].

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

Проверить, кстати можете и сами, ибо я пока не умею так высоко вычислять g2.

А ведь именно для 71# g2[] уже нулевой, так что формула проще:

vc[l]=

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

$p=71, lmin=11, lmax=31$

[Yadryara]

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

Вроде сошлось.

То, что правый край сходится, это видно, а ещё два правых значения нового 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]


(37-30)*vc[30] + (30-11+1)*vc[30+1]
+       cg[30] -           cg[30+1]
+       g2[30] -         2*g2[30+1] + g2[30+2]

(37-30)*24342 + (30-11+1)*980
+       59710 -           2660
+       30854 -         2*1540      + 0           =   274818


(37-29)*vc[29] + (29-11+1)*vc[29+1]
+       cg[29] -           cg[29+1]
+       g2[29] -         2*g2[29+1] + g2[29+2]

(37-29)*252110 + (29-11+1)*24342
+       574980 -           59710
+       263552 -         2*30854    + 1540        =  3198032

Дальше не проверял.

[Yadryara]

Ну а вот прога, которая это посчитала, то есть из vc[] для 5 разных паттернов длиной $l+1$ простым сложением получила cg[] для паттерна длиной $l$.

Вроде почистил получше:

allocatemem(2^30);
{print();
pfin=31; pn=nextprime(pfin+1);cg=vector(21);
for (o=1,5,
v=[0, 12, 30, 42, 54, 72, 2*pn, 90, 102, 114, 132, 144];
v[7]=v[o]+2*pn;

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

forprime(p=2, pfin, 

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)+2; 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==31,   print("o = ",o,"  --> ",nextprime(p+1),"# : ",strjoin(2*vc[1..vcmax],", "),", sum = ",2*vecsum(vc),", time: ",strtime(getwalltime()-tz0));
);
);

for(ll=1,#cg,cg[ll]+=2*vc[vcmax-#cg+ll]);
print();print();
);
print();print(#cg,"  cg = ",cg, "    ",vecsum(cg));
print();print();
}quit;

Пока самым примитивным способом: все 5 паттернов обсчитаны с нуля.

Можно ведь и g2[] и g0[] тоже считать через vc[] для более длинных паттернов. И, в каких-то случаях, это тоже может быть быстрее.

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

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

Небось за 40-45 минут справилась. Но ещё её результат проверить надо. У Вас все цифры есть.

[Dmitriy40]

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

]for (o=1,5,
v=[0, 12, 30, 42, 54, 72, 2*pn, 90, 102, 114, 132, 144];
v[7]=v[o]+2*pn;

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

Так делать нельзя: setminus требует чтобы оба аргумента были типа Set (сортированы по возрастанию и без дублей). Потому после установки значения v[7] надо натравить на него v=Set(v). Сравните для o=5 с и без этого (print(setminus(setminus(vector(v[#v]/2,i,i*2),v),setminus(vector(v[#v]/2,i,i*2),Set(v))));), увидите что без в a[] остаются элементы 90, 102, 114, которых в a[] быть никак не должно!
Соответственно что там дальше в программе считается - бог весть. Даже если вдруг что-то и совпало - это тоже ошибка.

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

hy=hammingweight(y)+2;

Скажите, а почему +2? У меня было +1. Это осталось от каких-то экспериментов или имеет глубокий смысл? Или это только для удобства непоказанных расчётов?
Насколько я вижу это ни на что не влияет, только смещает vc[] вправо на 1 элемент. При этом vc[1] становится чище абсолютно чистого (количество грязи меньше нуля) и этого мне уже не понять как такое возможно и зачем это учитывать.
Я +1 делаю потому что для чистого варианта количество грязи 0 (длина оставшегося a[] или количество единиц в маске), но массивы/векторы в PARI начинаются с 1, вот и смещаю чистые в 1-ю позицию. Зачем чистые смещать ещё правее, ведь чище чистого быть не может и потому vc[1]=0 тождественно.

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

У Вас все цифры есть.

Запустите (например отдельным потоком) с исходным вектором v[] и часов через 5 и у Вас будут все цифры. А первые для сравнения (41# и 43#) и уже через полчаса.

-- 06.05.2024, 14:11 --

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

сортированы по возрастанию и без дублей

Дубли оказывается не мешают, а вот сортированность строго необходима.

[Yadryara]

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

что без в a[] остаются элементы 90, 102, 114, которых в a[] быть никак не должно!

Посмотрю.

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

Даже если вдруг что-то и совпало - это тоже ошибка.

Так вроде всё совпало.

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

Скажите, а почему +2? У меня было +1. Это осталось от каких-то экспериментов или имеет глубокий смысл? Или это только для удобства непоказанных расчётов?

То-то и оно, что я не помню уже точно. Что-то у меня не сходилось и я
добавил ещё единичку. А! Ну так это вроде связано с тем что v[] удлинился ведь на единичку и a[] из-за этого укоротился тоже на на единичку.

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

А первые для сравнения (41# и 43#) и уже через полчаса.

Я уже пробовал считать g2 для 11-144 и дальше 37# не хватает памяти.

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

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

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

-- 06.05.2024, 16:44 --

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

Соответственно что там дальше в программе считается - бог весть. Даже если вдруг что-то и совпало - это тоже ошибка.

Поправил. Обе строки cg всё равно абсолютно идентичны.

Это хороший знак. Значит что-то лишнее считается и это можно сократить...

[Dmitriy40]

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

А! Ну так это вроде связано с тем что v[] удлинился ведь на единичку и a[] из-за этого укоротился тоже на на единичку.

Максимум hy тогда стал на 1 меньше вот и всё, минимум, который всегда строго нулевой (ноль грязи, чистый вариант), не изменился. А +1 в hy связано именно и только с минимумом, нет в PARI элемента vc[0] (и ww[0] тоже).
На работу это не влияет, просто странно. И чуть сбивает нумерацию (vcmax становится на 1 больше).

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

Я уже пробовал считать g2 для 11-144 и дальше 37# не хватает памяти.

Можно после строки
hy=hammingweight(y)+1;
добавить команду
if(hy<13, next);
которая не будет накапливать варианты с малым количеством грязи (и соответственно sum будет неверной), но сколько-то (в данном случае 9) правых элементов vc[] будут правильными до конца. Надо будет только подобрать число в условии чтобы хватало памяти на все ww[]. По идее можно получить 9 правых элементов как и указал, это около 6млн элементов в ww[], учитывая что для 37# их 5.8млн и оно в память влезает, а для 41# их 12млн и не влезает.
Правые элементы для 19-252 я посчитал по 127# именно так.

[Yadryara]

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

Максимум hy тогда стал на 1 меньше вот и всё, минимум, который всегда строго нулевой (ноль грязи, чистый вариант), не изменился. А +1 в hy связано именно и только с минимумом, нет в PARI элемента vc[0] (и ww[0] тоже).

Да я тогда ещё понял зачем Вы единичку добавили. И, когда добавлял ещё одну, понимал для чего я это делаю.

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

По идее можно получить 9 правых элементов как и указал,

Попробую.

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

Поправил. Обе строки cg всё равно абсолютно идентичны.

Это хороший знак. Значит что-то лишнее считается и это можно сократить...

Если из правильного a[] выбросить один элемент, причём именно правый a=a[1..60];, то всё равно считает правильно.

[Yadryara]

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

добавить команду
if(hy<13, next);
которая не будет накапливать варианты с малым количеством грязи (и соответственно sum будет неверной), но сколько-то (в данном случае 9) правых элементов vc[] будут правильными до конца. Надо будет только подобрать число в условии чтобы хватало памяти на все ww[].

9 правых посчитались только раз, для 41#. Затем исправил 13 на 14 и посчитались 8 правых уже вплоть до окейной 73#.

Но числа в конце счёта уже настолько длинные, что в таблицу еле как поместились только по 4 крайне правых числа. Перепроверяю, пока всё сходится.

Что-то у нас gris замолчал. Опять небось матрёшничает втихаря Да ещё и с перебором: 30300 раз вместо 30030

[Yadryara]

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

Перепроверяю, пока всё сходится.

Перестало сходиться. Ищу ошибку. Это может затянуться.

Я конечно могу выложить ту часть таблицы, где сошлось всё, что проверял. Если кому-нибудь интересно.

[Dmitriy40]

Я предпочту доверить сравнение Вам.
И подождать пока оформится следующая гениальная идея (я и эту то не понимаю) - как считать более чем на один шаг вперёд. Всё же пока выигрыш слишком мал, даже с удлинением паттернов.