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

[Yadryara]

А я ленюсь делать полноценное расщепление второго порядка.

Вот вроде бы единственное сравнение сразу по нескольким периодам:

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

Итого 2ч48м. Вместо 3ч44м. На треть быстрее.
Экономия памяти где-то на порядок (точнее не измерял).

А ведь можно было и не умножать на 2, а пройтись по всем паттернам, как это нужно будет делать для расщеплений последующих порядков.

Ну и нет сомнений, что около 5 с половиной часов получится.

[Dmitriy40]

Интересна зависимость размера второй таблицы (только для одного самого плохого элемента первой) от размера первой (без расщепления):
37#->71#: 60млн
41#->71#: 14млн
43#->71#: 3млн
47#->71#: 0.54млн
Ну и рост размера второй таблицы для наиболее удобного варианта 41#->:
41#->61#: 0.44млн
41#->67#: 2.9млн
41#->71#: 14млн
41#->73#: 44млн
41#->79#: 114млн
Всё ещё совсем непохоже на насыщение размера, что не позволяет отказаться от третьей таблицы и вложенного перебора.

[Yadryara]

Слева, видимо, значение pmid.

Я вот думаю, что надо подналечь на более короткие и узкие паттерны, может в процессе их обсчёта и сбора статистики ещё придут идеи ускорения. Вот закончу 1-й 11-156, а дальше вроде 2 раза подряд увеличение длины: не только 13-168, но и 15-180 ...

[Dmitriy40]

gris
Посчитал все 13-192 до 1.1e19. Нашёл одну пропущенную у Томаша:
3547548469412787251: 0 12 42 60 66 90 96 102 126 132 150 180 192
Её потом ещё НМ нашла.
И пропущенные (в недосчитанном куске) в SPT боинк проекте:
4958268923153051357: 0 12 42 60 66 90 96 102 126 132 150 180 192
5056116626025313091: 0 12 42 60 66 90 96 102 126 132 150 180 192
5064597206418405221: 0 12 42 60 66 90 96 102 126 132 150 180 192
5081754393702091957: 0 12 42 60 66 90 96 102 126 132 150 180 192
5154020923551309767: 0 12 42 60 66 90 96 102 126 132 150 180 192
Плюс совсем скоро там найдут и последнюю перед 1e19 (предыдущие уже нашли):
9995348564889375931: 0 12 42 60 66 90 96 102 126 132 150 180 192
Итого до 1e19 их будет 216шт.
После 1e16 нашёл следующие 23шт 13-192:
10013230717641471277: 0 12 42 60 66 90 96 102 126 132 150 180 192
10130392328070474157: 0 12 42 60 66 90 96 102 126 132 150 180 192
10153185061549088971: 0 12 42 60 66 90 96 102 126 132 150 180 192
10236355150921661327: 0 12 42 60 66 90 96 102 126 132 150 180 192
10246017460829141557: 0 12 42 60 66 90 96 102 126 132 150 180 192
10304613318488232701: 0 12 42 60 66 90 96 102 126 132 150 180 192
10326541662008009681: 0 12 42 60 66 90 96 102 126 132 150 180 192
10371425130288542017: 0 12 42 60 66 90 96 102 126 132 150 180 192
10383682450304082877: 0 12 42 60 66 90 96 102 126 132 150 180 192
10408168773472119061: 0 12 42 60 66 90 96 102 126 132 150 180 192
10499493692947708861: 0 12 42 60 66 90 96 102 126 132 150 180 192
10540143033014354611: 0 12 42 60 66 90 96 102 126 132 150 180 192
10560397483948992091: 0 12 42 60 66 90 96 102 126 132 150 180 192
10567963099523203771: 0 12 42 60 66 90 96 102 126 132 150 180 192
10607521634695145011: 0 12 42 60 66 90 96 102 126 132 150 180 192
10716366929681877161: 0 12 42 60 66 90 96 102 126 132 150 180 192
10717708445691097247: 0 12 42 60 66 90 96 102 126 132 150 180 192
10723236960793555441: 0 12 42 60 66 90 96 102 126 132 150 180 192
10732242437627290537: 0 12 42 60 66 90 96 102 126 132 150 180 192
10861110627532434967: 0 12 42 60 66 90 96 102 126 132 150 180 192
10960719362282020897: 0 12 42 60 66 90 96 102 126 132 150 180 192
10962757032949087217: 0 12 42 60 66 90 96 102 126 132 150 180 192
10965448136607379981: 0 12 42 60 66 90 96 102 126 132 150 180 192
До 15-228 расширяются только две уже известные:
2079914861571286679: 0 18 30 60 78 84 108 114 120 144 150 168 198 210 228
3665619319531504883: 0 18 30 60 78 84 108 114 120 144 150 168 198 210 228

