Правильно?
По моему не совсем.
0. Отсев по 37# вообще не производится, он произведён один раз при построении таблицы.
1. Блоками по 32 числа из таблицы внутри интервала 37# производится отсев по простым 41-128. Если в каждом блоке не осталось ни одного допустимого числа, то уход на проверку следующего блока.
2. Далее для всех оставшихся чисел из 32 производится их отсев каждого сразу по 23 простым 128-256: одно вычисление сразу всех 23 остатков и потом 19 сравнений с недопустимыми остатками сразу по 23 простым, если любой остаток совпал - переход к следующему числу.
3. Если число не отсеялось (так случается в среднем каждое 5156-е число), то проверка его дальше до упора.
4. Если проверили все блоки по 32 в таблице 37#, то продвигаем начало интервала на величину 37# и повторяем с п.1 пока не достигнем конца заказанного интервала (он обычно 1e17 если без оптимизаций, это секунд 40 в 4 потока, потом допроверка найденных кандидатов в PARI и цикл кусками по 1e17 до посинения).
Реально работает чуть более сложно (и раза в 3 быстрее), но принцип тот же.
Если
не годится по модулю 59, то и парный кандидат не годится по тому же модулю:
По моему это работает только для остатка 0 по каждому простому, по другим запрещённым остаткам не работает: для 59 остаток 2 разрешён, а 59-2=57 нет. Т.е. Вы предлагаете не проверять парные для всего лишь
всех чисел, которые дают остаток 0 по любому простому 41-67, менее 14% всех, при том что перебор по простым больше 37 идёт последовательно и парные числа просто не входят в проверяемый диапазон (проверяется кусочками по 1e17-1e21 в разных вариантах) ... Как-то очень уж сложно выходит.
И это я не вспоминаю что парные числа могут попасть на разные ядра/потоки и как между ними обмениваться тоже вопрос.
Получается что, например. для давно закрытого диапазона
такие числа проверялись по два раза?
Нет, не получается: проверяется и 1172883813594069709832759, и 6685437737486197346046331, но строго по одному разу каждое (на самом деле оба эти числа запрещены по 5 и не попадут даже в таблицу 37#). Куски по 37# перебираются линейно (с выравниванием на границу куска). Потери от выравнивания (и соответственно двойной проверки некоторых чисел) не превышают 37# на весь заказанный диапазон (1e17) и меньше сотой доли процента.
В итоге я всё равно плохо понимаю что именно Вы предлагаете исключить. Вот ткните в команду, которую не надо выполнять для второго числа из пары в алгоритме (это почти то что и делается у меня в программе, почти на PARI, только выделил где массивы, а где матрицы, а где скаляры, ну и без реальной инициализации и без многопоточности):
Код:
forstep(base=0,oo,1e17, MyProg(base); );\\Самый внешний цикл, реально вынесен из программы наружу (в PARI)
{MyProg(base)=my();
tab[]=vector(#37);\\Таблица увеличения числа относительно начала 37#
mm[,]=matrix(37#,19+23);\\Увеличение остатков по простым 41-128 и 128-256 от начала 37#
p42[]=primes([41,256]); pr19[]=primes([41,128]); p23[]=primes([128,256]);
mask7[]=vector(19,[]);\\Битовые маски разрешённых остатков по 19 простым 41-128
list8[,]=matrix(23,19];\\Список запрещённых остатков (их всегда 19) по 23 простым 128-256
for(bi=floor(base/37#),(base+1e17-1)/37#,
b=bi*37#; bm[]=vector(19+23,b%p42[]);\\Остатки по простым на начало диапазона 37#
forstep(i=1,#tab[],32,\\Цикл по таблице 37#
m32[]=vector(32,1);\\Пока все числа допустимы
forprime(p=41,128,
PAR: m32[]=m32[] and mask7[p][(mm[i..i+31,1..19]+bm[1..19])%p19[]];\\Параллельное вычисление 32-х остатков по модулю простого p и накопление в m32 только разрешённых чисел
if(m32[]==0, next(2));\\Если разрешённых чисел среди 32 не осталось, т.е. весь массив равен 0, переходим к следующему i
);
foreach(select(x->x==1,m32[],1),n,\\Цикл только по номерам ненулевых элементов в m32[]
PAR: m23[]=(mm[b+tab[i]+n,20..42]+bm[20..42])%p23[];\\Параллельное вычисление остатков одного числа b+tab[i]+n по 23 модулям простых 128-256
for(j=1,19, PAR: if(m23[]==list8[1..23,j], next(2)));\\Если хоть по одному простому число запрещено переходим к следующему n (сравнение параллельно сразу по всем 23 простым)
print(b+tab[i]+n);\\Тут какая-то дальнейшая проверка
);\\Цикл по кандидатам в m32[] после первого отсева
);\\Цикл по таблице 37#
);\\Цикл по 1e17
}
Всё правее символов "PAR:" выполняется одновременно для всего массива. Могу и на PARI корректно написать (вместо PAR сделать через apply()), но получится ещё более громоздко и менее понятно.
Ну и как сюда вкорячить парные числа то ... Они ж при совсем другом и base и bi и b. Да плюс среди m32[] их может быть и не одно, там же сразу 32 числа проверяются ...
такта на число (время второго фильтра не растёт вплоть до 32 проверяемых простых). Выигрыш 7% в скорости. При двухкратном проигрыше в объёме вычислений. Однозначно отказать.
тактов, а за 
такта или за 1.3 такта на число. Выигрыш -0.7 такта на число, или с 4.7 до 4.0 такта на два фильтра. Всего 18%! А при учёте прочих фильтров упадёт и до 15%. При 60% ускорении вычислений! Вот важность ускорять лишь критичные места, а не абы что. И первый фильтр при всей его важности оказывается не столь уж критическим местом.
встречается 16 раз из 64. Как это использовать — не понятно. Может кому идея придёт.
надо считать остатки не для 1-го числа и не для 6-го, а для центрального, 10-го. Тогда аппендикс всегда будет вверху, в первой строчке. И каждый остаток будет иметь парный, дополняющий его до 
. Например, здесь 
и 
.
кандидат, то и парный кандидат известен:
.
и перебираем как обычно снизу вверх диапазон 
. От 105 до 135. Не нашли ни одного подходящего числа по модулям 2-7. Значит симметричный диапазон 
с другой стороны от 105, то есть от 75 до 105, можно вообще не проверять. Ближайшие подходящие числа 73 и 137.
окажется пустым после проверки по 2-67. Но все оставшиеся числа в диапазонах (сколько их в среднем остаётся?) 
и 
будут в одинаковом количестве и на симметричных относительно 
или около 6%.