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

[Yadryara]

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

Т.е. флуктуации могут быть достаточно сильными
[...]
Так что надежда есть.

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

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

Потому что автору алгоритма плевать на скорость и тысячи/миллионы лет счёта её не пугают. Почему они не пугают остальных участников — вопрос более интересный, видимо никто из них просто не интересовался (или не добился адекватного ответа) потребным временем, что-то там считается и ладно.

Да, вопрос был не об авторе, вопрос об участниках. Наш форум-то читают участники Боинк-Герасима? Если да, прошу высказываться. Почему нужно считать более медленным(в сотни-тысячи раз?) способом??

Dmitriy40
Ваши способы ускорения процесса прокомментировать пока не могу. Подозреваю, Вы знаете что делать, лучше чем кто бы то ни было здесь.

[Dmitriy40]

Досчиталось до очередной вехи, покажу прогресс после 21.07:
327480747328610662288037: [ 0, 6, 12, 30, +42, 72, 90, 96, 120, 126, 132, 156, 162, 180, 210, 222, 240, 246, 252], len=18, valids=18
С одной ошибкой.
277053177769543606825607: [ 0, 6, 12, 30, 42, +72, 90, 96, 120, 126, 132, 156, 162, 180,+210, 222, 240, 246, 252], len=17, valids=17
286256141888020995520211: [ +0, 6, 12, 30, 42, +72, 90, 96, 120, 126, 132, 156, 162, 180, 210, 222, 240, 246, 252], len=17, valids=17
309436831159079027513491: [ 0, 6, 12, 30, 42, 72, 90, 96,+120, 126,+132, 156, 162, 180, 210, 222, 240, 246, 252], len=17, valids=17
348179697930199809433141: [ 0, 6, 12, 30, 42, 72, 90, +96, 120, 126, 132, 156, 162, 180,+210, 222, 240, 246, 252], len=17, valids=17
С двумя ошибками.
271752951257156063690531: [ 0, 6, 12, 30, 42, 72, -78, 90, 96, 120, 126,+132, 156, 162, 180,-188, 210, 222, 240, 246, 252], len=20, valids=18
301830852532980289784801: [ 0, 6, 12, 30, 42, -50, 72, 90, 96, 120, 126, 132, 156, 162,-170, 180, 210, 222, 240,+246, 252], len=20, valids=18
18 простых на своём месте.
347681709124158402217151:[0, 6, 12, 30, 42, 72, 90, 96, 120, 126, 132, 156, 162, 180, 182, 212, 240, 246, 252], valids=17
Две дырки (выделены жирным).

(Немного статистики и прикидок)

Цепочек с 17-ю верными простыми (т.е. valids=17) найдено 525шт, с 18-ю 28шт (цепочки сильно дальше основного диапазона счёта не учитываю), отношение получается 525:28 или почти 19:1, если бы это отношение сохранилось и для 19-ти верных простых, то должно бы уже быть найдено одна-две таких цепочек (не обязательно решений), однако их нет ни одной ...
Отношение len=17,valids=17 к len=18,valids=18 составляет 26:6 или больше 4:1, тоже получается пора бы цепочке с 19-ю простыми (и это уже именно решение).
Пора бы уже хоть чему-нибудь найтись ...

[gris]

новый мировой рекорд по сабжу:

5179852391836338871: 0 12 18 28 46 76 78 120 186 210 226 232 238 300 306 312 328 352 418 460 462 492 510 520 526 538

Это самый длинный на сегодня симметричный кортеж из последовательных простых чисел!
<......................>

[Yadryara]

Вы так сообщили, что могут подумать будто это Ваш мировой рекорд.

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

Запущен новый-старый Боинк-проект на основе программы whitefox.

Новый мировой рекорд был установлен как раз в этом проекте и заключается в обнаружении кортежа длиной $26$ :

https://boinc.termit.me/adsl/spt_list.php?k=26

Этот проект продолжает работать. Производительность увеличилась и превысила 5 терафлопс.

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

То есть весьма немало компов продолжают считать по столь чудовищно неэффективному алгоритму.

И ещё две недели считали. Теперь счёт в том проекте остановлен.

[Yadryara]