[Yadryara]

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

Посчитал все 13-192 до 1.1e19.

Почему бы уж тогда не посчитать все 13-168 до 1e19. Их количество ведь потенциально можно сравнить и посчитать кэф превышения.

Или центральные 13-ки имеют самостоятельную ценность? Ну, может быть. Но тогда и 13-168 имеют самостоятельную ценность, да и другие цепочки тоже.

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

Скоро (не обязательно на следующем простом, может и через одно-два) видимо придётся увеличивать pmid чтобы уменьшить второй размер.

Не пришлось. Второй размер — 1.9 млн для 71#. Счёт длился 31 час. g2[] уже нулевой.

(11-156-1-71#)

11     [0, 6, 30, 36, 66, 78, 90, 120, 126, 150, 156]


cg  o = 1 --> 71#: [5397242, 1444137442, 122592880532, 4924450701438, 1117072869
11238, 1579406489257020, 14782616387894048, 95122817579577582, 43090166566976584
0, 1393871571674830322, 3244127925542407278, 5445557844514820376, 65809342683053
95830, 5697450212287280000, 3510471835719480356, 1531752226101696968, 4746465843
35652158, 106310039876375860, 17664135862043230, 2159892797232040, 1756570460232
00, 7139543040000], sum=28547632595512800000, #ww[]=862+1903560, time : 15h, 27m
in, 6,127 ms

cg  o = 2 --> 71#: [314235140, 43197876390, 2067687268402, 49657179022168, 71068
2775634550, 6710368219456656, 44523310051790212, 215705971570426020, 78010385859
6537942, 2128846508773713126, 4394847654845146276, 6840246052548775896, 79679043
39590081444, 6880236220977675756, 4357967099852065774, 2004319320790037980, 6639
30562679695056, 157618170671700664, 26667958166453024, 3141704262018464, 2374570
63125060, 8691508224000], sum=36473777701320960000, #ww[]=997+1926622, time : 31
h, 38min, 23,915 ms


24  cg = [0, 319632382, 44642013832, 2190280148934, 54581629723606, 822390062545
788, 8289774708713676, 59305926439684260, 310828789150003602, 121100552426630378
2, 3522718080448543448, 7638975580387553554, 12285803897063596272, 1454883860789
5477274, 12577686433264955756, 7868438935571546130, 3536071546891734948, 1138577
147015347214, 263928210548076524, 44332094028496254, 5301597059250504, 413114109
148260, 15831051264000, 0]    65021410296833760000

time: 31h, 38min, 24,095 ms



2  do = [2, 4]

g2  o = 1 --> 71#: [0], sum=0, #ww[]=0+0, time : 13 ms

g2  o = 2 --> 71#: [0], sum=0, #ww[]=0+0, time : 17 ms


25  g2 = [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0
, 0]    0

time: 22 ms


vc  -->  71# : [8615676236, 1219507630880, 64188686107016, 1758252393107966, 291
93400227501994, 321246902459508228, 2480373791675579850, 13941455780369712060, 5
8342157668863403964, 183919196668057248918, 438350747504636460128, 7882689763384
39220936, 1063261933667299106358, 1066734787397413923222, 787956344439019242204,
 423879413603993325660, 164475574778029719768, 45821499624722434408, 92073629553
32355018, 1348958939318951802, 142794108869125784, 10022021770881600, 3461083637
76000, 0]      5048494209368064000000


time: 31h, 38min, 24,141 ms

После отдыха запущен новый счёт уже до финальной предокейной 73#. Надеюсь, продлится не более 3-х суток.

[Dmitriy40]

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

Почему бы уж тогда не посчитать все 13-168 до 1e19.

А чем не устраивает выборка таких цепочек из боинка? Они практически до 1e19 уже досчитали. И цепочек таких там 219шт (всего, с нуля). Ну да, может штук 5-8 пропущено, но это всего 5% погрешности кэфа.

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

Или центральные 13-ки имеют самостоятельную ценность?

