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

[Dmitriy40]

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

Сам я сейчас считаю самый короткий паттерн 9-84. Новости плохие: он не устаканился сразу после того как число $c_{\min}$ (с9) превысило ноль.

Да, неприятно.
Но хорошая новость в том что следующее значение 43# (на него ушло 9 минут) уже вроде бы правильное (эх, придётся добавить в программу вычисление отклонения):

v=[0, 12, 24, 30, 42, 54, 60, 72, 84]
13#: 0, 0, 0, 0, 0, 0, 0, 6, 10, 22, 20, 4, 2, sum=64
17#: 0, 0, 0, 0, 0, 4, 26, 92, 138, 166, 60, 22, 4, sum=512
19#: 0, 0, 0, 0, 16, 168, 622, 1244, 1552, 1008, 366, 128, 16, sum=5120
23#: 0, 0, 0, 52, 922, 5036, 13056, 20162, 18442, 9572, 3392, 950, 96, sum=71680
29#: 0, 0, 92, 3480, 34888, 144392, 315406, 410662, 317946, 147096, 47604, 11074, 960, sum=1433600
31#: 0, 170, 11372, 192398, 1283838, 4211514, 7803606, 8734594, 5930532, 2485060, 727276, 147320, 11520, sum=31539200
37#: 156, 25314, 825858, 9604582, 50786418, 141759764, 231348890, 231810674, 143192910, 55720990, 15091644, 2734560, 195840, sum=883097600
41#: 25928, 2194424, 50013522, 460777720, 2074673880, 5147266584, 7622973198, 6995091476, 4001889292, 1465245728, 372741528, 62117280, 4112640, sum=28259123200
43#: 3075976, 172443036, 2982765864, 22582804840, 87976549320, 195008570124, 262408889876, 220882584188, 117236333144, 40358558480, 9629086752, 1478049120, 90478080, sum=960810188800

С этим паттерном аналогично, стабилизации на 43# (14 минут счёта) тоже не наступило:

v=[0, 6, 18, 36, 48, 60, 78, 90, 96]
13#: 0, 0, 0, 0, 0, 0, 0, 0, 0, 2, 14, 42, 30, 8, sum=96
17#: 0, 0, 0, 0, 0, 0, 0, 2, 14, 92, 286, 266, 96, 12, sum=768
19#: 0, 0, 0, 0, 0, 0, 14, 130, 794, 2156, 2668, 1538, 352, 28, sum=7680
23#: 0, 0, 0, 0, 6, 72, 956, 6346, 21492, 35216, 29448, 11866, 2002, 116, sum=107520
29#: 0, 0, 0, 24, 542, 7208, 57810, 242326, 548434, 673056, 448210, 150138, 21604, 1048, sum=2150400
31#: 0, 0, 66, 2444, 41836, 426440, 2419688, 7598512, 13465216, 13488966, 7463260, 2120710, 269718, 11944, sum=47308800
37#: 0, 100, 7696, 205248, 2879384, 22781552, 101823496, 261043500, 389131082, 336237578, 163735794, 41753382, 4849292, 198296, sum=1324646400
41#: 86, 15556, 728848, 15639218, 180002808, 1162824978, 4328453218, 9487646180, 12375783316, 9538383100, 4205916924, 983492488, 105794760, 4003320, sum=42388684800
43#: 18448, 1953488, 69060882, 1179469642, 10979144778, 58631583864, 185237280994, 352946887468, 408038177160, 283116512406, 113848074894, 24597284220, 2480850036, 88984920, sum=1441215283200

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

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

ОК, эта задача мне вроде понятна, займусь теми что считаются за минуты.

[Yadryara]

Да, 9-84 сошёлся с третьей попытки на 43# :

23#                   -19    -8   -4  -5  -5   0   10   18   65   200
29#             -41   -24   -13   -6  -3   0   3    6    7   14    25
31#         -8   -7    -6    -5   -3  -1   0   3    4    5   10    20
37#    -8   -7   -5    -3    -2   -1  -1   0   2    2    3    3     6
41#   -14  -10   -7    -4    -3   -1   0   1   2    2    3    4     5
43#     0    0    0     0     0    0   0   0   0    0    0    0     0

Регулярность вроде есть, но при 37# и 41# левые края строк провалились вниз.

[Dmitriy40]

Yadryara
Условие $c_{\min}>0$ для работы формул неадекватно, а вот условие $p>d/2$ ($d$ это диаметр) для симметричных паттернов кажется всегда выполняется. А значит для 19-252 надо 113# (а 127# получится по формулам).

[Yadryara]

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

условие $p>d/2$ ($d$ это диаметр) для симметричных паттернов кажется всегда выполняется.

