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

[Yadryara]

Я тоже считал 9-96 по Вашей проге на PARI:

Period    Seconds   Otn.  Nominal

31#           4.5

37#          44.6   9.9        28

41#         375.5   8.4        32

43#        2743     7.3        34

47#       19166     7.0        38

То есть для последней строки время обсчёта возросло не в 38 раз, а всего лишь в 7.

[Dmitriy40]

Если в последней процедуре заменить строку
foreach(am[i],m, vc[#v+hammingweight(bitand(m,a))]+=k; );
на строки
if(pr[i]>v[#v]/2,
m=hammingweight(a); vc[#v+m-1]+=k*m; vc[#v+m]+=k*(pr[i]-#v-m);
,
foreach(am[i],m, vc[#v+hammingweight(bitand(m,a))]+=k; );
);
(это как раз вторая моя идея), то обсчёт окейной строки (и только её) сильно ускорится, он станет всего раза в два дольше предыдущей строки, что в общем позволит посчитать на PARI и наверное 53# для диаметров 96 (если уж посчитали 47#).

Удивительно что не получается уменьшить перебор вдвое, вроде же симметрично, ан нет, что-то недопонимаю.

Больше идей по ускорению пока нет, точнее они все не работают.
Для 19-252 можно добраться до 67# или даже 71#, но и всё, 53# считается 13 минут в одном потоке.
Кстати с 73# для него начнутся другие проблемы, числа превысят 2^64 и придётся помучиться со 128 битными числами, что очевидно замедлит счёт.

С паттерном 9-96 забавный казус приключился: при отладке раз забыл поправить в одном месте условие перехода ко второй идее и вдруг на 47# показало что она OK! И sum правильная, и все числа совпали с вычислениями по предыдущим ... Во как красиво перераспределились числа по vc[], у меня аж глаза на лоб полезли, подумал что на самом деле условие на окейные строки мягче ... Ан нет, по прежнему окейные строки p>v[#v]/2.

Кстати на этом паттерне sum(53#)=2e15, т.е. фактически за 78с выполнились два квадриллиона итераций! Больше 30 триллионов в секунду! Это конечно же не так, но показывает силу замены циклов на увеличение добавляемой константы.

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

И полной Базы 11-к, аналогичной 9-кам ведь нет, правильно?

По идее есть, у Томаша Брада, SPT11, более 9млн штук до 2.148e18, более 540М текста (у меня конечно скачана). Даже если вдруг несколько и пропущены, это мелочи.

[Yadryara]

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

По идее есть, у Томаша Брада, SPT11,

Да я вспомнил уже, перечитал: я же сам об этом говорил в декабре. Есть с чём сравнивать. Я так понимаю, Вы пока не думали считать 11-ки.

И База 9-к у меня нашлась, я сам в ней поищу и 9-96 и 9-108.

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

Больше идей по ускорению пока нет, точнее они все не работают.
Для 19-252 можно добраться до 67#

Круто. Я сам хотел именно о 67# спросить. В быстром обсчёте 61# уже не сомневался.

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

Вот ещё формулы нашёл для SPT3:

$c_{max}(2\#)= \dfrac{d}{2} + 1$

$c_{max}(3\#)= \dfrac{d}{2} - \dfrac{d}{6}+ 1$

$c_{max}(5\#)= \dfrac{d}{2} - \dfrac{d}{6} - \lfloor\dfrac{d}{15}\rfloor + 1$

Я и для 7# поискал. И $c_{max}(7\#)$ тоже можно выразить через диаметр, но сложно. Значения $c$ для диаметра 168 симметричны относительно значений $c$ для диаметра 252 по модулям до 7 включительно.

[Dmitriy40]

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

Я так понимаю, Вы пока не думали считать 11-ки.

У них минимальный диаметр 132 (2шт), потом 4шт 144, потом 5шт 156, потом 10шт 168 и потом много 180. Слишком уж большие диаметры, даже для минимального окейной будет лишь 67#, а для 144 будет 73#, это всё слишком далеко.
Запустил на пробу паттерн [0 6 12 36 42 66 90 96 120 126 132], 41# считалось 1.6с, 43# 17с, 47# 167с, можно предположить на 53# хватит полчаса, на 59# пяти часов, на 61# двух суток, на 67# надо суток 4-5. Т.е. за неделю в одном потоке посчитать видимо можно, один паттерн. Как-то слишком долго.
По моему интереснее центральная 9-ка диаметром 108 в 9-252, она считается 2.4с на 41#, 22с на 43#, 192с на 47#, значит на окейный 59# хватит часа полтора. Хм, а пожалуй и запущу.

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

[vicvolf]

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

Но одно дело спрогнозировать строку с погрешностью не более 1% и совсем другое — точно.

Конечно прогноз, как метод, не дает 100% результата, а только с некоторой вероятностью. Пригоден ли в данном случае данный метод? Допустим мы определим среднюю прогнозируемую "загрезненность" кортежа 19-252. Чем она больше, тем больше времени потребуется на поиск кортежа 19-252. Но это все с определенной вероятностью. Нет гарантии, что действительно так и будет.

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

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

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

не может такая красота не работать для всех нечётных симметричных паттернов и кортежей.

Это не доказательство, но может быть рабочей гипотезой, которую надо проверить.

[Dmitriy40]

Симметричных паттернов нечётной длины бесконечное количество, все проверить невозможно физически.

Паттерн центральной 9-ки из 10-252 посчитал, хватило 1ч20м, 59# разумеется окейная.

Yadryara
Задача чем-то похожа на поиск размещения малых простых в пентадекатлоне, там тоже искали как расставить кратные простым чтобы покрыть максимум (или минимум) элементов вектора. Здесь же ищем не только сам вариант покрытия, но и подсчитываем количество всех вариантов (это sum) и сколько они оставляют непокрытых элементов (в vc[]).

Интересно могут ли быть паттерны, у которых по простым до окейной строки v[#v]/2 покрываются вообще все места (весь a[], в нём не остаётся элементов)? Тогда у таких дальше (с ростом p) будет увеличиваться лишь vc[#v] (минимальный элемент), остальные замрут (в нулях) ... Если правильно понимаю.

[Yadryara]

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

на 67# надо суток 4-5.

Но 67# если и считать, то только для очистки совести. А так-то не надо.

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

По моему интереснее центральная 9-ка диаметром 108 в 9-252,

Ну это само собой.

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

И всё равно не понимаю зачем эта куча данных, для поиска закономерностей и так полно информации,

А Вы, кроме уже озвученных, пытались ещё найти закономерности? Или не хотите отвлекаться?

vicvolf в сообщении #1634549 писал(а):

Это не доказательство, но может быть рабочей гипотезой, которую надо проверить.

Ну так проверили уже. Не менее 28 раз. Как только финальное число праймориала преодолевает радиус, нечётный симметричный паттерн всегда сходится, то есть все нужные числа теперь можно получать по точным формулам.

Почему так происходит, я не понимаю, не говоря уже о доказательстве. Предложите другой метод проверки? Это интересно.

[vicvolf]

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

Ну так проверили уже. Не менее 28 раз. Как только финальное число праймориала преодолевает радиус, нечётный симметричный паттерн всегда сходится, то есть все нужные числа теперь можно получать по точным формулам.

Очень хорошо. У Вас есть рабочая гипотеза - формулы для расчета средней загрязненности кортежа. С помощью прогностических методов Вы подтверждаете эти формулы сопоставляя с большим объемом реальных данных. Это достаточно для написания хорошей статьи вместе с Дмитрием.

[Dmitriy40]

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

А Вы, кроме уже озвученных, пытались ещё найти закономерности? Или не хотите отвлекаться?

Я искал не закономерности в vc[], а закономерности в переходе между уровнями вложенности циклов, чтобы поменьше раз запускать более глубокие уровни (это и есть первая моя идея).
Там есть и ещё идеи, но проверка их на PARI не даёт ускорения, а реализовывать в асме муторно (там нет встроенной команды сортировки, надо писать), да и сколько она займёт времени ... Но может дать ускорение раза в полтора.
Вообще по этим циклам ещё думать и думать, там ещё полно возможностей оптимизации, например можно подумать как ускорить проход более глубоких уровней если в a[] остался ровно один элемент (ровно один единичный бит в aa, hammingweight(aa)=1) (это похоже на идею №2, только по другому аргументу), возможно получится вместо более глубоких вложенных циклов пройти их просто подряд, линейно, и что-то там на что-то домножить. Т.е. ускорить выбор между cmin и cmin+1, точнее даже не выбор, а сразу подсчёт обоих в таком вот случае, а он вроде бы весьма не редок.
Ещё пробую ускорить самый глубокий цикл (это как бы идея №2), он же больше всего работает, но кроме как для окейной строки пока не получается. Да и для 19-252 это начнёт давать эффект только кажется с 67# (и то лишь 10% для него).
Идей много, но не про vc[], а про ускорение вычисления какой его элемент и на сколько надо увеличить. Не математика, а программирование.
Вот по поводу аналога пентадекатлона который день уже думаю, что бы из этого извлечь ... Можно например попытаться быстрее посчитать одно единственное cmin, но зачем оно без остальных, ведь остальные по нему не восстановить, даже имея ещё и cmax (его как и cmin тоже попробовать поискать теоретически).

Пока вот только что сделал многопоточность, теперь 53# для 19-252 вместо 770с посчиталось за 145с (1.3 раза ускорение от другой идеи). Через полчаса будет и 59# (которое до этого считалось 4ч), а к завтрашнему утру и 61#. На 67# понадобится до пары недель, не уверен что буду считать. Или может на другом компе запущу на несколько дней, вместо поиска кортежа 19-252.

[Yadryara]

vicvolf в сообщении #1634564 писал(а):

У Вас есть рабочая гипотеза - формулы для расчета средней загрязненности кортежа.

Да-а-а? А что же это за зверь такой "средняя загрязненность кортежа" ? Никто из нас такого понятия пока не вводил, ибо не было надобности. На каждый период $p\#$ считается точное количество чистых решений, с одним лишним простым, с двумя лишними и так далее. Максимальное количество таких загрязняющих простых очень быстро сходится и не меняется с дальнейшим увеличением периода.

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

Интересно могут ли быть паттерны, у которых по простым до окейной строки v[#v]/2 покрываются вообще все места (весь a[], в нём не остаётся элементов)? Тогда у таких дальше (с ростом p) будет увеличиваться лишь vc[#v] (минимальный элемент), остальные замрут (в нулях) ...

Ну нет конечно, если только Вы не о вырожденных паттернах.

Увы, на сегодня всё.

[vicvolf]

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

На каждый период $p\#$ считается точное количество чистых решений, с одним лишним простым, с двумя лишними и так далее. Максимальное количество таких загрязняющих простых очень быстро сходится и не меняется с дальнейшим увеличением периода.

Понял, почему сходится. Количество кортежей с лишними простыми конечно, поэтому с ростом $p\#$ стремится к 0. Не знаю, зачем потребовалось такое большое количество вычислений, чтобы это установить.

[Dmitriy40]

Yadryara
Смотрите как интересно: если взять окейную строку 59# для 9-108

v=[0, 18, 24, 48, 54, 60, 84, 90, 108]+;\\Центральная 9
13#: 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 6, 18, 52, 38, 14, sum=128
17#: 0, 0, 0, 0, 0, 0, 0, 0, 0, 2, 50, 156, 388, 320, 98, 10, sum=1024
19#: 0, 0, 0, 0, 0, 0, 0, 2, 46, 410, 1540, 3206, 3276, 1466, 274, 20, sum=10240
23#: 0, 0, 0, 0, 0, 0, 20, 432, 3590, 15424, 35594, 45646, 31188, 10002, 1388, 76, sum=143360
29#: 0, 0, 0, 0, 0, 118, 3386, 35278, 175130, 497350, 824188, 792896, 417946, 108078, 12278, 552, sum=2867200
31#: 0, 0, 0, 14, 1030, 28220, 318416, 1895608, 6657048, 14199002, 18364034, 14088422, 6059540, 1328570, 133156, 5340, sum=63078400
37#: 0, 0, 42, 4678, 175766, 2611544, 19866458, 89357910, 250951118, 443202300, 486651824, 323257980, 123097364, 24620448, 2310648, 87120, sum=1766195200
41#: 0, 84, 13968, 770798, 16932808, 182051804, 1108013524, 4142691586, 9842229472, 14940333264, 14334475856, 8456711872, 2910185200, 535330564, 46850320, 1655280, sum=56518246400
43#: 84, 30072, 2639632, 87296324, 1357307994, 11492099258, 58252326888, 186440247144, 385318411908, 515479563042, 441106638160, 234725520120, 73726725914, 12562141996, 1034815928, 34613136, sum=1921620377600
47#: 32556, 6225562, 348351442, 8312644096, 101881257928, 718710859776, 3132814845354, 8781512760472, 16104399333526, 19340733543434, 15016791819252, 7321681911080, 2127915564658, 339202330224, 26423216576, 839652864, sum=73021574348800
53#: 7296146, 930256774, 38621613382, 736602966318, 7589978857392, 46510188089196, 179730090243196, 452571543446402, 752980030575288, 827404766752526, 592364264818538, 268262768576580, 72954318002166, 10968910127560, 811730817320, 24518908416, sum=3212949271347200
59#: 1295064074, 122825808690, 4063646341290, 64980254846514, 581689967886012, 3171339005472996, 11076124774825438, 25484416612797590, 39071804184934830, 39847238085038946, 26645461047083900, 11337699790512612, 2914859915740588, 417213906162200, 29590093049760, 858161794560, sum=160647463567360000, OK

посчитать отношение vc/sum и нормировать на 1 (x=vc/sum; x/vecmax(x)), то получим:
[0.00000, 0.00000, 0.00010, 0.00163, 0.01460, 0.07959, 0.27796, 0.63955, 0.98054, 1.00000, 0.66869, 0.28453, 0.07315, 0.01047, 0.00074, 0.00002]
Мне одному кажется тут аналогия с доской Гальтона и чуточку смещённое вправо нормальное распределение? Может этого окажется достаточно для хотя бы грубой оценки, ведь sum то для любых праймориалов мы знаем точно, осталось правильно его размазать по известному количеству ячеек vc[].

Впрочем для 9-96 распределение несколько другое:
[0.00000, 0.00003, 0.00078, 0.00949, 0.06464, 0.26158, 0.64856, 1.00000, 0.95962, 0.56438, 0.19585, 0.03719, 0.00336, 0.00011]
Тоже похоже на нормальное, но скособоченное по другому.

Но идея то интересная ...

-- 28.03.2024, 22:37 --

О! Слушайте, а если не считать нифига все эти числа, а попытаться размазать известное количество по известному количеству ячеек чтобы распределение удовлетворяло Вашим формулам для следующего простого, а? Можно какой-нибудь метод поиска приближений натравить.
Распределение вообще единственно с данной суммой или нет? Если нет, это плохо ...

[Yadryara]

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

Тоже похоже на нормальное, но скособоченное по другому.

Болд мой. Ну то-то и оно, что флуктуации. Я это уже отмечал ранее: то правый край гуляет, то левый.

Возьмём один из самых простых паттернов. Его стартовая строка — 11#. А вот мы возьмём и начнём применять формулы на шаг раньше, со строки 7#:

v=[0, 12, 24]+

         3     4     5     6     7     8     9

03#:     0,    0,    0,    0,    0,    0,    2,   sum =     2
05#:     0,    0,    0,    0,    2,    2,         sum =     4
07#:     0,    0,    2,    2,   12,               sum =    16

               4    18    58    48                sum =   128

         4    72   318   598   288                sum =  1280
      
       128  1572  5610  7730  2880                sum = 17920


11#:     0,    2,   20,   48,   58,               sum =   128

13#:     2,   58,  304,  568,  348,               sum =  1280, OK

17#:    86, 1362, 5352, 7640, 3480,               sum = 17920, OK


         0     2    -2    10   -10

         2    14    14    30   -60

        42   210   258    90  -600

И мы видим, что суммы всё равно совпадают, а различия имеют некую закономерность...

Эталонные значения перечислены через запятую.

vicvolf, вы издеваетесь, что ли?

vicvolf в сообщении #1634594 писал(а):

Количество кортежей с лишними простыми конечно,

С чего вдруг оно конечно-то?

vicvolf в сообщении #1634594 писал(а):

поэтому с ростом $p\#$ стремится к 0.

Ну как же оно стремится к 0, когда оно наоборот с ростом $p\#$ увеличивается в разы и это прекрасно видно, в том числе в нынешнем примере ???

А значение $c_{max}$ в нынешнем случае устаканилось на 7. То есть тройка простых 12-12 может быть загрязнена другими простыми в количестве до 4-х штук.

[Dmitriy40]

Про не единственность сам догадался: можно всю sum засунуть в cmin, формулы останутся рабочими.
Собственно sum и p никак не ограничивают распределение чисел.

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

[Yadryara]

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

Так что не зная где вершина и крутизну спада (вдруг всё же не совсем нормальное) похоже ничего не посчитаешь.

Двиганием вершины я уже занимался, кстати. Удавалось добиться, что относительная погрешность для всех чисел строки стала меньше одного процента. Но этого мало. О чём и написал.

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

Во как красиво перераспределились числа по vc[], у меня аж глаза на лоб полезли, подумал что на самом деле условие на окейные строки мягче ...

Ну может и хорошо, что условия сходимости такие жёсткие. Количество шагов точно известно заранее. Может это позволит со временем понять и сам механизм сходимости.

А зачем нам нормальное распределение, нам вроде биномиальное нужно...