YadryaraПро разные шаги я бы сказал так:
1. Для паттернов с двумя и более квадратами величина шагов не актуальна, они проверяются Пеллем очень быстро (доли секунд).
2. Для паттернов с одним квадратом величина шагов тоже не актуальна, их проще проверять квадратичным перебором. Причём не по каждому простому, а там легко накладываются достаточно неплохие ограничения на это простое и потому перебор идёт с большим шагом (от сотен тысяч до миллиардов). Не всегда он укладывается в секунды и часы (для 14 и 15), но нескольких суток вроде хватает. Да и паттернов таких весьма немного. Макарова кажется почти все их уже проверила.
3. Паттерны без квадратов. Вот тут глухо. Перебор ускорителем даже до 2e33 даже для наибольшего шага требует порядка трёх суток и соответственно порядка 4 месяцев до 8e34. Для меньших шагов время растёт пропорционально. Подключение квадратичных переборов требует перебора простых до порога -p, который для 14 составляет примерно 4.3e15, а для 15 примерно 2.7e16 (все qr<106 запрещены или проверены до конца). Это слишком много. Это многовато даже для 13, где порог примерно 2.3e12 (qr<118 запрещены или проверены).
А кто-нибудь занимается понижением этого порога?
Без понятия. Чем занимается Хуго информации в открытом доступе не видел. А остальные похоже даже не в курсе как и чем и зачем можно уменьшать порог (готовую программу Хуго не даёт, только исходник) ...
Я несколько раз порывался запустить счёт, но каждый раз увидев оценку времени понимал что выгоднее поступать по другому: каждое конкретное значение qr будет проверяться примерно сутки (здесь и далее везде для счёта в один поток), разных qr<600 чтобы получить -p1e12 (что всё равно слишком много) примерно 150 штук, т.е. грубо надо 5 месяцев на такое уменьшение порога, но очень многие из этих qr или запрещены, или можно проверить относительно быстро (сильно быстрее суток), но надо для каждого руками проверять какие разрешены (программа выходит слишком сложной) и писать отдельную программу перебора (универсальная опять же выходит слишком сложной).
Пытался подойти к этому вопросу с другой стороны: перебрать на асме быстро все большие простые (которые дают и шаг паттерна и начальное число больше порога, ведь это 99% всего квадратичного перебора), но вычисление обратного элемента в кольце по модулю страшно медленно даже на асме, PARI применяет КТО со скоростью примерно 2e7/c (везде указываю интервал, не штуки), а асм простые генерит почти 1e9/c, но обратный элемент (нужный для КТО по схеме Гарнера) лишь 4e7/c, всего вдвое быстрее PARI, это грустно. К счастью обратный элемент можно вычислить лишь один раз для каждого простого в квадрате и каждого шага (он из этой пары и вычисляется), независимо от паттерна с таким шагом, а дальше или быстрые умножения или даже и без них, но это значит встраивать в цикл перебора простых ещё и перебор шагов паттернов, а потом ещё и перебор самих паттернов и возможных мест в них, что совершенно очевидно заметно замедлит и без того медленный перебор простых с вычислением обратного элемента, т.е. скорость упадёт с 4e7/с до скажем 1e7/с и на перебор простых до 2.3e12 понадобится дня три (хотя скорее неделя-две), плюс проверка не отброшенных простых в PARI. Зато это позволит уменьшить порог практически до 1e9-1e10 (как только доля подходящих простых упадёт до долей процента). Ценой встраивания в асм код двух дополнительных циклов по реальным паттернам (от них нужно как минимум начальное число до подстановки дополнительных простых, а лучше и список допустимых мест). При этом на PARI ровно тот же перебор возможных мест в паттернах с однократным вычислением обратного элемента идёт со скоростью 5e6/c (для 5-ти мест, что довольно часто), так что ускорение от переписывания на асм похоже менее чем двойное, а трудности многократные. На PARI перебрать простые до 2.3e12 потребует порядка недели на каждый из 3000 паттернов ... Возможно на асм снижение скорости будет не таким сильным, но она в любом случае не превысит скорости вычисления обратного элемента 4e7/с, т.е. для вычисления всех обратных элементов для p<2.3e12 и 20 разных шагов надо порядка двух недель, ну и плюс проверка начального числа, в итоге несколько месяцев, в принципе достижимо ...
Есть и другая идея: каждое конкретное qr допустимо не для каждого паттерна, некоторые или попадают на занятые места, или не дают нужных остатков по уже расставленным простым. Конечно это как раз и есть те запреты выше, но возможно проверить конкретное qr по списку конкретных паттернов будет проще чем пытаться запретить qr для любых. Но эта идея пришла только вчера и реализовать пока не успел, прикидочная оценка даёт что для qr=106 для 13-ек из 3408 паттернов подходит около 400, в остальные
не вставляется. Это хорошо, возможно получится написать более-менее универсальную программу перебора для каждого qr только подходящих паттернов, ведь там в каждом можно наложить сильные ограничения на
и перебирать их с большим шагом (как и делал руками, а тут будет автоматически). Насколько это просто и выгодно оценок пока не сделал.
Но всё это практически неприменимо к 14 и 15, слишком велик там порог -p, надо выдумывать что-то ещё. Даже просто генерация простых до 2.7e16 займёт порядка года, а ещё ведь по любому надо делать гораздо более медленные проверки ...
И пока совершенно непонятно куда бы тут эффективно прилепить SSE/AVX (кроме одного места с проверкой мест паттернов после вычисления обратного элемента в кольце по модулю). А без SSE/AVX скорость как-то не сильно от PARI отличается и за что тогда бороться непонятно.
, this is not something it will accept.
![$\tikz[scale=.08]{
\fill[green!90!blue!50] (0,20) rectangle (144,50);
\fill[green!70!blue!80] (0,0) rectangle (144,20);
\draw[step=10] (60,0) grid (120,100);
\draw (0,90) rectangle (10,100);
\draw (10,90) rectangle (60,100);
\draw (120,90) rectangle (132,100);
\draw (132,90) rectangle (144,100);
\draw (0,80) rectangle (10,90);
\draw (10,80) rectangle (60,90);
\draw (120,80) rectangle (132,90);
\draw (132,80) rectangle (144,90);
\draw (0,70) rectangle (10,80);
\draw (10,70) rectangle (60,80);
\draw (120,70) rectangle (132,80);
\draw (132,70) rectangle (144,80);
\draw (0,60) rectangle (10,70);
\draw (10,60) rectangle (60,70);
\draw (120,60) rectangle (132,70);
\draw (132,60) rectangle (144,70);
\draw (0,50) rectangle (10,60);
\draw (10,50) rectangle (60,60);
\draw (120,50) rectangle (132,60);
\draw (132,50) rectangle (144,60);
\draw (0,40) rectangle (10,50);
\draw (10,40) rectangle (60,50);
\draw (120,40) rectangle (132,50);
\draw (132,40) rectangle (144,50);
\draw (0,30) rectangle (10,40);
\draw (10,30) rectangle (60,40);
\draw (120,30) rectangle (132,40);
\draw (132,30) rectangle (144,40);
\draw (0,20) rectangle (10,30);
\draw (10,20) rectangle (60,30);
\draw (120,20) rectangle (132,30);
\draw (132,20) rectangle (144,30);
\draw (0,10) rectangle (10,20);
\draw (10,10) rectangle (60,20);
\draw (120,10) rectangle (132,20);
\draw (132,10) rectangle (144,20);
\draw (0,0) rectangle (10,10);
\draw (10,0) rectangle (60,10);
\draw (120,0) rectangle (132,10);
\draw (132,0) rectangle (144,10);
\node at (5,95){\text{№}};
\node at (34,95){\text{LCM}};
\node at (65,95){\text{8}};
\node at (75,95){\text{9}};
\node at (85,95){\text{10}};
\node at (95,95){\text{11}};
\node at (105,95){\text{12}};
\node at (115,95){\text{13}};
\node at (125.9,95){\text{Pat}};
\node at (137.8,95){\text{Done}};
\node at (6,85){\text{1}};
\node at (48,85){\text{7207200}};
\node at (95,85){\text{24}};
\node at (105,85){\text{4}};
\node at (115,85){\text{6}};
\node at (126,85){\text{34}};
\node at (5,75){\text{...}};
\node at (5,65){\text{21}};
\node at (40.1,65){\text{253354997095200}};
\node at (95,65){\text{18}};
\node at (105,65){\text{4}};
\node at (115,65){\text{6}};
\node at (126,65){\text{28}};
\node at (5,55){\text{22}};
\node at (40,55){\text{494233458919200}};
\node at (95,55){\text{22}};
\node at (105,55){\text{4}};
\node at (115,55){\text{6}};
\node at (126,55){\text{32}};
\node at (5,45){\text{23}};
\node at (39,45){\text{3013774290727200}};
\node at (95,45){\text{16}};
\node at (105,45){\text{4}};
\node at (115,45){\text{6}};
\node at (126,45){\text{26}};
\node at (138,45){\text{26}};
\node at (5,35){\text{24}};
\node at (38.9,35){\text{3293614962237600}};
\node at (85,35){\text{36}};
\node at (95,35){\text{12}};
\node at (105,35){\text{32}};
\node at (126,35){\text{80}};
\node at (138,35){\text{80}};
\node at (5,25){\text{25}};
\node at (38.8,25){\text{5436568048111200}};
\node at (85,25){\text{50}};
\node at (95,25){\text{32}};
\node at (105,25){\text{26}};
\node at (115,25){\text{2}};
\node at (125.7,25){\text{110}};
\node at (137.7,25){\text{110}};
\node at (5,15){\text{26}};
\node at (37.5,15){\text{21096420035090400}};
\node at (85,15){\text{16}};
\node at (95,15){\text{16}};
\node at (105,15){\text{12}};
\node at (126,15){\text{44}};
\node at (138,15){\text{44}};
\node at (5,5){\text{27}};
\node at (35.5,5){\text{7236072072036007200}};
\node at (95,5){\text{16}};
\node at (105,5){\text{4}};
\node at (115,5){\text{6}};
\node at (126,5){\text{26}};
\node at (138,5){\text{26}};
}$](https://dxdy-03.korotkov.co.uk/f/2/4/8/24861aa1162470a51ff9551ea878bac082.png "$\tikz[scale=.08]{
\fill[green!90!blue!50] (0,20) rectangle (144,50);
\fill[green!70!blue!80] (0,0) rectangle (144,20);
\draw[step=10] (60,0) grid (120,100);
\draw (0,90) rectangle (10,100);
\draw (10,90) rectangle (60,100);
\draw (120,90) rectangle (132,100);
\draw (132,90) rectangle (144,100);
\draw (0,80) rectangle (10,90);
\draw (10,80) rectangle (60,90);
\draw (120,80) rectangle (132,90);
\draw (132,80) rectangle (144,90);
\draw (0,70) rectangle (10,80);
\draw (10,70) rectangle (60,80);
\draw (120,70) rectangle (132,80);
\draw (132,70) rectangle (144,80);
\draw (0,60) rectangle (10,70);
\draw (10,60) rectangle (60,70);
\draw (120,60) rectangle (132,70);
\draw (132,60) rectangle (144,70);
\draw (0,50) rectangle (10,60);
\draw (10,50) rectangle (60,60);
\draw (120,50) rectangle (132,60);
\draw (132,50) rectangle (144,60);
\draw (0,40) rectangle (10,50);
\draw (10,40) rectangle (60,50);
\draw (120,40) rectangle (132,50);
\draw (132,40) rectangle (144,50);
\draw (0,30) rectangle (10,40);
\draw (10,30) rectangle (60,40);
\draw (120,30) rectangle (132,40);
\draw (132,30) rectangle (144,40);
\draw (0,20) rectangle (10,30);
\draw (10,20) rectangle (60,30);
\draw (120,20) rectangle (132,30);
\draw (132,20) rectangle (144,30);
\draw (0,10) rectangle (10,20);
\draw (10,10) rectangle (60,20);
\draw (120,10) rectangle (132,20);
\draw (132,10) rectangle (144,20);
\draw (0,0) rectangle (10,10);
\draw (10,0) rectangle (60,10);
\draw (120,0) rectangle (132,10);
\draw (132,0) rectangle (144,10);
\node at (5,95){\text{№}};
\node at (34,95){\text{LCM}};
\node at (65,95){\text{8}};
\node at (75,95){\text{9}};
\node at (85,95){\text{10}};
\node at (95,95){\text{11}};
\node at (105,95){\text{12}};
\node at (115,95){\text{13}};
\node at (125.9,95){\text{Pat}};
\node at (137.8,95){\text{Done}};
\node at (6,85){\text{1}};
\node at (48,85){\text{7207200}};
\node at (95,85){\text{24}};
\node at (105,85){\text{4}};
\node at (115,85){\text{6}};
\node at (126,85){\text{34}};
\node at (5,75){\text{...}};
\node at (5,65){\text{21}};
\node at (40.1,65){\text{253354997095200}};
\node at (95,65){\text{18}};
\node at (105,65){\text{4}};
\node at (115,65){\text{6}};
\node at (126,65){\text{28}};
\node at (5,55){\text{22}};
\node at (40,55){\text{494233458919200}};
\node at (95,55){\text{22}};
\node at (105,55){\text{4}};
\node at (115,55){\text{6}};
\node at (126,55){\text{32}};
\node at (5,45){\text{23}};
\node at (39,45){\text{3013774290727200}};
\node at (95,45){\text{16}};
\node at (105,45){\text{4}};
\node at (115,45){\text{6}};
\node at (126,45){\text{26}};
\node at (138,45){\text{26}};
\node at (5,35){\text{24}};
\node at (38.9,35){\text{3293614962237600}};
\node at (85,35){\text{36}};
\node at (95,35){\text{12}};
\node at (105,35){\text{32}};
\node at (126,35){\text{80}};
\node at (138,35){\text{80}};
\node at (5,25){\text{25}};
\node at (38.8,25){\text{5436568048111200}};
\node at (85,25){\text{50}};
\node at (95,25){\text{32}};
\node at (105,25){\text{26}};
\node at (115,25){\text{2}};
\node at (125.7,25){\text{110}};
\node at (137.7,25){\text{110}};
\node at (5,15){\text{26}};
\node at (37.5,15){\text{21096420035090400}};
\node at (85,15){\text{16}};
\node at (95,15){\text{16}};
\node at (105,15){\text{12}};
\node at (126,15){\text{44}};
\node at (138,15){\text{44}};
\node at (5,5){\text{27}};
\node at (35.5,5){\text{7236072072036007200}};
\node at (95,5){\text{16}};
\node at (105,5){\text{4}};
\node at (115,5){\text{6}};
\node at (126,5){\text{26}};
\node at (138,5){\text{26}};
}$")
![$\tikz[scale=.08]{
\fill[green!90!blue!50] (0,20) rectangle (81,70);
\fill[green!70!blue!80] (0,0) rectangle (81,20);
\draw (0,100) rectangle (10,110);
\draw (10,100) rectangle (55,110);
\draw (55,100) rectangle (68,110);
\draw (68,100) rectangle (81,110);
\draw (0,90) rectangle (10,100);
\draw (10,90) rectangle (55,100);
\draw (55,90) rectangle (68,100);
\draw (68,90) rectangle (81,100);
\draw (0,80) rectangle (10,90);
\draw (10,80) rectangle (55,90);
\draw (55,80) rectangle (68,90);
\draw (68,80) rectangle (81,90);
\draw (0,70) rectangle (10,80);
\draw (10,70) rectangle (55,80);
\draw (55,70) rectangle (68,80);
\draw (68,70) rectangle (81,80);
\draw (0,60) rectangle (10,70);
\draw (10,60) rectangle (55,70);
\draw (55,60) rectangle (68,70);
\draw (68,60) rectangle (81,70);
\draw (0,50) rectangle (10,60);
\draw (10,50) rectangle (55,60);
\draw (55,50) rectangle (68,60);
\draw (68,50) rectangle (81,60);
\draw (0,40) rectangle (10,50);
\draw (10,40) rectangle (55,50);
\draw (55,40) rectangle (68,50);
\draw (68,40) rectangle (81,50);
\draw (0,30) rectangle (10,40);
\draw (10,30) rectangle (55,40);
\draw (55,30) rectangle (68,40);
\draw (68,30) rectangle (81,40);
\draw (0,20) rectangle (10,30);
\draw (10,20) rectangle (55,30);
\draw (55,20) rectangle (68,30);
\draw (68,20) rectangle (81,30);
\draw (0,10) rectangle (10,20);
\draw (10,10) rectangle (55,20);
\draw (55,10) rectangle (68,20);
\draw (68,10) rectangle (81,20);
\draw (0,0) rectangle (10,10);
\draw (10,0) rectangle (55,10);
\draw (55,0) rectangle (68,10);
\draw (68,0) rectangle (81,10);
\node at (5,105){\text{№}};
\node at (31,105){\text{LCM}};
\node at (62,105){\text{Pat}};
\node at (75,105){\text{Done}};
\node at (6,95){\text{1}};
\node at (45,95){\text{7207200}};
\node at (63,95){\text{34}};
\node at (5,85){\text{...}};
\node at (37,85){\text{}};
\node at (63,85){\text{}};
\node at (5,75){\text{20}};
\node at (38,75){\text{15850052618400}};
\node at (62,75){\text{160}};
\node at (5,65){\text{21}};
\node at (37,65){\text{253354997095200}};
\node at (63,65){\text{28}};
\node at (75,65){\text{28}};
\node at (5,55){\text{22}};
\node at (37,55){\text{494233458919200}};
\node at (63,55){\text{32}};
\node at (75,55){\text{32}};
\node at (5,45){\text{23}};
\node at (36,45){\text{3013774290727200}};
\node at (63,45){\text{26}};
\node at (75,45){\text{26}};
\node at (5,35){\text{24}};
\node at (35.9,35){\text{3293614962237600}};
\node at (63,35){\text{80}};
\node at (75,35){\text{80}};
\node at (5,25){\text{25}};
\node at (35.8,25){\text{5436568048111200}};
\node at (62,25){\text{110}};
\node at (74,25){\text{110}};
\node at (5,15){\text{26}};
\node at (34.5,15){\text{21096420035090400}};
\node at (62,15){\text{44}};
\node at (75,15){\text{44}};
\node at (5,5){\text{27}};
\node at (32.5,5){\text{7236072072036007200}};
\node at (62,5){\text{26}};
\node at (75,5){\text{26}};
}$](https://dxdy-02.korotkov.co.uk/f/5/e/0/5e0d92358d8bc27bc030a78b514c971b82.png "$\tikz[scale=.08]{
\fill[green!90!blue!50] (0,20) rectangle (81,70);
\fill[green!70!blue!80] (0,0) rectangle (81,20);
\draw (0,100) rectangle (10,110);
\draw (10,100) rectangle (55,110);
\draw (55,100) rectangle (68,110);
\draw (68,100) rectangle (81,110);
\draw (0,90) rectangle (10,100);
\draw (10,90) rectangle (55,100);
\draw (55,90) rectangle (68,100);
\draw (68,90) rectangle (81,100);
\draw (0,80) rectangle (10,90);
\draw (10,80) rectangle (55,90);
\draw (55,80) rectangle (68,90);
\draw (68,80) rectangle (81,90);
\draw (0,70) rectangle (10,80);
\draw (10,70) rectangle (55,80);
\draw (55,70) rectangle (68,80);
\draw (68,70) rectangle (81,80);
\draw (0,60) rectangle (10,70);
\draw (10,60) rectangle (55,70);
\draw (55,60) rectangle (68,70);
\draw (68,60) rectangle (81,70);
\draw (0,50) rectangle (10,60);
\draw (10,50) rectangle (55,60);
\draw (55,50) rectangle (68,60);
\draw (68,50) rectangle (81,60);
\draw (0,40) rectangle (10,50);
\draw (10,40) rectangle (55,50);
\draw (55,40) rectangle (68,50);
\draw (68,40) rectangle (81,50);
\draw (0,30) rectangle (10,40);
\draw (10,30) rectangle (55,40);
\draw (55,30) rectangle (68,40);
\draw (68,30) rectangle (81,40);
\draw (0,20) rectangle (10,30);
\draw (10,20) rectangle (55,30);
\draw (55,20) rectangle (68,30);
\draw (68,20) rectangle (81,30);
\draw (0,10) rectangle (10,20);
\draw (10,10) rectangle (55,20);
\draw (55,10) rectangle (68,20);
\draw (68,10) rectangle (81,20);
\draw (0,0) rectangle (10,10);
\draw (10,0) rectangle (55,10);
\draw (55,0) rectangle (68,10);
\draw (68,0) rectangle (81,10);
\node at (5,105){\text{№}};
\node at (31,105){\text{LCM}};
\node at (62,105){\text{Pat}};
\node at (75,105){\text{Done}};
\node at (6,95){\text{1}};
\node at (45,95){\text{7207200}};
\node at (63,95){\text{34}};
\node at (5,85){\text{...}};
\node at (37,85){\text{}};
\node at (63,85){\text{}};
\node at (5,75){\text{20}};
\node at (38,75){\text{15850052618400}};
\node at (62,75){\text{160}};
\node at (5,65){\text{21}};
\node at (37,65){\text{253354997095200}};
\node at (63,65){\text{28}};
\node at (75,65){\text{28}};
\node at (5,55){\text{22}};
\node at (37,55){\text{494233458919200}};
\node at (63,55){\text{32}};
\node at (75,55){\text{32}};
\node at (5,45){\text{23}};
\node at (36,45){\text{3013774290727200}};
\node at (63,45){\text{26}};
\node at (75,45){\text{26}};
\node at (5,35){\text{24}};
\node at (35.9,35){\text{3293614962237600}};
\node at (63,35){\text{80}};
\node at (75,35){\text{80}};
\node at (5,25){\text{25}};
\node at (35.8,25){\text{5436568048111200}};
\node at (62,25){\text{110}};
\node at (74,25){\text{110}};
\node at (5,15){\text{26}};
\node at (34.5,15){\text{21096420035090400}};
\node at (62,15){\text{44}};
\node at (75,15){\text{44}};
\node at (5,5){\text{27}};
\node at (32.5,5){\text{7236072072036007200}};
\node at (62,5){\text{26}};
\node at (75,5){\text{26}};
}$")
, при этом все три простых числа неизвестны. То есть 
дают все возможные остатки. А вот 
даёт не все возможные остатки. Поэтому далеко не все 
и 
запрещены. Всего 
вариантов.
запрещены. Всего 
остатков, из них 
вариантов.
остатков, из них 
вариантов.
остатков, из них 
вариантов.
остатков, из них 
вариантов.
вполне ставится в позицию 32p+1); 
(для паттернов с 7-ю возможными местами, как например тот же b34), уже 4%. Но вот например для 22<qr<600 есть 171 вариант, из которых реально в 217 паттернах из 3408 встречаются лишь qr=129,253,262,323,362,394,469,473,497,551,566,597 (и 106 который проверил выше 6e26 и дальше не учитываю), причём не более чем три из них. И на пустых местах встречаются лишь по одному (323 или 551), по два и по три только на местах с простыми (т.е. 323 и 551 "не спариваются" с прочими в одном паттерне). И каждое qr только на своём месте (относительно 32p).
встречаются лишь 298 вариантов. Теперь интересно сколько времени займёт перебор простых в квадрате во всех этих 298 вариантах, меньше 170 дней (сколько заняло бы обычное уменьшение порога до 1e12) или нет.