Тоже подумал, что стабилизация диаметром определяется. Ну вот видите, какая простая зависимость. Кстати, чтобы она лучше была видна, надо Стартовую строку и Загрязнённость поменять местами. Тогда d и St будут в соседних столбцах, а последнюю строчку с $d=96$ придётся выбросить:

   Len    Pattern    St  Zagr    c3    c4        c5

1.   3    0  6 12    5#     2     0     2         2

2.   3    0 12 24   11#     4     0     2        20

3.   3    0 18 36   17#     8     0    10       264

4.   3    0 24 48   23#    10     0    72      4332

5.   3    0 30 60   29#    13     0    38      2598

6.   3    0 36 72   31#    15     0     0       260

7.   3    0 42 84   41#    18     0   922    173122

Загрязнённость тоже прямо пропорциональна диаметру, но зависит не только от него, но и от параметра $c_{min}$, он же количество чистых простых, он же Len$.

[Yadryara]

Вот ещё формулы нашёл для 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$

[Yadryara]

И они даже для любого SPT работают. Проверил и для 19-252.

[Dmitriy40]

А я знаю как ускорить программу в несколько раз и для некоторых паттернов полностью отказаться от самого внутреннего (с наибольшим простым) цикла. Но слишком много кода переписывать.

[Yadryara]

То есть какую-то закономерность обнаружили?

[Dmitriy40]

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

Первая идея: иногда текущая маска удаляемых элементов полностью попадает на уже удалённые элементы, если таких случаев для данного цикла перебора больше одного, то вложенные циклы можно вызвать лишь ровно один раз, а значения vc[] увеличить сразу на k (сколько таких случаев попалось из всех), ведь каждый раз считается фактически одинаковое.
Вариант этой идеи: иногда попадаются допустимые остатки, которые вообще не удаляют элементов, можно сделать тоже ровно один вызов внутренних циклов. Это даже удобно объединить с условием выше в одно. Правда это кажется уже только для p>d/2, но может и на одно p раньше бывает, не знаю.

Вторая идея: иногда все варианты допустимых остатков содержат лишь один удаляемый элемент, т.е. если он попадёт на уже удалённый ранее (циклами верхних уровней), то эффекта не будет, иначе будет уменьшение длины на 1, и никаких других вариантов быть не может, можно взять маску сразу по всем допустимым остаткам и проверить сколько из них ещё не удалены, и тогда сделать всего ровно два увеличения vc[] на разные величины, один раз вообще без текущего простого, второй раз без него же, но увеличивать предыдущий элемент vc[], сумма двух увеличений будет равна количеству допустимых остатков по данному простому. Т.е. вместо последнего цикла по допустимым остаткам сделать всего два добавления к vc[] двух разных величин, в зависимости от количества единичных битов в маске сравнения. Правда это работает только для самого внутреннего цикла и только если все допустимые остатки удаляют максимум один элемент (обычно это как раз для случая p>d/2, но иногда бывает и на одно-два p раньше).
Вариант этой идеи: даже если есть не только по одному удаляемому элементу, то те что строго по одному можно посчитать без цикла, а оставшиеся - обычным циклом.

На PARI это всё вряд ли даст ощутимый эффект (до второй идеи просто не добраться, а первая будет срабатывать слишком редко), а вот на асме может ускорить, особенно для простых близких к концу (к начале работы формул). Но блин переписывать почти всё ...


Ещё странное наблюдение: практически всегда (исключений не видел) допустимые остатоки по каждому простому удаляют или k или k+1 элементов, не было такого чтобы вся группа допустимых остатков удаляла более двух вариантов длины, т.е. по каждому простому происходит уменьшение длины или на k, или на k+1, разумеется если до этого вектор был полный, иначе зависит от того как совпадут. А значит например не бывает тройных шагов сдвига влево минимального ненулевого элемента. Либо я на такие пока не наткнулся.

[Yadryara]

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

А значит например не бывает тройных шагов сдвига влево минимального ненулевого элемента.

Вот здесь разве я не показывал тройной шаг?

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

для простых близких к концу (к начале работы формул)

"И всё же конец мой ещё не конец, конец это чьё-то начало"...

[Dmitriy40]

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

Вот здесь разве я не показывал тройной шаг?

Да, там и четверной даже есть, на 19#. Значит я что-то не так понимаю или не так выразился. Шаг видимо может быть и большим, но для каждого простого их всего два варианта выходит, или k, или k+1. А для некоторых и один вариант, только k. Так например для 19-252 для p<19 и для p=31,59,61. Не знаю чем это может помочь, просто интересное наблюдение.

[Yadryara]

Каждая мелочь может оказаться важна. Можно ли ещё раз объяснить на примерах?

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

т.е. по каждому простому происходит уменьшение длины или на k, или на k+1,

