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

[Dmitriy40]

3-108 до 1e10:

1e10: [0.004556, 0.029611, 0.089501, 0.167122, 0.216018, 0.205252, 0.148592, 0.083834, 0.037390, 0.013295, 0.003785, 0.000863, 0.000157, 0.000023, 0.000003, 0.000000, 0.000000, 0.000000, 0.000000, 0.000000, 0.000000, 0.000000], sum=4.321341770 e43289 / 6.523576147 e43292 * 1.000 e10 = 6624192
1e10: nn=[37790, 220818, 600841, 1019009, 1201623, 1051131, 703602, 370724, 155895, 52885, 14740, 3306, 678, 126, 19, 7, 6, 1, 3, 1, 2, 2, 0, 0, 0, 1], sum=5433210, time: 14min, 5,635 ms

Кэф: $6624192/5433210=1.219$
311МБ текста.

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

Надеюсь, они у Вас проверяются.

Что значит проверяются? Они строятся из последовательных простых, среди которых выделяются куски заданного диаметра, содержащие искомый паттерн, и целиком записываются в лог. Вот несколько первых кортежей:
5: [0, 2, 6, 8, 12, 14, 18, 24, 26, 32, 36, 38, 42, 48, 54, 56, 62, 66, 68, 74, 78, 84, 92, 96, 98, 102, 104, 108], len=28, valids=3
19: [0, 4, 10, 12, 18, 22, 24, 28, 34, 40, 42, 48, 52, 54, 60, 64, 70, 78, 82, 84, 88, 90, 94, 108], len=24, valids=3
29: [0, 2, 8, 12, 14, 18, 24, 30, 32, 38, 42, 44, 50, 54, 60, 68, 72, 74, 78, 80, 84, 98, 102, 108], len=24, valids=3
43: [0, 4, 10, 16, 18, 24, 28, 30, 36, 40, 46, 54, 58, 60, 64, 66, 70, 84, 88, 94, 96, 106, 108], len=23, valids=3
59: [0, 2, 8, 12, 14, 20, 24, 30, 38, 42, 44, 48, 50, 54, 68, 72, 78, 80, 90, 92, 98, 104, 108], len=23, valids=3
73: [0, 6, 10, 16, 24, 28, 30, 34, 36, 40, 54, 58, 64, 66, 76, 78, 84, 90, 94, 100, 106, 108], len=22, valids=3
83: [0, 6, 14, 18, 20, 24, 26, 30, 44, 48, 54, 56, 66, 68, 74, 80, 84, 90, 96, 98, 108], len=21, valids=3
103: [0, 4, 6, 10, 24, 28, 34, 36, 46, 48, 54, 60, 64, 70, 76, 78, 88, 90, 94, 96, 108], len=21, valids=3
173: [0, 6, 8, 18, 20, 24, 26, 38, 50, 54, 56, 60, 66, 68, 78, 84, 90, 96, 98, 104, 108], len=21, valids=3
Что тут ещё надо проверять-то?

-- 02.07.2024, 13:15 --

Программа на PARI, которая их ищет:

v=[0,54,108]; nn=vector(v[#v]); t0=getwalltime(); allocatemem(10^8);
{for(n=0,999, pp=primes([n*1e7,(n+1)*1e7+108]); b=1;for(ip=1,#pp, p=pp[ip];
while(b<=#pp && pp[b]-p<108, b++); if(b>#pp, break);
if(pp[b]-p!=108 || !setsearch(pp[ip..b],p+54), next); nn[b-ip+1]++;
write("n3d108.txt", p,": ",pp[ip..b]-vector(b-ip+1,j,p),", len=",b-ip+1,", valids=",#v));
b=#nn; while(b>#v && nn[b]==0, b--);
write("n3d108.txt", n+1,"e7: nn=",nn[#v..b],", sum=",vecsum(nn));
print(n+1,"e7: nn=",nn[#v..b],", sum=",vecsum(nn),", time: ",strtime(getwalltime()-t0)));

[Yadryara]

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

Что значит проверяются? Они строятся из последовательных простых,

Ага вижу, что не псевдо, а именно простые. Ну как-то нужно проверить кортежи, хотя бы выборочно. Займусь.

Гипотеза чистоплотности прекрасно подтвердилась:

Len     3    4    5    6    7    8    9   10   11   12   13

Sred    2   17   58  127  192  212  179  117   60   25    8
Fact    3   24   75  148  204  207  162  100   49   20    6

Как и для 13-168: сначала фактические доли всегда выигрывают, затем вблизи самого популярного варианта происходит перелом и уже только проигрывают.

[Dmitriy40]

5-120-5:

1e11: [0.007488, 0.043208, 0.116211, 0.193593, 0.223878, 0.190913, 0.124470, 0.063482, 0.025702, 0.008335, 0.002175, 0.000457, 0.000077, 0.000010, 0.000001, 0.000000, 0.000000, 0.000000, 0.000000, 0.000000, 0.000000, 0.000000], sum=6.187303814 e136982 / 4.458746157 e136987 * 1.000 e11 = 1387678
1e11: nn=[10804, 55957, 136377, 206610, 218013, 171830, 104766, 50025, 19057, 5885, 1554, 318, 59, 9, 2, 5, 3, 3, 2, 0, 0, 1, 0, 2], sum=981282, time: 1h, 10min, 15,490 ms

Кэф: $1387678/981282=1.414$
66МБ текста кортежей.
Несколько из них:
7: [0, 4, 6, 10, 12, 16, 22, 24, 30, 34, 36, 40, 46, 52, 54, 60, 64, 66, 72, 76, 82, 90, 94, 96, 100, 102, 106, 120], len=28, valids=5
11: [0, 2, 6, 8, 12, 18, 20, 26, 30, 32, 36, 42, 48, 50, 56, 60, 62, 68, 72, 78, 86, 90, 92, 96, 98, 102, 116, 120], len=28, valids=5
37: [0, 4, 6, 10, 16, 22, 24, 30, 34, 36, 42, 46, 52, 60, 64, 66, 70, 72, 76, 90, 94, 100, 102, 112, 114, 120], len=26, valids=5
107: [0, 2, 6, 20, 24, 30, 32, 42, 44, 50, 56, 60, 66, 72, 74, 84, 86, 90, 92, 104, 116, 120], len=22, valids=5
137: [0, 2, 12, 14, 20, 26, 30, 36, 42, 44, 54, 56, 60, 62, 74, 86, 90, 92, 96, 102, 104, 114, 120], len=23, valids=5
151: [0, 6, 12, 16, 22, 28, 30, 40, 42, 46, 48, 60, 72, 76, 78, 82, 88, 90, 100, 106, 112, 118, 120], len=23, valids=5
277: [0, 4, 6, 16, 30, 34, 36, 40, 54, 60, 70, 72, 76, 82, 90, 96, 102, 106, 112, 120], len=20, valids=5
359: [0, 8, 14, 20, 24, 30, 38, 42, 50, 60, 62, 72, 74, 80, 84, 90, 98, 102, 104, 108, 120], len=21, valids=5
389: [0, 8, 12, 20, 30, 32, 42, 44, 50, 54, 60, 68, 72, 74, 78, 90, 98, 102, 110, 114, 120], len=21, valids=5
401: [0, 8, 18, 20, 30, 32, 38, 42, 48, 56, 60, 62, 66, 78, 86, 90, 98, 102, 108, 120], len=20, valids=5
541: [0, 6, 16, 22, 28, 30, 36, 46, 52, 58, 60, 66, 72, 76, 78, 90, 100, 102, 106, 112, 118, 120], len=22, valids=5
557: [0, 6, 12, 14, 20, 30, 36, 42, 44, 50, 56, 60, 62, 74, 84, 86, 90, 96, 102, 104, 116, 120], len=22, valids=5
571: [0, 6, 16, 22, 28, 30, 36, 42, 46, 48, 60, 70, 72, 76, 82, 88, 90, 102, 106, 112, 120], len=21, valids=5
877: [0, 4, 6, 10, 30, 34, 42, 52, 60, 64, 70, 76, 90, 94, 100, 106, 114, 120], len=18, valids=5
1033: [0, 6, 16, 18, 28, 30, 36, 54, 58, 60, 64, 70, 76, 84, 90, 96, 118, 120], len=18, valids=5
9431: [0, 2, 6, 8, 30, 32, 36, 42, 48, 60, 66, 80, 90, 102, 108, 116, 120], len=17, valids=5
10103: [0, 8, 30, 36, 38, 48, 56, 60, 66, 74, 78, 90, 108, 120], len=14, valids=5
98963: [0, 18, 30, 36, 50, 54, 60, 78, 90, 116, 120], len=11, valids=5
101021: [0, 6, 30, 42, 60, 68, 86, 90, 92, 96, 98, 120], len=12, valids=5
991603: [0, 4, 16, 18, 30, 40, 48, 60, 90, 100, 114, 120], len=12, valids=5
1005041: [0, 8, 30, 32, 38, 60, 66, 90, 92, 102, 120], len=11, valids=5
9991349: [0, 8, 30, 60, 84, 90, 92, 102, 114, 120], len=10, valids=5
10023787: [0, 30, 60, 90, 102, 114, 120], len=7, valids=5
99930833: [0, 8, 14, 18, 30, 36, 44, 56, 60, 74, 78, 90, 98, 120], len=14, valids=5
100015099: [0, 30, 34, 42, 60, 70, 78, 90, 114, 120], len=10, valids=5
999946427: [0, 2, 30, 42, 60, 90, 96, 110, 120], len=9, valids=5
1000017169: [0, 30, 34, 54, 60, 78, 88, 90, 118, 120], len=10, valids=5
9999974597: [0, 12, 30, 56, 60, 90, 104, 120], len=8, valids=5
10000023877: [0, 12, 30, 34, 60, 76, 90, 120], len=8, valids=5
99999873157: [0, 30, 60, 90, 120], len=5, valids=5

[Yadryara]

Ещё посчитал для 3-108:

10^    Чистый     Общий    Кортежей

10      0.799     1.219     5433210
09      0.766     1.194      761142
08      0.805*    1.160      111186
07      1.319**   1.120       17209

* — ненадёжный, посчитан по 131 кортежу;
** — совсем ненадёжный, посчитан по 3 кортежам.

[Yadryara]

Пока 5-120 не смотрел, неторопливо вожусь с 3-108:

Диапазон  Чистые, шт.  Доля чистых       Все, шт.

1 E4         0.000000     0.0000 %        100.120
1 E5         0.000427     0.0001 %        514.725
1 E6         0.080393     0.0026 %       3035.23 
1 E7         3.95778      0.0205 %      19276.6
1 E8       105.467        0.0817 %     129023
1 E9      1973.15         0.2172 %     908518
1 E10    30176.9          0.4556 %    6624192
1 E11   404323            0.8119 %   49800887

Да, ещё буду искать эти кортежи до 1е11. Для 1е6 общий кэф 1.047.

[Yadryara]

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

Да, ещё буду искать эти кортежи до 1е11.

Опять забыл, что после 4e9 резкое торможение и поиск займёт не 9, а 39 часов. Нет, пока не буду выше 1е10 считать.

Лучше пойду по 3-кам вплоть до 3-252, если получится.

[Dmitriy40]

3-108:

1e11: [0.008119, 0.046096, 0.121822, 0.199096, 0.225474, 0.187905, 0.119445, 0.059239, 0.023252, 0.007286, 0.001830, 0.000368, 0.000059, 0.000008, 0.000001, 0.000000, 0.000000, 0.000000, 0.000000, 0.000000, 0.000000, 0.000000], sum=2.220495147 e136984 / 4.458746157 e136987 * 1.000 e11 = 49800887
1e11: nn=[483498, 2465777, 5881636, 8712672, 8981902, 6857287, 4010524, 1845865, 677447, 200331, 47840, 9345, 1583, 234, 28, 7, 6, 1, 3, 1, 2, 2, 0, 0, 0, 1], sum=40175992, time: 1h, 5min, 12,647 ms

Кэф: $49800887/40175992=1.240$
Кортежи после 1e10 не сохранял.

[Yadryara]

Спасибо!

10^    Чистый     Общий    Кортежей (чистых, всех)

11      0.836     1.240      483498       40175992
10      0.799     1.219       37790        5433210
09      0.766     1.194        2577         761142
08                1.160         131         111186
07                1.120           3          17209
06                1.047                       2900

Рост общего кэфа с ростом диапазона очевидно тормозится, но рост чистого вроде как ускоряется. Хотя по чистому это может и флуктуации, которые могут влиять на тысячные доли кэфа и на тысячах штук. То бишь значение 0.766 всё же не сильно надёжное. И 1.047 для общего тоже.

Весьма неожиданно обнаружил очень точные схождения количеств общих кортежей:

Pat/10^      8         9         10

3- 60   222008   1519360   10858342
3-120   221676   1519133   10862854
3-180   222226   1518738   10862078
3-240   222109   1520378   10862626
3-300   221820   1518230   10859084

Думаю, многие заметили, что паттерны с диаметром кратным 60-ти, отличаются: их больше чем других для самых разных длин. Но чтобы такой эффект!

[Yadryara]

Я так понял, что это работает для всех паттернов, где все гэпы кратны 30-ти:

Pat/10^      8         9         10

5-120     5523     28917     162852
5-240     5538     28641     163187
5-360     5446     28495     163027

И относительная погрешность, которая и так крошечная, падает с ростом диапазона. То есть если мы знаем количество всех кортежей для 19-540, то мы знаем его и для 19-1080 и для всех 19-к с диаметром $540k$.

Может ли это помочь в текущих задачах, пока непонятно.

Да, 5-ки считал, поправив прогу Dmitriy40:

allocatemem(10^9);
{print();d=360;v=[0,d/4,d/2,3*d/4,d]; nn=vector(v[#v]); t0=getwalltime();
for(n=0,99, pp=primes([n*1e8,(n+1)*1e8+d]); b=1;for(ip=1,#pp, p=pp[ip];
while(b<=#pp && pp[b]-p<d, b++); if(b>#pp, break);
if(pp[b]-p!=d
|| !setsearch(pp[ip..b],p+d/2)
|| !setsearch(pp[ip..b],p+d/4)
|| !setsearch(pp[ip..b],p+3*d/4)
, next); nn[b-ip+1]++;
);
b=#nn; while(b>#v && nn[b]==0, b--);

print(n+1," e8: nn=",nn[#v..b],", sum= ",vecsum(nn),", time: ",strtime
(getwalltime()-t0));print(););
print();
}quit;

Я уже забыл как работает Сетсёч, но интуитивно сделал так.

[Dmitriy40]

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

Я уже забыл как работает Сетсёч, но интуитивно сделал так.

Сделали правильно. Хотя лучше бы было вместо d/x поставить v[2],v[3],v[4] - будет работать с произвольными паттернами длиной 5, не только кратными d/4. Я именно так и посчитал 5-120-5 выше.

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

То есть если мы знаем количество всех кортежей для 19-540, то мы знаем его и для 19-1080 и для всех 19-к с диаметром $540k$.

Не совсем так, для каждого диапазона есть максимальный интервал между простыми, а значит и сумма 18 соседних интервалов не уйдёт в бесконечность, а будет ограничена. Т.е. начиная с какого-то диаметра кортежей будет ровно 0, хотя формула будет давать ненулевое число. Например до $10^{19}$ максимальный интервал между простыми не превышает 1510, а значит диаметр 19-ки в этом диапазоне не более чем 1510*18=27180. Разумеется и он сильно не достигается (большие интервалы обычно не соседствуют друг с другом), но как оценка сверху годится.
Дальше $2^{64}$ точных данных вроде как нет, но можно пользоваться гипотезой Крамера, что интервал порядка $\ln^2(p)$. Т.е. в любом случае диаметр любого кортежа для любого диапазона ограничен сверху.

-- 04.07.2024, 18:58 --

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

[Yadryara]

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

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

Ну так я специально стараюсь писать о чём именно говорю:

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

То есть если мы знаем количество всех кортежей

А все это и чистые и грязные. Чистых, кстати, ровно 0 уже для 5-360 и тех диапазонов. Их количество очень сильно отличается для разных паттернов. А количество всех почему-то почти совпадает.

[Yadryara]

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

Рост общего кэфа с ростом диапазона очевидно тормозится

Это подтверждается и для 5-120-5:

10^    Чистый     Общий    Кортежей (чистых, всех)

11      0.962     1.414       10804         981282
10      0.953*    1.371         975         162852
09      0.872*    1.307          85          28917
08      0.616**   1.228           8           5523
07      0.236**   1.119           1           1184

Ненадёжные чистые кэфы комментировать не хочется.

Обновил схему. Болдом выделил значения на интересующей диагонали.

$\tikz[scale=.05]{ \node at (0,153){\text{25}}; \node at (0,144){\text{24}}; \node at (0,135){\text{23}}; \node at (0,126){\text{22}}; \node at (0,117){\text{21}}; \node at (0,108){\text{20}}; \node at (0,99){\text{19}}; \node at (0,90){\text{18}}; \node at (0,81){\text{17}}; \node at (0,72){\text{16}}; \node at (0,63){\text{15}}; \node at (0,54){\text{14}}; \node at (0,45){\text{13}}; \node at (0,36){\text{12}}; \node at (0,27){\text{11}}; \node at (0,18){\text{10}}; \node at (0,9){\text{9}}; \node at (23,0){\text{03-108}}; \node at (24,0){\text{}}; \node at (49,0){\text{05-120}}; \node at (48,0){\text{}}; \node at (74,0){\text{07-132}}; \node at (72,0){\text{}}; \node at (99,0){\text{09-144}}; \node at (96,0){\text{}}; \node at (124,0){\text{11-156}}; \node at (120,0){\text{}}; \node at (149,0){\text{13-168}}; \node at (144,0){\text{}}; \node at (174,0){\text{15-180}}; \node at (168,0){\text{}}; \node at (208,0){\text{17}}; \node at (192,0){\text{}}; \node at (233,0){\text{19}}; \node at (16,9){\text{77}}; \node at (28,9){\textbf{119}}; \node at (16,18){\text{80}}; \node at (28,18){\text{122}}; \node at (16,27){\text{84}}; \node at (28,27){\text{124}}; \node at (54,9){\text{131}}; \node at (54,18){\text{137}}; \node at (42,27){\text{96}}; \node at (54,27){\textbf{141}}; \node at (82,45){\textbf{?}}; \node at (95,54){\text{154}}; \node at (95,63){\text{156}}; \node at (110,63){\textbf{?}}; \node at (95,72){\text{161}}; \node at (120,72){\text{191}}; \node at (120,81){\text{198}}; \node at (135,81){\textbf{?}}; \node at (120,90){\text{204}}; \node at (147,99)[red]{\text{265}}; \node at (159,99){\textbf{312}}; \node at (171,117)[red]{\text{314}}; \node at (183,117)[red]{\textbf{?}}; \node at (183,108)[red]{\text{352}}; \node at (207,135)[red]{\textbf{?}}; \node at (231,153)[red]{\textbf{?}}; }$

[vicvolf]

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

Думаю, многие заметили, что паттерны с диаметром кратным 60-ти, отличаются: их больше чем других для самых разных длин. Но чтобы такой эффект!

Я уже писал Вам - Учите матчасть. А Вы мне - Мы сами с усами. В чем ценность этих, так называемых, исследований, если Вы не понимаете что происходит.

[Yadryara]

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

Я уже писал Вам - Учите матчасть.

И где же пруф?

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

А Вы мне - Мы сами с усами.

И где пруф?

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

В чем ценность этих, так называемых, исследований, если Вы не понимаете что происходит.

А Вы понимаете что происходит?

[Yadryara]

А вот сравнил кэфы для 3-60

10^    Чистый     Общий    Кортежей (чистых, всех)

11      
10      1.000     1.220      861693       10858342
09      0.971     1.196       84523        1519360
08      0.963     1.162        7514         222008
07                1.128         568          34189
06                1.053          34           5766
05                0.947           1           1087
04                                             223

с 3-108:

10^    Чистый     Общий    Кортежей (чистых, всех)

11      0.836     1.240      483498       40175992
10      0.799     1.219       37790        5433210
09      0.766     1.194        2577         761142
08                1.160         131         111186
07                1.120           3          17209
06                1.047                       2900

Общие почти совпадают, а по чистым опять рост роста...