Begemot82 в сообщении #1057373 писал(а):

Постановку задачи можно переписать по другому.
Для поиска симметричного кортежа из 19 последовательных простых чисел с минимальным диаметром 252 надо в последовательности $Q_k=2787151+9699690k$ найти такие k ( k=0,1,2... ), чтобы
все числа вида $Q_k + d_i$ были последовательными простыми числами. Здесь $d_i$ принадлежат кортежу

0  6  12  30  42  72  90  96  120  126  132  156  162  180  210  222  240  246  252

Для поиска вместо 2787151 можно взять любое из 383 чисел

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

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

Смотрел, какие возможны остатки для этого паттерна и сколько их.

$\tikz[scale=.08]{ \draw[step=10cm] (0,210) grid +(170,20); \node at (5,225) {\text{Mod}}; \node at (15,225){\text{2}}; \node at (25,225){\text{3}}; \node at (35,225){\text{5}}; \node at (45,225){\text{7}}; \node at (55,225){\text{11}}; \node at (65,225){\text{13}}; \node at (75,225){\text{17}}; \node at (85,225){\text{19}}; \node at (95,225){\text{23}}; \node at (105,225){\text{29}}; \node at (115,225){\text{31}}; \node at (125,225){\text{37}}; \node at (135,225){\text{41}}; \node at (145,225){\text{43}}; \node at (155,225){\text{47}}; \node at (165,225){\text{53}}; \node at (5,215){\text{Ost}}; \node at (15,215){\text{1}}; \node at (25,215){\text{2}}; \node at (35,215){\text{2}}; \node at (45,215){\text{2}}; \node at (55,215){\text{2}}; \node at (65,215){\text{2}}; \node at (75,215){\text{2}}; \node at (85,215){\text{6}}; \node at (95,215){\text{6}}; \node at (105,215){\text{12}}; \node at (115,215){\text{12}}; \node at (125,215){\text{20}}; \node at (135,215){\text{24}}; \node at (145,215)[red]{\text{23}}; \node at (155,215)[red]{\text{26}}; \node at (165,215)[red]{\text{32}}; }$

Для $19\#$ перемножением чисел нижней строки как раз получаем $384$ различных остатка о которых говорил Begemot82. Для $41\#$ получаем $159252480$ различных остатков, что примерно соответствует вышеупомянутым двумстам миллионам Dmitriy40.

Красным цветом отметил сомнительные количества остатков. Их может быть и побольше.

[Dmitriy40]

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

Смотрел, какие возможны остатки для этого паттерна и сколько их.

Эту табличку достаточно просто получить для любого паттерна (и я уже показывал такую программку):

