Симметричные кортежи из последовательных простых чисел

[Yadryara]

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

Возможно мы оба считаем неправильно: уже первая цепочка 13-192 с начальным числом 2479672831189511 не является допустимой с точки зрения паттерна 19-252 (число 2479672831189511-30 делится на 29, т.е. при переборе вариантов 19-252 такая цепочка гарантировано найдена не будет,

Да, но это пока не колышет совершенно. Вопрос интересует конкретный: из каких групп получились эти чистые 13-ки? Две чистые группы дали прекрасные средние: 11 и 9. У меня есть ошибка? Вашу прогу не вижу, потому сказать не могу.

А почему других цепочек 219, а не 221 ?

-- 09.09.2024, 17:55 --

Вот Ваш вектор:

26 нулей
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 4, 6, 28, 54, 47, 38, 19, 8, 2, 0, 1],

Вот мой:

16 нулей + [0, 6, 18, 24, 51, 51, 36, 17, 5, 1, 0]

У кого ошибка?

[Dmitriy40]

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

А почему других цепочек 219, а не 221 ?

Потому что к маю 2024 в боинках не нашли вот эти две цепочки (это тот самый недосчитанный тогда batch87 в SPT боинке):
4874789823823097579: 0 18 24 48 60 78 84 90 108 120 144 150 168
5110045405206766183: 0 18 24 48 60 78 84 90 108 120 144 150 168
А у меня они есть и потому у меня на 2 больше. Сейчас же взял из боинка потому что помнил что там они точно есть (взял откуда быстрее вспомнил).

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

Вопрос интересует конкретный: из каких групп получились эти чистые 13-ки?

Так в этом и вопрос: каких именно групп? Они же разные для 13-192 как цепочек длиной 13 и для 13-192 как части 19-252. И первые ко вторым не приводятся! Точнее не всегда приводятся. Вы же не вычитали 30 из начального числа 13-192 чтобы перейти к начальному числу соответствующей 19-252? А я попробовал и получил вон то кратное 29 и вылет программы. Обходя который число цепочек сократилось до 155 и 99 штук.
И вопрос как считать группы остался подвешенным, я не вполне понимаю как правильно делать, ведь часть цепочек 13-192 выходит принадлежит к запрещённым вариантам, которых в vc[] просто нет и быть не может.
И соответственно непонятно кто и в чём ошибся. Может я, может Вы, может мы оба (да вдруг ещё и по разному) ... Вопрос не в ошибке вычислений, а в задаче, что именно вычислять. Раньше, с найденными цепочками в рамках поиска 19-252, такого вопроса и не стояло, все такие цепочки проходили по паттерну 19-252, а вот уже 6шт 17-240-1 Врублевского - не проходили (правда их и не обсчитывали по группам особо то, или могли тоже ошибиться).

[Yadryara]

Забыли пока про 19-252. Смотрим как себя ведут другие чистые кортежи.

После проверки по 3, 5, 7, 11, 13, 19, 23 и 29 образовалась цепочка из 13 родных и 17 чужих чисел. Как часто получается так, что все 13 родных чисел прошли все дальнейшие проверки и оказались простыми, а все 17 чужих проверки не прошли? В среднем 11 раз.

После проверки по 3, 5, 7, 11, 13, 19, 23 и 29 образовалась цепочка из 13 родных и 18 чужих чисел. Как часто получается так, что все 13 родных чисел прошли все дальнейшие проверки и оказались простыми, а все 18 чужих проверки не прошли? В среднем 9 раз.

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

[Dmitriy40]

Тогда у меня посчитано неправильно, все два (или уже три?) раза. Потому что в том или ином виде существенно опирается на паттерн 19-252. Пользуйтесь своей программой.

[Yadryara]

Ну да, всё чётко. От чистых к грязным. Стоило только перейти к тысячам. Взял буквально первый попавшийся паттерн. 11-144-4. 23 106 чистых кортежей.

         Len = 11        Valids = 11

