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

[Yadryara]

Уточнение терминологии.

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

   p#        c4        c5         c6       c7        c8       c9            Sum

   5#                                                          4              4

   7#                                       1         8        3             12

  11#                             2        32        41        9             84

  13#                   3        93       354       261       45            756
-------------------------------------------------------------------------------
  17#         3       222      2085      4584      2574      360           9828

  19#       267      7278     40857     65304     30114     3600         147420

Прерывистая линия между 13# и 17# — точка устаканивания.
В качестве начальных значений берём строку для 13#

Прерывистая линия между 13# и 17# — радиус.
Строчку 13# выше радиуса вплотную к нему называю стартовой.
Строчку 17# ниже радиуса вплотную к нему называю окейной.

Да, радиус паттерна в точности равен половине его диаметра. Ещё один пример:

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

А значит для 19-252 надо 113# (а 127# получится по формулам).

Диаметр — 252;
Радиус — 126;
Стартовая строка — 113#;
Окейная строка — 127#.

Ещё помарку заметил:

Dmitriy40 писал(а):

v=[0, 6, 12]+
3#: 0, 0, 2, sum=2
5#: 0, 2, 2, sum=4
7#: 2, 10, 4, sum=16
11#: 26, 78, 24, sum=128, OK
13#: 338, 750, 192, sum=1280, OK
17#: 5482, 10134, 2304, sum=17920, OK

Здесь окейная строка — 7# , но почему-то в её конце не стоит OK.

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

v=[0, 42, 84] — 40 часов
v=[0, 12, 42, 72, 84] — 15 часов
v=[0, 24, 42, 60, 84] — 15 часов
v=[0, 30, 42, 54, 84] — 15 часов
v=[0, 12, 24, 42, 60, 72, 84] — 5 часов ?
v=[0, 12, 30, 42, 54, 72, 84] — 5 часов ?
v=[0, 24, 30, 42, 54, 60, 84] — 5 часов ?
v=[0, 6, 18, 36, 48, 60, 78, 90, 96] — 400 часов ?

Ну и надо бы заметить, что лично я например не уверен на 100%, что окейная строка будет именно строкой стабилизации (сходимости, устаканивания).

Да, на 99% с чем-то уверен: не может такая красота не работать для всех нечётных симметричных паттернов и кортежей.

[Dmitriy40]

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

Здесь окейная строка — 7# , но почему-то в её конце не стоит OK.

Все меньшие 17# проверял руками, мог просчитаться.

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

Значит ищем в этой Базе все 9-84. Это наш факт. Затем считаем среднюю ожидаемую частотность до 1е16 (или, если угодно, до 1е25). Затем сравниваем её с фактом. Ожидаю превышение над фактом на 30-40%.

