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

[Yadryara]

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

А с другой стороны Вы пишите

Пишете.

Кстати, эти вероятности могут быть интересны Дмитрию для решения практического вопроса:

На каком периоде считать, $67\#$ или $71\#$ ?

В первом случае по HL-1 ожидается 0.5 чистых кортежей, а во втором — 9-10. (Можно посчитать точнее.)

И это сложный выбор. Потому как есть сразу несколько критериев. Например, Дмитрий хочет найти именно наименьший кортеж. Если бы его устроил любой из 9-10, то конечно надо считать на треть быстрее на периоде $71\#$.

[vicvolf]

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

И когда же наступает этот счастливый момент, необходимой точности?

Когда количество простых $k$ кортежей на интервале достаточно велико. Поэтому с ростом $k$ такой интервал тоже растет.

Цитата:

Для доли чистых 19-252, т.е. с учётом констант C,C1-C10? Последняя из которых равна 139968081763087868053405.50716615643237 и соответственно даёт огромную погрешность вплоть до аж $10^{60}$

Когда Вы определяете количество "грязных" простых кортежей на интервале для больших $k$, то соответственно для получения достаточной точности требуется большой интервал. Когда определяете количество "чистых" простых кортежей, то используете формулу включений, исключений с простыми кортежами еще большей длины, поэтому для немодифицированной формулы требуется еще больший интервал.

Цитата:

когда нам надо до $10^{25...26}$.

Для этого и модифицировали формулу.

[Dmitriy40]

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

И это сложный выбор. Потому как есть сразу несколько критериев. Например, Дмитрий хочет найти именно наименьший кортеж. Если бы его устроил любой из 9-10, то конечно надо считать на треть быстрее на периоде $71\#$.

Тут хитрее: смотрите, кортежей на 71# по идее в 22 (11/0.5) раза больше чем на 67#, а проверить надо в 52 раза больше вариантов, т.е. вероятность обнаружения даже любого из 11 кортежей снижается в 52/22=2.4 раза. Т.е. во столько раз дольше вероятно придётся ждать на периоде 71# до обнаружения любого кортежа. Выигрыш 71/52=1.365 с новой программой не играет (он играет только по отношению к старой программе) ведь проверка и 67# и 71# не линейна и проверяет не 67 или 71 поддиапазон, а лишь 48 или 52.
С другой стороны, 0.5 кортежа не так уж и мало, тем более с разбросом даже в одну сигму ±0.7, да плюс возможные флуктуации, так что кортеж (и даже не один) вполне может обнаружиться и до 67#. И не придётся проверять в 2.4 раза дольше, ведь теперь проверка по 71# не линейна и не проверит поддиапазон 67# раньше остальных, кортежи размазаны по всему диапазону почти равномерно.
Но даже если и не найдётся кортежа до 67#, то перенаходка всех кортежей по 67# проверкой по 71# займёт лишь 1/52 времени полной проверки 71#, что меньше 2% и на что смело наплюю. На самом деле 71# я в одиночку проверить не буду, это десятки лет счёта. Ну если конечно не перепишу прогу под GPU (возможно только Nvidia) и не получу скорость в десятки раз выше (что пока сомнительно, там огромные сложности и с AVX2 и вообще асмом).
Я до сих пор раздумываю стоит ли убирать перепроверку диапазона 0-1.7e24 и в какие тормоза это выльется, что почти 22% от 67#, что уж говорить про жалкие 2%.

vicvolf
Спасибо за очередные банальности.

[vicvolf]

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

Спасибо за очередные банальности.

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

[Yadryara]

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

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

0.6 чистых кортежей на 1е25 — это и есть матожидание

Сначала поправлю ссылку:

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

0.6 чистых кортежей на 1е25 — это и есть матожидание:

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

Давайте сразу на 19-252 бросаться не будем,

И вскоре бросились и посчитали. В теме всё есть вплоть до текстов программ.

Для тех кому непонятно, что $67\#$ поменьше чем $10^{25}$, а $71\#$ в 5.5 раз больше чем $10^{26}$, такая табличка:

