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

[Yadryara]

Благодарю!

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

Повезло что у 48-48 тоже c5>0 уже при 37#, потому для него досчитал и 41# за 40 минут.

Это отлично. Значит уже два паттерна из серии 6k-6k сходятся на шаг раньше.

42-42                                                           ... 19  20  21

23#                                263  67   8  -9 -11  -2  14  33  53 101 200

29#                        172  46  18   4  -2  -3  -2   2   6  11  14  16  25

31#               3508 131  25   4  -2  -3  -3  -1   1   3   6   9  11  14  20

37#           222   32   4  -1  -2  -3  -2  -1   0   1   2   3   4   5   5   6

41#      -10   -8   -6  -5  -4  -3  -2  -1  -1   0   1   2   3   3   4   4   5



48-48                                                              ... 21  22  23

29#                      2742 366  94  31   4  -6  -6  -2   4  11  18  25  34  50

31#              1296 704 206  78  28   7  -2  -4  -2   0   4   8  13  18  23  29

37#       153 226 141  63  27  11   3   0  -1  -1   0   1   2   4   6   8   9  10

41#     1   2   2   3   3   2   0   0  -1  -1  -1   0   1   2   3   4   4   5   6

На очереди серия паттернов длины 5: 6k-6k-6k-6k.

Знаю, что при $k=1$ решений нет. Остальные вроде допустимы.

[Yadryara]

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

На очереди серия паттернов длины 5: 6k-6k-6k-6k.

Знаю, что при $k=1$ решений нет. Остальные вроде допустимы.

Не-а. Только при $k=5$ допустим паттерн диаметром 120, который я полностью обсчитать не могу.

Dmitriy40, Вы вроде бы давно в теме. Есть ли какой-то полный список симметричных паттернов нечётной длины, диаметром скажем до 100?

[Yadryara]

Обсчитал ещё один паттерн:

6-12-12-6  d = 36       5 ...  10    11

13#                 -11   -2   40   100   

17#             -8   -1    1    9    17

19#          0   0    0    0    0     0

23#      0   0   0    0    0    0     0

В принципе тенденция мне ясна. Самый показательный пока паттерн 42-42, в котором 18 лишних простых. В паттерне 19-252 30 лишних простых и его предпоследняя строка, видимо, гораздо более регулярна. Но одно дело спрогнозировать строку с погрешностью не более 1% и совсем другое — точно.

[Dmitriy40]

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

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

На очереди серия паттернов длины 5: 6k-6k-6k-6k.
Знаю, что при $k=1$ решений нет. Остальные вроде допустимы.

Не-а. Только при $k=5$ допустим паттерн диаметром 120,

Любые $k=5n$.

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

Dmitriy40, Вы вроде бы давно в теме. Есть ли какой-то полный список симметричных паттернов нечётной длины, диаметром скажем до 100?

Когда-то считал, сейчас поищу, может они даже в теме выкладывались.
Вот что нашёл для диаметра до 100:

n=3, max= 12, x: 0 6 12
n=3, max= 24, x: 0 12 24
n=3, max= 36, x: 0 18 36
n=3, max= 48, x: 0 24 48
n=3, max= 60, x: 0 30 60
n=3, max= 72, x: 0 36 72
n=3, max= 84, x: 0 42 84
n=3, max= 96, x: 0 48 96
n=5, max= 36, x: 0 6 18 30 36
n=5, max= 48, x: 0 18 24 30 48
n=5, max= 60, x: 0 12 30 48 60
n=5, max= 60, x: 0 18 30 42 60
n=5, max= 60, x: 0 24 30 36 60
n=5, max= 60, x: 0 6 30 54 60
n=5, max= 72, x: 0 12 36 60 72
n=5, max= 72, x: 0 30 36 42 72
n=5, max= 72, x: 0 6 36 66 72
n=5, max= 84, x: 0 12 42 72 84
n=5, max= 84, x: 0 24 42 60 84
n=5, max= 84, x: 0 30 42 54 84
n=5, max= 96, x: 0 18 48 78 96
n=5, max= 96, x: 0 30 48 66 96
n=5, max= 96, x: 0 36 48 60 96
n=5, max= 96, x: 0 6 48 90 96
n=7, max= 60, x: 0 12 18 30 42 48 60
n=7, max= 72, x: 0 12 30 36 42 60 72
n=7, max= 72, x: 0 6 30 36 42 66 72
n=7, max= 84, x: 0 12 24 42 60 72 84
n=7, max= 84, x: 0 12 30 42 54 72 84
n=7, max= 84, x: 0 24 30 42 54 60 84
n=7, max= 96, x: 0 18 36 48 60 78 96
n=7, max= 96, x: 0 6 18 48 78 90 96
n=7, max= 96, x: 0 6 30 48 66 90 96
n=7, max= 96, x: 0 6 36 48 60 90 96
n=9, max= 84, x: 0 12 24 30 42 54 60 72 84
n=9, max= 96, x: 0 6 18 36 48 60 78 90 96