Да - из них образуются 15-228, 17-240 и искомая 19-252. К тому же именно про них задавали выше вопрос про аппроксимацию.
Но вообще мне просто было интересно есть ли пропущенные цепочки, и в недосчитанных интервалах, и в просчитанных, и 4 дня счёта (в 4 потока) приемлемая цена за вопрос. Оказалось во вторых нету, это хорошо, повышает доверие к результатам. Но хорошо, запустил и 13-168 просчитаться, на них 2 дня хватит.

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

для 71#. Счёт длился 31 час.

О как, а моя программа на асме в 4 потока собралась считать 61# аж неделю! Про 71# и 73# вообще молчу. Что значит замена вложенного перебора (31#->61#) на линейный (pmid#->71#). И расщепление тоже явно сильно помогло.

[Yadryara]

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

А чем не устраивает выборка таких цепочек из боинка?

Психологически некомфортно из-за потенциальных пропусков. Хоть их и немного.

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

Но хорошо, запустил и 13-168 просчитаться, на них 2 дня хватит.

Надеюсь только в промежутках считаете. Раз есть доверие к боинкам.

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

Да - из них образуются 15-228, 17-240 и искомая 19-252. К тому же именно про них задавали выше вопрос про аппроксимацию.

Ну вот и у меня вопрос к gris. 19-252 здесь всё равно не найдётся.

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

И расщепление тоже явно сильно помогло.

Первого порядка конечно помогает. Но неужели расщепление второго порядка поможет в плане скорости?

[Yadryara]

Кстати, насчёт аппроксимации. Раз простые числа являются строительными кирпичиками кортежей, то и в формуле надо использовать либо интегральный логарифм, либо другие способы вычисления $\pi(x)$. Ну и книжку Дербишира никто не отменял.

[Dmitriy40]

Насколько я понял о таких сложных материях как распределение простых чисел никто и не заморачивался, пытались строить аппроксимацию от фонаря, просто таблицы чисел, без учёта их природы. Я выше тоже.

В интервале 1.1-1.2e19 есть ещё 17шт 13-192. До 15-228 не расширяются.

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

Надеюсь только в промежутках считаете. Раз есть доверие к боинкам.

Разумеется нет, полностью. 2 дня не сильно жалко. А на только пропуски хватило бы пары часов.

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

Но неужели расщепление второго порядка поможет в плане скорости?

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

[Yadryara]

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

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

Довольно странно. Ведь мы учитывали распределение простых чисел много когда. Например, когда речь шла о 12 делителях. Ну а тут-то куда от простых деваться если из них и строим. Например, самый популярный гэп из подходящих долгое время равен 6, а потом на первое место выходит не 12 и не 18, а 24.

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

Разумеется нет, полностью.

Интересно... То есть Вы считаете, что перепроверить всё же не помешает. Иначе какой смысл 2 дня вместо двух часов.

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

вон у Вас вообще всего два паттерна для 71# считались как я понял

Да, правильно понято.

Эх, сейчас немного некогда...

[Dmitriy40]

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

Интересно... То есть Вы считаете, что перепроверить всё же не помешает.

Ну да.
Во первых не вполне понятно где точно нижняя граница недосчитанного интервала, например между предпоследней и последней цепочкой 13-168 перед разрывом нашёл ещё одну:
4830075992994769333: 0 18 24 48 60 78 84 90 108 120 144 150 168 - была
4874789823823097579: 0 18 24 48 60 78 84 90 108 120 144 150 168 - новая
4890492034527070403: 0 18 24 48 60 78 84 90 108 120 144 150 168 - была
Во вторых не факт что пропущенный интервал у Томаша 3.53-3.56e18 НМ&Ко досчитала корректно (полные данные она не выкладывала так что проверить невозможно, только верить на слово).
В третьих в обоих проектах есть ошибочные цепочки, значит теоретически могут быть и пропущенные (у Томаша все ошибочные я пересчитал сам, ничего интересного не обнаружил, но попадает ли 13-168 в разряд интересного не помню, в SPT они будут когда-то пересчитаны самим проектом, но неизвестно когда).
Так что проще задать полный диапазон, запустить и пусть само считает, чем разбираться где точно что пропущено. 2 дня не столь много, не жалко.

[Dmitriy40]