? v=[0,6,12,30,42,72,90,96,120,126,132,156,162,180,210,222,240,246,252];
? forprime(p=2,67, m=setminus(vector(p,i,i-1),Set(-v%p)); print(p,": ",m,", len=",#m);)
2: [1], len=1
3: [1, 2], len=2
5: [1, 2], len=2
7: [3, 4], len=2
11: [4, 8], len=2
13: [3, 5], len=2
17: [1, 2], len=2
19: [2, 3, 11, 12, 16, 17], len=6
23: [3, 9, 10, 14, 15, 21], len=6
29: [1, 2, 3, 4, 5, 6, 7, 8, 11, 14, 24, 27], len=12
31: [5, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 22], len=12
37: [1, 3, 4, 6, 8, 9, 10, 11, 14, 17, 18, 20, 24, 26, 27, 30, 33, 34, 35, 36], len=20
41: [1, 4, 5, 7, 9, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 26, 28, 30, 31, 34, 37, 39], len=24
43: [2, 4, 7, 8, 11, 15, 17, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 32, 34, 38, 41, 42], len=24
47: [1, 2, 3, 6, 7, 10, 11, 12, 14, 16, 18, 19, 20, 23, 24, 27, 28, 29, 31, 33, 34, 37, 38, 39, 40, 43, 44, 46], len=28
53: [1, 4, 5, 6, 7, 8, 9, 12, 14, 15, 17, 18, 20, 21, 22, 24, 26, 28, 29, 30, 31, 35, 36, 37, 38, 40, 42, 44, 45, 46, 48, 49, 51, 52], len=34
59: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 16, 18, 19, 20, 23, 24, 25, 27, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 44, 48, 50, 52, 54, 58], len=40
61: [1, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 20, 23, 24, 25, 28, 29, 30, 33, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 52, 54, 56, 58, 60], len=42
67: [1, 3, 4, 5, 6, 7, 9, 10, 11, 12, 13, 15, 17, 18, 19, 20, 23, 24, 26, 27, 29, 30, 31, 32, 33, 34, 35, 36, 40, 41, 42, 43, 47, 48, 49, 50, 51, 52, 53, 54, 56, 57, 59, 60, 63, 64, 65, 66], len=48

Но 200млн вариантов моя программа использует лишь для более длинных паттернов, конкретно для этого ограничивается 37# и 6.636млн - следующее значение 159млн уже не влезает в память:

n=19, max=252, x: 0 6 12 30 42 72 90 96 120 126 132 156 162 180 210 222 240 246 252
Size:6.636e6*19(41..127)=179MB, 0.016s

Для какого паттерна было 200млн я уже не помню, вот нашёл 96млн:

n=24, max=100, x: 0 4 6 10 12 16 24 30 34 40 42 46 52 60 66 70 72 76 82 84 90 94 96 100
Size:95.76e6*8(53..83)=1532MB, 0.020s

Т.е. в список "формул" попали все по 47#, а простые с 53 проверялись уже по делимости, не по "формулам", причём для 8шт простых 53..83 выполняется не медленное деление с остатком, а быстрое взятие остатка из таблицы.

[Yadryara]

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

Но 200млн вариантов моя программа использует лишь для более длинных паттернов, конкретно для этого ограничивается 37# и 6.636млн - следующее значение 159млн уже не влезает в память:

Ну так всё правильно, у меня тоже не хватает памяти. Только я всё-таки сумел попробовать посчитать эти 159 миллионов. Каждый остаток формируется на лету(на базе этих 6-ти миллионов), из него получается цепочка и сразу проверяется по диапазону. Затем формируется следующий и проверяется. Зачем их запоминать-то. Разве что для скорости для маленьких диапазонов.

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

простые с 53 проверялись уже по делимости, не по "формулам", причём для 8шт простых 53..83 выполняется не медленное деление с остатком, а быстрое взятие остатка из таблицы.

Чувствую, Вы разобрались не хуже Jarekа. Мне эти тонкости пока не понятны.

[Dmitriy40]

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

Ну так всё правильно, у меня тоже не хватает памяти. Только я всё-таки сумел попробовать посчитать эти 159 миллионов. Каждый остаток формируется на лету(на базе этих 6-ти миллионов), из него получается цепочка и сразу проверяется по диапазону. Затем формируется следующий и проверяется. Зачем их запоминать-то.

Ну вообще говоря можно считать и вовсе без таблиц, сделать 17 вложенных циклов по каждому простому 3..61 (чтобы перекрыть диапазон до 61#=1.17e23) и получать начальное число цепочки из китайской теоремы об остатках (КТО), и потом уже его проверять тем или иным способом.
Беда только в том что до 61# надо проверить 6e15 вариантов! А ведь КТО далеко не мгновенна. Но даже без неё, чтобы проверить начальное число на допустимость надо например проверить 19 чисел на простоту, но PARIx64 проверяет такие большие числа (которые больше $2^{64}$) со скоростью 4e5/c, т.е. проверить даже только начальное число для 6e15 цепочек займёт 6e15/4e5/86400=174e3 суток. А учитывая что проверять надо 19 чисел, а не одно, то время ещё утроится (много цепочек отбрасывается сразу по первой-второй проверке). Т.е. более тысячи лет.
Вот сварганил быстренько программу перебора остатков по простым 43..61, всего около 38млн вариантов:

v=[0,6,12,30,42,72,90,96,120,126,132,156,162,180,210,222,240,246,252];
m=vector(67,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]););\\Списки допустимых остатков для каждого простого
x0=Mod(1,2); forprime(p=3,41, x0=chinese(x0,Mod(m[p][1],p));); t0=getwalltime();\\Для простых 2..41 возьму просто наименьший допустимый остаток
{foreach(m[61],m61,
   foreach(m[59],m59,
      foreach(m[53],m53,
         x53=chinese([x0,Mod(m61,61),Mod(m59,59),Mod(m53,53)]);
         foreach(m[47],m47,
            x47=chinese(x53,Mod(m47,47));
            foreach(m[43],m43,
               x=lift(chinese(x47,Mod(m43,43)));
               n+=x;\\Только для замера скорости КТО без проверки цепочки
            \\   foreach(v,d, if(!ispseudoprime(x+d), next(2)); ); print(x);\\Проверка цепочки
            );
         );
      );
   );
)}
print("Time: ",strtime(getwalltime()-t0));

