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

[Dmitriy40]

Программа с учётом однократных и повторных двойных загрязнений:

\\v=[0,6,12,30,42,72,90,96,120,126,132,156,162,180,210,222,240,246,252];
\\v=[0, 18, 24, 54, 84, 90, 108];\\7-108-1
v=[0, 6, 18, 30, 36];
{CalcC(w)=my();
   MC = 2^(#w-1); forprime(p=3,#w, m=p-#Set(-w%p); MC *= m/p/(1 - 1/p)^#w; ); if(MC==0, return(0));
   PM = 1; forprime(p=#w+1,w[#w]/2, m=p-#Set(-w%p); PM *= m/(p - #w); ); if(PM==0, return(0));
   BC = prodeulerrat(( p^#w - #w*p^(#w-1) )/(p-1)^#w, 1, nextprime(#w+1));
   return(MC * BC * PM);
}
print("v=",v);
{dd=setminus(vector(v[#v]/2,i,i*2),v);\\Список мест загрязнений
C = CalcC(v); C1=C2=0;
printf("C =%f\n",C);
for(a=1,#dd,
   C1 += CalcC(concat(dd[a],v));\\Одинарное загрязнение
   for(b=1,a-1, C2 += CalcC(concat([dd[a],dd[b]],v)); );\\Повторные двойные загрязнения, недопустимые вернут 0
);
printf("C1=%f\n",C1);
printf("C2=%f\n",C2);
for(po=9,11, L=intnum(t=100, 10^po, 1/log(t)^#v * (C - C1/log(t) + C2/log(t)^2) ); printf("10^%u: %0.6f\n",po,L); );
quit;}

-- 21.07.2024, 13:08 --

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

Значит всё-таки комбинаторный взрыв, которого опасался чуть раньше.

Похоже да, если для 5-36 из оценки 237651 вычесть реальные чистые 226131 получим 11520, которые почти равны сумме трехкратных и более загрязнений 9579+766+28+1=10374, разницу в 1146 можно списать на погрешность, всего-то 0.51%. Т.е. для достижения хорошей точности надо учитывать не только однократные и повторные двухкратные, но и повторные трёх и более кратные загрязнения, по крайней мере пока весь хвост не станет меньше желаемой погрешности.
Надо наверное взять подлиннее паттерн, но поменьше диаметром, скажем 7-60, посчитать его докуда получится и для него попытаться учесть трёх и более кратные загрязнения.

[Dmitriy40]

Учёт повторных трёхкратных загрязнений оказался несложен:

   for(b=1,a-1,
      C2 += CalcC(concat([dd[a],dd[b]],v));\\Повторные двойные загрязнения, недопустимые вернут 0
      for(d=1,b-1, C3 += CalcC(concat([dd[a],dd[b],dd[d]],v)); );\\Повторные тройные загрязнения, недопустимые вернут 0
   );
...
for(po=9,11, L=intnum(t=100, 10^po, 1/log(t)^#v * (C - C1/log(t) + C2/log(t)^2 - C3/log(t)^3) ); printf("10^%u: %0.6f\n",po,L); );

Для 5-36 оценка улучшилась с 237651 до 224801, что меньше реального 226131 всего на 0.6%.
Но для 7-108-1 всё равно чушь. Похоже надо учитывать больше загрязнений или не только повторные или ещё как.

Да, так как у меня большие загрязнения считаются только повторные (если CalcC вернула 0, то остаток цикла не выполняется), то и комбинаторный взрыв не случается, точнее он не совсем взрывается, так, подгорает, время от учёта трёхкратных загрязнений выросло раз в 10 всего лишь, с секунды до 8с, для 7-108-1, а для 5-36 вообще лишь вдвое, с 77мс до 142мс.

Часть функции под интегралом в скобках смахивает на ряд Тейлора или аналогичный ... Может там где факториала не хватает? Хотя 5-36 предсказало отлично.

[Yadryara]

Dmitriy40, Вы взялись даже активней чем я ожидал Можно теперь я чуток отдохну

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

vicvolf, отвечу позже. Помните что сказал Мортимер Холмсу?

"Как практик Вы не знаете себе равных."

Ну вот и Дмитрий как практик не знает себе равных.

Нужно ли считать интеграл от 2-х. Теоретически да, конечно. Математики знают толк в таких вещах. Ну а практически мы видим что PARI прекрасно справляется с таким счётом для коротких паттернов, но совсем не справляется на нужной высоте для более длинных.

Дмитрий предложил обоснованный рецепт, я его поддержал. И мы получили результат, отлично согласованный с другим проверенным способом подсчёта. Могут ли два проверенных способа быть неверны? Очень вряд ли.

        Yadr         HL-1      Kprev

10^24:  11.28843 /  1.93177    5.84
10^25:  51.97412 /  8.69426    5.98
10^26: 246.69127 / 40.43282    6.10

Говорил, что кэф прибавляет по 1-2 десятых на порядок? Показывал, что он близок к 6-ти для 1е25?

Да, показывал для другого диаметра, но ведь выяснил, что от диаметра общий кэф почти не зависит.

Ну и получаются те же самые числа. Например, 8 кортежей до 1е25 — простым делением 52 на 6.

И ещё есть эффект чистоплотности. Его тоже интересно проверить.

[vicvolf]

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

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

Асимптотика в первой гипотезе Харди-Литтлвуда заключается в том, что точность прогноза количества кортежей по сравнению с фактом возрастает с ростом диапазона.

10^       HL-1      Fact  Pogresh.

8       2437.2711    159   14.3
9       2908.1197    638   3.56
10      5090.8037   2883   0.766
11     16014.133   13809   0.160
12     74214.578   71638   0.0360
13    400943.47   399276   0.00418
14   2317911.7   2318062  -0.0000648
15  13999274 
16  87556996 

Например для кортежей 7-108-1 при $10^8$ по гипотезе 2437 кортежей, а фактически 159. Зато при $10^{14}$ по гипотезе 2317911, а фактически 2318062. Обратите внимание, что при высокой точности количество кортежей большое.

Теперь в этом случае:

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

:

10^20: 0.0000000000000000000
10^21: 0.0196565776281462124
10^22: 0.0995547908122199061
10^23: 0.4378621494576471064
10^24: 1.9247740223690655377
10^25: 8.6872659204322943087
10^26: 40.4258257534193743967
10^27: 193.7728754005331360582
10^28: 954.8651781196793723739
10^29: 4827.7910944571652489437
10^30: 24999.0812869896684233021

Наибольшая точность в асимптотической формуле достигаться при максимальном диапазоне, т.е. при $10^{30}$. При этом количество кортежей достаточно большое 24999. При $10^{24}$ и $10^{25}$ количество кортежей мало, поэтому асимптотическая формула дает плохую точность (см. предыдущий пример).

-- 21.07.2024, 15:38 --

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

Нужно ли считать интеграл от 2-х. Теоретически да, конечно. Математики знают толк в таких вещах. Ну а практически мы видим что PARI прекрасно справляется с таким счётом для коротких паттернов, но совсем не справляется на нужной высоте для более длинных.

Согласен.

Цитата:

Дмитрий предложил обоснованный рецепт,

Не согласен. Доводы я привел выше. Вы можете меня слушать или нет. Моя задача предупредить.

[Dmitriy40]

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

Обратите внимание, что при высокой точности количество кортежей большое.

Только перепутали причину и следствие. Кортежей много (сильно больше начальной ошибки) - потому и точность высокая.

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

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

т.е. на бесконечности. Никто и не спорит. Вопрос о точности сильно раньше бесконечности, в интересующих нас диапазонах, а не $10^{40\ldots50}$. Где выбор $2$ в качестве границы нулевого количества не оптимален, хотя и математически разумеется верен (до $2$ никаких простых точно нет, не говоря уж про кортежи).

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

Вы можете меня слушать или нет. Я Вас предупредил.

Ваши предупреждения противоречат практике/реальности, либо слишком неточны (ошибка на 11 порядков!! Сотня триллионов кортежей там где их вообще нет ни одного!). Стоит сначала привести теорию к практике, а потом уже предупреждать.

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

Не согласен. Доводы я привел выше.

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

И ещё. Раз уж речь зашла про асимптотическое равенство, то такие формулы вообще нельзя складывать/вычитать нигде кроме как на бесконечности, всегда может появиться непрогнозируемо огромная ошибка. Т.е. не получится найти количество чистых кортежей как разницу всех и только грязных. Yadryara, о, он и Вас предупредил, рады этому, внемлем предупреждению? И будем вкуривать теорию пока не найдём точную формулу для чистых кортежей без опоры на грязные (и все суммарно)? Теория это ж сила. vicvolf, с этим я даже и не спорю. Надо только уметь прикладывать теорию к конкретным практическим вопросам, а не только к бесконечности.

-- 21.07.2024, 15:56 --

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

При $10^{24}$ и $10^{25}$ количество кортежей мало, поэтому асимптотическая формула дает плохую точность (см. предыдущий пример).

Однако для паттернов 5-36, 7-108-1 и некоторых других асимптотическая формула при правильно выбранной нулевой границе даёт очень даже хорошую точность даже с малым количеством кортежей. Т.е. это Ваше утверждение - ошибочно.
Короче так и скажите что понятия не имеете почему там $2$ в качестве нижней границы стоит и почему его нельзя изменить - и успокоимся. И даже про сумму интегралов забудем, которую Вы пытались опровергнуть (не разобравшись что на самом деле считается).

-- 21.07.2024, 16:04 --

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

Например для кортежей 7-108-1 при $10^8$ по гипотезе 2437 кортежей, а фактически 159.

И это тоже Ваша проблема! Вашей оценки! Потому что при другом выборе нижнего предела интегрирования оценка даёт:

10^7: 47.9637684137426093019
10^8: 159.7510363100900196852
10^9: 630.5776298470541474385
10^10: 2813.1679409158959862592
10^11: 13736.4157550321162497156
10^12: 71938.0164378272162999433
10^13: 398664.6792160341229239348
10^14: 2315637.1801502456532415715

Ну и где ваша хвалёная громадная погрешность, а? 160 вместо реальных 163? Это Вы называете плохой точностью, менее 2% ошибки на полутора сотнях коттежей?! Окститесь. И научитесь правильно применять теорию к практике.

[vicvolf]

Обозначим количество простых кортежей вида $p,p+2m_1,p+2m_2,...,p+2m_k$, не превосходящих $x$ - $\pi_{m_1,m_2,...,m_k}(x)$, тогда по первой гипотезе Харди-Литтлвуда:

$\pi(m_1,m_2,...,m_k)(x) \sim C(m_1,m_2,...,m_k)\int_2^x{\frac{dt}{\ln^{k-1}(t)}}$,(1)

где $C(m_1,m_2,...,m_k)$ - постоянная зависящая от вида кортежа.

Пусть нам известно количество простых кортежей определенного вида, не превосходящих $a$ - $\pi(m_1,m_2,...,m_k)(a)$ (2), тогда:

$\pi(m_1,m_2,...,m_k)(x)\sim C(m_1,m_2,...,m_k) (\int_2^a{\frac{dt}{\ln^{k-1}(t)}}+\int_a^x{\frac{dt}{\ln^{k-1}(t)}})$. (3)

Подставим (2) в (3) и получим:

$\pi(m_1,m_2,...,m_k)(x)\sim \pi(m_1,m_2,...,m_k)(a)+C(m_1,m_2,...,m_k)\int_a^x{\frac{dt}{\ln^{k-1}(t)}}$. (4)

Формула (4) это некоторая модификация первой гипотезы Харди-Литтлвуда. Она более точная, чем формула (1), так вместо приближенного значения $C(m_1,m_2,...,m_k) \int_2^a{\frac{dt}{\ln^{k-1}(t)}}$ подставляется точное $\pi(m_1,m_2,...,m_k)(a)$.

В частном случае, если нам известно об отсутствии простых кортежей определенного вида, не превосходящих $a$, т.е. $\pi(m_1,m_2,...,m_k)(a)=0$, то формула (4) имеет вид:

$\pi(m_1,m_2,...,m_k)(x)\sim C(m_1,m_2,...,m_k)\int_a^x{\frac{dt}{\ln^{k-1}(t)}}$, (5)

о которой говорил Дмитрий.

[Yadryara]

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

И ещё есть эффект чистоплотности. Его тоже интересно проверить.

Проверил. Опять подтвердился.

10^ OP    0       1       2       3       4       5       6

5     0.120   0.343   0.346   0.155   0.033   0.003   0.000
5     0.109   0.174   0.478   0.130   0.087   0.000   0.022

6     0.185   0.393   0.299   0.104   0.017   0.001   0.000
6     0.209   0.343   0.313   0.097   0.030   0.000   0.007

7     0.247   0.415   0.255   0.072   0.010   0.001   0.000
7     0.208   0.435   0.270   0.062   0.022   0.002   0.002

8     0.303   0.422   0.217   0.052   0.006   0.000   0.000
8     0.300   0.429   0.213   0.048   0.009   0.001   0.000

9     0.352   0.420   0.185   0.038   0.004   0.000   0.000
9     0.360   0.426   0.175   0.035   0.004   0.000   0.000

10    0.396   0.412   0.160   0.029   0.003   0.000   0.000
10    0.417   0.406   0.150   0.025   0.002   0.000   0.000

11    0.435   0.402   0.139   0.023   0.002   0.000   0.000
11    0.460   0.393   0.126   0.019   0.002   0.000   0.000

В верхней строчке каждой пары теоретические доли, в нижней — фактические. Для 5-36 эффект малозаметен: реальная доля чистых больше всего лишь в 1.06 раза. А вот для 7-108-1 уже в 1.24 раза:

          0       1       2       3       4       5       6       7       8

8     0.004   0.030   0.095   0.180   0.230   0.210   0.141   0.071   0.027
8     0.006   0.025   0.067   0.172   0.209   0.239   0.129   0.055   0.055

9     0.009   0.053   0.138   0.220   0.235   0.180   0.102   0.044   0.014
9     0.006   0.045   0.159   0.238   0.229   0.168   0.078   0.044   0.020

10    0.016   0.079   0.179   0.243   0.225   0.149   0.073   0.027   0.008
10    0.014   0.087   0.186   0.255   0.217   0.149   0.057   0.023   0.009

11    0.025   0.108   0.213   0.254   0.206   0.120   0.052   0.017   0.004
11    0.030   0.121   0.227   0.257   0.197   0.109   0.041   0.013   0.004

12    0.036   0.136   0.240   0.256   0.185   0.096   0.037   0.011   0.002
12    0.043   0.157   0.257   0.251   0.169   0.083   0.029   0.008   0.002

13    0.048   0.165   0.261   0.251   0.164   0.077   0.027   0.007   0.001
13    0.060   0.189   0.273   0.241   0.146   0.064   0.020   0.005   0.001

14    0.061   0.191   0.276   0.242   0.144   0.062   0.020   0.005   0.001
14    0.076   0.217   0.285   0.229   0.124   0.049   0.015   0.003   0.001

15    0.075   0.216   0.286   0.230   0.126   0.049   0.014   0.003   0.001
15    0.093   0.243   0.292   0.214   0.107   0.039   0.010   0.002   0.000

Напомню формулировку:

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

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

Три нижних левых выигрывают у верхних, остальные проигрывают. И именно для чистых выигрыш наибольший: $\dfrac{93}{75}\approx1.24$.

Программа:

(PARI)

{print();

cm = 7;
k = 8;

f=vector(15);fo=vector(15);

f[8]  = [   1,       4,       11,     28,     34,     39,     21,     9,      9,      2 ];
f[9]  = [   4,      29,     102,    153,    147,    108,    50,     28,     13,     3 ];
f[10] = [  41,     250,    536,    736,    627,    431,    166,    66,     26,     3 ]; 
f[11] = [  419,    1671,   3130,   3546,   2722,   1501,   565,    186,    56,     12 ]; 
f[12] = [  3087,   11269,  18443,  17949,  12140,  5932,   2078,   593,    125,    21 ]; 
f[13] = [  24030,  75583,  108959, 96375,  58305,  25391,  8181,   2014,   382,    48 ];
f[14] = [  177056, 502986, 661258, 530930, 288540, 114539, 33688,  7580,   1296,   170 ];
f[15] = [  1299308, 3400588, 4082114, 2996106, 1497968, 540945, 145706, 29900,  4631,   549 ];

fo[1] =    0;
fo[2] =    2;
fo[3] =    4;
fo[4] =    6;
fo[5] =    10;
fo[6] =    24;
fo[7] =    57;
fo[8] =    163;  
fo[9] =    642;  
fo[10] =   2887;   
fo[11] =   13813;   
fo[12] =   71642; 
fo[13] =   399280;  
fo[14] =   2318066;
fo[15] =   13997875;

mor=[ 
6, 
210, 
200560490130, 
2.305567963946 E36,
6.107692946593 E127,
1.959034064500 E415,
1.952288231513 E1329,
5.949067958000 E4297,
4.305235385595 E13620,
6.523576146660 E43292,
4.458746156594 E136987,
1.470555276084 E433636,
1.753664729516 E1372340,
1.672547671403 E4340851,
4.012967119696 E13731288,
2.540148384222 E43424119,
2.048235031377 E137328734 ];


predok = 53;

vc=[554408, 115745660, 7407543216, 216318061332, 3429058539864, 32521729709928, 196088606111368, 781359053318046, 2106299320426628, 3885606017883462, 4914156988792810, 4230571480579892, 2435923197894882, 907258494170660, 205839739312028, 25609408974336, 1489970557864, 36686447616];

c=vc*1.0; 

print1("   ");

for(i=1,9,
printf("       %d",
i-1));
print();print();

forprime(p=predok+1,sqrt(1e16),

 while(p^2>10^k,

if(k<10,print1(k,"   "),print1(k,"  "));
for(i=1,9,
printf("  %0.3f ",
c[i]/vecsum(c)));

print();

if(k<10,print1(k,"   "),print1(k,"  "));
for(i=1,9,
printf("  %0.3f ",
f[k][i]/fo[k]));

print();
print();

 k++);

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();

}quit;

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

[Dmitriy40]

vicvolf
Беру обратно все свои плохие/резкие слова в Ваш адрес.
И спасибо что обосновали найденное мною ухищрение.

[Yadryara]

vicvolfу тоже не мешало бы взять кое-какие слова назад.

Итак, зная среднюю ожидаемую частотность всех кортежей 19-252, равную 8.7 штук до 1е25, осталось лишь поточнее определить долю чистых. Для этого нужно побольше фактических данных.

vicvolf, теперь понятно как считается затравка? Как затем на её основе по той самой красивой формуле считаются все доли?

[Yadryara]

Однако же, сам я задолбался искать затравку для 9-144-1. В облаке нету. Еле как нашёл на 43-й странице. Обсчитал, чистоплотность снова есть и её рост тоже, чистых больше в 1.3 раза: 5.2% вместо 4.0%.

          0       1       2       3       4       5       6       7       8

8     0.001   0.006   0.028   0.075   0.140   0.192   0.200   0.163   0.106
8     0.000   0.000   0.000   0.286   0.000   0.286   0.286   0.143   0.000

9     0.002   0.015   0.053   0.118   0.183   0.209   0.183   0.125   0.068
9     0.000   0.000   0.100   0.167   0.100   0.233   0.300   0.100   0.000

10    0.004   0.026   0.082   0.157   0.210   0.207   0.156   0.092   0.043
10    0.000   0.011   0.136   0.114   0.182   0.261   0.182   0.068   0.034

11    0.007   0.042   0.113   0.190   0.222   0.192   0.127   0.066   0.027
11    0.005   0.044   0.148   0.156   0.223   0.203   0.127   0.060   0.018

12    0.012   0.060   0.144   0.215   0.224   0.172   0.102   0.047   0.017
12    0.012   0.082   0.166   0.207   0.208   0.174   0.091   0.038   0.015

13    0.017   0.080   0.172   0.232   0.218   0.151   0.081   0.034   0.011
13    0.023   0.101   0.192   0.238   0.204   0.137   0.067   0.025   0.010

14    0.024   0.100   0.198   0.242   0.207   0.131   0.064   0.024   0.007
14    0.031   0.120   0.219   0.245   0.193   0.114   0.052   0.018   0.005

15    0.031   0.122   0.220   0.247   0.194   0.112   0.050   0.018   0.005
15    0.042   0.145   0.241   0.246   0.176   0.094   0.039   0.013   0.003

16    0.040   0.143   0.238   0.247   0.179   0.096   0.040   0.013   0.003
16    0.052   0.169   0.256   0.242   0.160   0.079   0.030   0.009   0.002

[vicvolf]

Уточню степень логарифма.

Обозначим количество простых кортежей вида $p,p+2m_1,p+2m_2,...,p+2m_k$, не превосходящих $x$ - $\pi_{m_1,m_2,...,m_k}(x)$, тогда по первой гипотезе Харди-Литтлвуда:

$\pi(m_1,m_2,...,m_k)(x) \sim C(m_1,m_2,...,m_k)\int_2^x{\frac{dt}{\ln^{k+1}(t)}}$,(1)

где $C(m_1,m_2,...,m_k)$ - постоянная зависящая от вида кортежа.

Пусть нам известно количество простых кортежей определенного вида, не превосходящих $a$ - $\pi(m_1,m_2,...,m_k)(a)$ (2), тогда:

$\pi(m_1,m_2,...,m_k)(x)\sim C(m_1,m_2,...,m_k) (\int_2^a{\frac{dt}{\ln^{k+1}(t)}}+\int_a^x{\frac{dt}{\ln^{k+1}(t)}})$. (3)

Подставим (2) в (3) и получим:

$\pi(m_1,m_2,...,m_k)(x)\sim \pi(m_1,m_2,...,m_k)(a)+C(m_1,m_2,...,m_k)\int_a^x{\frac{dt}{\ln^{k+1}(t)}}$. (4)

Формула (4) это некоторая модификация первой гипотезы Харди-Литтлвуда. Она более точная, чем формула (1), так вместо приближенного значения $C(m_1,m_2,...,m_k) \int_2^a{\frac{dt}{\ln^{k+1}(t)}}$ подставляется точное $\pi(m_1,m_2,...,m_k)(a)$.

В частном случае, если нам известно об отсутствии простых кортежей определенного вида, не превосходящих $a$, т.е. $\pi(m_1,m_2,...,m_k)(a)=0$, то формула (4) имеет вид:

$\pi(m_1,m_2,...,m_k)(x)\sim C(m_1,m_2,...,m_k)\int_a^x{\frac{dt}{\ln^{k+1}(t)}}$, (5)

о которой говорил Дмитрий.

Проверка. Для простых чисел $k=0$ и на основании (1) получаем:

$\pi(x) \sim C(0,0,...,0)\int_2^x{\frac{dt}{\ln(t)}}$,

где $C(0,0,...,0)=1$.

-- 23.07.2024, 09:56 --

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

vicvolfу тоже не мешало бы взять кое-какие слова назад.

Все мы можем ошибаться, но эмоции надо держать при себе.

-- 23.07.2024, 10:02 --

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

vicvolf, теперь понятно как считается затравка? Как затем на её основе по той самой красивой формуле считаются все доли?

Как я понял это в основном нужно для определения доли чистых с целью прогноза количества чистых?

-- 23.07.2024, 10:06 --

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

vicvolf
Беру обратно все свои плохие/резкие слова в Ваш адрес.
И спасибо что обосновали найденное мною ухищрение.

Гоню обратно я огни впервые с сотворения. Ты звал меня? Чаи гони, гони поэт варенье! (Маяковский).

[Yadryara]

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

Как я понял это в основном нужно для определения доли чистых с целью прогноза количества чистых?

Совершенно верно. А теперь, говоря Вашим языком, контрольный вопрос:

И как же нам определить ту самую долю чистых?

По HL-1 её удаётся определить только для самых коротких паттернов. Уже для 7-108-1 по-хорошему надо вычислять 6-кратные загрязнения. 9-144 загрязнён ещё сильнее. Это видно из последних таблиц:

          0       1       2       3       4       5       6       7       8

15    0.075   0.216   0.286   0.230   0.126   0.049   0.014   0.003   0.001
15    0.093   0.243   0.292   0.214   0.107   0.039   0.010   0.002   0.000

15    0.031   0.122   0.220   0.247   0.194   0.112   0.050   0.018   0.005
15    0.042   0.145   0.241   0.246   0.176   0.094   0.039   0.013   0.003

Вверху — доли для 7-108-1.

Обратите внимание, на этой высоте (1е15) доли 7-кратного загрязнения 9-к (0.018 и 0.013) даже больше чем 6-кратного загрязнения 7-к (0.014 и 0.010).

Конечно радует быстрое снижение долей с ростом высоты счёта. Эх, хотел посмотреть эти же паттерны на высоте 1е25 на той же 43-й странице, но Дмитрий не показывал загрязнения больше 2-кратных.

В общем, по HL-1 подсчитать долю чистых для 19-252 пока не представляется возможным. Как быть?

[Dmitriy40]

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

Эх, хотел посмотреть эти же паттерны на высоте 1е25 на той же 43-й странице, но Дмитрий не показывал загрязнения больше 2-кратных.

Да не вопрос, вот всё что было насчитано до 1e26, в том виде как выдала программа: https://cloud.mail.ru/public/nyrv/LrqQ6k8v1
Да, некоторых паттернов там нет, хоть Вы и показали их позже 13 июня, но так и не стал считать до 1e26. Не показалось это принципиальным, скорее экстенсивным.

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

В общем, по HL-1 подсчитать долю чистых для 19-252 пока не представляется возможным. Как быть?

Я пока так и не понял почему нужен учёт сильно грязных, что там с чем пересекается. И почему для 5-36 прекрасно сработало, а для 7-60 и 7-108-1 нет.

Вот предположим, что все грязные кортежи можно разделить на несколько не пересекающихся множеств, например как при загрязнении наших кортежей двойкой и четвёркой будет три множества: с 2, с 4, без обоих. Первые два даёт HL-1, осталось понять как считать третье. Можно поделить и на несколько большее количество, например для 5-36 можно поделить на 2, 4, 14, 22, без всех этих, они все не пересекающиеся. Правда это лишь 4 варианта однократных загрязнений из 14, но уже и так даёт возможность оценить долю чистых сверху (ведь эти количества однократно грязных вычитаются из всех). Оценка конечно очень так себе, уменьшает оценку с 491318 (всех) до 410190 (якобы чистых) при точном количестве последних 226131. А если ещё предположить (неправильно!) что и остальные 10 вариантов загрязнений дадут примерно тот же эффект и аппроксимировать уменьшение от 4-х загрязнений на все 14, то оценка чистых упадёт до $491318-(491318-410190)\frac{14}{4}=207370$, что отличается от точного 226131 на 8.3%. В принципе уже неплохо, хоть и ненадёжно, и это уже нельзя назвать оценкой ни сверху, ни снизу.
Надо думать как считать все остальные загрязнения. И пока этот путь мне не кажется совсем уж бесперспективным, надо внимательнее анализировать как пересекаются множества грязных кортежей и можно ли их корректно учесть без комбинаторного взрыва.

[vicvolf]

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

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

Посмотрите здесь https://ru.wikipedia.org/wiki/%D0%A4%D0 ... 0%B8%D0%B9 для вероятностей. Ведь доли - это и есть вероятности.

[Dmitriy40]

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

Посмотрите здесь https://ru.wikipedia.org/wiki/%D0%A4%D0 ... 0%B8%D0%B9 для вероятностей. Ведь доли - это и есть вероятности.

Снова советуете/вещаете банальности. Я ведь именно так и учитываю повторные двухкратные загрязнения, вычитая $|A \cap B|$ из $|A|+|B|$. И для 7-60 и 7-108-1 работает неправильно, видимо какие-то части множеств учитываются более чем однажды. Но формула очевидно верна, с этим не спорю.
А если Вы про цепочку сумм с чередующимися знаками, то и это есть в программе (вычисление C3). И тоже не работает для 7-60 и 7-108-1, где-то я ошибся. Либо асимптотическое равенство даёт слишком большую ошибку и надо более аккуратно его вычислять.

Кстати, чтобы не таскать везде степень $k+1$ и чтобы длина кортежа была $k$ вместо $k+1$, проще обозначить кортеж как $p+m_1, p+m_2 ,p+m_3,\ldots, p+m_k$ с подразумеваемым условием $m_1=0$ и всё. Формулы упростятся,, а суть не изменится.

-- 23.07.2024, 18:50 --

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

Либо асимптотическое равенство даёт слишком большую ошибку и надо более аккуратно его вычислять.

Проверил для 7-60, похоже дело именно в этом: для 1e26 оценка чистых по двухкратным загрязнениям даёт 10877746786252422.166714/17785940087194066.809622=0.611592 (интеграл беру с 2) при точной оценке в 0.569604, что всего на 7.3% меньше. А по трёхкратным 10680423352838930.024627/17785940087194066.809622=0.600498, что больше 0.569604 на 5.4%. С учётом всё больших загрязнений точность повышается, как и должно быть.