В базе 81589 девяток диаметром 84 до 1e16.
Чтобы сравнить с прикидками их надо сделать до 1e8# (PARI легко справился за минуту):
10^8#: c9/sum=0.25323207760655043670705558488824500812, sum=1.5503569128101014639216699313142007837e43424109
Сама sum (это ведь количество грязных до 1e8#) нам видимо не нужна.
Теперь чтобы получить количество грязных до 1e16 надо взять sum до 43#=1.3e16 и поделить на 1.3 (грубовато, но для прикидки сойдёт), получим 960810188800/1.3=739e9. А чистых среди них должно быть 0.253232, т.е. 187e9. Реально же меньше 82e3 ... В 2.3млн раз меньше.
При том что даже прикидка даёт 3075976 чистых до 43# (это ведь посчитано точно), что даже поделённое на 1.3 всё равно почти в 30 раз больше реального.
И? Опять что-то не то посчитал? Путаюсь я в этих кэфах.

-- 27.03.2024, 15:10 --

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

Предположительное время обсчёта окейной указано справа.

Нет, несколько по другому. Например для v=[0, 12, 24, 42, 60, 72, 84] время счёта 41# две минуты, значит на окейную 43# надо 72 минуты. В один поток, многопоточная у меня пока не работает (но могу в общем запустить сразу 4 паттерна считаться). Вот прикинул более точные цифры:

v=[0, 42, 84] - 51 час
v=[0, 12, 42, 72, 84] - 10 часов
v=[0, 24, 42, 60, 84] - 10 часов
v=[0, 30, 42, 54, 84] - 10 часов
v=[0, 12, 24, 42, 60, 72, 84] - 72 минуты
v=[0, 12, 30, 42, 54, 72, 84] - 140 минут
v=[0, 24, 30, 42, 54, 60, 84] - 72 минуты
v=[0, 6, 18, 36, 48, 60, 78, 90, 96] - 27 дней

Длиной 7 пожалуй запущу считаться, пары часов не жалко.

-- 27.03.2024, 15:22 --

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

[Yadryara]

Dmitriy40, давайте аккуратно считать. Я ведь показывал сравнение уже на 3-х паттернах и все результаты были близкими.

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

В базе 81589 девяток диаметром 84 до 1e16.

Сколько из них до 1е8, 1е9, 1е10, ... 1е15 ? Это будет 3-й столбец.

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

Сама sum (это ведь количество грязных до 1e8#)

Обычно это сумма всех: и чистых и грязных.

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

Чтобы сравнить с прикидками их надо сделать до 1e8# (PARI легко справился за минуту):
10^8#: c9/sum=0.25323207760655043670705558488824500812, sum=1.5503569128101014639216699313142007837e43424109

Программу можете показать?

[Yadryara]

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

И? Опять что-то не то посчитал?

Не то Где бузина, а где дядька

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

При том что даже прикидка даёт 3075976 чистых до 43# (это ведь посчитано точно),

Это чистые 9-ки, собранные из малопростых.

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

При том что даже прикидка даёт 3075976 чистых до 43# (это ведь посчитано точно), что даже поделённое на 1.3 всё равно почти в 30 раз больше реального.

Ну конечно же 9-к, собранных из малопростых (проверенных на делимость лишь на простые до 43-х) гораздо больше чем 9-к, собранных из простых до 1е16.

А вот 9-к, собранных из малопростых (проверенных на делимость на простые до 1е8) пока считаем равным числу 9-к, собранных из простых до 1е16.

[Dmitriy40]

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

Сколько из них до 1е8, 1е9, 1е10, ... 1е15 ? Это будет 3-й столбец.

1e9: 0
1e10: 8
1e11: 20
1e12: 73
1e13: 403
1e14: 2315
1e15: 13514
1e16: 81589

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

Обычно это сумма всех: и чистых и грязных.

У меня чистые входят в грязные.

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

Программу можете показать?

? c0=[0,0,0,0,0,0,0,0,3075976, 172443036, 2982765864, 22582804840, 87976549320, 195008570124, 262408889876, 220882584188, 117236333144, 40358558480, 9629086752, 1478049120, 90478080]; cm=9;
? for(k=1,8, c=c0*1.0; forprime(p=47,10^k, for(i=cm,#c-1, c[i]=c[i]*(p-i)+c[i+1]*(i+1-cm);); c[#c]*=p-#c;); print("10^",k,": c",cm,"/sum=",c[cm]/vecsum(c)); );
10^1: c9/sum=3.2014398222001868929389937793299137837 E-6
10^2: c9/sum=0.00027672908869630203858064936508483109089
10^3: c9/sum=0.013117668863171328416561786029924797282
10^4: c9/sum=0.049069615944334215815571780073308430251
10^5: c9/sum=0.098400903802331048117422616513907989200
10^6: c9/sum=0.15177232096585074141618121885171438037
10^7: c9/sum=0.20412980147180142896080456376527909183
10^8: c9/sum=0.25323207760655043670705558488824500812

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

Длиной 7 пожалуй запущу считаться, пары часов не жалко.

Досчитал (41# показываю для контроля):

v=[0, 12, 24, 42, 60, 72, 84]+
41#: 2552, 488216, 20304990, 327428600, 2597907138, 11516502178, 30620795916, 50555886616, 52238555334, 33420350378, 13143650526, 3365193200, 640468068, 83112048, 4112640, sum=198534758400
43#: 580088, 57697540, 1672655460, 21196772352, 140715539306, 540736343014, 1272515083792, 1884029154536, 1763462702754, 1033785965466, 378752038876, 91815446816, 16451690256, 1969154064, 90478080, sum=7147251302400, OK

v=[0, 12, 30, 42, 54, 72, 84]+
41#: 9828, 1045948, 34333108, 516906102, 4188401156, 19755840734, 56442652104, 99340903200, 108010521004, 72061865836, 28946728386, 6765649296, 917088162, 83459296, 4112640, sum=397069516800
43#: 1399756, 105274396, 2718043978, 33811505990, 232808040662, 951086975378, 2388665885520, 3744970360832, 3672851380636, 2235137661432, 827037080292, 180146290344, 23095086736, 1977140768, 90478080, sum=14294502604800, OK

v=[0, 24, 30, 42, 54, 60, 84]+
41#: 3408, 396130, 13676382, 216457390, 1847287206, 9106325012, 26958805368, 49031994710, 54928211950, 37241611162, 14921956726, 3591403120, 598356332, 74160864, 4112640, sum=198534758400
43#: 518818, 41217314, 1114369158, 14532242694, 104644815652, 444048907580, 1151988124010, 1861353542190, 1873164435058, 1154743068634, 427476309196, 96965353984, 15324643200, 1763276832, 90478080, sum=7147251302400, OK

Кроме того реализовал свою вторую идею, оказалось что одно следующее простое можно досчитать лишь вдвое медленнее предыдущего. Запустил для паттернов длиной 5 диаметром 84, вот что выдало за минут 50:

v=[0, 12, 42, 72, 84]+
41#: 36, 20880, 2074146, 71568848, 1149895688, 10039451410, 51957202280, 167173578980, 342307286952, 449274964550, 375723695276, 196463610436, 62290534256, 11605217348, 1307930546, 104454064, 4112640, sum=1669475598336
43#: 22248, 4920852, 289375800, 7104492432, 89293710442, 643045110210, 2832845525820, 7920839243996, 14312693289510, 16786210924710, 12681363182524, 6052003892844, 1770421716180, 308441461344, 32957144064, 2468245712, 90478080, sum=63440072736768, OK

v=[0, 24, 42, 60, 84]+
41#: 560, 144468, 8368126, 196288482, 2354484780, 16278352832, 69695262276, 193259965146, 355455747956, 435739598126, 350858907920, 179231278518, 55253258698, 9919643984, 1123372912, 96810912, 4112640, sum=1669475598336
43#: 165748, 22081568, 890117982, 16288035990, 161444246680, 955357217112, 3583068148854, 8834704903174, 14585328821814, 16145037424854, 11795593485458, 5502283624362, 1565540097940, 263718320368, 28413113568, 2292453216, 90478080, sum=63440072736768, OK

v=[0, 30, 42, 54, 84]+
41#: 508, 58226, 3552546, 101742618, 1459075038, 11658099150, 56082084228, 170818565444, 338786100888, 441164905144, 373097699652, 199030370402, 64052850898, 11843988724, 1276889350, 95502880, 4112640, sum=1669475598336
43#: 77530, 9259454, 433119510, 9397291782, 107899047042, 721209777318, 2990356653404, 8005664335868, 14134067172936, 16524759245696, 12636069664678, 6142454211630, 1819345976760, 313976169000, 32077887600, 2262368480, 90478080, sum=63440072736768, OK

[Yadryara]

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

Чтобы сравнить с прикидками их надо сделать до 1e8# (PARI легко справился за минуту):
10^8#: c9/sum=0.25323207760655043670705558488824500812, sum=1.5503569128101014639216699313142007837e43424109
Сама sum (это ведь количество грязных до 1e8#) нам видимо не нужна.

Не нужна, нам нужна $c9$. Она у Вас, как понимаю $c9\approx3.926\cdot10^{43424108}$.

Вот формула для Средней Ожидаемой Частотности:

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

А сейчас для среднего столбца я беру только чистые 372:

$$\frac{372\cdot1000}{200560490130}\approx0.000002$$

Допустим, $c9$ посчитано правильно. Тогда подставим все три числа и вот наша СОЧ:

$$\frac{3.926\cdot10^{43424108}\cdot10^{16}}{999999..\#}$$

[Dmitriy40]

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

Тогда подставим все три числа и вот наша СОЧ:

$$\frac{3.926\cdot10^{43424108}\cdot10^{16}}{9999999999999937\#}$$

Простите, но 1e16# очень примерно равно $\exp(1e16)\approx10^{4.343\cdot10^{15}}$, так что дробь будет порядка
? 3.926e43424108*1e16/exp(1e16)
%1 = 2.0770120018311993387061961590941027619 E-4342944775608394
12-13 младших знаков в порядке могут и отличаться, но что он будет около 4.3e15 - однозначно. Более 4 квадриллионов нулей после запятой как-то мало похоже на правду.
И? Что опять не так?

[Yadryara]

Правильно Ваша прога считает. Моя намного медленнее, до 1е12 дошла. Похоже превышение над фактом будет весьма серьёзное ибо для 1е11 оно составило 11%, а для 1е12 уже почти 69%.

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

И? Что опять не так?

Я поправил пост, просто Вы не заметили:

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

$$\frac{3.926\cdot10^{43424108}\cdot10^{16}}{999999..\#}$$

Поставил две точки вместо двух недостающих цифр. Поленился сразу точное число найти и указать. На всякий случай, в знаменателе $99999989\#$

Об остальном позже.

[Dmitriy40]

Мда, я с 1e8# тоже ошибся, 1e8#=2.5401483842215342462788890842604146196 E43424119 и тогда дробь для 1e16 будет
? 3.9260010206257956280639458393354973103 E43424108*1e16/2.5401483842215342462788890842604146196 E43424119
%1 = 154557.94019800840344065946470655508813
Уже всего вдвое больше реального.

Выходит и c9 нам отдельно не нужно, нужно сразу c9*100^k/10^k#.

PS. 99999989#=1e8#, в праймориале берётся по предыдущее простое, так что ничего искать не надо, можно указывать ровную границу.

[Yadryara]

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

PS. 99999989#=1e8#, в праймориале берётся по предыдущее простое, так что ничего искать не надо, можно указывать ровную границу.

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

Таблицу попробую составить.

[Dmitriy40]

Ну то есть для 19-252 затык по прежнему в получении c19 для 113# (дальше будут работать Ваши формулы).

[Yadryara]

Ну вот, пока так:

10^   (СОЧ-Факт)/Факт

10        -48.5 %
11         11.1 %
12         68.9 %
13         74.9 %
14         79.0 %
15
16         89.4 %

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

Ну то есть для 19-252 затык по прежнему в получении c19 для 113# (дальше будут работать Ваши формулы).

Так точно

[Dmitriy40]

Посчитал и последний паттерн диаметром 84:

v=[0, 42, 84]+
41#: 0, 922, 173122, 10114884, 264451498, 3690470360, 30525389506, 159502826194, 546738842952, 1254433960054, 1939829127142, 2010825208458, 1370908155696, 593640303464, 155014292414, 22997963896, 1954975470, 118152928, 4112640, sum=8090458521600
43#: 922, 382202, 36923288, 1432056700, 27972605728, 312318799636, 2154383026562, 9637504008018, 28785548614950, 58285744033094, 80313951107298, 74764828913634, 46102752304520, 18198488287324, 4375341061204, 606228704920, 48928011056, 2791544864, 90478080, sum=323618340864000, OK

Реализован свою первую идею, причём на PARI, оказалось она очень даже работает (паттерн 0, 24, 30, 36, 60, без неё vs с ней):
23#: 0.8с vs 0.15с
29#: 19с vs 1.2с
31#: 488 vs 8.0с
37# ~15600с vs 53.7с
Причём рост времени вовсе не кратен количеству допустимых остатков, заметно медленнее. Значит удастся посчитать ещё дальше.
Программа:

{Calc(i,a,k)=my(nn=0,m,aa);
   foreach(am[i],m,
      aa=bitand(m,a);
      if(pr[i]<pmax,
         if(aa==a, nn++; next);
         Calc(i+1,aa,k);
      ,
         vc[#v+hammingweight(aa)]+=k;
      );
   );
   if(nn>0, Calc(i+1,a,k*nn); );
}

v=[0,24,30,36,60];
pr=primes([3,127]);
a=setminus(vector(v[#v]/2,i,i*2),v); print("v=",v);
m=vector(#pr,i,[]); am=vector(#m,i,[]);
{for(ip=1,#pr,
   p=pr[ip];
   m[ip]=setminus(vector(p,i,i-1),Set(-v%p));
   am[ip]=vecextract(vector(p-1,i,fromdigits(Vecrev(apply(t->(t+i)%p>0,a)),2)),m[ip]);
);}
{for(i=1,#pr,
   pmax=pr[i]; if(pmax>37, break);
   tz0=getwalltime();
   vc=vector(100);
   Calc(1,2^#a-1,1);
   cmax=#vc; while(vc[cmax]==0,cmax--);
   print(pmax,"#: ",strjoin(vc[#v..cmax],", "),", sum=",vecsum(vc));
   print("Time: ",strtime(getwalltime()-tz0));
);}

[Dmitriy40]

Вот такая процедура ещё в полтора раза быстрее:

{Calc(i,a,k)=my(nn=0,m,aa);
   if(pr[i]<pmax,
      foreach(am[i],m,
         aa=bitand(m,a);
         if(aa==a, nn++ , Calc(i+1,aa,k) );
      );
      if(nn>0, Calc(i+1,a,k*nn); );
   ,
      foreach(am[i],m, vc[#v+hammingweight(bitand(m,a))]+=k; );
   );
}

-- 28.03.2024, 04:02 --

Реализация первой идеи в асме позволила посчитать 53# для 9-96 за 0.85с+6.15с+45с+78с=130с (41#+43#+47#+53#) вместо 27 дней! А вот время для 53# всего 78с вместо 330с это заслуга второй идеи.

v=[0, 6, 18, 36, 48, 60, 78, 90, 96]+
41#: 86, 15556, 728848, 15639218, 180002808, 1162824978, 4328453218, 9487646180, 12375783316, 9538383100, 4205916924, 983492488, 105794760, 4003320, sum=42388684800
43#: 18448, 1953488, 69060882, 1179469642, 10979144778, 58631583864, 185237280994, 352946887468, 408038177160, 283116512406, 113848074894, 24597284220, 2480850036, 88984920, sum=1441215283200
47#: 2638912, 208604384, 5966150812, 84399257952, 661108726694, 3027885235412, 8366916229460, 14186817548230, 14804134497452, 9379965296622, 3479088063478, 700691930536, 66711478656, 2285103000, sum=54766180761600
53#: 324716512, 20902290136, 503776107960, 6104804482808, 41583775244820, 168289021557828, 417250539557090, 643345325264126, 617368529577870, 363089666016550, 125996605394148, 23923371451560, 2164473655992, 70838193000, sum=2409711953510400, OK

Более короткие паттерны считаются заметно дольше, например паттерн v=[0, 6, 36, 48, 60, 90, 96] считался 57c+501c+757с (43#+47#+53#).

[Yadryara]

Золотая голова у Вас, что тут скажешь. И знания.

Сколько можно тянуть, видимо, летом буду покупать новый комп и отгадайте к кому я обращусь за советом

Я тут много чего хотел сказать по разным аспектам. Продолжу пока по частотности.

Значение для 1е15 оказалось предсказуемым:

10^   (СОЧ-Факт)/Факт

10      -48.5 %
11       11.1 %
12       68.9 %
13       74.9 %
14       79.0 %
15       85.0 %
16       89.4 %

И, видимо, можно предсказать количество таких 9-к до 1е17 с погрешностью всего в пару процентов:

Считаем СОЧ и делим на 1.94.

Но будет ли такая линейность продолжаться до 1е25 — совершенно непонятно. И выяснить-то это нельзя — не с чем сравнивать. И полной Базы 11-к, аналогичной 9-кам ведь нет, правильно?

Ой!! Только сейчас заметил, что Вы 9-96 уже обсчитали. Ура. Его-то есть с чем сравнивать.