В показанном варианте она отрабатывает за 30.5с, если же коммент переставить на строку выше чтобы добавить и проверку цепочек, то время уже 5м11с. И чтобы перебрать весь диапазон 61#=1.173e23 надо в 159млн раз больше времени или 5м11с*159e6=49.5e9с или 1567лет.
Т.е. скорость КТО составила 1.26e6 цепочек/с, а скорость с проверкой всего лишь 123e3 цепочек/с.
Причём сделать проверку ispseudoprime на порядок быстрее не получится, там принципиально завязано на малую теорему Ферма, а её проверять очень неудобно (для чисел больше разрядности проца/винды, но это в любом случае не больше $2^{64}$) и долго.

Моя же программа обрабатывает около 600e6 цепочек/с. Потому что медленная проверка на простоту заменена на проверку делимости на малые простые (до сотни тысяч, точную проверку на простоту делает потом PARI), а на совсем малые даже и деление не выполняется, (почти) готовый остаток берётся из таблицы (и не для каждого числа, а одновременно для 32, для чего и применено AVX2). Плюс вместо КТО идёт просто линейный перебор блоков длиной 7.421e12 с коэффициентом заполнения 6.636e6/7.421e12 (т.е. в каждом интервале длиной 7.421e12 проверяются лишь 6.636e6 вариантов). Линейный же потому что формирование всех таблиц (которые нужны для отказа от медленных делений на совсем малые простые) занимает около 1с, а обработка одного блока 6.636e6/600e6=0.011с, в 90 раз быстрее. Потому пересчитывать все таблицы для каждого блока (при переходе к следующему остатку по простым больше 37) сильно невыгодно, лучше посчитать их один раз и потом идти линейно, проверок будет больше, но далеко не в 90 раз (а всего в $\frac{41}{24} \frac{43}{24} \frac{47}{28} \frac{53}{34} \frac{59}{40} \frac{61}{42} = 17.16$ раз, тоже неприятно, но и не 90 раз). Плюс линейный проход легко раскладывается на несколько потоков практически без накладных расходов, а вот если каждый раз пересчитывать общие таблицы, то всё время уйдёт на это. Реальная скорость ещё в разы выше из-за не упомянутых оптимизаций и многопоточности.
Так что есть большая разница на чём именно писать программу и куча (далеко не очевидных) тонкостей как её оптимизировать по скорости работы.

[Dmitriy40]