Group                   vc      Fact  F*10^3/vc  Pred/Posl
11+11                   58        23    396.552      
11+12                  702       230    327.635      1.210
11+13                 4496      1376    306.050      1.071
11+14                14900      3817    256.174      1.195
11+15                29470      6744    228.843      1.119
11+16                34028      6494    190.843      1.199
11+17                20116      3424    170.213      1.121
11+18                 5758       869    150.920      1.128
11+19                  976       123    126.025      1.198
11+20                   88         6     68.182      1.848

[Yadryara]

То-то и оно, что это простое рассуждение пришло мне в голову ещё тогда, когда я впервые заговорил о порядке проверки:

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

Что если искать чистую 19-ку надо прежде всего среди самых чистых, то есть среди 54760 кандидатов, а затем уже среди 6792018 и так далее...

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

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

Родные — числа предписанные паттерном, чужие — нет.

valids — количество родных простых чисел на отрезке числового ряда ограниченного диаметром, len — суммарное количество родных и чужих простых чисел на том же отрезке.

Если при поиске 19-ки найден кортеж для которого $valids = 19$, а $len > 19$, то такой кортеж называю грязным.

Если при поиске 19-ки найден кортеж для которого $valids < 19$, а $len = 19$, то такой кортеж называю неполным.

Если при поиске 19-ки найден кортеж для которого $valids = len = 19$, то такой кортеж называю чистым. Это и есть искомая 19-ка.

Следуя покерной терминологии, неполные кортежи также различаю по близости к цели: $valids = len - 1$ это дро, а $valids = len - 2$ — ранер-ранер.

Вот только что был приведён пример найденного дро:

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

19+29: 6887962633672761855714167: [ +0, 6, 12, -26, 30, 42, 72, 90, 96, 120, 126, 132, 156, 162, 180, 210, 222, 240, 246, 252], len=19, valids=18

Итак, ключ найден и предъявлен.

Осталось разобраться насколько же он ускоряет поиск. Для этого нужны другие тесты. Dmitriy40, Вы прикидывали как приспособить Вашу прогу для поиска 17-к. Лучше поискать другие цепочки, которые гораздо короче и потому быстрей находятся — 9-ки, 11-ки. Причём лучше выбирать такие кортежи, ожидаемое количество которых в проверяемом диапазоне около 11 штук.

Видимо, метод более эффективен для коротких кортежей.

[Yadryara]

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

Лучше поискать другие цепочки, которые гораздо короче и потому быстрей находятся — 9-ки, 11-ки. Причём лучше выбирать такие кортежи, ожидаемое количество которых в проверяемом диапазоне около 11 штук.

Посмотрел где сколько решений, начиная с 7-к:

  Pattern   Naideno  Diapazon        Time

   7-60    301 kort.    0-29#
   7-72-1  187 kort.    0-29#
   7-72-2  228 kort.    0-29#

   9- 84     7 kort.    0-29#
   9- 96     2 kort.    0-29#
   9-108     2 kort.    0-29#

   9- 96    19 kort.    0-31#                  setsearch   7.1 min
   9-108    16 kort.    0-31#     25.0 min     setsearch   9.5 min

Последний паттерн более-менее подходит. Среднее время нахождения кортежа:

$$\frac{25\cdot60}{16}\approx 94 sec/kort$$

Вот варианты разбиения этого паттерна по группам для 29#/17:

    9    9                                                    9
    +    +                                                    +
    6    7                                                   15
  [12, 692, 5806, 26648, 69110, 104178, 94798, 46586, 9906, 664]

Теперь надо перебирать кандидатов из групп 9+6, 9+7 и так далее. Как только 1-й чистый кортеж найдётся, засечь время. Оно в среднем должно быть меньше 94 секунд. А на сколько? Вот это и надо выяснить тестами.

[Yadryara]

Что-то тишина. Я конечно сам попытался применить описанный метод.

Результат даже лучше ожиданий. С использованием setsearch среднее время нахождения кортежа — 36 секунд.

