кортежи последовательных простых. ключ к 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 и тех диапазонов. Их количество очень сильно отличается для разных паттернов. А количество всех почему-то почти совпадает.