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

[Dmitriy40]

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

А что за 6-30 ? Я говорил про 5-60.

Опечатался.

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

И ни черта-то я не понял пока.

Чего именно? Ваш внутренний цикл считает в kps сколько элементов из a[] не разделились на простые 2-29 если к ним добавить kan, которая получается из КТО из остатков по тем же самым простым. Т.е. считается сколько (a[]+kan)%p>0, что равно a%p+kan%p (ну с коррекцией если сумма больше p-1), но a%p это константа, а kan%p как раз и называются m3,m5,m7 и т.д. Потому можно из полного списка a[] оставить только те элементы, которые не разделились на 3 (для каждого m3), потом из получившегося списка оставить что не разделились на 5 (тоже с учётом m5), и т.д. Это и делает каждый select. И тогда kps просто равна длине оставшегося списка (плюс 5=#v) так как эти элементы не разделились ни на одно из простых, что и требовалось.

-- 17.03.2024, 18:23 --

И знаете, мне вот кажется что можно обойтись и не вложенными циклами по простым, а просто подряд их выполнить ... Т.е. общее количество итераций будет не произведением количества допустимых остатков, а их суммой. Ведь для каждого конкретного m3 для каждого элемента a[] которые попали на кратное 3 известно их общее количество, оно равно ko/#m[3], можно эту величину вычесть из всех таких элементов an[], который изначально заполнить величиной ko. Или не ko, а mor и тогда не ko/#m[3], а mor/3, надо додумать. Правда как из an[] получить vc[] или kps непонятно ... Но идея вычёркивать запрещённые комбинации (их проще пересчитать) перспективная.

[Yadryara]

Спасибо, обдумаю.

А между тем 31# для 5-60 уже обсчитан. Каких-то 36 минут! И да, точное совпадение с

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

Предполагая, что устаканивание произойдёт уже на следующем шаге, я посчитал по формулам:

31#
 372   49228   1400322   14849698   72373736   179254380   235010290   160650282   53186652   7481680   342144 ;     sum = 724598784

Собственно, я в этом прогнозе был уверен на 95-99%.

Первое число $372$ это как раз и есть чистое количество $valids=5$, то есть $valids=5, len=5$, второе число $49228$ это $valids=5, len=6$ и т. д. вплоть до $valids=5, len=15$.

[Yadryara]

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

Теперь уже и для четвёрок 6-6-18:

А теперь и для центральных пятёрок 24-6-6-24.

Степень 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

Тенденция снова ожидаемо повторилась.

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

И формулы получаются жутко красивые. Покажу позже.

Показываю. В качестве начальных значений беру строку для 29#:

c5= 0; c6= 372; c7= 19964; c8= 307062; c9= 1946818; c10= 5908748;
c11= 9195112; c12= 7301150; c13= 2741054; c14= 427520; c15= 21384;

А следующая строка и её сумма считаются так:

c5=c5*(p-5) + 1*c6;
c6=c6*(p-6) + 2*c7;
c7=c7*(p-7) + 3*c8;
c8=c8*(p-8) + 4*c9;
c9=c9*(p-9) + 5*c10;
c10=c10*(p-10) + 6*c11;
c11=c11*(p-11) + 7*c12;
c12=c12*(p-12) + 8*c13;
c13=c13*(p-13) + 9*c14;
c14=c14*(p-14) + 10*c15;
c15=c15*(p-15);

s = s*(p-5);

Где $p$ — следующее простое: $31, 37, ...$

[Dmitriy40]

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

Первое число $372$ это как раз и есть чистое количество $valids=5$, то есть $valids=5, len=5$,

В каких пределах? До $10^8$ таких пятёрок $197$, до $10^9$ их $1501$, а до $31^2=961$ их нет.

[Yadryara]

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

До $10^8$ таких пятёрок $197$, до $10^9$ их $1501$, а до $31^2=961$ их нет.

Так я эти числа как раз и привёл, см. левый и правый столбцы:

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

Степень 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

О каких пределах спрашиваете?

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

Таким образом, частотность у нас 331 тысяча на 200 ярдов. А в среднем на тысячу сколько? Понятно сколько:

$$\frac{331776\cdot1000}{200560490130}$$

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

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

И это число в среднем столбце, в самом верху.

[Dmitriy40]

Всё, теперь понял.
Как-то отношение грязных к чистым ну совсем не радует, почти 2млн для 31#.

[Yadryara]

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

Как-то отношение грязных к чистым ну совсем не радует, почти 2млн для 31#.

Впоследствии, для больших значений удобнее говорить о доле чистых среди всех. Если для $31\#$ (простые до $10^3$) она действительно крошечная, то затем она весьма быстро растёт.

Для $97\#$ (простые до $10^4$)

$\dfrac {1485487291820451372306983953984} {2400180841066841191758378383179776} \approx 0.0006$

Для $313\#$ (простые до $10^5$) $ \approx 0.006$

Для $997\#$ (простые до $10^6$) $ \approx 0.020$

Для $99991\#$ (простые до $10^{10}$) $ \approx 0.124$

То бишь 12% уже есть, а стремится она, понятное дело, к 100%.

[Yadryara]

Всё-таки вернусь к более простым паттернам. А то вдруг люди всё ещё не понимают о чём речь. Первые 4 позиции паттерна 19-252 — это четвёрка 6-6-18.

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

Число, которое не делится нацело на все простые от $2$ до $31$ включительно, назову $pp31$.

Сейчас я их называю малопростыми. Количество кортежей с такими числами $pp5$ здесь указано в первой строке, $pp7$ — во второй и $pp31$ — в последней. $c4$ это кортежи с $valids=4, len=4$, а $c9$ — с $valids=4, len=9$.

   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

  23#     12351    212718    890481   1165320    469710    50400        2800980

  29#    521493   6886194  23977023  27515880  10115910  1008000       70024500

  31#  20966505 226995090 681973215 700844760 237705930 22176000     1890661500

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

c4 = 0; c5 = 3; c6 =  93; c7 = 354; c8 = 261; c9 = 45;

и считаем следующие строки и их суммы рекуррентно:

c4=c4*(p-4) + 1*c5;
c5=c5*(p-5) + 2*c6;
c6=c6*(p-6) + 3*c7;
c7=c7*(p-7) + 4*c8;
c8=c8*(p-8) + 5*c9;
c9=c9*(p-9);

s = s*(p-4);

Где $p$ — следующее простое: $17, 19, ...$

А считать по формулам, пусть даже и огромные числа, намного быстрее чем перебором.

Где я эти формулы взял? Подметил закономерности и вывел.

Аналогичные формулы будет работать и для 19-252, но для этого паттерна устаканивание уж больно долго не наступает.

Можно ли хотя бы примерно оценить искомые значения пораньше? Вот об этом я и спрашиваю господ математиков.

[Yadryara]

Вот фрагмент такой же таблицы для паттерна 19-252. Она в два раза шире, ибо продолжается до 49 ($valids=19, len = 49$).

p#    29   30   31    32     33      34       35       36        37        38

29#                                                                        24

31#                                                    24       488      2932

37#                           4      98     1006     9158     51810    195582

41#              4   102   1814   19784   166006   947414   3653662  10108734  

43#    2  118 2578 36174 371608 2856156 15702392 62086738 180749476 395325934

Устаканивание произойдёт, когда значение для $valids=19, len = 19$ станет отличным от нуля. Ориентировочно при 83# - 89#.

Досчитать до туда перебором пока нереально. Предстоит понять что
могут дать закономерности в имеющихся числах. А они есть.

[Dmitriy40]

Да, я тоже посчитал вчера все до 43# для 19-252, цифры совпадают с Вашими. Интересно что уже c50 после 17# везде нулевой.

С другой стороны, выполняемые операции в каждом цикле очень просты, фактически это просто побитовое И с одним из m[p] вариантов, которые легко посчитать заранее и в цикле просто выбирать один из. Есть надежда что на нормальном языке можно сделать сильно быстрее, что позволит за разумное время посчитать и 53# и 59#, что вероятно даст ненулевой c23. И, возможно, станет возможным применить Ваши формулы, необязательно ждать ненулевого c19, выше для 6-6-18 Вы именно так и взяли, предыдущее простое перед c4>0.

А считать далее 67# (ну или 71#) вообще бессмысленно, всего за двух-трёхкратное время (на PARI) можно вычислить КТО и проверить на кортеж, а уж дотуда он первый должен быть.

[Yadryara]

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

Интересно что уже c50 после 17# везде нулевой.

Раньше был и c60 для 7#. Я так понимаю, что если уж по модулю 19 запретились все варианты, начиная с c50, то им уже и неоткуда взяться в дальнейшем.

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

выше для 6-6-18 Вы именно так и взяли, предыдущее простое перед c4>0.

И для 24-6-6-24 ещё выше — тоже. Ещё раньше я прикидывал, что центральная 7-ка 7-72 (6-24-6-6-24-6) тоже поддаётся обсчёту (максимум — c18). Центральную 9-ку (9-108) пока не смотрел. Может быть, если набрать побольше данных на разных паттернах, станет лучше понятно как себя ведут числа на ранних стадиях. Это само по себе интересно.

[Dmitriy40]

Я оказался прав: действительно, реализовав код без списков, просто с bitand чисел из векторов, получил ускорение ещё почти в 9 раз. Теперь можно на PARI посчитать и 47# для 19-252 меньше чем за сутки.
Но учитывая простоту вычислений в циклах (фактически одна операция логического И) это лучше сделать на С или асме. И дотянуться до 53# или 59# (может быть лишь многопоточно). Вот и займусь пожалуй.

Код (только новые куски):

am=vector(#m,i,[]);
forprime(p=2,#m,
   m[p]=setminus(vector(p,i,i-1),Set(-v%p));
   am[p]=vector(p-1,i,fromdigits(Vecrev(apply(t->(t+i)%p>0,a)),2));\\Для каждого числа в векторе выставим бит если соответствующий элемент a[] плюс смещение не делится на простое
);
a2=2^#a-1;\\Изначально все элементы нужны
foreach(m[3],m3, a3=bitand(am[3][m3],a2);
foreach(m[5],m5, a5=bitand(am[5][m5],a3);
foreach(m[7],m7, a7=bitand(am[7][m7],a5);
foreach(m[11],m11, a11=bitand(am[11][m11],a7);
foreach(m[13],m13, a13=bitand(am[13][m13],a11);
foreach(m[17],m17, a17=bitand(am[17][m17],a13);
foreach(m[19],m19, a19=bitand(am[19][m19],a17);
foreach(m[23],m23, a23=bitand(am[23][m23],a19);
foreach(m[29],m29, a29=bitand(am[29][m29],a23);
foreach(m[31],m31, a31=bitand(am[31][m31],a29);
foreach(m[37],m37, a37=bitand(am[37][m37],a31);
foreach(m[41],m41, a41=bitand(am[41][m41],a37);
   vc[#v+hammingweight(a41)]++;

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

[Yadryara]

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

Вот и займусь пожалуй.

Ой, спасибо. Предыдущие ускорения вроде понятны, нынешнее посмотрю.

А я пока по новой шерстил короткие паттерны.

[Yadryara]

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

что позволит за разумное время посчитать и 53# и 59#,

Ещё есть такое соображение: поскольку паттерн 19-252 симметричный, нужно считать ровно половину интервала, например 53#/2 и 59#/2. И все числа в таблице будут ровно в 2 раза меньше.

[Dmitriy40]

Yadryara
Написал. Даже AVX не пригодился, просто обычный асм х64. Скорость ещё почти в 800 раз выше! Это уже со счётом лишь половины (но числа в таблице сразу удвоил). Все числа 23#-43# выдаются правильно, 43# считается 2 секунды, 47# минуту, 53# полчаса, запустил 59# в три потока (в четвёртом считается 47# на PARI для образца), к обеду досчитается всё. Пока покажу 47# и 53# (c19-c50):

47#:  0,  0,  0,  0,  0,  0,  0,  0,   0,    24,   1406,   34278,   520308,   5590512,   44192112,   255924622,  1087592188,   3438714568,   8217471808,  14998221970,  20942301992,  22275622040,  17925228472,  10827430718,   4874885124,  1630911948,  406659102,   75530368,   9994728,   810792,  27480,  0, sum=107017666560
53#:  0,  0,  0,  0,  0,  0,  0,  0, 178, 16902, 460544, 7121330, 78869428, 657860428, 4116175026, 19280190180, 68067144514, 183171836012, 379227347730, 605935215088, 745332928752, 702113842442, 503399988380, 272878823040, 111161557082, 33924337564, 7758154760, 1318925414, 158040254, 11479392, 348600,  0, sum=3638600663040

Эх, замедлилось продвижение к c19, всего лишь c27. Похоже даже если ещё немного ускорить (раза в полтора-два, резервы ещё есть), всё равно c19>0 недостижимо ...