Я решил сделал разбивку по-другому, по 13#:

    9   9   9   9   9
    +   +   +   +   +
   11  12  13  14  15
  [ 6, 18, 52, 38, 14]

Понятно, что родных чисел всегда 9, это же 9-ка, так что упрощаю, группы различаю только по количеству чужих чисел:

   11  12  13  14  15
  [ 6, 18, 52, 38, 14]

Понятно, что если брать две самых чистых группы с 11-ю и 12-ю чужими числами, то, скорей всего, из 16-ти несколько кортежей найдётся.

Посему дальнейшую проверку делал только для этих групп. И вуаля! 4 кортежа нашлись всего за 76 секунд, то бишь по 19 секунд на кортеж вместо 36.

Прогу пока не показываю, она сырая. Ещё поиграюсь с параметрами.

16 кортежей покажу, проверьте, кто хочет:

1   185383291519   108
2   68245271009   108
3   189298731179   108
4   3905211463   108
5   169573477499   108
6   909894593   108
7   71200853743   108
8   117831765659   108
9   64921399163   108
10   178033552969   108
11   147674328983   108
12   21088950343   108
13   161539051673   108
14   125368946849   108
15   168011019049   108
16   66729642719   108

[Dmitriy40]

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

[Yadryara]

А я раньше говорил про количество. Что именно лучше считать? Но время всё-таки важнее. Надо сравнивать на одном и том же компе.

Вот как считал старым способом.

(Оффтоп)

allocatemem(2^28);

