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

[Yadryara]

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

Итак, после допиливания удалось на PARI посчитать паттерн 9-108 до конца, по 59#, менее чем за 3 минуты,

Это что-то невероятное, но у меня посчитала меньше чем за минуту!! Ничегошеньки пока не понял. Ну, кроме того, что Вы очень умный

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

Ругаться может и буду,

Да за один только вот такой перебор Вы меня просто убьёте:

forstep(i=1, mor,2,

Я даже массив a[] не вычислял вообще. Потому что мне наплевать пока на это было, мне главное было два этих массива вычислить правильно, пусть даже перебор как попало организован.

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

Вы говорите имея некие данные для 41# можно вычислить vc[] для 43# быстрее чем перебором 24 разрешённых остатков, так?

Ну Вы же видели мою прогу, которую ругали за лишний игрек. Но считает-то она моментально и правильно. Если ей дать данные, то есть те самые 3 массива. Которые получаются в ходе перебора 41#.

Та, прога которая ниже, заточена под конкретный шаг для конкретного паттерна.

Самые важные места кое-где откоментил.

(Чур не убивать!)

{print(); v=[0, 30, 60, 90, 120]; lm=26; vc=vector(lm); c1g1=vector(lm); g2=vector(lm);

p=19; mor=1; forprime(i=2,p,mor=mor*i); pn=nextprime(p+1);



forstep(i=1, mor,2,

for(j=1,#v,

x=i+v[j];

if(
x%3  ==0 || x%5  ==0 || x%7  ==0 || x%11 ==0 ||
x%13 ==0 || x%17 ==0 || x%19 ==0 , next(2)));

len=2; fl=vector(v[#v]);


forstep(j=i+2,i+v[#v]-2, 2,

if(j%3<>0 && j%5<>0 && j%7<>0 && j%11<>0 && j%13<>0 && j%17<>0 &&
 j%19<>0 ,len++;fl[j-i]=1)); \\Вычисление длин и флагов


c1g1[len]=c1g1[len]+2*fl[v[#v]-4*pn];  \\   28-120       0-92

\\shirok 0,28,92,120

                                       \\   2*94
                                       \\   4*96
                                       \\   8*98
                                       \\ ...
                                       \\  24*116
                                       \\  26*118
                                     
forstep(j=2,26,2,
g2[len]=g2[len]+fl[j]*fl[j+4*pn]); \\ Перемножение флагов для широкой вилки



\\obychn

c1g1[len]=c1g1[len]+2*fl[v[3] -2*pn];  \\  14-60       60-106
c1g1[len]=c1g1[len]+2*fl[v[4] -2*pn];  \\  44-90       30-76
c1g1[len]=c1g1[len]+2*fl[v[#v]-2*pn];  \\  74-120       0-46



\\forstep(j=4,v[#v]-2*pn-4,2,          \\   2*48
                                       \\   4*50
                                       \\ ...
                                       \\  14*60        x
                                       \\  16*62
                                       \\ ...
                                       \\  30*76        x
                                       \\ ...
                                       \\  44*90        x
                                       \\ ...
                                       \\  60*106       x
                                       \\  62*108
                                       \\ ...
                                       \\  72*118

forstep(j= 2,12,2, g2[len]=g2[len]+fl[j]*fl[j+2*pn]); \\Перемножение флагов для обычной вилки
forstep(j=16,28,2, g2[len]=g2[len]+fl[j]*fl[j+2*pn]);
forstep(j=32,42,2, g2[len]=g2[len]+fl[j]*fl[j+2*pn]);
forstep(j=46,58,2, g2[len]=g2[len]+fl[j]*fl[j+2*pn]);
forstep(j=62,72,2, g2[len]=g2[len]+fl[j]*fl[j+2*pn]);


\\print();
\\print(i+2,"   ",vc[len],"   ",len,"     ",c1g1[len]);


vc[len]=vc[len]+1;

);

print();
print(vc,"   ",vecsum(vc));
print();
print(c1g1,"   ",vecsum(c1g1));
print();
print(g2,"   ",vecsum(g2));
print();


cm=5; p=pn;

kan = vector(#vc);y = vector(#vc);
v = vector(#vc);



for(i=cm,#vc,kan[i]=vc[i]*p);

skan=vecsum(kan);

\\print(vc,"         ", vecsum(vc));
\\print(kan,"     ", skan);

for(i=cm,#vc, y[i]=cm*vecsum(vc)*kan[i]/skan;kan[i]=kan[i]-y[i] );

\\print(y,"         ", vecsum(y));
\\print(kan,"      ", vecsum(kan));
\\print();

forstep(i=#vc,cm,-1,

v[i]=y[i]*(i-cm)/cm - c1g1[i] - g2[i] ;

\\print(i, "    ",v[i]);

);

print();

kan[#vc]=kan[#vc]-v[#vc];

\\print(kan[#vc]);

print();

\\print(c1g1,"         ", vecsum(c1g1));

\\print();

forstep(i=#vc-1,cm,-1,

kan[i] = kan[i] + v[i+1] - g2[i+1] - v[i];

kan[i-1] = kan[i-1] + g2[i+1];

\\print(i, "    ",kan[i]);
);


\\obr = 

print(kan, "    ",vecsum(kan));

\\print(obr-kan);

print();

}quit;

[Dmitriy40]

(Оффтоп)

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

Ну Вы же видели мою прогу, которую ругали за лишний игрек.

Боюсь Вы меня не совсем верно поняли. Я ругал не за y[], а за то что он несущественен для работы программы и потому затрудняет разбирательство с ней для вычленения а что она собственно делает. Пока программы работают правильно и считают за секунды - к ним претензий нет, хоть как написанные. А вот если приходится не просто взять и запустить, а вникать, да не просто в код, а в идеи в нём реализованные - стоит постараться их более явно выражать. Оформлением кода, комментариями, пояснениями, ещё чем-то ... А то смотрю на строчку кода и понятия не имею в какой цикл она входит, под каким условием сидит, в инициализации она один раз выполнится (и тогда плевать на неё) или будет шуршать миллиарды раз.
Ещё меня очень сильно настораживают операции деления при вычислениях в целых числах, сразу мысль "а всегда ли разделится?", "а если нет, то что?". Увидев деление y[] на cm я и полез разбираться что это за зверь y[] и почему его можно делить.
Ну или это мой перфекционизм поднял голову. ;-)

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

Но считает-то она моментально и правильно. Если ей дать данные, то есть те самые 3 массива.

Обнаружив что в ней нет вычислений этих массивов я понял что толку мне от программы нет. Всегда же можно обойтись одним массивом: vc[]=my_new_array[] или vc[]=vc[]+my_new_array[]. И весь вопрос как его (или их) вычислить ...

-- 19.04.2024, 16:44 --

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

Это что-то невероятное, но у меня посчитала меньше чем за минуту!!

Вполне возможно: gp32 использует структуры со служебными полями меньшей длины и потому больше их элементов влезает и в кэши процессора и в память и потому же чуть быстрее происходит выделение и освобождение памяти под каждую переменную, так что в общем не удивительно. Когда что-то долго считается на PARI я обязательно проверяю скорость обоих вариантов, и x64 и x32, в разных программах скорости могут соотноситься совсем по разному и заранее бывает не угадаешь.

[Yadryara]

Dmitriy40, теперь дошли руки детально разобраться с той моей прогой при помощи схемы. Так я не только y[] выбросил, но и v[]. И от kan[] отказался. Она сократилась до совсем неприличных размеров:

{print(); cm=3; p=13;

vc   = [0,0,0,0,0,2,12,60,40,12,2,0]; 
c1g1 = [0,0,0,0,0,2, 6,38,26,10,2,0];  
g2   = [0,0,0,0,0,0, 2,12,12, 8,2,0,0]; 

for(i=cm,#vc-1, vc[i] =

(p-i)*vc[i] + (i-cm+1)*vc[i+1]
+   c1g1[i] -        c1g1[i+1]
+     g2[i] -        2*g2[i+1] + g2[i+2]         );

print(vc, "    ",vecsum(vc));
print();
}quit;

Теперь-то понятно что она делает? Вычисляет vc[] по новой, более универсальной формуле.

[Dmitriy40]

Посмотрел я Вашу предыдущую программу, вычисляющую c1g1[] и g2[].
Вот этот кусок кода в самом начале

p=19; mor=vecprod(primes([1,p]));
forstep(i=1,mor,2,
   for(j=1,#v,
      x=i+v[j];
      if(x%3==0 || x%5==0 || x%7==0 || x%11==0 || x%13==0 || x%17==0 || x%19==0, next(2));
   );

фактически перебирает в i все кандидаты в решения (то что мы в соседней теме записывали в таблицу и называли то формулами, то ещё чем-то) до 19#. Для вычисления vc[] для следующего простого 23#. Т.е. для вычисления vc[] для 113# для 19-252 надо перебрать все кандидаты в решения до 109#. Но простите их порядка 9.4e35! А само решение должно встретиться до 1e25 (ну пусть до 1e26), т.е. в миллиарды раз раньше/быстрее. Как-то слишком непрактично.
С другой стороны, это i нужно вроде бы только для fl[] и для len, а их наверняка можно вычислить существенно проще - len думаю просто равна расстоянию Хэмминга между чем-нибудь, а fl[] зависит от разности j-i и потому должен часто почти повторяться для разных i.

В последней программе не хватает вычисления vc[#vc].

[Yadryara]

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

фактически перебирает в i все кандидаты в решения (то что мы в соседней теме записывали в таблицу и называли то формулами, то ещё чем-то) до 19#. Для вычисления vc[] для следующего простого 23#. Т.е. для вычисления vc[] для 113# для 19-252 надо перебрать все кандидаты в решения до 109#. Но простите их порядка 9.4e35!

Ну так я же сразу и сказал, что Вы убьёте меня за такой перебор! Понятно же, что эту часть переделывать надо. Вы просили, я дал то, что было на тот момент. Сырое, но рабочее.

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

В последней программе не хватает вычисления vc[#vc].

Так оно не нужно, я же нолики специально добавил в хвосты. В g2[] два нолика добавил. Кстати c1g1 я теперь именую просто cg.

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

С другой стороны, это i нужно вроде бы только для fl[] и для len, а их наверняка можно вычислить существенно проще - len думаю просто равна расстоянию Хэмминга между чем-нибудь, а fl[] зависит от разности j-i и потому должен часто почти повторяться для разных i.

Конечно же повторяется. Уже проверял кое-какие варианты. Для некоторых i он вообще запрещён, их можно и не тыкать вилками.

[Dmitriy40]

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

Так оно не нужно, я же нолики специально добавил в хвосты.

А, вот оно что. Да, так работает, только я сразу поправил чтоб без ноликов было:

for(i=#v,#vc, vc[i]=(pn-i)*vc[i] + c1g1[i] + g2[i] + if(i+1>#g2, 0, (i-#v+1)*vc[i+1]-c1g1[i+1]-2*g2[i+1]) + if(i+2>#g2, 0, g2[i+2]); );

До кучи ещё мелкая оптимизация (не по скорости, а по простоте логики):

forstep(j= 2,12,2, g2[len]=g2[len]+fl[j]*fl[j+2*pn]); \\Перемножение флагов для обычной вилки
forstep(j=16,28,2, g2[len]=g2[len]+fl[j]*fl[j+2*pn]);
forstep(j=32,42,2, g2[len]=g2[len]+fl[j]*fl[j+2*pn]);
forstep(j=46,58,2, g2[len]=g2[len]+fl[j]*fl[j+2*pn]);
forstep(j=62,72,2, g2[len]=g2[len]+fl[j]*fl[j+2*pn]);

заменяется на (перечисляем пропуски):

forstep(j=2,72,2, if(!setsearch([14,30,44,60],j), g2[len]+=fl[j]*fl[j+2*pn]); ); \\Перемножение флагов для обычной вилки

А на самом деле можно даже и вот эти числа в списке не высчитывать:

forstep(j=2,72,2, if(!setsearch(v,j) && !setsearch(v,j+2*pn), g2[len]+=fl[j]*fl[j+2*pn]); ); \\Перемножение флагов для обычной вилки

Соответственно можно список подходящих j вынести за все циклы и посчитать один раз.

Теперь осталось цикл forstep(i=1,mor,2, превратить обратно в перебор по каждому простому и потом внимательно посмотреть как меняются c1g1 и g2 при расчёте каждого простого и можно ли вообще перейти от c1g1 и g2 для одного простого к им же но уже по следующему простому без перебора всех триллионов вариантов.

[Yadryara]

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

превратить обратно в перебор по каждому простому и потом внимательно посмотреть как меняются c1g1 и g2 при расчёте каждого простого и можно ли вообще перейти от c1g1 и g2 для одного простого к им же но уже по следующему простому

Разумеется, это и есть главная мечта: формулы найти для cg и g2.

Но это будь здоров какая сложная задача, хотя уравнений знаю уже немало. Всё никак не опубликую.

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

Соответственно можно список подходящих j вынести за все циклы и посчитать один раз.

Ну вот я на это уже намекал:

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

Кстати, эти 30 грязных определяются очень рано, уже после $19\#$. Их, видимо, можно в студию.

То есть не просто список всех возможных загрязнений паттернов, а список разрешённых/запрещённых a[] для каждого размера вилки. Скажем, шаг вилки 26, a[6] разрешён, a[32] тоже разрешён, но если нет такого паттерна в котором и a[6], и a[32] могут быть одновременно заняты малопростыми числами, то и нечего тыкать вилкой ни в a[6], ни в a[32].

[Dmitriy40]

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

То есть не просто список всех возможных загрязнений паттернов, а список разрешённых/запрещённых a[] для каждого размера вилки. Скажем, шаг вилки 26, a[6] разрешён, a[32] тоже разрешён, но если нет такого паттерна в котором и a[6], и a[32] могут быть одновременно заняты малопростыми числами, то и нечего тыкать вилкой ни в a[6], ни в a[32].

Если посмотреть на список всех комбинаций a[], дающих в окейной строке (и всех дальше, там уже ничего не меняется) vc[0..3] (т.е. начиная с чистых), то увидим интересную картину: vc[0] всегда образуется ровно одной комбинацией (0 вариантов загрязнения); vc[1] всегда образуется v[#vc]/2+1-#v вариантами (т.е. присутствуют все варианты загрязнения одним числом), а вот начиная с vc[2] количество вариантов становится резко меньше общего количества комбинаций (даже с учётом что из a[] исключены v[]). Например для последнего посчитанного 11-144 (в массиве ww у меня только уникальные комбинации a[] соответствующей длины):
59#: #ww: [1, 60, 994, 8494, 46852, ...]
61#: #ww: [1, 62, 1050, 8982, 48574, ...]
67#: #ww: [1, 62, 1058, 9034, 48760, ...]
71#: #ww: [1, 62, 1058, 9034, 48764, ...]
73#: #ww: [1, 62, 1058, 9034, 48764, ...]
Т.е. второе значение стабилизировалось уже на 61# (окейная лишь 73#) и равно всем возможным вариантам загрязнений, а вот третье значение стабилизировалось на 67# и всем возможным комбинациям 62*61/2=1891 уже не равно, т.е. уже не любые загрязнения двумя числами реально присутствуют. Аналогично и с загрязнениями по три числа, из 37820 реализовались лишь 9034.

С другой стороны, в этом

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

Кстати, эти 30 грязных определяются очень рано, уже после $19\#$. Их, видимо, можно в студию.

Вы не совсем правы (UPD: если речь про 19-252, что-то уже не уверен), в середине #ww[] числа продолжают увеличиваться вплоть до предокейной строки, т.е. появляются новые комбинации загрязнений. И для 19-252 новые комбинации будут и для 113#, всего несколько (десятков) штук, но будут. Собственно Ваши формулы для окейных строк работают как раз потому что в тех уже не появляется новых комбинаций загрязнений, их множество стабилизировалось и потому формулы столь просты и не зависят от этого множества, только от количеств соответствующей длины (которые и лежат в vc[]).

Если же говорить про малые простые, то по 19# все комбинации загрязнений уникальны, лишь для следующих простых комбинации загрязнений начинают повторяться (массив это общее количество вариантов загрязнений заданной длины/степени, левый 0 это чистые):
19#: #ww: [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 2, 8, 44, 70, 118, 78, 48, 16], len=31, 384 / 384
23#: #ww: [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 10, 40, 146, 346, 576, 600, 390, 134, 36, 6], len=31, 2284 / 2304
29#: #ww: [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 24, 230, 822, 2268, 4396, 6012, 5512, 3260, 1284, 344, 72, 6], len=31, 24230 / 27648
31#: #ww: [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 24, 488, 2780, 10278, 25554, 44516, 55602, 48338, 28518, 11430, 3452, 812, 108, 6], len=31, 231906 / 331776
37#: #ww: [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 4, 98, 968, 8370, 40984, 137018, 320136, 545468, 658854, 549262, 325204, 136642, 44218, 10986, 1770, 162, 6], len=31, 2780150 / 6635520
41#: #ww: [...], len=31, 31.1e6 / 159e6

И последняя моя PARI программа как раз и преобразует множество загрязнений по одному простому к множеству загрязнений по другому (в частности следующему) простому, т.е. обрабатывает не 6635520 вариантов, а лишь 2780150 (или 31млн вместо 159млн). И пока весь список всех вариантов загрязнений влезает в память можно переходить от одного простого к любому другому всего одним циклом по списку остатков по новому простому (мы же для любого остатка точно знаем какие варианты он может учистить (уменьшить степень загрязнённости) и как именно, а какие варианты оставит столь же грязными). Именно поэтому время не растёт в p-#v раз для каждого простого p, а остаётся почти постоянным с того момента как количество вариантов загрязнения почти перестало расти (что происходит на простом около трети диаметра).
И вот если бы как-то связать множество возможных загрязнений и ваши c1g1 с g2 ...

[Yadryara]

Ой здорово, сколько статистики!

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

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

Может не мы, а Вы точно знаете? Очень интересно. Пример бы...

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

И вот если бы как-то связать множество возможных загрязнений и ваши c1g1 с g2 ...

Ну так и посмотрим на примере...

-- 20.04.2024, 18:37 --

Ну вот какие 6 вариантов загрязнить 19-ку 30 числами ?

[Dmitriy40]

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

Ой здорово, сколько статистики!

Она вся есть в ww[] в моей программе, я просто её вывожу на экран, но не сохраняю. Чтобы получить вот эти строки просто к показу vc[] добавляете показ чисел #ww[k=1..31] (именно длин массивов с данным k) и всё.

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

Ну вот какие 6 вариантов загрязнить 19-ку 30 числами ?

Ну вот меняете в моей программе v[] на 19-252, предел цикла forprime(p=3,nextprime(v[#v]/2), на forprime(p=3,23, и после отработки (за тысячные доли секунды) выводите содержимое ww[31]:

print(ww[31]);
foreach(ww[31],m, print(vecextract(a,m[1][1])); );

Map([21235740289049400480450941027461, 1; 21235741497975220094530359919749, 1; 26306342087823698032410568955013, 1; 204250691690199630442929422664456, 1; 204250691690494778348108641272584, 1; 204290151029246999840041455387432, 1])
[2, 8, 20, 26, 32, 48, 56, 60, 68, 78, 86, 92, 98, 102, 110, 116, 138, 146, 158, 168, 170, 176, 182, 198, 200, 212, 228, 230, 236, 242]
[10, 22, 24, 40, 52, 54, 64, 66, 70, 76, 82, 94, 100, 106, 114, 136, 142, 150, 154, 166, 174, 184, 192, 196, 202, 204, 226, 232, 244, 250]
[10, 16, 22, 24, 40, 52, 54, 70, 76, 82, 84, 94, 106, 114, 136, 142, 150, 154, 160, 166, 174, 184, 192, 196, 204, 220, 226, 232, 244, 250]
[10, 22, 24, 40, 52, 54, 66, 70, 76, 82, 94, 100, 106, 114, 136, 142, 150, 154, 160, 166, 174, 184, 192, 196, 202, 204, 226, 232, 244, 250]
[2, 8, 20, 26, 48, 50, 56, 60, 68, 78, 86, 92, 98, 102, 110, 116, 138, 146, 152, 158, 170, 176, 182, 186, 198, 200, 212, 228, 230, 242]
[2, 8, 20, 26, 48, 50, 56, 60, 68, 78, 86, 98, 102, 110, 116, 138, 146, 152, 158, 170, 176, 182, 186, 188, 198, 200, 212, 228, 230, 242]

Здесь единицы это значит что каждая комбинация загрязнения встретилась один раз, а сами комбинации это длинное число, двоичный код которого является маской элементов a[] (если 1 то элемент остаётся в a[]). Если честно уже не помню надо ли показывать результат в обратном порядке Vecrev(vecextract()) или нет, т.е. откуда начинается нумерация, для количества единиц в числе (считается ведь только оно) это без разницы. А может вообще все эти списки загрязнений симметричны (между собой) и смена порядка ничего не изменит ...

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

Пример бы...

ОК, давайте разберём как обработается остаток 24 по модулю 29 для всех вот этих 6-ти вариантов грязных цепочек.
В строке с am=... остатку m[11]=24 соответствует число/маска am[11]=324517315718368994658257656078335, в котором нулевых битов всего 4шт: 13, 39, 64, 90, что соответствует числам 34, 92, 150, 208 в a[], именно эти числа могут вырезаться (если они там ещё оставались) из массива a[] при обработке остатка 24. Выше привёл содержимое ww[31] до обработки 29, а вот что будет в ww[31] если в foreach(am,x, для p=29 обработать только один остаток m[11]=24 с единственной маской x=324517315718368994658257656078335:

[2, 8, 20, 26, 48, 50, 56, 60, 68, 78, 86, 98, 102, 110, 116, 138, 146, 152, 158, 170, 176, 182, 186, 188, 198, 200, 212, 228, 230, 242]

От 6 грязных вариантов остался только один. Проверяем.
Из первого исключилось число 92 и у него k уменьшилось с 31 до 30.
Из второго исключилось число 150 и у него k уменьшилось с 31 до 30.
Из третьего исключилось число 150 и у него k уменьшилось с 31 до 30.
Из четвёртого исключилось число 150 и у него k уменьшилось с 31 до 30.
Из пятого исключилось число 92 и у него k уменьшилось с 31 до 30.
Из шестого ни одно из 4-х чисел не исключилось и потому k не изменилось.
Таким образом при обработке одного остатка по модулю 29 из 6-ти вариантов загрязнения один остался с тем же k, а остальные 5 вариантов k уменьшили на 1.
Как получается число 324517315718368994658257656078335 для m[11]=24 видно в строке am=... - биты маски сбрасываются в 0 для тех позиций, в которые попадает число кратное 29 с учётом того что первое кратное ему будет смещено на 24 (или на 29-24, не помню). Ну это по идее. Реально там ещё и Vecrev потому что vecextract считает нулевой бит за маску первого элемента массива, а fromdigits наоборот.
После отработки всех 12 остатков по модулю 29 все 6 вариантов ww[31] сохраняются, но 2, 3, 4, 6 встречаются уже по два раза:

Map([21235740289049400480450941027461, 1; 21235741497975220094530359919749, 2; 26306342087823698032410568955013, 2; 204250691690199630442929422664456, 2; 204250691690494778348108641272584, 1; 204290151029246999840041455387432, 2])

И в #ww[31] по прежнему останется 6, а 10 (сумма всех повторов) пойдёт в vc[31] для 29#.

-- 20.04.2024, 20:16 --

Структура ww[k]=Map() в PARI имеет хитрое внутреннее устройство и это не совсем массив, потому для него нельзя обратиться по индексу (например ко второму элементу ww[31][2]). Но можно запрашивать количество элементов #ww[k] и можно перебрать их все foreach(ww[k],m, (а вот цикл for(j=1,#ww[k], m=ww[k][j]; уже не сработает так как тут обращение по индексу j).
Выше показал содержимое ww[31] после 23#, а вот как оно в действительности:

foreach(ww[31],m, print(m));

[[26306342087823698032410568955013, 1], Vecsmall([5, 4, 3])]
[[204250691690199630442929422664456, 1], Vecsmall([0, 0, 1])]
[[204290151029246999840041455387432, 1], Vecsmall([0, 0, 1])]
[[204250691690494778348108641272584, 1], Vecsmall([2, 3, 2])]
[[21235740289049400480450941027461, 1], Vecsmall([0, 6, 2])]
[[21235741497975220094530359919749, 1], Vecsmall([0, 0, 1])]

Т.е. каждый элемент не просто массив из двух элементов что мы туда положили, а ещё и служебный массив указателей (два элемента которого нужны для построения двоичного дерева, а про третий не понял). И потому в программе приходится указывать лишний индекс в b=m[1][1]; qq=m[1][2]; чтобы обратиться лишь к нашим данным, а не к служебным.
Так же не работает vecsort на Map (да и многие остальные векторные функции), т.е. не получится пройтись по таблице в другом порядке кроме как выдаст foreach. В частности из-за этого пришлось единую таблицу ww делить на подтаблицы ww[k] по величине k равной количеству единиц (оставшихся чисел) в вариантах загрязнения (потому что перебор по k должен идти строго по возрастанию).
В общем далеко не любые операции с массивами применимы и к Map, это скорее исключения.

-- 20.04.2024, 20:27 --

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

в котором нулевых битов всего 4шт: 13, 39, 64, 90, что соответствует числам 34, 92, 150, 208 в a[], именно эти числа могут вырезаться (если они там ещё оставались) из массива a[] при обработке остатка 24

Фактически это четырёхзубая вилка. Понятно что для меньших простых зубьев будет больше, для больших меньше.

Да, ещё, кажется выше невнятно сказал: в ww[k] для каждого k=len хранятся маски чисел из a[], которые пока ещё остались не вычеркнутыми/удалёнными. Списки чисел (вектора) хранить очень накладно и медленно, потому вместо них храню лишь маски какие элементы вектора ещё остались. И вычёркивание элемента из вектора делается командой bitand с правильной маской (где вычёркиваемым элементам соответствуют нулевой бит, а всем остальным 1). Ну а #a[] заменяется на hammingweight(x) (подсчитывающей количество единичек в числе x, т.е. оставшихся элементов в a[]).

[Yadryara]

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

что соответствует числам 34, 92, 150, 208 в a[], именно эти числа могут вырезаться (если они там ещё оставались) из массива a[] при обработке остатка 24.

То есть, если позиция в списке есть, то она гарантированно выбивается, а длина кортежа гарантированно уменьшается?

Ну вот видите, ни в одном из 6 вариантов не встретилось больше одного подходящего числа. Значит для этого остатка вилкой тыкать бесполезно, g2 не изменится. А чисел выбивания для остальных 11 остатков тоже только 4 или 5 и все они идут с шагом 58?

[Dmitriy40]

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

А чисел выбивания для остальных 11 остатков тоже только 4 или 5 и все они идут с шагом 58?

Да я и не смотрел. Понятно что 58=29*2 и соответственно в 252 влезет или 4 или 5.

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

Ну вот видите, ни в одном из 6 вариантов не встретилось больше одного подходящего числа. Значит для этого остатка вилкой тыкать бесполезно, g2 не изменится.

Да, но ведь только для этого остатка.
Можно вывести полную матрицу какой остаток сколько чисел выбивает из каждого варианта для ww[31], вот например для 29# от 23# (выполнять после вычисления 23# по показанной программе):

forprime(p=29,29,
   am=vecextract(vector(p-1,i,fromdigits(Vecrev(apply(t->(t+i)%p==0,a)),2)), m=setminus(vector(p,i,i-1),Set(-v%p)));\\Обратная маска, единицы для выбиваемых чисел
   print("ww[31]:\t\t\t\tm[]:\t",strjoin(m,"\t"));
   foreach(ww[31],xx, print1(xx[1][1],":"); foreach(am,m, print1("\t",hammingweight(bitand(m,xx[1][1]))); ); print; );
);
ww[31]:                         m[]:    1       2       3       4       5       6       7       8       11      14      24      27
26306342087823698032410568955013:       1       2       2       2       1       2       1       0       0       1       1       3
204250691690199630442929422664456:      1       1       1       1       2       2       2       1       3       0       1       0
204290151029246999840041455387432:      0       1       2       1       2       2       2       1       3       1       1       0
204250691690494778348108641272584:      1       1       1       1       2       2       2       1       3       1       1       0
21235740289049400480450941027461:       1       2       2       2       1       1       1       1       0       1       1       3
21235741497975220094530359919749:       1       2       2       2       1       1       1       1       0       1       0       3

Видно что некоторые остатки и ничего не выбивают, а некоторые могут и три числа выбить.

Для сравнения левый край, как из ww[22]=10 выбиваются числа:

ww[22]:                         m[]:    1       2       3       4       5       6       7       8       11      14      24      27
5407439546445871545802499294400:        0       1       2       1       2       1       0       0       1       1       1       1
4001044270236653826773841093152:        0       0       1       1       2       2       1       0       1       1       1       1
2733703155018246050721327751712:        0       0       1       2       2       2       1       0       1       1       1       1
5407439551020664076082468099136:        0       1       2       2       2       1       0       0       1       1       1       1
3961739673989343284486410871328:        0       0       1       2       1       2       1       0       1       1       1       1
5407439551167661567919840564416:        0       1       2       2       1       1       0       0       1       1       1       1
5793569268377447606788536010241:        1       2       1       1       1       1       0       1       1       1       1       2
162735903088342354835455980095776:      1       0       1       1       1       1       2       1       2       1       1       1
336837150291637450080447890624:         0       1       2       2       1       1       0       1       1       1       1       1
3961584931484432334909478019584:        1       0       1       1       2       2       1       0       1       1       1       1

Видно что есть уменьшение k на 2, т.е. для 29# минимальный ненулевой элемент vc[] будет на 2 меньше чем для 23#. И ещё видно что один остаток может выбивать и больше двух вариантов количества чисел (чего для правого края не было видно).

-- 20.04.2024, 21:46 --

59# для 5-120 считалось на асме 7 дней в 4 потока. Слишком долго. Пока не показываю. Окейная 61# собирается считаться недели 4.

[Yadryara]

Dmitriy40, вроде немного разобрался и Вашу прогу проверил.

Паттерн 3-36.

После 11# было 2 кортежа длиной 11 (3 чистых и 8 грязных). $vc[9] = 2$.
________________________________________________________________

Переход к 13#.

Умножаю количество таких кортежей на 13: $2\cdot13 = 26$. Но, поскольку существует лишь $13-3 = 10$ возможных остатков по модулю 13, то это означает, что после всех операций останется ровно $2\cdot10 = 20$ кортежей из 26.

На данный момент у них одинаковая загрязнённость — максимальная. Пока что $vc[9] = 20$. Она может остаться прежней для всех 20-ти кортежей. Но только в том случае если все 10 остатков, представляющих из себя либо шило, либо вилку, промажут по всем кортежам со всеми расстановками грязных чисел.

Эти 10 остатков повели себя так:

ost     1       2       4       5       6       7       9      10      11     12

46230:  0       1       0       1       0       1       2       1       1      0
26925:  1       0       0       1       1       2       1       0       1      0

8 нулей, значит $e = 8$. То есть остались 8 кортежей длиной 11. $vc[9] = 8$.

2 двойки, значит $g2 = 2$. То есть остаток 7 может быть только обычной вилкой с шагом 26. Она точным попаданием обеими зубцами выбила два грязных числа из кортежа с расстановкой 26925. Остаток 9, то бишь тоже вилка-26, тоже выбила два грязных числа, но уже из кортежа с расстановкой 46230.

Так образовались два кортежа длиной 9. vc[7] += 2.

Оставшиеся 10 кортежей лишились по одному грязному числу, которые были выбиты либо шилом, либо одним из зубцов вилки. $g1 = 10$.

Так образовались два кортежа длиной 10. vc[8] += 10.

Некоторые из этих чисел есть и в таблице, которую составил ещё вчера. В нижних строках.

Pattern                                   0, 18, 36
                    vc_13#                                                 vc_11# L

                         0 =  0*10 + 1* 0                                         3
                                             
                         0 =  0* 9 + 2* 0           +  0                          4
            
    g2  c1  cg  g1   е   6 =  0* 8 + 3* 2 -  2      +  2 - 2* 0       
        
                        66 =  2* 7 + 4*12 -  6 +  2 + 12 - 2* 2 +  0     
                                         
3/3  0   4   2   4  16 330 = 12* 6 + 5*60 - 38 +  6 + 12 - 2*12 +  2   26/13 =  2

3/4  2  30   6  38  80 548 = 60* 5 + 6*40 - 26 + 38 +  8 - 2*12 + 12  156/13 = 12  

3/5 12 142  38 238 350 258 = 40* 4 + 7*12 - 10 + 26 +  2 - 2* 8 + 12  780/13 = 60

3/6 12  94  26 190 198  64 = 12* 3 + 8* 2 -  2 + 10      - 2* 2 +  8  520/13 = 40

3/7  8  26  10  58  54   8 =  2* 2             +  2             +  2  156/13 = 12   
   
3/8  2   4   2  10   8                                                 26/13 =  2
_________________________________________________________________________
    36 300  84 538 706                                               1664

[Yadryara]

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

2 двойки, значит $g2 = 2$.

Ну то бишь количество $g2$ считать на этом периоде несложно. Количество двоек просто нужно умножить на количество именно таких расстановок и все такие произведения сложить. В данном случае оба раза умножить на 1.

Dmitriy40
Догадываетесь уже как считать cg? Буду потихоньку выкладывать уравнения, которые можно проверить, например, по схеме.

$$\frac{c1_i + cg_i}{g1_i + 2g2_i + cg_i}=\frac{l_{min}}{i-l_{min}}$$

[Yadryara]

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

Количество двоек просто нужно умножить на количество именно таких расстановок и все такие произведения сложить.

Даже ещё проще. См. Ваш дополненный код:

(Оффтоп)

allocatemem(10^8);

print(); v=[0, 24, 48];lm=11;g2=vector(lm);pm=17;

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);
print();

{forprime(p=1, pm, \\ 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));

);

pm=nextprime(pm+1);

print();

forprime(p=pm,pm,
   am=vecextract(vector(p-1,i,fromdigits(Vecrev(apply(t->(t+i)%p==0,a)),2)),
 m=setminus(vector(p,i,i-1),Set(-v%p)));\\Обратная маска, единицы для выбиваемых чисел

for(l=1,lm,
   foreach(ww[l],xx,
 foreach(am,m,
u=hammingweight(bitand(m,xx[1][1]));
if(u==2,g2[l]+=xx[1][2]);
));
);
);

print();
print("g2 = ",g2);
print();
print();

}quit;

Например, найдены такие значения:

v=[0, 24, 48]

g2 = [0, 0, 0, 0, 0,   0,    2,   26,  22,  34, 8]; \\ 11# --> 13#
g2 = [0, 0, 0, 0, 0,   6,   42,   88,  98,  50, 4]; \\ 13# --> 17#
g2 = [0, 0, 0, 0, 0, 226, 1174, 1674, 838, 120, 0]; \\ 17# --> 19#