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

[Yadryara]

Ну вот вроде что-то становится понятно. Не зря же ещё прошлым летом писал, что нужно и запрещённые остатки смотреть. Сразу-то их больше, а потом намного меньше — всегда 19.

Что же получается, Вам удаётся генерить добавки для периода $131071\#$ в самом низу, в интервале $0-67\#$ ?? А какой там кэф фильтрации? Или это я упрощаю? Или это получается, но очень долго? Под конец-то, добавки всё равно генерятся, куда же без этого, откуда кортежи тогда берутся.

[Yadryara]

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

иметь список запрещённых остатков вместо разрешённых, запрещённых всего 19шт независимо от величины простого (для простых больше 41).
[..]
(причём эти 19 чисел можно сделать одинаковыми для всех простых больше 252),

Научился считать запрещённые остатки. И именно если посчитать их для наибольшего числа паттерна, видно, что как только модуль превышает диаметр, они становятся строго одинаковыми и равны паттерну :

{print();
v=[0,6,12,30,42,72,90,96,120,126,132,156,162,180,210,222,240,246,252];
forprime(p=2,280,
zapr=Set((vector(19,i,p+v[#v])-v)%p);
print(p,"   ",zapr,"   ",#zapr);
);print();
}quit;

[Dmitriy40]

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

Что же получается, Вам удаётся генерить добавки для периода $131071\#$ в самом низу, в интервале $0-67\#$ ??

Фактически да, хотя впрямую они и не вычисляются. Это же эквивалентная формулировка.
Точнее вообще не вычисляются для периодов до 32717# (даже исходные добавки в 67#), а вот для периода 131071# добавки в 67# вычисляются, а дальше проверяются на допустимость (а фактически что меньше 67# в периодах 32719#-131071#). И увеличить период с 131071# до хоть праймориала десятков миллионов нетрудно (хотя размер exe жалко, по 4 байта на простое, а вставлять генерацию простых лень), но после полумиллиона проверка начинает подтормаживать, слишком много делений делается, потому ограничился 131071.
Похоже запутал. Переформулирую:
Для периодов 71#-32717# добавки вообще не генерятся, ни по каждому праймориалу, ни по 67#, генерятся сразу их вычеты/остатки по этим простым.
Для периодов 32719#-131071# генерится добавка в 67# и проверяется что она так и останется меньше 67# по каждому периоду. При этом сама добавка в большом периоде не вычисляется, проверяется лишь равенство нулю правого слагаемого в формуле КТО выше (а фактически допустимость остатка/вычета).
Так что добавки в периодах больше 67# не генерятся никогда. Но фактически их можно считать таковыми (в самом низу каждого большого периода).

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

А какой там кэф фильтрации?

А остановите счёт файлом STOP и посмотрите сколько строк в файле n19d252.temp (не считая последней с нулями) - вот столько строк осталось из 293.4e15/221184=1326573158400 в каждой вушке. У меня на какой-то вушке получилось 4260 строк. Значит фильтрация 1326573158400:4260 или 311.4e6:1. При теоретической 308.35e6:1. Хорошее совпадение.

[Dmitriy40]

Вот ещё одна забавная идея как ускорить поиск, и тоже не дающая практического результата.
Как известно для 19-252 по модулю 17# есть всего 64 добавки, идея: а давайте исключим из них те добавки, которые совпадают с однократно загрязнёнными 19-252, они же дают не искомую 19-252, а len=20, чего нам как бы не нужно. А потом исключим и двухкратно загрязнённые, и трёхкратно, и ... И не только по модулю 17# ...
Проверил, составил табличку сколько добавок остаётся (исходно и при загрязнении до 5, уже слишком долго считается, там знаки вопроса):
\begin{tabular}{|r|r|r|r|r|r|r|} \hline \# & 0 & -1 & -2 & -3 & -4 & -5 \\ \hline 3\# & 2 & 0 & 0 & 0 & 0 & 0 \\ 5\# & 4 & 0 & 0 & 0 & 0 & 0 \\ 7\# & 8 & 0 & 0 & 0 & 0 & 0 \\ 11\# & 16 & 0 & 0 & 0 & 0 & 0 \\ 13\# & 32 & 13 & 0 & 0 & 0 & 0 \\ 17\# & 64 & 49 & 29 & 0 & 0 & 0 \\ 19\# & 384 & 363 & 336 & 290 & 274 & 274 \\ 23\# & 2304 & 2264 & 2215 & 2142 & 2122 & ? \\ 29\# & 27648 & 27614 & 27559 & 27501 & ? & ? \\ \hline \end{tabular}
Наибольший выигрыш получается лишь при 13# и однократном загрязнении, почти втрое.
Разумеется так решения могут быть пропущены (раз в таблице есть нули), но поискать хоть какое-то можно попытаться быстрее полного поиска ...

Остающиеся вопросы:
не вполне понятен смысл нулей в таблице (понятно что вычеркнули слишком много, но вот почему так получилось);
дойдёт ли 19# тоже до нуля при дальнейшем загрязнении или начиная с 19# выходят на плато;
если не дойдёт, то связано ли это с длиной искомой 19-252 (пока не очевидно, может просто совпадение).

На последний вопрос ответ похоже таки "совпадение": проверил 13-192, у него для 13# уменьшается как 32 -> 16 -> 1 -> 0, т.е. доходит до нуля уже при трёхкратном загрязнении.
А 17# даже при пятикратном загрязнении на плато не вышло: 192 -> 175 -> 150 -> 142 -> 133 -> 126.

[Yadryara]

Dmitriy40
Обдумаю.

А пока часть своей статистики покажу.

3-й период 67# G22

Внутреннее сравнение:

Кортеж      Штук
   0/0       139
   1/1      1621       0.086
   2/2      8323       0.195       2.267
   3/3     26241       0.317       1.626
   4/4     59376       0.442       1.394
   5/5    101027       0.588       1.330
   6/6    131693       0.767       1.304
   7/7    137599       0.957       1.248
   8/8    116283       1.183       1.236
   9/9     80489       1.445       1.221
  10/10    45188       1.781       1.233
  11/11    20943       2.158       1.212
  12/12     7766       2.697       1.250
  13/13     2426       3.201       1.187
  14/14      560       4.332       1.353
  15/15       99       5.657       1.306
  16/16        9      11.000       1.944
  17/17        3       3.000       0.273
________________
          739785

Внешнее сравнение
3-го периода 67# G21 с
3-м периодом 67# G22

Кортеж       Штук
   0/0        139
   1/1       1621
   2/2       8323
   3/3      26241       1.112
   4/4      59376       1.089
   5/5     101027       1.095
   6/6     131693       1.102
   7/7     137599       1.100
   8/8     116283       1.102
   9/9      80489       1.085
  10/10     45188       1.110
  11/11     20943       1.090
  12/12      7766
  13/13      2426
  14/14       560
  15/15        99
  16/16         9
  17/17         3
______________________________
           739785       1.0987

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

Ну вот уточняю, сравнив сотни тысяч кортежей высшего качества 3-го периода 67# группы G21 с сотнями тысяч таких же кортежей 3-го периода 67# группы G22: не 1.094, а пока 1.112.

Ну а теперь, как видно из таблицы — 1.099.

[Yadryara]

С тех пор как начал считать все чистые кортежи, то есть те, для которых valids=len, их найдено уже свыше 1.8 млн в трёх группах. И по ним набралась такая общая статистика:

                                       Чистых
                                     кортежей
            Группа   Проверено        на юнит
3-й период 67# G21        1132         508.32
3-й период 67# G22        1999         462.94      1.098

2-й период 67# G25         960         340.48      1.493

[Yadryara]

Проговорю явно. Какой же вывод из этих соотношений? Довольно простой:
Соотношения между кортежами определённых длин ожидаемо примерно одинаковые. Соответственно, таблица мат. ожиданий 19/19 построена довольно точно, хотя предположение о том, что то же самое соотношение вблизи 1.1 сохраняется и между другими группами в одном и том же периоде ещё толком не проверено.

С одной стороны хочется проверить побыстрее это соотношение для 23-й группы 3-го периода, с другой — надо досчитывать 22-ю, раз уж взялся. Буду досчитывать, ещё больше половины осталось.

[Yadryara]

Перевернул таблицу нашего счёта. Теперь бо́льшие числа вверху. И образное выражение "подъём в горы (в космос)" соответствует картинке. Оказывается посчитали уже гораздо больше половины 2-го периода 67#.

$\tikz[scale=.08]{ \fill[green!30!blue!20] (20,50) rectangle (30,60); \fill[green!30!blue!20] (20,40) rectangle (40,50); \fill[green!30!blue!20] (40,30) rectangle (50,40); \fill[green!30!grey!40] (110,40) rectangle (120,50); \fill[green!30!grey!40] (30,30) rectangle (40,40); \fill[green!30!grey!40] (60,20) rectangle (110,30); \fill[green!90!blue!50] (20,30) rectangle (30,40); \fill[green!90!blue!50] (0,10) rectangle (20,110); \fill[green!90!blue!50] (110,20) rectangle (120,40); \fill[green!90!blue!50] (0,20) rectangle (60,30); \fill[green!90!blue!50] (0,10) rectangle (120,20); \draw[step=10cm] (0,0) grid +(130,110); \node at ( 5,5){\textbf{19}}; \node at (15,5){\textbf{20}}; \node at (25,5){\textbf{21}}; \node at (35,5){\textbf{22}}; \node at (45,5){\textbf{23}}; \node at (55,5){\textbf{24}}; \node at (65,5){\textbf{25}}; \node at (75,5){\textbf{26}}; \node at (85,5){\textbf{27}}; \node at (95,5){\textbf{28}}; \node at (105,5){\textbf{29}}; \node at (115,5){\textbf{30}}; \node at (125,5){\textbf{\%}}; \node at (125,105){\textbf{0.1}}; \node at (125,95){\textbf{0.1}}; \node at (125,85){\textbf{0.1}}; \node at (125,75){\textbf{0.1}}; \node at (125,65){\textbf{0.1}}; \node at (125,55){\textbf{0.1}}; \node at (125,45){\textbf{0.1}}; \node at (125,35){\textbf{1.8}}; \node at (125,25){\textbf{59}}; \node at (125,15){\textbf{100}}; }$

[Yadryara]

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

С одной стороны хочется проверить побыстрее это соотношение для 23-й группы 3-го периода, с другой — надо досчитывать 22-ю, раз уж взялся. Буду досчитывать, ещё больше половины осталось.

Правильно сделал, что продолжил досчитывать. Теперь уже больше 1.1 млн чистых кортежей найдено в 22-й группе. И показатели наконец-то хорошо сгладились. И это позволило мне сделать прогноз по многим кортежам и сверить с фактом. За основу взял наибольшее количество кортежей, для 7/7. Оба кэфа брал одни и те же, отличаются только степени.

Кортеж                                    Прогноз    Факт
valids/len                                  штуки   штуки
7/7                                                206400

                      1       1
8/8     206400 / 0.956 / 1.229        =    175671  174517

                      2       3
9/9     206400 / 0.956 / 1.229        =    121657  120427

                      3       6
10/10   206400 / 0.956 / 1.229        =     68553   67821

                      4       10
11/11   206400 / 0.956 / 1.229        =     31431   31450

                      5       15
12/12   206400 / 0.956 / 1.229        =     11726   11723

                      6       21
13/13   206400 / 0.956 / 1.229        =      3559    3680

                      7       28
14/14   206400 / 0.956 / 1.229        =       879     846

                      8       36
15/15   206400 / 0.956 / 1.229        =       177     163

                      9       45
16/16   206400 / 0.956 / 1.229        =      28.9      14

                      10       55
17/17   206400 / 0.956  / 1.229       =      3.84       3

                      11       66
18/18   206400 / 0.956  / 1.229       =     0.416       0

                      12       78
19/19   206400 / 0.956  / 1.229       =     0.037       0

Это данные по 2399 юнитам. Соответственно, чтобы найти одну 19/19 надо в среднем проверить $\dfrac{2399}{0.037}\approx$ 65 тысяч юнитов в этой группе. Но только где ж их взять-то, ведь их всего 5390.

Кортежи я записываю максимально компактно, могу прислать кое-что для сверки. Только начальное число, из которого можно вытащить всю остальную инфу. Например, вот 14 штук 16/16:

20266049405567742983270431
20494408701482521521129781
17825579844793180784908951
21114108505414471842103021
17164684840426702978128811
16047006704614473567223171
17251188549605228276662531
21459477996467782207330321
22149771805777034242647751
21387898173206153881315951
22512392447323157449090387
23344730600614081509420937
15835535652669990815548357
18816443418624746244130147

[Dmitriy40]

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

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

А какой там кэф фильтрации?

А остановите счёт файлом STOP и посмотрите сколько строк в файле n19d252.temp (не считая последней с нулями) - вот столько строк осталось из 293.4e15/221184=1326573158400 в каждой вушке. У меня на какой-то вушке получилось 4260 строк. Значит фильтрация 1326573158400:4260 или 311.4e6:1. При теоретической 308.35e6:1. Хорошее совпадение.

В последней вушке только что полностью посчитанной группы 3G30 оказалось 4393 строк, т.е. кэф фильтрации был 1326573158400:4393 или 302e6:1, т.е. заметно меньше теоретического, хотя совпадение всё равно считаю хорошим, заодно виден и разброс.

[Yadryara]

А я считаю не хорошим, а прекрасным. На тысячах 302, а не 308 — малое расхождение. Ещё тогда проверил программно величину этого кэфа. Сошлось. Кстати, поднимите руку, кто понимает, что это за кэф фильтрации и как его считать. Важнейший параметр, между прочим.

Между тем у меня существенная корректировка аппроксимации произошла. Цифры то сглаживаются, то вновь комкаются. Поясню на примере 22-й группы 3-го периода (2G22 в обозначении Дмитрия):

Посчитано 3799 юнитов
Найдено 1753697 кортежей
В среднем 461.62 кортежей на юнит

Кортеж    Штук        Отн1       Отн2       Отн3
   0/0    357
   1/1    3859          93
   2/2    19549        197       2134      
   3/3    62098        315       1595       1338
   4/4    140657       441       1402       1137
   5/5    238085       591       1338       1048
   6/6    312092       763       1291       1036
   7/7    326966       955       1251       1032
   8/8    276311      1183       1240       1009
   9/9    190517      1450       1226       1011
  10/10   107618      1770       1221       1004
  11/11   49663       2167       1224        997
  12/12   18576       2674       1234        992

  13/13   5732        3241       1212       1018
  14/14   1329        4313       1331        911
  15/15   255         5212       1208       1101
  16/16   30          8500       1631        741
  17/17   3          10000       1176       1386

Соотношение высчитываются между соседними значениями. Например, кортежей 16/16 30 штук, а 17/17 — 3 штуки, то есть в 10.000 раз меньше. Это число и видим в соответствующей строке в 3-м столбце. Точка опущена. В следующих столбцах справа уже считаются соотношения между соотношениями.

Теперь смотрим на 4-й столбец. Видим что-то типа параболы, с вершиной где-то между 10/10 и 11/11 и значением где-то в районе 1220. Нижняя часть, где штук намного меньше, отделена пустой строкой, потому что по этим данным пока нельзя понять картину. Но комканье есть и выше. В 5-м столбце неуклонное падение нарушается : 1137, 1048, 1036, 1032, 1009, 1011, 1004, 997, 992.

Это из-за того, что кортежей 8/8 нашлось многовато. Раньше таких неровностей было гораздо больше. Надеюсь на сглаживание, после чего ещё раз сделаю аппроксимацию. В том числе для 19/19.

[Dmitriy40]

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

А я считаю не хорошим, а прекрасным.

Поясню: если предполагать что кандидаты полностью случайны среди всех, то их должно быть 4302, получить же 4260 вероятность не выше 26%, а получить 4393 не выше 8.3%. Считаю обе эти вероятности слишком малыми и потому совпадение не столь уж прекрасным. Или из 1326573158400 кандидатов проходят сито фильтрации не совсем случайные, нужна ещё в разы большая выборка чтобы сгладить флуктуации.

[Yadryara]

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

Поясню: если предполагать что кандидаты полностью случайны среди всех, то их должно быть 4302, получить же 4260 вероятность не выше 26%, а получить 4393 не выше 8.3%. Считаю обе эти вероятности слишком малыми и потому совпадение не столь уж прекрасным.

Отклонение на $4393-4302 = 91$ штуку — рекордное на 642 попытки?

Вот если бы при матожидании 4302 штуки нашлись бы 3000 штук, это да, это повод задуматься.

Лично мне гораздо интереснее поиск закономерностей, который я показал выше. Это ведь ещё один способ определить ожидаемое количество 19/19.

[Dmitriy40]

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

Отклонение на $4393-4302 = 91$ штуку — рекордное на 642 попытки?
Вот если бы при матожидании 4302 штуки нашлись бы 3000 штук, это да, это повод задуматься.

Нет, это не максимум, а лишь одна попытка.
Запустил на основном компе счёт тысячи вушек в 1G29 с выдачей размера выдачи после фильтрации, первые 5 получились такими: 4327, 4254, 4437, 4307, 4309.
Оценивать абсолютные числа неразумно, надо считать в стандартных отклонениях $\frac{|x-4302|}{\sqrt{4302}}$. И 4393 дают 1.39 сигмы, что совсем немало. А 4437 даёт 2.06 сигмы и вероятность не более 2%. 3000 дали бы почти 20 сигм и это совершенно нереально - означает что кандидаты остаются ну совершенно не случайные и стоило бы поискать неучтённые зависимости.

[Dmitriy40]

На 40шт вушек наибольшее отклонение было 4125, это 2.7 сигмы или вероятность не более 0.35%.
Две вушки дали ровно 4302 и 4303.

UPD.
100 вушек дали минимум 4125 (2.7 сигмы и 0.35% вероятность) и максимум 4492 (3 сигмы и 0.18% вероятность).
Арифметическое среднее совпало с медианой и равно 4295 (смещение центра на -0.16% или -0.107 сигмы).
В диапазон плюс-минус одной сигмы попало 72% вместо теоретических 68.3%.
Можно сделать вывод что распределение таки весьма близко к случайному.