{print();

t0=getwalltime();

v=[0, 18, 24, 48, 54, 60, 84, 90, 108];

kkor=0;
w=2*3*5*7*11*13*17*19*23*29*31;

kkan=1;m=vector(31,i,[]);
forprime(p=2,#m, m[p]=setminus(vector(p,i,i-1),Set(-v%p));
printf("%d: x %d: %d\n",p,#m[p],m[p]);
kkan*=#m[p]);print();

print(w);print();
print(kkan);print();

mm=vector(200,i,[]); forprime(p=14,#mm, mm[p]=Set(-v%p));

x0=Mod(1,2);
foreach(m[31],m31,
foreach(m[29],m29,
foreach(m[23],m23,
foreach(m[19],m19,
foreach(m[17],m17,
foreach(m[13],m13,
foreach(m[11],m11,
foreach(m[7],m7,
foreach(m[5],m5,
foreach(m[3],m3,
kan=lift(chinese([x0,Mod(m31,31),Mod(m29,29),Mod(m23,23),Mod(m19,19),Mod(m17,17),
Mod(m13,13),Mod(m11,11),Mod(m7,7),Mod(m5,5),Mod(m3,3)]));
no++;

forprime(p=32,#mm, if(setsearch(mm[p], kan%p), next(2)));

if(ispseudoprime(kan)
&& nextprime(kan+1)-kan==v[2]
&& nextprime(kan+v[2]+1)-kan==v[3]
&& nextprime(kan+v[3]+1)-kan==v[4]
&& nextprime(kan+v[4]+1)-kan==v[5]
&& nextprime(kan+v[5]+1)-kan==v[6]
&& nextprime(kan+v[6]+1)-kan==v[7]
&& nextprime(kan+v[7]+1)-kan==v[8]
&& nextprime(kan+v[8]+1)-kan==v[9],

kkor++;
print(kkor,"   ",kan);
);

))))))))));

print();print();
print(kkan);
print(no);

print();
print(strtime(getwalltime()-t0));
print();

quit;}

А вот так новым.

(Оффтоп)

{print();

t0=getwalltime();

v=[0, 18, 24, 48, 54, 60, 84, 90, 108];

d=v[#v];

a=setminus(vector(d/2,i,i*2),v);

vdel   = [3,5,7,11,13];
vdelob = [3,5,7,11,13,17,19,23,29,31];pro=1; w=2*vecprod(vdel);

kgr=vector(15);slc=0;kkor=0;

print(w);
print();

m=vector(31,i,[]);

for(j=1, #vdelob, p=vdelob[j];

m[p]=setminus(vector(p,i,i-1),Set(-v%p));pro*=#m[p];

printf("%d:x%d:%d:   %d\n",p,#m[p],m[p],pro););

mm=vector(200,i,[]); forprime(p=32,#mm, mm[p]=Set(-v%p));

x0=Mod(1,2);

foreach(m[13],m13,
foreach(m[11],m11,
foreach(m[7],m7,
foreach(m[5],m5,
foreach(m[3],m3,

y=chinese([x0,Mod(m3,3),Mod(m5,5),Mod(m7,7),Mod(m11,11),Mod(m13,13)]);

x=lift(y);

kkan++;

lc=0;

for(i=1, #a,

for(j=1, #vdel, p=vdel[j];

if((x+a[i])%p==0, next(2)));

lc++);
kgr[lc]++;

if(lc<=12,

print();print1(lc);

foreach(m[31],m31,
foreach(m[29],m29,
foreach(m[23],m23,
foreach(m[19],m19,
foreach(m[17],m17,
kan=lift(chinese([y,Mod(m31,31),Mod(m29,29),Mod(m23,23),Mod(m19,19),
Mod(m17,17)]));
no++;

forprime(p=32,#mm, if(setsearch(mm[p], kan%p), next(2)));

if(ispseudoprime(kan)
&& nextprime(kan+1)-kan==v[2]
&& nextprime(kan+v[2]+1)-kan==v[3]
&& nextprime(kan+v[3]+1)-kan==v[4]
&& nextprime(kan+v[4]+1)-kan==v[5]
&& nextprime(kan+v[5]+1)-kan==v[6]
&& nextprime(kan+v[6]+1)-kan==v[7]
&& nextprime(kan+v[7]+1)-kan==v[8]
&& nextprime(kan+v[8]+1)-kan==v[9],

kkor++;
print();
print(kkor,"   ",kan);
);

)))));

);

)))));

print();
print(kkan);
print(no);

print();print(kkan, "   ",kgr[11..#kgr], "   ",vecsum(kgr));print();

print();
print(strtime(getwalltime()-t0));
print();

quit;}

[Dmitriy40]

Время важнее, но оно однозначно пересчитывается из количества. На каждом компе отдельно (по разному). И количества можно сравнивать независимо от компов (скорости). Это полезнее.

[Yadryara]

Я же не против. Какие счётчики куда добавить?

[Dmitriy40]

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

[Yadryara]

Окей, воткнул счётчик прямо перед ispseudoprime.

Результаты:

Старый способ:

1    185383291519     54872
2     68245271009     78498
3    189298731179    235226
4      3905211463    296936
5    169573477499    429969
6       909894593    537207
7     71200853743    788833
8    117831765659    855946
9     64921399163    897664
10   178033552969    942459
11   147674328983    980790
12    21088950343   1006275
13   161539051673   1037528
14   125368946849   1115123
15   168011019049   1374866
16    66729642719   1544144

Новый:

1   168011019049    47137
2    68245271009   110178
3      909894593   174991
4   169573477499   198739

То есть когда новая программа пришла на проверку кортежа в 47137-й раз, 1-й кортеж был обнаружен.

[Yadryara]

Да, видно что результативность новым методом выше. И всё-таки смотреть по времени мне больше нравится, это же комплексная оценка. И её удалось ещё существенно улучшить!

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

Ещё поиграюсь с параметрами.

Разбивку по группам сделал по 17#, а количество чужих не более 11. И всего лишь за 78 секунд было найдено 6 кортежей. 13 секунд на кортеж! Это вам не 36 секунд старым способом.

Я писал об ожидании ускорения в 1.8 раза, а тут 2.7 раза.

Ну а сами кортежи и количество проверок вот:

1   169573477499   28046
2   161539051673   71289
3     3905211463   130044
4    68245271009   149493
5   168011019049   186013
6   117831765659   298342

Разбивка по группам вот:

Чужих       9  10   11   12   13  14  15
Вариантов   2  50  156  388  320  98  10         1024