Вот кстати, увеличив массив m[] до 2^9 (дальше заметного выигрыша уже нет) и добавив перед проверкой цепочки ещё одну предпроверку
forprime(p=67,#m, if(!setsearch(m[p],x%p), next(2)); );
можно ускорить программу с 5м11с до 1м4с, почти впятеро!

[Yadryara]

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

И чтобы перебрать весь диапазон 61#=1.173e23

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

проверок будет больше, но далеко не в 90 раз (а всего в $\frac{41}{24} \frac{43}{24} \frac{47}{28} \frac{53}{34} \frac{59}{40} \frac{61}{42} = 17.16$ раз

А дальше не смотрели?

Я посмотрел. Диапазон для $67\# \approx 8e24$. Поскольку поиск не предполагается вести выше $1e24$, то перебирать нужно будет не все 293 квадриллиона, а около 37. И, при каждом следующем модуле это количество снижается, падая на десяти тысячах простых до 174 миллионов:

(Код)

allocatemem(2^30);
{print();
v=[0,6,12,30,42,72,90,96,120,126,132,156,162,180,210,222,240,246,252];
prim=1;kob=1;pfin=104729;
forprime(p=2,pfin,
m=setminus(vector(p,i,i-1),Set(-v%p));prim=prim*p;kob=kob*#m);
print(pfin," ,len=",#m,  "   ", round(kob*10^24/prim));print();
}quit;

Вот только сколько времени займёт генерация этих миллионов... Возможно, стоит ориентироваться на запрещённые остатки, а не на разрешённые.

[Dmitriy40]

Запрещённых остатков ровно 19 для всех простых с 43 и далее.
Но это не помогает потому что количество разрешённых вариантов растёт медленнее роста простого числа, а значит падает относительная доля разрешённых вариантов, а значит растёт доля запрещённых. Т.е. запрещённых прямо сразу гораздо больше разрешённых, ну и смысл тогда их генерить если их на много порядков больше.

Я не знаю как генерить эти вот миллионы без перебора всех 293e15 (или примерно эквивалентного количества при учёте других простых).
Собственно моя программа примерно это и делает, сокращает количество 6.636e6 до сколько сможет в каждом интервале 7.421e12.

[Yadryara]

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

Собственно моя программа примерно это и делает, сокращает количество 6.636e6 до сколько сможет в каждом интервале

А симметрия прибавок для этих $6635520$ остатков учитывается?

Первый остаток — $30469$. Прибавив к нему $339354$ получим второй остаток, затем прибавив ещё $2202486$ — третий. Таким образом, список прибавок, которых тоже $6635520$, получается такой:

$339354, 2202486, 1209754, ... , 2681070, 84370, 1114436, 84370, 2681070, ... , 2202486, 339354, 61046.$

То есть прибавки доходят до $1114436$, разворачиваются и идут в обратную сторону полностью повторяя последовательность. И в самом конце добавка $61046$ для перехода к следующему интервалу. Эта закономерность для прибавок прослеживается начиная с модуля $17$.

Различных прибавок для нынешнего модуля $37$ не так уж много — $3937$. Можно их шифровать, экономить память. И, возможно, перейти к модулю $41$.

[Dmitriy40]

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

А симметрия прибавок для этих $6635520$ остатков учитывается?

Нет, все 6.636e6 элементов хранятся в прямом виде. Причина далее.

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

Различных прибавок для нынешнего модуля $37$ не так уж много — $3937$. Можно их шифровать, экономить память. И, возможно, перейти к модулю $41$.

Нет смысла экономить память для хранения только лишь остатков, её ведь всего лишь 6.636e6*8=53МБ (так как остатки бывают и больше $2^{32}$, то на каждый надо 8 байтов), экономия даже всех их несущественна по сравнению с требуемой таблицей 6.636e6*42=280МБ (каждый остаток по модулю простых 41..256 (раньше бралось 19 чисел до 127) для отказа от медленных делений и быстрого вычисления остатков очередного начального числа по модулю этих простых для проверки на допустимость) и она уже совсем не симметричная. Для 159e6 потребуется уже 159e6*(8+42)=8ГБ, что в x32 программе невозможно, а переписывать программу под x64 не так просто (регулярно пытаюсь, но каждый раз бросаю на полпути, ведь эффект ускорения 41/24=1.7 раза уже получен другим путём, да и 8Г памяти выделить на текущем компе не получится без ухода в тормозной своп).
Т.е. экономить память можно, так или иначе, но только лишь ценой потери скорости, причём не в пару раз, а в десятки. А я вообще-то бился за скорость, ценой памяти. И проблема вовсе не в таблице вот этих остатков или их приращений.

(Чуть более подробное объяснение зачем нужна огромная таблица)

Для отбраковки цепочки надо выяснить например недопустим ли остаток начального числа по всем простым (хотя бы на несколько малых). Т.е. вместо foreach(v,t,if(!isprime(x+t),next(2))) выполнить forprime(p=41,256,if(!setsearch([...],x%p),next(2))). Вопрос как именно посчитать x%p. Прямое деление слишком медленно (конкретные числа будут во втором офтопе, написанном раньше, так вто возможны повторы, извините за нудность). Можно заменить на x-floor(x*p^-1)*p, где в скобках умножение на обратный элемент p в поле 2^96 или 2^128, умножения на порядок быстрее делений. Можно заменить на x0%p+d%p, где сложение тоже по модулю p, а x0 это начало интервала кратного 37#=7.421e12 и x0%p считается один раз на 6.636e6 итераций, а d это 6.636e6 остатков по модулю 37#=7.421e12, тут выигрыш в том что d имеет разрядность 64 вместо 96 или 128 и взятие d%p можно выполнить быстрее. Но ведь можно же и заранее посчитать все d%p для всех d и всех p=41..256, они ведь не меняются при смене x0, это и будет таблица 6.636e6*42 элементов и тогда для вычисления x%p=x0%p+d%p достаточно сложения плюс условного вычитания (последнее и реализует сложение по модулю: так как при сложении не может получиться 2p и больше, значит достаточно сравнить с p и если не меньше то вычесть p, на это хватает двух команд).

Так что огромная таблица позволяет полностью отказаться от делений и от замены их умножениями и для получения x%p выполнять всего три команды суммарно за 1 такт в среднем.

Таблица остатков 6.636e6, которую Вы хотите сократить, при этом в работе не участвует и нужна лишь потом при восстановлении точного значения x из x0 и индекса в огромной таблице когда находится вероятно подходящая цепочка.

(Почему проверка цепочки такая медленная?)

Смотрите, для проверки цепочки на допустимость надо как минимум получить остаток начального числа по малым простым (до сотен, это уже отфильтрует 99.96% цепочек при учёте простых до 256, остальные можно допроверять и медленнее), что можно сделать разными способами, начиная от тупого деления с остатком (не требует никакой дополнительной памяти более килобайтов) за время 100-200 тактов на каждое число и на каждое простое (три команды деления x32 для чисел до 2^96 или две x64 для чисел до 2^128), или умножить на обратное простое с получением частного, его умножить снова на простое и вычесть из исходного, на это теоретически хватит 9 тактов под x64 (6 умножений и 9 сложений-вычитаний), можно же иметь таблицу остатков по модулю каждого простого (те самые 6.636e6*42 элементов, в данном случае достаточно по байту) и обойтись всего лишь сложением плюс вычитание плюс условная пересылка, хватит 1 такта. Имея же AVX2 можно эту процедуру выполнять сразу для 32 начальных чисел (или для одного начального и 32 малых простых, что впрочем менее выгодно) за 1.5 такта, т.е. практически 20 чисел на такт или 0.05 такта на число. Т.е. в 100 раз быстрее наилучшего подхода без дополнительных таблиц! Именно поэтому я посчитал разумным разменять память под таблицы на стократную скорость. Разумеется общая скорость вовсе не в 100 раз выше, ведь там много и других действий кроме получения остатка по модулю малого простого, но с AVX2 и почти все они тоже выполняются сразу для 32-х чисел за практически то же время.

Теоретически можно применить AVX2 и для вычислений с обратными простыми, но в нём нет 64-битных умножений, их придётся заменять на 32-битные, которых понадобится 12шт вместо 6-ти и огромная морока с учётом переносов при сложении-вычитании, займёт это всё тактов 30, а обработано будет лишь 4 числа, т.е. не быстрее вычислений без AVX2, потому данный вариант даже не прорабатывал.

Ещё можно считать не сразу от начального числа, а лишь от остатка из таблицы остатков (который за такт потом приводить к реальному), они уже не 96-128 битные, а лишь 64-битные, это сильно проще, хватит 2 умножения и вычитания за 2 такта без AVX2 или 6 умножений и 5 сложений-вычитаний (плюс штук 6 команд мороки с переносами) за тактов 11-12 и всего 4 числа с AVX2, по 3 такта на число. Тоже не прорабатывал, 0.05 такта на число гораздо привлекательнее, даже в комплекте с памятью под 400МБ.

В итоге деление даст скорость 105 тактов (5 тактов уйдёт на проверку полученного остатка по модулю простого) на число или максимум 3.7e9/105=35млн/с если вдруг все цепочки отпадут по первому же простому (это совершенно не так, но для сравнения пусть). Умножение на обратный элемент даст 14 тактов или 264млн/с (или 8 тактов и 462млн/с по другому варианту). С огромной таблицей же хватит 6 тактов на число и скорость будет 620e6/c. Не слишком впечатляюще, но таблица позволяет применить AVX2 (в котором нет делений, но есть сложения-вычитания и условные пересылки) - который проверит сразу 32 числа десятью командами за 6 тактов или по 0.19 такта на число и соответственно 18млрд/с. И усложнять код из 10 команд для экономии памяти получая при этом существенный проигрыш в скорости (5%-10% на каждую дополнительную команду) не думаю что имеет смысл.

PS. Специально для любительниц читать исключительно выборочно и обсмеивать лишь самые большие числа: реальная скорость в 30 раз меньше (600e6 вместо 18e9) потому что далеко не все цепочки отбраковываются уже первой же проверкой, каждая проверка отбраковывает в среднем всего около 30% цепочек и приходится делать достаточно много проверок (тысячи) для передачи в PARI на финальную проверку достаточно мало кандидатов чтобы тот не слишком тормозил с их проверкой.

[Dmitriy40]

Как известно программа для боинка на основе primesieve не умеет работать с числами больше $2^{64}$, вот я и озадачился какие последние цепочки могут быть найдены перед этим порогом. Проверил последний квадриллион перед $2^{64}$ (точнее чуть больше, с 18445680e12 до $2^{64}$), нашёл последние цепочки каждого типа и каждой длины, получилась следующая табличка:

Используется синтаксис Text

STPT(4):  18446744073709550717: 0 2 54 56
TPT(4):   18446744073709550717: 0 2 54 56
SPT(4):   18446744073709550717: 0 2 54 56
SPT(3):   18446744073709546253: 0 18 36
SPT(6):   18446744073709389671: 0 6 30 98 122 128
SPT(5):   18446744073709356257: 0 30 42 54 84
SPT(8):   18446744073708948031: 0 58 88 108 178 198 228 286
TPT(6):   18446744073707387861: 0 2 78 80 150 152
SPT(10):  18446744073703484059: 0 24 58 72 78 274 280 294 328 352
STPT(6):  18446744073687086327: 0 2 42 44 84 86
SPT(7):   18446744073685601711: 0 42 48 60 72 78 120
TPT(8):   18446744073654368999: 0 2 18 20 42 44 48 50
SPT(9):   18446744073614141399: 0 60 78 90 210 330 342 360 420
STPT(8):  18446744072944736189: 0 2 18 20 42 44 60 62
TPT(10):  18446744070645217037: 0 2 12 14 42 44 60 62 102 104
SPT(12):  18446744067777362191: 0 78 112 126 138 208 210 280 292 306 340 418
SPT(14):  18446744007199404031: 0 16 18 58 108 130 160 168 198 220 270 310 312 328
TPT(12):  18446744006124899651: 0 2 18 20 60 62 90 92 96 98 156 158
SPT(16):  18446743929515477789: 0 38 44 68 98 162 168 198 344 374 380 444 474 498 504 542
SPT(11):  18446743529266396009: 0 12 30 78 102 120 138 162 210 228 240
TPT(14):  18446743441615856537: 0 2 60 62 120 122 132 134 144 146 162 164 240 242
STPT(10): 18446742978387887921: 0 2 6 8 18 20 30 32 36 38
SPT(18):  18446734892880817309: 0 24 42 54 90 124 142 174 220 264 310 342 360 394 430 442 460 484
STPT(12): 18446731560670193279: 0 2 30 32 48 50 72 74 90 92 120 122
SPT(13):  18446727494468699149: 0 12 72 114 120 210 252 294 384 390 432 492 504
SPT(20):  18446624553496676281: 0 42 70 90 96 118 120 252 358 370 408 420 526 658 660 682 688 708 736 778
TPT(16):  18446497274552202797: 0 2 12 14 54 56 132 134 240 242 270 272 300 302 432 434

Не знаю зачем оно может понадобиться, рекордных цепочек не нашлось, вообще никаких неожиданностей не видно, просто интересно.
Показываю только наиболее длинный или редкий вариант, понятно что любая STPT цепочка является и TPT и SPT цепочкой.
Если кто не в курсе обозначений, первая S означает симметричность, первая T что цепочка из простых близнецов, P что цепочки только из простых чисел, последняя T что цепочки (tuple).

[Dmitriy40]

Поиск КПППЧ19d252 досчитал до 5e23, решения не найдено, из интересного:
434510678411396023322707: [ 0, 6, 12, 30, 42, +72, 90, 96, 120, 126, 132, 156, 162, 180, 210, 222, 240, 246, 252], len=18, valids=18
С одной ошибкой.
358007708381432364925597: [ 0, 6, 12, 30, 42, 72, +90, 96, 120, 126, 132, 156, 162, 180, 210, 222, 240, 246,+252], len=17, valids=17
367471340632262497514551: [ 0, +6, 12, 30, 42, 72, 90, 96, 120, 126, 132, 156, 162, 180, 210, 222,+240, 246, 252], len=17, valids=17
398679156750068161477591: [ 0, +6, 12, 30, 42, 72, 90, 96, 120, 126, 132, 156, 162, 180, 210, 222,+240, 246, 252], len=17, valids=17
407274799959034300457377: [ +0, 6, 12, 30, 42, 72, 90, 96, 120, 126, 132, 156,+162, 180, 210, 222, 240, 246, 252], len=17, valids=17
411995805739113491080567: [ +0, 6, 12, 30, 42, 72, 90, 96, 120,+126, 132, 156, 162, 180, 210, 222, 240, 246, 252], len=17, valids=17
413623036385336736172427: [ 0, 6, 12, 30, 42, +72, 90, +96, 120, 126, 132, 156, 162, 180, 210, 222, 240, 246, 252], len=17, valids=17
420500455232809280269021: [ 0, 6, 12, 30, 42, 72, 90, 96, 120, 126, 132, 156, 162, 180, 210, 222,+240, 246,+252], len=17, valids=17
430271971583436254387497: [ 0, 6, 12, 30, 42, 72, +90, 96, 120, 126, 132, 156, 162, 180, 210, 222, 240, 246,+252], len=17, valids=17
484402521202574185816987: [ 0, 6, 12, 30, 42, 72, 90, 96, 120, 126, 132, 156, 162, 180, 210, 222,+240,+246, 252], len=17, valids=17
С двумя ошибками.
397584513960218821500191: [ 0, 6, 12, 30, 42, 72, 90, 96, 120, 126,+132, 156,-158, 162, 180, 210, 222,-236, 240, 246, 252], len=20, valids=18
470598488344258287639707: [ 0, 6, 12, 30, -32, 42, 72, 90, 96,-104,-110,+120, 126, 132, 156, 162,-176, 180, 210, 222, 240, 246, 252], len=22, valids=18
497042258815657777926371: [ 0, 6, 12, 30, -38, +42, 72, 90, 96, 120, 126, 132, 156, 162,-176, 180,-198, 210, 222, 240, 246, 252], len=21, valids=18
С 18-ю простыми на своих местах.
359540506216112922000227: [ +0, 6, 12, -14, 30, 42, 72, 90, 96, 120, 126, 132, 156, 162, 180, 210, 222,-224,+240, 246,+252], len=18, valids=16
421256495980380168644357: [ +0, +6, 12, -20, 30, 42, 72, 90, 96, 120, 126, 132, 156, 162, 180, 210, 222, 240, 246,+252], len=17, valids=16
484514280519791779811921: [ +0, 6, +12, -26, 30, 42, 72, 90, 96, 120, 126, 132, 156, 162, 180, 210, 222, 240, 246,+252], len=17, valids=16
495494811824144355473071: [ +0, +6, 12, -28, 30, 42, 72, 90, 96, 120, 126, 132, 156, 162, 180, 210, 222,+240, 246, 252], len=17, valids=16
С 13-ой в центре.
432021824240632917437227:[0, 6, 12, 16, 42, 72, 90, 96, 120, 126, 132, 156, 162, 196, 210, 222, 240, 246, 252], valids=17
461469903651693879956941:[0, 6, 12, 30, 70, 72, 90, 96, 120, 126, 132, 156, 162, 180, 210, 222, 240, 246, 306], valids=17
По две дырки.