Что за уменьшение длины? Длина строки? Это количество от первого ненулевого $c$(левого) до последнего ненулевого $c$ (правого)? Так она обычно увеличивается. Или имеете в виду снизу вверх идти?

-- 26.03.2024, 19:06 --

Или уменьшение длины это уменьшение $c_{max}$ ?

[Dmitriy40]

Вот здесь я приводил один из вариантов ускорения Вашей программы, в частности все циклы там были организованы так:

a2=a;
foreach(m[3],m3, a3=select(t->(t+m3)%3>0,a2);

Т.е. на каждом шаге длина aXX[] могла или остаться той же, или уменьшиться.

Встаёт вопрос а сколько остатков mX[] из всех допустимых уменьшают длину поданного на вход вектора и на сколько уменьшают. Для этого смотрим сколько в полном вектора a[] чисел кратных простому с учётом смещения для данного разрешённого остатка:

? v=[0,6,12,30,42,72,90,96,120,126,132,156,162,180,210,222,240,246,252]; a=setminus(vector(v[#v]/2,i,i*2),v);
? p=19; setminus(vector(p,i,i-1),Set(-v%p))
%1 = [2, 3, 11, 12, 16, 17]
? foreach(%1,i, print(i," : ",select(t->(t+i)%p==0,a)); );
2 : [36, 74, 112, 150, 188, 226]
3 : [16, 54, 92, 130, 168, 206, 244]
11 : [8, 46, 84, 122, 160, 198, 236]
12 : [26, 64, 102, 140, 178, 216]
16 : [22, 60, 98, 136, 174, 212, 250]
17 : [2, 40, 78, 116, 154, 192, 230]

Видим что каждый из допустимых остатков уменьшает длину a[] (удаляет из него перечисленные числа) на 6 или на 7 (конечно если удаляемые элементы не попадут в уже удалённые внешними циклами, пусть этот будет самым верхним).
А вот то же для простого p=17:

? p=17; setminus(vector(p,i,i-1),Set(-v%p))
%2 = [1, 2]
? foreach(%2,i, print(i," : ",select(t->(t+i)%p==0,a)); );
1 : [16, 50, 84, 118, 152, 186, 220]
2 : [32, 66, 100, 134, 168, 202, 236]

Тут длина a[] будет уменьшаться всегда только на 7 (если это самый верхний цикл).

Вот про длину a[] я и говорил, что она не может уменьшаться совсем уж произвольно.
Ну и в конце длина остатка a[] будет использована в увеличении одного из vc[#v+#a]++.


И если вдруг например из 24 допустимых остатков для 43# для 19-252 на конкретном значении a[] после всех внешних циклов (3#-41# для 19-252) скажем 7 штук пытаются удалить только уже отсутствующие в a[] числа (ну вот так совпало, поудаляли там много уже обработкой простых 3#-41#), то результат такого удаления будет идентичным для всех этих 7-ми допустимых остатков и значит все внутренние циклы (47# и далее) будут считать одно и то же 7 раз. Т.е. можно вызвать их все 1 раз вместо 7, но увеличивать vc[] не на 1, а на 7. И вместо 24 вызовов внутренних циклов достаточно сделать лишь 17+1. А они ведь далеко не быстрые! Плюс этот финт можно проводить на каждом шаге (каждом цикле, по каждому простому), и чем глубже расчёт (больше p), тем меньше оставшаяся длина a[] и тем чаще будут пытаться удалять уже отсутствующее и тем больше экономия времени. Это и есть первая идея.
Плюс, списки удаляемых чисел для каждого из допустимых остатков могут различаться лишь в уже удалённой части a[] и значит будут давать ровно тот же эффект идентичных вызовов внутренних циклов, их тоже можно сделать один раз с увеличением vc[] не на 1, а больше.

Вторая идея. Возьму другой паттерн и посмотрим на остатки для p=29:

]? v=[0,24,30,36,60]; a=setminus(vector(v[#v]/2,i,i*2),v);
? p=29; setminus(vector(p,i,i-1),Set(-v%p))
%1 = [1, 2, 3, 4, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 23, 24, 25, 26]
? a1=[]; foreach(%1,i, print(i," : ",x=select(t->(t+i)%p==0,a)); a1=concat(a1,x); ); Set(a1)
1 : [28]
2 : [56]
3 : [26]
4 : [54]
6 : [52]
7 : [22]
8 : [50]
9 : [20]
10 : [48]
11 : [18]
12 : [46]
13 : [16]
14 : [44]
15 : [14]
16 : [42]
17 : [12]
18 : [40]
19 : [10]
20 : [38]
21 : [8]
23 : [6]
24 : [34]
25 : [4]
26 : [32]
%2 = [4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 26, 28, 32, 34, 38, 40, 42, 44, 46, 48, 50, 52, 54, 56]

Т.е. каждый допустимый остаток удаляет максимум одно число из a[]. В конце объединил все возможно удаляемые числа в одном векторе.
Теперь смотрите, предположим внешние циклы оставили от a[] вектор ax=[2, 10, 14, 40, 44, 54, 58] (ну вот так случилось, для примера). Зададимся вопросом какие элементы vc[] надо увеличить и на сколько чтобы обработать все 24 допустимых остатка по модулю p=29. Можно конечно просто перебрать их и каждый раз удалять из ax[] один конкретный элемент с записью в a29[], потом vc[#v+#a29]++. А можно посчитать сколько раз будет удален элемент из ax[] при выполнении такого цикла, ведь все удаляемые числа уже есть в a1[], а значит количество совпадений a1[] с ax[] и есть это вот количество уменьшений длины ax[] на 1:

? setintersect(ax,%2)
%3 = [10, 14, 40, 44, 54]

Т.е. длина ax[] была равна 7 и в 5 случаях (для перечисленных удаляемых чисел, неизвестно для каких остатков) из 24 она будет уменьшена на 1, а в 19 случаях останется той же. Значит надо vc[#v+6] увеличить на 5, а vc[#v+7] увеличить на 19.
Всё, выполнять цикл по 24 допустимым остаткам по модулю p=29 не понадобилось, одна intersect и два увеличения vc[] на две разные величины, всё остальное считается заранее.

И разумеется в терминах векторов лишь для большей понятности, реально всё ровно так же работает и с масками и bitand()+hammingweight(), даже намного быстрее. А уж в асме и ещё быстрее, там hammingweight() делается одной командой.

[Dmitriy40]

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

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

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

ОК, эта задача мне вроде понятна, займусь теми что считаются за минуты.

Посчитал все паттерны из того списка (и немножко других). В основном до 41# (это минуты счёта каждого) или до начала работы формул (такие строки помечены OK справа и плюсиком правее паттерна). 40КБ текста, столько сообщением не показать, приложу файлом.
Считать дальше влом, каждая 43# претендует на несколько часов (а то и до 15), но пользы от 43# никакой, и так уже понятно что оно даст OK для диаметра 84 (т.е. можно получать и по формулам), а для диаметра 96 не хватит и 47# (последний пример в файле).
Считать ли доли чистых среди грязных до 1e26 (за 4ч каждую) - не вижу смысла, когда реально понадобится можно досчитать на PARI до p<1e6 (секунды) или p<1e9 (минуты), а потом просто домножить на величину 1e13#1e6# (или 1e13#/1e9#), ошибка составит единицы-десятки процентов, учитывая что они все и не нужны, те что будут реально интересны можно будет и досчитать точно.

Вложение:

d252-ya3.txt [37.71 Кб]
Скачиваний: 19

[Yadryara]

Dmitriy40, отлично!

Итак, у нас есть 19 полностью обсчитанных нечётных симметричных паттернов:

v=[0,  6, 12]+
v=[0, 12, 24]+
v=[0, 18, 36]+
v=[0, 24, 48]+
v=[0, 30, 60]+
v=[0, 36, 72]+
v=[0,  6, 18, 30, 36]+
v=[0, 18, 24, 30, 48]+
v=[0,  6, 30, 54, 60]+
v=[0, 12, 30, 48, 60]+
v=[0, 18, 30, 42, 60]+
v=[0, 24, 30, 36, 60]+
v=[0,  6, 36, 66, 72]+
v=[0, 12, 36, 60, 72]+
v=[0, 30, 36, 42, 72]+
v=[0, 12, 18, 30, 42, 48, 60]+
v=[0,  6, 30, 36, 42, 66, 72]+
v=[0, 12, 30, 36, 42, 60, 72]+
v=[0, 12, 24, 30, 42, 54, 60, 72, 84]+

И здорово, что среди них всё-таки есть одна-единственная красавица-девятка. Вот её-то и надо нынче взять в оборот.

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

Вы выкладывали базу 9-к до 1е16. Там было вроде 7.4 млн чистых 9-к. И даже посчитали сколько из них чистых центральных 9-108. Вроде 80+ тысяч. Там наверное и 9-ки с диаметром 96 можно найти. Затем попытаться обсчитать и сопоставить.

Это я писал по памяти: я и забыл, что минимальный диаметр для SPT9 равен 84, а не 96.

Значит ищем в этой Базе все 9-84. Это наш факт. Затем считаем среднюю ожидаемую частотность до 1е16 (или, если угодно, до 1е25). Затем сравниваем её с фактом. Ожидаю превышение над фактом на 30-40%.

Остальное прокомментирую позже. Что ж Вы сразу не сказали, что речь идёт о длине вектора загрязнений (вектора $a$)