Более длинные имеют диаметр больше 100.
Программа у меня 2015г на паскале.

В принципе несложно программку на PARI написать по генерации таких паттернов: начинаем от центра и расставляем числа с шагом 6 симметрично, проверяем по остаткам. Вот, буквально на коленке:

? for(a=1,8, vv=[-a,0,a]*6; forprime(p=5,13, if(#setminus(vector(p,i,i-1), Set(vv%p))==0, next(2))); print(vv); );
[-6, 0, 6]
[-12, 0, 12]
[-18, 0, 18]
[-24, 0, 24]
[-30, 0, 30]
[-36, 0, 36]
[-42, 0, 42]
[-48, 0, 48]
? for(a=1,8, for(b=a+1,8, vv=[-b,-a,0,a,b]*6; forprime(p=5,13, if(#setminus(vector(p,i,i-1), Set(vv%p))==0, next(2))); print(vv); ));
[-24, -6, 0, 6, 24]
[-30, -6, 0, 6, 30]
[-36, -6, 0, 6, 36]
[-18, -12, 0, 12, 18]
[-30, -12, 0, 12, 30]
[-42, -12, 0, 12, 42]
[-48, -12, 0, 12, 48]
[-30, -18, 0, 18, 30]
[-42, -18, 0, 18, 42]
[-48, -18, 0, 18, 48]
[-30, -24, 0, 24, 30]
[-36, -24, 0, 24, 36]
[-36, -30, 0, 30, 36]
[-42, -30, 0, 30, 42]
[-48, -30, 0, 30, 48]
[-48, -42, 0, 42, 48]
? for(a=1,8, for(b=a+1,8, for(c=b+1,8, vv=[-c,-b,-a,0,a,b,c]*6; forprime(p=5,13, if(#setminus(vector(p,i,i-1), Set(vv%p))==0, next(2))); print(vv); )));
[-36, -24, -6, 0, 6, 24, 36]
[-36, -30, -6, 0, 6, 30, 36]
[-30, -18, -12, 0, 12, 18, 30]
[-42, -18, -12, 0, 12, 18, 42]
[-42, -30, -12, 0, 12, 30, 42]
[-48, -30, -12, 0, 12, 30, 48]
[-48, -42, -12, 0, 12, 42, 48]
[-42, -30, -18, 0, 18, 30, 42]
[-48, -42, -18, 0, 18, 42, 48]
[-48, -42, -30, 0, 30, 42, 48]
? for(a=1,8, for(b=a+1,8, for(c=b+1,8, for(d=c+1,8, vv=[-d,-c,-b,-a,0,a,b,c,d]*6; forprime(p=5,13, if(#setminus(vector(p,i,i-1), Set(vv%p))==0, next(2))); print(vv); ))));
[-42, -30, -18, -12, 0, 12, 18, 30, 42]
[-48, -42, -30, -12, 0, 12, 30, 42, 48]

И так далее. Простые проверять надо лишь до длины паттерна, не диаметра (впрочем можно и до диаметра, тут же всё быстро).
Если хочется паттерн в обычном виде, то печатаем не vv, а vv+vector(#vv,i,-vv[1]).

-- 22.03.2024, 14:51 --

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

допустим паттерн диаметром 120, который я полностью обсчитать не могу.

Да и я не особо: 41# считалось 12м и выдало c8>0, на 43# с c7>0 хватит 8ч, но 2 недели считать 47# для c6>0 влом (надо делать прогу нормальной многопоточной).

Используется синтаксис Text

v=[0, 30, 60, 90, 120]
13#: 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 6, 50, 144, 262, 214, 88, 4, sum=768
17#: 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 2, 22, 276, 978, 2148, 2782, 2076, 846, 86, sum=9216
19#: 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 4, 64, 958, 4962, 14786, 29056, 36452, 28302, 11908, 2396, 136, sum=129024
23#: 0, 0, 0, 0, 0, 0, 0, 0, 0, 4, 100, 1800, 16526, 80342, 238372, 470972, 618364, 529124, 276392, 79420, 10602, 414, sum=2322432
29#: 0, 0, 0, 0, 0, 0, 0, 0, 110, 2166, 29932, 246060, 1247402, 4070456, 8945984, 13474964, 13763816, 9206072, 3784366, 869042, 94686, 3312, sum=55738368
31#: 0, 0, 0, 0, 0, 0, 46, 1748, 33704, 433656, 3597134, 19515776, 70640798, 175188168, 301943884, 361135616, 294634754, 158294842, 52826640, 10004632, 918456, 27714, sum=1449197568
37#: 0, 0, 0, 0, 2, 398, 18308, 392410, 5374430, 49034754, 300196598, 1252435066, 3626357174, 7393713608, 10667157110, 10815179168, 7552745040, 3504625158, 1021231936, 171277008, 14185874,398134, sum=46374322176
41#: 0, 0, 0, 70, 5330, 185802, 4092850, 61008728, 625536908, 4410577570, 21557766242, 73989799298, 180492978482, 315241586114, 394058526358, 349112610308, 214656147160, 88415263012, 23079368484, 3499140014, 264143994, 6861612, sum=1669475598336

-- 22.03.2024, 14:57 --

Кстати условие #setminus(vector(p,i,i-1), Set(vv%p))==0 эквивалентно условию #Set(vv%p)==p (длина списка запрещённых остатков равна самому простому, т.е. разрешённых не остаётся), что существенно проще.

[Yadryara]

Благодарю. И почти половина этих паттернов уже обсчитана.

Взял паузу на обдумывание.

[gris]

Dmitriy40, очень интересные конструкции на ПАРИ. Ну и результаты, конечно. Yadryara, ваши исследования тоже интересны.
Я читаю, но, к сожалению, нет спокойного времени для более вдумчивого изучения. Весна-с! Надеюсь, не обострение

[Dmitriy40]

Yadryara
7.7ч считалось:

43#: 0, 0, 234, 25244, 1192850, 32816370, 584943578, 7063918814, 58764050828, 340853753918, 1396845829202, 4094380257838, 8660256010148, 13264690909920, 14663711206226, 11566293072314, 6371496516642, 2367993120760, 562849557524, 78588340826, 5531494440, 135719092, sum=63440072736768

[Yadryara]

Спасибо.

Я ещё не упомянул об этом вопросе. По причине его очевидности.

А для тех паттернов, которые уже обсчитаны и есть точные формулы, реально ли посчитать оценку для нужной высоты? Например, для центральных 5-к (24-6-6-24):

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

Степень 10-ки, Средняя ожидаемая частотность, Факт.

   3       0.000002         0
   4       0.006443         0
   5       0.217638         1
   6       2.790            3
   7      26.604           27
   8     223.537          197
   9    1781.532         1501
  10   13853.840        11535

В этом примере посчитано до $10^{10}$, но надо-то до $10^{25}$.

Да, я помню, что Dmitriy40 при подсчёте общего количества довольно быстро (за часы) дошёл до $5 \cdot 10^{25}$, но тогда расчёт был проще.

[Yadryara]

Вот сводная статистика по всем SPT3, для которых удалось добраться до точных формул. Как раз все диаметры до 100:

   Len    Pattern  Zagr  St-St   c3    c4        c5

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

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

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

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

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

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

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

8.   3    0 48 96    20    41#    0    32      2244

Стартовые Строки полностью:

(2.)

0 2 20 48 58

(3.)

0 10 264 1978 5998 6484 2574 556 56

(4.)

0, 72, 4332, 69716, 443326, 1297482, 1884968, 1412596, 533592, 84928, 3388

(5.)

0, 38, 2598, 82832, 1177908, 8487904, 33786472, 75277014, 93091582, 61986798, 20841306, 3234106, 215762, 4480

(6.)

0, 0, 260, 17878, 487640, 6641892, 50493968, 229799540, 644261040, 1110622436, 1153892762, 698314552, 235091702, 41448078, 3469356, 102096

(7.)

0, 922, 173122, 10114884, 264451498, 3690470360, 30525389506, 159502826194, 546738842952, 1254433960054, 1939829127142, 2010825208458, 1370908155696, 593640303464, 155014292414, 22997963896, 1954975470, 118152928, 4112640

(8.)

0, 32, 2244, 83302, 2773756, 62621704, 882704766, 7953709458, 47306902950, 190299946364, 525224314390, 1000940896542, 1316531453644, 1188026343384, 727593074588, 296905718420, 78125698774, 12570810480, 1154941526, 55767040, 1251036

[Dmitriy40]

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

Да, я помню, что Dmitriy40 при подсчёте общего количества довольно быстро (за часы) дошёл до $5 \cdot 10^{25}$, но тогда расчёт был проще.

Считать надо простые до корня из конца диапазона, в окрестности 1e12 простые генерятся со скоростью 1.5c/1е9 (не простых, а интервал), значит до $\sqrt{5\cdot10^{25}}=7\cdot10^{12}$ хватало порядка 3ч. Тут вычисления сложнее, не одно произведение и деление, а 10 произведений и сумма, но тогда вычисления занимали 3% общего времени, теперь займут пусть даже 30% (реально сильно меньше, ведь не нужно медленных делений), это менее 35% потеря скорости, т.е. хватит часов четырёх.

Правда числа быстро (уже для p>750) уйдут за верхнюю представимую границу (порядка 1e308) и что с этим делать? Нормировать? Не получится ли что какое-то значение будет более чем в 1e308 раз меньше sum или максимального (меньшее тогда просто обнулится)?

Чего-то я туплю, не соображу по каким формулам считать, по таким $c_i = c_i (p-i) + c_{i+1}(i-c_{\min}+1), i=c_{\min} \ldots c_{\max}, c_{\min}=\#v, c_{\max+1}=0$ отсюда?

Так, отвечать не надо, это мысли вслух, сам разобрался: формулы те, а что делать с переполнением сейчас додумаю, может реально оно и не возникнет.

[Yadryara]

Да, формулы те самые. $C_{max}$ можно и без сложения считать.

Я, когда считал на Пари, понижал разрядность и сильно, в разы увеличивалась скорость:

if(o2>10^80,o1=round(o1/10^50);o2=round(o2/10^50);w=round(w/10^50));

То есть преодолели числа 80-й порядок, я их все на 50 порядков уменьшил. И так раз за разом. Сверял точность с другим способом и отличий ни в одном из 30 знаков не выявил ни разу.

[Dmitriy40]

Хм, а ведь для больших p (сильно больше длины vc[]) вторым слагаемым в формуле можно и пренебречь, а соответственно и вообще всеми vc[i>cmin] ...
Предлагаю забить на сверхточность и считать точные значения лишь до p<1e6, а дальше считать одно лишь vc[cmin], ведь нас интересует только оно.
Смотрите, вот для паттерна v=[0, 24, 30, 36, 60] точное значение c5 и sum для p<1e6:
1.2140432734322464270909307008420340923 E433630, sum=6.6054269119312780736477092929711935511 E433630
А вот какие они будут если точно считать лишь до p<1e3, а дальше до p<1e6 лишь одно c5 (полная сумма):
1.3121098168949540529022145578406222823 E433629, sum=1.3121098168949540529022145578406222823 E433629
А вот оно же, но после 1e3 c5 считается только первое слагаемое (т.е. просто умножаем и всё):
1.3051568768301136170328884747230664597 E433629, sum=1.3051568768301136170328884747230664597 E433629
В последнем случае вообще считаю разницу несущественной, а во втором разница всего один порядок, при том что сами числа имеют порядок аж 433630, т.е. предлагаю тоже считать равными.
И тогда достаточно знать произведение (p-cmin) для простых от 1e6 и выше и точное значение vc[cmin] для p<1e6, которое легко посчитать на PARI, это секунды.
А произведения (p-cmin) зависят только от величины cmin, которая равна #v, т.е. длине паттерна и больше ни от чего не зависит, т.е. для каждой длины паттерна можно посчитать один раз и всё.
Т.е. для любого паттерна достаточно быстро на PARI посчитать точное значение vc[cmin] для p<1e6, а потом просто домножить на известное число (которое посчитать один раз и навсегда).
Точность выходит несколько порядков, но для порядков из триллионов (для p>2e12) предлагаю считать приемлемой.
Произведения (p-cmin) для cmin=3..19 ровно так же мало отличаются друг от друга (для p>>19), например для 1e6<p<1e8 отличия для cmin 3 и 19 отличие всего два порядка из 42990480. Т.е. и их точно считать нет нужды, достаточно одного любого cmin. Вот например произведения для cmin=3 и cmin=19 для 1e6<p<1e9:
1e7: 7.163000208 E3907214, 6.083393033 E3907213
1e8: 7.287975726 E42990482, 7.308441806 E42990480
1e9: 5.956094710 E433847372, 9.073122459 E433847369
Не сказал бы что отличия так уж велики, три порядка из 433млн.
Так что пожалуй достаточно насчитать лишь произведения (p-19) как наиболее интересные, а остальные считать достаточно близкими к ним.
А праймориал (который sum) растёт как exp(x), а все остальные значения vc[] от него отличаются не сильно, значит даже и произведения считать не сильно надо, достаточно поделить праймориал 1e9 на праймориал 1e6, или exp(1e9-1e6)=2.638448222e433860187, что с неплохой степенью точности равно 9.073122459e433847369 для cmin=19 для 1e6<p<1e9, для грубой оценки вполне сгодится, зато вообще ничего вычислять не нужно, лишь экспоненту один раз.
Ну или можно считать на PARI точные значения vc[] до p<1e9, это минуты, а дальше домножать на нужную экспоненту (погрешность которой будет ещё меньше) и всё.
Как Вам такая идея упрощения расчётов?

[Yadryara]

Совершенно я не против таких экспериментов, если это сильно не вредит точности. Не во всё вник, но о том, что интересуют именно чистые, то бишь $c_{min}$ я сразу сказал. Мне интересно, будет ли частотность и дальше обгонять факт и насколько сильно. Для 10-го порядка было на 20%.

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

домножить на известное число (которое посчитать один раз и навсегда).

Конечно.

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

произведение (p-cmin) для простых от 1e6 и выше и точное значение vc[cmin] для p<1e6, которое легко посчитать на PARI, это секунды.
А произведения (p-cmin)

Это не произведения, это разности. Я так подозреваю, что имели в виду сомножители $(p-c_{min})$, просто дважды написали не то слово.

[Dmitriy40]

Соответственно для паттерна v=[0, 24, 30, 36, 60] точное значение c5=vc[cmin=5] для p<1e8 равно 7.9025656247869692640730186809525569115e43424112 (30с счёта PARI), а оценочное для p<1e13 (т.е. для диапазона 1e26) будет в exp(1e13-1e8) раз больше или 1e4342944813697 плюс-минус сколько-то миллиардов порядков.
Точность оценю сравнением с 8.3519448537908096669774791596647757319e4340844*exp(1e13-1e7)=4e4342944816932 (точное до 1e7 за 3с на экспоненту). Точность 9 цифр порядка! Т.е. погрешность порядка не миллиарды, а всего лишь тысячи.
Другая проверка, посчитаю точное c5 до p<1e6 и умножу на exp(1e8-1e6) и сравню с точным до p<1e8 выше: 1.2140432734322464270909307008420340923e433630*exp(1e8-1e6)=6.2e43428783, точность 4 цифры порядка, погрешность снова тысячи порядков, уже похуже.
Сравню и переход 1e7 к 1e8: 8.3519448537908096669774791596647757319e4340844*exp(1e8-1e7)=2e43427348, те же 4 цифры порядка точные, та же погрешность в тысячи порядков.
Т.е. погрешность порядка как бы и не растёт особо, а может и вообще почти не растёт.

Не вижу особого смысла повышать точность для столь коротких паттернов (столь больших чисел). Вы видите?

В принципе до 1e13 простые генерить порядка 5ч, ну плюс точные вычисления пусть даже столько же, десять часов немного, вопрос насколько это реально нужно, а то мне программу переписывать сравнимое время, правда потом она сможет считать любые паттерны (с затравки, точных значений).


Мне кажется гораздо более важным найти методику вычислений vc[] до стабилизации формул, чтобы не считать до 83#-89# для 19-252. А для такого анализа данных уже полно, да и новые насчитать не так уж сложно.

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

Это не произведения, это разности.

Имел в виду произведение(-я) всех таких разностей для всех p и конкретного (или всех интересующих) cmin.

[Dmitriy40]

Кстати, погрешность в тысячи порядков вообще не страшна ведь для частотности берётся отношение c5/sum, а они обе растут с примерно одинаковой погрешностью, ведь при отбрасывании всех прочих vc[] при вычислении vc[cmin] как я предлагаю это отношение это просто c5*(p-cmin)/(sum*(p-cmin)) и для p>cmin оно уже не меняется.

Или по другому, смотрите на точные отношения c5/sum для того же паттерна:

? for(k=3,8,c=c0;forprime(p=31,10^k,for(i=cm,#c-1,c[i]=c[i]*(p-i)+c[i+1]*(i+1-cm);););print("10^",k,": c5/sum=",c[cm]/vecsum(c[cm..#c-1]));)
10^3: c5/sum=0.019758857288582353545641688029906402636
10^4: c5/sum=0.065920496919088498270540597499801704631
10^5: c5/sum=0.12411299279519796710975326199735559906
10^6: c5/sum=0.18379482350176932234225765079524081423
10^7: c5/sum=0.24024813352062236144032345040232388879
10^8: c5/sum=0.29181503136481607763016103150545619965
10^9: c5/sum=0.33824436542576658977061029060797032068

За исключением первого остальные почти точно произведение c5(1e4) на превышение порядка над 1e3, т.е. для 10^n дробь будет примерно 0.6*(n-3). И тогда можно сразу предположить и следующие значения:

10^10: c5/sum=0.42
10^11: c5/sum=0.48
10^12: c5/sum=0.54
10^13: c5/sum=0.60

Реально они будут чуть меньше, но уже совсем не на порядки, а на десяток процентов. А просто праймориал (для sum) посчитать сильно легче чем vc[cmin] для каждого варианта паттерна.

А если присобачить логарифм, то возможно выйдет ещё точнее: $0.24+\frac{\ln(10^7)}{\ln(10^9)}\cdot 0.66\cdot2=0.343$ (0.66 это величина 1e4, 2 это разница 1e9 и 1e7, 0.24 это величина 1e7), уже совсем похоже на 1e9:0.338.

Осталось проверить что такое же наблюдается и для других паттернов.