Зато во всём недосчитанном интервале 4.89e18-5.248e18 нашлась всего одна новая цепочка 13-168:
5110045405206766183: 0 18 24 48 60 78 84 90 108 120 144 150 168
А я то думал их там штук 7 могло быть ...

[Yadryara]

Флуктуации. И у меня тоже: то 28 часов, то всего лишь 5. Если желаете можете добавить в Ваш файл. Сверка с другим способом подсчёта была только до 43# включительно.

(11-156-1)

11     [0, 6, 30, 36, 66, 78, 90, 120, 126, 150, 156]


cg  o = 1 --> 73#: [35101303862, 4414188471544, 204157705869568, 488521714645662
6, 70651073333495156, 676015539480280036, 4530290136340202878, 22028954658410771
424, 79268421106145707764, 212793792336382713454, 426260123918398530842, 6341856
76791568579484, 695331325905782305512, 556277933301315827882, 321198241723461304
614, 132553899146922252914, 38918799831162003442, 8175239185576544036, 124524046
7793283578, 136530717594944344, 9857355098495040, 346108363776000], sum=31336664
33127273120000, #ww[]=1580+2027335, time : 28h, 27min, 31,924 ms

cg  o = 2 --> 73#: [42346860, 12649974404, 1205316486876, 53065169154780, 128405
5958618062, 18933543577291840, 181982277612147430, 1193151907955524558, 54994280
88814085774, 18157365979117805590, 43382681105991045238, 75283862747093711622, 9
4785285749518807668, 86209880807573654130, 56296138410088480788, 262176381919663
72792, 8647073204172826748, 1998960278215560540, 316932799877361660, 33114847941
068240, 2111166545498400, 60526642176000], sum=418225939971840000000, #ww[]=189+
2043840, time : 33h, 59min, 32,298 ms


24  cg = [0, 35143650722, 4426838445948, 205363022356444, 4938282315611406, 7193
5129292113218, 694949083057571876, 4712272413952350308, 23222106566366295982, 84
767849194959793538, 230951158315500519044, 469642805024389576080, 70946953953866
2291106, 790116611655301113180, 642487814108889482012, 377494380133549785402, 15
8771537338888625706, 47565873035334830190, 10174199463792104576, 156217326767064
5238, 169645565536012584, 11968521643993440, 406635005952000, 0]    355189237309
9113120000

time: 33h, 59min, 32,342 ms




1  do = [2]

g2  o = 1 --> 73#: [0], sum=0, #ww[]=0+0, time : 15 ms


25  g2 = [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0
, 0]    0

time: 17 ms


vc  -->  73# : [1718535906790, 198375642902486, 8925142161834362, 21577757281012
3008, 3232454878516154980, 32570302236479989438, 232473799465525677588, 12150074
95118827449338, 4744203541502545556762, 13985041589332858068428, 312265059632550
38299916, 52721034262753716829006, 66950001847414697497712, 63449022202165963259
902, 44445089171108163207302, 22772664478630822982004, 8456047597713202289780, 2
265091689880034664298, 439366216077805164368, 62253644270232075820, 636549207358
3815672, 430079163247259040, 14250969556992000, 0]      313006640980819968000000



time: 33h, 59min, 32,365 ms

[Yadryara]

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

Сверка с другим способом подсчёта была только до 43# включительно.

Проверил кэф превышения и долю чистых:

1. [0, 6, 30, 36, 66, 78, 90, 120, 126, 150, 156]

1     E14      1.494     2.5 %        8

1     E15      1.637     3.3 %       45

1     E16      1.780     4.1 %      258

1     E17      1.949     5.1 %     1487

1     E18      2.028     6.1 %     9132

2.148 E18      2.050     6.5 %    16769

Сводная таблица:

Паттерн      От 0 до   Kпревыш.   Чистых    Кортежей  Обсч/Пат

   9- 84    1     E16    1.894    25.3 %      81588      1/  1
   9- 96    1     E16    1.826    17.5 %      87501      1/  1
   9-108    1     E16    1.788    12.8 %      87326      1/  1
   9-120    1     E16    1.735     9.0 %     442966      7/  7
   9-132    1     E16    1.675     5.9 %     488223      8/  8
  11-132    1     E16    1.961     8.2 %        962      2/  2
  11-144    1     E16    1.970     5.7 %       1571      4/  4
  11-156    1     E16    1.780     4.1 %        258      1/  5

  11-132    2.148 E18    2.166    11.6 %      59143      2/  2
  11-144    2.148 E18    2.106     8.5 %     104962      4/  4
  11-156    2.148 E18    2.050     6.5 %      16769      1/  5

