2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему На страницу Пред.  1 ... 8, 9, 10, 11, 12, 13, 14 ... 72  След.
 
 Re: кортежи последовательных простых. ключ к 19-252
Сообщение17.03.2024, 18:00 
Заслуженный участник


20/08/14
11780
Россия, Москва
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 непонятно ... Но идея вычёркивать запрещённые комбинации (их проще пересчитать) перспективная.

 Профиль  
                  
 
 Re: кортежи последовательных простых. ключ к 19-252
Сообщение17.03.2024, 18:31 
Аватара пользователя


29/04/13
8128
Богородский
Спасибо, обдумаю.

А между тем 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$.

 Профиль  
                  
 
 Re: кортежи последовательных простых. ключ к 19-252
Сообщение17.03.2024, 20:18 
Аватара пользователя


29/04/13
8128
Богородский
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, ...$

 Профиль  
                  
 
 Re: кортежи последовательных простых. ключ к 19-252
Сообщение17.03.2024, 22:01 
Заслуженный участник


20/08/14
11780
Россия, Москва
Yadryara в сообщении #1633170 писал(а):
Первое число $372$ это как раз и есть чистое количество $valids=5$, то есть $valids=5, len=5$,
В каких пределах? До $10^8$ таких пятёрок $197$, до $10^9$ их $1501$, а до $31^2=961$ их нет.

 Профиль  
                  
 
 Re: кортежи последовательных простых. ключ к 19-252
Сообщение18.03.2024, 02:55 
Аватара пользователя


29/04/13
8128
Богородский
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$$

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

 Профиль  
                  
 
 Re: кортежи последовательных простых. ключ к 19-252
Сообщение18.03.2024, 03:59 
Заслуженный участник


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

 Профиль  
                  
 
 Re: кортежи последовательных простых. ключ к 19-252
Сообщение18.03.2024, 07:29 
Аватара пользователя


29/04/13
8128
Богородский
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%.

 Профиль  
                  
 
 Re: кортежи последовательных простых. ключ к 19-252
Сообщение18.03.2024, 11:13 
Аватара пользователя


29/04/13
8128
Богородский
Всё-таки вернусь к более простым паттернам. А то вдруг люди всё ещё не понимают о чём речь. Первые 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, но для этого паттерна устаканивание уж больно долго не наступает.

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

 Профиль  
                  
 
 Re: кортежи последовательных простых. ключ к 19-252
Сообщение18.03.2024, 18:19 
Аватара пользователя


29/04/13
8128
Богородский
Вот фрагмент такой же таблицы для паттерна 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#.

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

 Профиль  
                  
 
 Re: кортежи последовательных простых. ключ к 19-252
Сообщение18.03.2024, 20:51 
Заслуженный участник


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

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

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

 Профиль  
                  
 
 Re: кортежи последовательных простых. ключ к 19-252
Сообщение19.03.2024, 00:20 
Аватара пользователя


29/04/13
8128
Богородский
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) пока не смотрел. Может быть, если набрать побольше данных на разных паттернах, станет лучше понятно как себя ведут числа на ранних стадиях. Это само по себе интересно.

 Профиль  
                  
 
 Re: кортежи последовательных простых. ключ к 19-252
Сообщение19.03.2024, 01:10 
Заслуженный участник


20/08/14
11780
Россия, Москва
Я оказался прав: действительно, реализовав код без списков, просто с 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)]++;
Фактически код делает ровно то же что и предыдущий, только не удаляет элементы из списка, а сбрасывает соответствующие биты в числе.

 Профиль  
                  
 
 Re: кортежи последовательных простых. ключ к 19-252
Сообщение19.03.2024, 01:56 
Аватара пользователя


29/04/13
8128
Богородский
Dmitriy40 в сообщении #1633332 писал(а):
Вот и займусь пожалуй.

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

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

 Профиль  
                  
 
 Re: кортежи последовательных простых. ключ к 19-252
Сообщение19.03.2024, 04:15 
Аватара пользователя


29/04/13
8128
Богородский
Dmitriy40 в сообщении #1633303 писал(а):
что позволит за разумное время посчитать и 53# и 59#,

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

 Профиль  
                  
 
 Re: кортежи последовательных простых. ключ к 19-252
Сообщение19.03.2024, 05:17 
Заслуженный участник


20/08/14
11780
Россия, Москва
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 недостижимо ...

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 1076 ]  На страницу Пред.  1 ... 8, 9, 10, 11, 12, 13, 14 ... 72  След.

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group