$\tikz[scale=.1]{ \draw[step=20cm] (0,300) grid +(60,50); \draw (0,350) -- (60,350); \draw (0,330) -- (60,330); \draw (0,310) -- (60,310); \node at (10,345){\text{Диапазон}}; \node at (30,345){\text{Чистых}}; \node at (50,345){\text{Всех}}; \node at (10,335){$\leqslant 67\#$}; \node at (10,325){$\leqslant 10^{25}$}; \node at (10,315){$\leqslant 10^{26}$}; \node at (10,305){$\leqslant 71\#$}; \node at (30,335)[red]{\text{0.5}}; \node at (30,325)[red]{\text{0.6}}; \node at (30,315){\text{3.2}}; \node at (30,305){\text{11}}; \node at (50,325){\text{8.7}}; \node at (50,315){\text{40.4}}; }$

Dmitriy40, понял. 11 кортежей это посчитано или прикидка? Поправьте, в общем, табличку, если что.

[Dmitriy40]

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

11 кортежей это посчитано или прикидка?

Посчитано конечно, благо PARI берёт интегралы влёт, вот цифры "всех":

? 1592669394.7454967047727717796940585531*intnum(t=1e20,vecprod(primes([2,67])),1/log(t)^19)
%1 = 7.4089452575996516710703096922429396190
? 1592669394.7454967047727717796940585531*intnum(t=1e20,vecprod(primes([2,71])),1/log(t)^19)
%2 = 129.90945892866154759444642716688386150
? 1592669394.7454967047727717796940585531*intnum(t=1e8,vecprod(primes([2,71])),1/log(t)^19)
%3 = 129.91645746365924618929057702689249578

Последнее число специально для Вас, конкретно с 1e8 как предлагали - и как видно разница вообще несущественна (и на 3 с лишним порядка меньше одной сигмы, см. ниже).

Кстати про допуски, вот числа для всей таблицы с разбросом в одну сигму (если верить формуле 4.10 vicvolf):

Чистые:
67: 0.51096683390272137231990193039503393003 +- 0.71481944146946742953756854894449662578
10^25: 0.60654064521609277352535163128956936153 +- 0.77880719386513936689904628543338421679
10^26: 3.1577701304210924331720589312727594494 +- 1.7770115729564319393912482047196788315
71#: 10.969648653259594600254498798126080790 +- 3.3120459920205810149652785658828370211
10^27: 16.782714042228751774564595651043852765 +- 4.0966710927567460470648817471044012016
Все:
67#: 7.4089452575996516710703096922429396189 +- 2.7219377762174600583196820175881914226
10^25: 8.6872659204322943086811609840623335541 +- 2.9474168216308147936167361714150012980
10^26: 40.425825753419374390216627594476546953 +- 6.3581306807440954319660922319898660296
71#: 129.90945892866154759444642716688386149 +- 11.397783070784491272732696456947878267
10^27: 193.77287540053313619050457198356294532 +- 13.920232591466750926190995651616689931

Всё это легко считается на PARI буквально в одну-две строки, ведь все константы C и C1-C10 (для доли чистых) я показывал выше.
Табличкой:
\begin{tabular}{|c|c|c|} \hline \text{Диапазон} & \text{Чистых} & \text{Всех} \\ \hline 67\# & 0.51 \pm 0.71 n & 7.4 \pm 2.7 n \\ \hline 10^{25} & 0.61 \pm 0.78 n & 8.7 \pm 2.9 n \\ \hline 10^{26} & 3.2 \pm 1.8 n & 40 \pm 6.4 n \\ \hline 71\# & 11 \pm 3.3 n & 130 \pm 11.4 n \\ \hline 10^{27} & 17 \pm 4.1 n & 194 \pm 14 n \\ \hline \end{tabular}
$n$ - количество сигм.

Как видно есть где-то 0.2% (3 с небольшим сигмы) вероятность что кортежа не будет и до 71# (вероятность из количества сигм для нормального распределения в PARI можно получить командой erfc(n/sqrt(2))).

PS. Нет смысла отвечать НМ, она даже понятий мат.ожидание или вероятность не осилила, забейте.

[gris]

Возникла мысль и не удалось её вовремя придавить.
Формируем индикаторный вектор простых на интервале 19# где-нибудь в диапазоне E16. Затем берём аналогичный интервал в диапазоне E26, с помощью приближённых формул определяем количество простых и пропорционально и случайно удаляем единички из индикации.
На получившемся векторе проводим разнообразные статистические эксперименты. При наличии достаточных ресурсов можно увеличить модельный интервал до 29#.
Проведённые испытания показали хорошую статистику по небольшим кортежам.
Было ли это уже в 17 веке? Можно ли всерьёз подходить к вопросу? Спасибо.

[Yadryara]

gris в сообщении #1648852 писал(а):

Проведённые испытания показали хорошую статистику по небольшим кортежам.

Сами же видите, что мы здесь привыкли конкретику обсуждать. Так что хорошую статистику — в студию.

[Dmitriy40]

gris в сообщении #1648852 писал(а):

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

А я вот этого не понял, зачем удалять единички случайно если можно легко удалить их не случайно, ведь найти все простые в интервале 19# совсем несложно. Или первое просто быстрее?

[gris]

Dmitriy40, в общем-то это просто забава моделирования простых чисел в диапазонах Е40,например. Идея была такая: посчитать вектор длиной 19# именно в Е40, а потом его использовать миллиард раз. Но при этом чуть-чуть изменять, соблюдая похожесть на простые.
Всё-таки это быстрее, кмк. При этом даже формулы по КТО сохраняют валидность(?).

[Yadryara]

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

Есть ещё несколько второстепенных вопросов, о них, видимо, позже.

Я так и не доделал ускорение из-за учёта симметрии. Сейчас вернулся к нему.

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

Т.е. не вижу никакого уменьшения количества паттернов вдвое, ну кроме как для C1.

А теперь посмотрите:

for(i1=1,#a/2,
   forprime(p=3,#v+1, if(m0[p]==2^(-a[i1]%p), next(2)); );
   m1=m0; t=CC[#v+1];
 forprime(p=3,#m1, m1[p]=bitnegimply(m1[p],2^(-a[i1]%p));
 t*=hammingweight(m1[p]); ); C1 +=2*t; nn[1]++;

   for(i2=i1+1,#a-i1,
      forprime(p=3,#v+2, if(m1[p]==2^(-a[i2]%p), next(2)); );
      m2=m1; t=CC[#v+2];
 forprime(p=3,#m2, m2[p]=bitnegimply(m2[p],2^(-a[i2]%p));
 t*=hammingweight(m2[p]); ); C2 +=t*2; nn[2]++;

      for(i3=i2+1,#a-i1,
         forprime(p=3,#v+3, if(m2[p]==2^(-a[i3]%p), next(2)); );
         m3=m2; t=CC[#v+3];
 forprime(p=3,#m3, m3[p]=bitnegimply(m3[p],2^(-a[i3]%p));
 t*=hammingweight(m3[p]); ); C3 +=t*2; nn[3]++;

         for(i4=i3+1,#a-i1,
ovc++;
            forprime(p=3,#v+4, if(m3[p]==2^(-a[i4]%p), next(2)); );
            m4=m3; t=CC[#v+4];
 forprime(p=3,#m4, m4[p]=bitnegimply(m4[p],2^(-a[i4]%p));
 t*=hammingweight(m4[p]); ); C4 +=t*2; nn[4]++;
))));

А теперь видите уменьшение количества паттернов вдвое для всех $C_i$ ?

А ovc(Обращения к Внутреннему Циклу) у меня при тестировании уменьшились более чем вдвое.

[Dmitriy40]

Да, паттернов вдвое меньше везде.
Погрешность возросла до 6 младших цифр (из 38) для C5. Некритично.
Зато время уменьшилось с 72.1с до 33.6с, чуть более чем вдвое.
При необходимости можно пожалуй и C11 посчитать (типа меньше суток).

[Yadryara]

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

Зато время уменьшилось с 72.1с до 33.6с, чуть более чем вдвое.

Ура! Неслучайно же количество загрязняющих паттернов всегда чётное.

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

При необходимости можно пожалуй и C11 посчитать (типа меньше суток).

Я так понимаю, теперь с этим ускорением можно надеяться на всего лишь 14 часов.

А не посчитать ли нам теперь по HL-1, извиняюсь за выражение, минимальное очко , 21-324 ?

По Вашей проге 2 паттерна нашёл:

[0, 12, 30, 42, 54, 60, 84, 114, 120, 144, 162, 180, 204, 210, 240, 264, 270, 282, 294, 312, 324]

[0, 12, 30, 42, 54, 60, 72, 84, 114, 120, 162, 204, 210, 240, 252, 264, 270, 282, 294, 312, 324]

[Dmitriy40]

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

А не посчитать ли нам теперь по HL-1, извиняюсь за выражение, минимальное очко , 21-324 ?

Попробовать можно, но оно считается сильно медленнее (3м6с и 3м18с для двух паттернов против 33.6с, для C5), причём замедление растёт с ростом номера константы, значит о C10 можно забыть. Хватит ли C8-C9 для приличной точности прогноза доли чистых не уверен.
Вот первые константы (с Вашей доработкой) и количество всех кортежей:

v=[0, 12, 30, 42, 54, 60, 72, 84, 114, 120, 162, 204, 210, 240, 252, 264, 270, 282, 294, 312, 324]
C =22484139264.891698882318075099084270700
C1=4374250959372.6000588973751653265564380
C2=411437742400755.32945245180258107064852
C3=24927059231252026.068712689629028946158
C4=1093441485845415696.0298940127499512308
C5=37010704184490638039.639096498197378944
[1, 71, 2801, 55624, 708683, 6514233, 0, 0, 0, 0, 0]
10^20: 0.E-62 +- 0.E-31
10^21: 0.00012326800059464151374514012643170250367 +- 0.011102612331998335325157965056563686939
10^22: 0.00057885887477774040271541952417277808446 +- 0.024059486170276795890843891308319885712
10^23: 0.0023405633801897233095964284002738158666 +- 0.048379369365357826143930145055655974104
10^24: 0.0094398137299932944704582918996956491166 +- 0.097158703830348078962006931712667748283
10^25: 0.039150766895462957182405118426102936050 +- 0.19786552730443713444263373213935761883
10^26: 0.16789541134441179660958448064995331038 +- 0.40975042567935398864816630552740809165
10^27: 0.74398048720456976888133113347742243372 +- 0.86254303498699110930804855517576820557
10^28: 3.3995342484822594553592250952354919288 +- 1.8437825925206744546290095372294243183
10^29: 15.983336347758908150521203110949804255 +- 3.9979165008487743740771956054343982657
10^30: 77.166224480667924152073429932010698902 +- 8.7844308000386640960318074912662281719

v=[0, 12, 30, 42, 54, 60, 84, 114, 120, 144, 162, 180, 204, 210, 240, 264, 270, 282, 294, 312, 324]
C =60707176015.207586982258802767527530888
C1=11683343782474.649503568809567368793817
C2=1086317606098750.9413618497848704379815
C3=65009813964907480.177769745726390942734
C4=2814495559815963494.2336211710203502004
C5=93939323159896633418.068815715314791279
[1, 71, 2828, 57136, 744565, 7029833, 0, 0, 0, 0, 0]
10^20: 0.E-61 +- 0.E-31
10^21: 0.00033282360160553208711187834136559675989 +- 0.018243453664411573995041907621840800296
10^22: 0.0015629189618998990873316327152665008280 +- 0.039533769892332543490531654455945664875
10^23: 0.0063195211265122529359103566807393028396 +- 0.079495415757842621247935604325288668203
10^24: 0.025487497070981895070237388129178252614 +- 0.15964804123753568643480625228303117598
10^25: 0.10570707061774998439249381975047792733 +- 0.32512623797188375241450567671614097938
10^26: 0.45331761062991185084587809775487393801 +- 0.67328865327577877639490247065057089673
10^27: 2.0087473154523383759795940603890405710 +- 1.4173028312440282344006847874575156259
10^28: 9.1787424709021005294699077571358282074 +- 3.0296439511767881219317995207411168604
10^29: 43.155008138949052006407248399564471488 +- 6.5692471516109859334346990352255761282
10^30: 208.34880609780339521059826081642888703 +- 14.434292712072988691189600333588006525

Очевидно ждать чистых 21-324 до 1e28-1e29 бессмысленно.

[Yadryara]

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

Хватит ли C8-C9 для приличной точности прогноза доли чистых не уверен.

Может и не хватить, да.

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

Очевидно ждать чистых 21-324 до 1e28-1e29 бессмысленно.

И также очевидно, что прогноз vicvolf-а в 1е36 и для 21-324 завышен. Кстати, vicvolf тогда не понимал, что такое чистый кортеж, так что говорил о всех, что делает тот прогноз ещё жутче неточным.