Похоже на правду. Программа:

(PARI)

{print();

k = 14;

f = [ 0, 0, 0,   0, 0, 0,   0, 0, 0,   0, 0,

     1,  0,  8, 45, 258, 1487,  9132, 16769];

\\  12  13  14  15   16    17     18    end


mor=[ 0, 0, 0,   0, 0, 0,   0, 0, 0,   0, 0,
 
1.4705552760839308761649229845696490594 E433636,
1.7536647295156189735811651573073679657 E1372340,
1.6725476714034538506990478976102144813 E4340851,
4.0129671196962765407337488720246638814 E13731288,
2.5401483842215342462788890842604146196 E43424119,
2.0482350313774922452835522308588480309 E137328734,
2.9557521529413355924858770497467279652 E134281009,
6.1501327818293311097988392787319372235 E136486324 ];

\\print(mor);


vc=[1718535906790, 198375642902486, 8925142161834362, 21577757281012
3008, 3232454878516154980, 32570302236479989438, 232473799465525677588, 12150074
95118827449338, 4744203541502545556762, 13985041589332858068428, 312265059632550
38299916, 52721034262753716829006, 66950001847414697497712, 63449022202165963259
902, 44445089171108163207302, 22772664478630822982004, 8456047597713202289780, 2
265091689880034664298, 439366216077805164368, 62253644270232075820, 636549207358
3815672, 430079163247259040, 14250969556992000];
 \\ 73# , sum=

cm=11; c=vc*1.0; 


forprime(p=73+1,sqrt(2.148e18),


 while(p^2>10^k,

print(k,"      ",c[1]*10^k/mor[k]/f[k],"      ",round(c[1]/vecsum(c)*10^3));

print();
print();

 k++);

\\mor

if(c[1]>1e160000000,

kpon++;
print();
print(kpon);
print();

for(i=1,#c, c[i]=c[i]/(1e160000000);

print(c[i]);

);
print();
);

 for(i=1,#c-1, c[i]=c[i]*(p-i-cm+1)+c[i+1]*i);

 c[#c]*=p-#c-cm+1);


print();
print(k,"      ",c[1]*2.148e18/mor[k]/f[k],"      ",round(c[1]/vecsum(c)*10^3));

print();

}quit;

А вот так я выцеплял нужные количества цепочек из Базы 11-к:

(PARI)

{print();

x=fileopen("spt11.txt","r");

v=[0, 6, 30, 36, 66, 78, 90, 120, 126, 150, 156];

f=vector(19);
y=vector(12);
t=vector(12);
sto=1;


for(i=1, 9042039,



ksov=0;

s=filereadstr(x);

for(j=1,12,y[j]=strsplit(s," ")[j];

if(j>=2,t[j]=eval(y[j]);

if(t[j]==v[j-1],ksov++)));



z=eval(strsplit(y[1],":"));

\\print(z[1], "   ",y[1]);



if(ksov==11, k11++;


for(st=sto,18,
if(z[1]<10^st,f[st]++;

if(st>sto,f[st]=f[st]+f[sto];sto=st;

if(f[st]==1,k=st);

print(k11, "   ",f);print();
);

next(2)));


);
);

print();print();
print(k, "   ",k11, "   ",f);print();

print();
print();


}quit;

[Dmitriy40]

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

А вот так я выцеплял нужные количества цепочек из Базы 11-к:

Зачем такие сложности? Так проще:

x=fileopen("spt11.txt","r");
v=[0, 6, 30, 36, 66, 78, 90, 120, 126, 150, 156];
vv=concat(" ",strjoin(v," ")); k11=0; f=vector(20);\\Готовим строку для сравнения
{while(s=filereadstr(x),
ss=strsplit(s,":"); if(#ss!=2 || ss[2]!=vv, next);\\Делим строку на части и пропускаем всё что не цепочка
k11++; z=eval(ss[1]); sto=0; while(z>10^sto, sto++); f[sto]++;\\Десятичный логарифм начального числа
);}
fileclose(x); for(z=2,#f, f[z]+=f[z-1]); print(f,", all=",k11);\\Меньшие цепочки добавляем к большим
quit;