Пентадекатлон мечты

[EUgeneUS]

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

Медленнее разве что основной комп Дмитрия,

И мой\мои

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

И в одном потоке. И на моём компе.

Это понятно.

Некоторые предложения по ускорению (сорри, если уже сделано).

1. Надо уходить от "давайте поделим на какое-нибудь число, чтобы потом при каждой итерации на него умножать".

$n=n_0 + 6 \cdot \text{LCM} \cdot i$, всё тоже самое, но минус одно умножение в цикле.
$n_0$ и $\text{LCM}$, конечно заранее посчитали.

От второго умножения тоже можно избавиться:
$n_{i+1}=n_i + 6 \cdot \text{LCM}$, только прибавлять нужно для каждого $i$ (до длинного ифа), а умножать можно для 40% из них (после длинного ифа).

2. Оптимизация длинного ифа.
а) для простых $5, 7, 11, 13,$ можно заранее составить список запрещенных остатков по модулю $5 \cdot 7 \cdot 11 \cdot 13=5005$, и проверять эти остатки за одно вычисление модуля по $5005$ и за одну проверку в списке. Это вроде бы должно быть быстрее, чем четыре раза считать модуль. Но не уверен.

б) На всякий случай: делает ли PARI\GP оптимизацию в ифах? То есть прекратит ли он считать все остатки, в случае неудачи в начале? Если нет, или нет уверенности, то это нужно делать руками.

[Yadryara]

EUgeneUS в сообщении #1705815 писал(а):

На всякий случай: делает ли PARI\GP оптимизацию в ифах?

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

Да, немало идей уже реализовано. Например:

EUgeneUS в сообщении #1705815 писал(а):

2. Оптимизация длинного ифа.
а) для простых $5, 7, 11, 13,$ можно заранее составить список запрещенных остатков по модулю $5 \cdot 7 \cdot 11 \cdot 13=5005$, и проверять эти остатки за одно вычисление модуля по $5005$ и за одну проверку в списке. Это вроде бы должно быть быстрее, чем четыре раза считать модуль.

Две идеи, которые предложил впс, уже отрабатывались.

1. Можно вообще не выполнять терапевтику (проверку в длинном ифе) самых важных, самых маленьких модулей, а попросту разбивать программы на части. Например, по модулю 5 не проверять, а экономить 20% перебора, запуская 4 программы.

2. Объединение модулей. Вы тоже об этом подумали.

И обе идеи дают ускорение. И нужна балансировка для каждого компа.

3. Дмитрий ранее предлагал ещё проверку делать биттестом. Я об этом вспомнил и попытался применить. И именно на практике обнаружил, что выигрыш по времени происходит, когда биттестом проверяешь разрешённые остатки, а не запрещённые. И именно для моего компа это даёт ускорение. Даже несмотря на огромные числа.

Ну и таких примеров масса.

[EUgeneUS]

Yadryara
ИМХО, не нужно адаптировать по каждый комп.

А известно ли во сколько раз быстрее работает isprime, чем factor для чисел $10^{48} ... 10^{53}$?

-- 14.10.2025, 10:13 --

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

Да, немало идей уже реализовано.

Избавление от умножений в цикле реализовано?

-- 14.10.2025, 10:18 --

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

1. Можно вообще не выполнять терапевтику (проверку в длинном ифе) самых важных, самых маленьких модулей, а попросту разбивать программы на части. Например, по модулю 5 не проверять, а экономить 20% перебора, запуская 4 программы.

Из остатков по модулю $5005$ живых будет $2880$, можно их посчитать (один раз для каждого паттерна), а потом перебирать автоматически.

-- 14.10.2025, 10:23 --

EUgeneUS в сообщении #1705822 писал(а):

Из остатков по модулю $5005$ живых будет $2880$, можно их посчитать (один раз для каждого паттерна), а потом перебирать автоматически.

Кстати, тогда уж и тройку туда же: Из остатков по модулю $15015$ живых будет $5760$.

-- 14.10.2025, 11:06 --

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

И пониже посмотрю. Это же не константа, параметры поиска можно и нужно варьировать.

Это не константа в том смысле, что зависит:
0. От того, какую цепочку ищем и по какому типу паттернов.
1. От желаемой вероятности найти цепочку.
2. От количества паттернов.
3. Немного зависит от того, как обрабатываются разрешенные остатки по модули три.
Если всё, что выше задано, то это константа.

[EUgeneUS]

EUgeneUS в сообщении #1705822 писал(а):

А известно ли во сколько раз быстрее работает isprime, чем factor для чисел $10^{48} ... 10^{53}$?

Поясню откуда вопрос.
Пусть isprime быстрее работает, чем factor, в 100 раз.
Тогда после проверки на простоту обязательных простых, нужно проверять на простоту остальные числа (18 штук), до первого попадания в простое.

Тогда за $18/100$ от времени факторизации, получаем дополнительную фильтрацию перед отправкой на факторизацию $0.94^{18} \approx 0.328$, в три раза. Даже немного больше.

[vicvolf]

VAL
Критерий допустимости расстояния $d$

Для $A_1 = 2^{34}, A_2 = 3^{34}$:

$d$ допустимо ⇔ ∃ простые $p, q$: $3^{34}q - 2^{34}p = d$

Минимальное допустимое расстояния $d$:
$d_{\text{min}} = 3^{34}\cdot 2 - 2^{34}\cdot 3 \approx 3.3\times 10^{16}$

[Yadryara]

EUgeneUS в сообщении #1705822 писал(а):

Избавление от умножений в цикле реализовано?

Вроде не реализовано. Я внимательно в эту сторону пока не смотрел.

Всё ещё не дошли руки наладить автоматизированный сбор статистики. 8 потоков пока работают. Картина по слабым приближениям уже более-менее понятная:

0 — 1e51

Valids         7 8 9   10   11   12   13   14   15   16   17   18   19   20   21
Приб    123        2    3         2    4    1    2    1                               15

Приб    124      4 1    1    4    4    4    1         1                               20
Приб    125    1   1    2    3    4    7    2    5    3                               28
Приб    126      1 2    1    5    3    3    2    3                                    20
Приб    127        1         2    5    4    5    2    1    1                          21
Приб    128             3    6    3    3    3    1    3                               22
Приб    129    1 1 2    1    3    1    9    4    3                                    25
________________________________________________________________________________________
               2 6 9   11   23   22   34   18   16    9    1                         151

Верхнюю строчку ещё не досчитал. Из-за того, что она по-прежнему считается для в 10 раз большего диапазона: 0-1e52.

Ещё и в других паттернах найдены приближения. Покажу пока наилучшие:

                                                                             Valids
178380987012396308863900153677813852686655763044946   1 1111111111111 11  1      17
86174083595630569956285027121743705191886528900946     11 1 1 11111111111 1      16
104294449752115369891319446528628065539537370668946   11  1111111 1 11 1111      16
295415766633890967695868882781142450066682604736146   1 1111111111111  1  1      16
426177122559697931539690746264517602313535884476946   1 11111 11111 11 11 1      16
428302514214814024822755190512136462009263089460946   1111111111 1  1111  1      16
536485877155679109909361726753963129692995263246546   1 1 11111111111 1  11      16
614729180547673494252251341610226140422432039736146   1111 11 111 1 111 111      16
703847910379081045003610200533905190084822515566546   11 1111 11111 1 11 11      16
953802445779976491201723818940647104284640217052946   1 11111 11 11111 1 11      16
954362124827898235312664833988160660856220507278546   1111 11 1 11111 1 111      16
958060655676002182969017719449293633922929570531346   1111111 11 11 11 1 11      16
969753822486232787519188100369583182149298433334546   1111111 111  1111  11      16

[Dmitriy40]

EUgeneUS в сообщении #1705815 писал(а):

б) На всякий случай: делает ли PARI\GP оптимизацию в ифах? То есть прекратит ли он считать все остатки, в случае неудачи в начале? Если нет, или нет уверенности, то это нужно делать руками.

Да, вычисления "ленивые", до первого результата, код if(x>0&&5/x>1,...) работает даже с x=0. Это сделано специально, не столько даже ради ускорения, сколько ради допустимости конструкций типа if(k>0&&v[k]>7,) если k может быть и меньше 1.

EUgeneUS в сообщении #1705815 писал(а):

1. Надо уходить от "давайте поделим на какое-нибудь число, чтобы потом при каждой итерации на него умножать".

Теоретически да, практически смысла мало: вычисление с двумя умножениями p=p1+m*i;n=a*p-20 выполняются за 780нс, а два сложения p+=m;n+=am; выполняются за 700нс. И хотя казалось бы выигрыш более 10%, но это всего 80нс из примерно 3.2мкс на проверку у Yadryara или порядка 2.5%. Сделать можно ибо просто, хотя эффект почти незаметен.
Отказ от вычисления p невыгоден, всё равно же придётся его вычислять, не умножением (сложением), так делением, а это точно медленнее.
Можно даже два других простых тоже вычислять сложениями, а не делениями, вот это даст бОльший эффект, хотя тоже не особо, всего 200нс выигрыш, правда это уже 6.3% от 3.2мкс.

EUgeneUS в сообщении #1705822 писал(а):

А известно ли во сколько раз быстрее работает isprime, чем factor для чисел $10^{48} ... 10^{53}$?

А Вы видели что в программе уже три цикла с factor (третий с numdiv которая тот же factor)? И Вы про какой спрашиваете, наверное про первый как самый часто запускаемый? А он выполняет не factor(), а factor(,30000), что довольно сильно отличается ибо проверяет лишь делители до 3e4 (и этим числом можно ещё и играться ради общей скорости на конкретном диапазоне чисел), зато для всех мест где они возможны и при первой же ошибке кандидат выкидывается.
Плюс и isprime() у нас с Антоном выполняется в другом виде, позволяющем отвергнуть кандидата на 10% быстрее.
И разумеется порядок проверок isprime и factor исследовался и тестировался и выбран быстрейший.

EUgeneUS в сообщении #1705834 писал(а):

Пусть isprime быстрее работает, чем factor, в 100 раз.

isprime() намного быстрее factor() (последний в любом случае делает и isprime, как минимум для проверки последнего числа в разложении, плюс для всех найденных достаточно больших делителей). Но isprime() медленнее factor(,30000) (хотя и быстрее factor(,300000)) - и этим я с Антоном пользуемся.

EUgeneUS в сообщении #1705822 писал(а):

Кстати, тогда уж и тройку туда же: Из остатков по модулю $15015$ живых будет $5760$.

Тройка обычно учитывается вместе с двойкой при умножении lcm(v)*6 и коррекции p1 (тот самый +5/6*m).

[EUgeneUS]

Dmitriy40
Спасибо за разъяснения.

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

И разумеется порядок проверок isprime и factor исследовался и тестировался и выбран быстрейший.

Прекрасно.

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

А Вы видели что в программе уже три цикла с factor (третий с numdiv которая тот же factor)?

Видел, но мельком. С момента возобновления темы озадачился подсчетом шансов и подробно в оптимизации кода не разбирался.
Кстати, а откуда можно забрать текущую версию со всеми оптимизациями?

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

Тройка обычно учитывается вместе с двойкой при умножении lcm(v)*6 и коррекции p1 (тот самый +5/6*m).

Это я помню. И уже отмечал, что такая работа с тройкой выбрасывает половину "хороших" цепочек и увеличивает $N$ как минимум в два раза.
Вчера показывал с числами, как это влияет на примере $D(12.15)$, чуть позже выложу для $D(48,21)$

-- 14.10.2025, 15:25 --

Вот при выполнении такого же количества проверок i (до фильтрации длинным ифом)

Обновил. Выводил к одинаковой вероятности 0.900:
Для 6*lcm:

p1   3.04758E+40
m   5.5416E+38
a   320226
i (на паттерн)   1115000000
I_all = I*(паттернов)   3.345E+14
   
паттернов   300000
n = 0.4*(паттернов)*i   1.338E+14
p = (p1 + m*i)   6.17888E+47
N=a*p-20   1.97864E+53

P(1)   1.72251E-14
P(win)==1-(1/EXP(1))^(P(1)*n)   0.90021322

Для 2*lcm

p1   3.04758E+40
m   5.5416E+38
a   320226
i (на паттерн)   1535000000
I_all = I*(паттернов)   4.605E+14
   
паттернов   300000
n = 0.2676*(паттернов)*i   1.2323E+14
p = (p1 + m*i)   8.50635E+47
N=a*p/3-20   9.07985E+52
P(1)   1.87171E-14
P(win)==1-(1/EXP(1))^(P(1)*n)   0.900391699

Разница.
а) Для 6*Lcm N больше: 1.97864E+53 против 9.07985E+52
б) А вот количество итераций больше у 2*lcm: 4.605E+14 против 3.345E+14. Но для 2*lcm в количество итераций входят и итерации с плохим остатком по модулю 3.

[Dmitriy40]

EUgeneUS в сообщении #1705870 писал(а):

И уже отмечал, что такая работа с тройкой выбрасывает половину "хороших" цепочек и увеличивает $N$ как минимум в два раза.

Я поиском не занимаюсь, так что тогда переспрашивать не стал (были другие непонятные вопросы), а теперь вот поясните пожалуйста что Вы тут имеете в виду, что за "хорошие" цепочки выбрасываются, плохо это или хорошо в плане проверки, и с чего вдруг берётся удвоение N (это ведь ожидаемое количество проверенных кандидатов, да?), ведь мы наоборот отбрасываем точно "плохие" цепочки, которые иначе стали бы проверяться, т.е. N должно наоборот вдвое уменьшаться для того же диапазона по n? Либо я что-то не понял.

EUgeneUS в сообщении #1705870 писал(а):

Кстати, а откуда можно забрать текущую версию со всеми оптимизациями?

Несмотря на сказанное, лучше брать как раз у него, именно у него точно работающий вариант, у меня скорее куча тестовых (я уже сам забываю какие из них более-менее боевые потому что мне таковые просто не нужны были):

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

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

[EUgeneUS]

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

и с чего вдруг берётся удвоение N (это ведь ожидаемое количество проверенных кандидатов, да?),

Нет, у меня выше $N$ - это число в цепочке, до которого нужно считать, чтобы получить заданную вероятность.
$i$ - количество итераций до\без длинного ифа.
$n$ - количество кандидатов после длинного ифа (оно нужно для расчета финальной вероятности).

-- 14.10.2025, 15:45 --

$0.4$ - коэффициент фильтрации длинным ифом, если фильтровать по остаткам от модуля 5 и больше.
$0.2676$ - коэффициент фильтрации длинным ифом, если фильтровать по остаткам от модуля 3 и больше.

-- 14.10.2025, 15:47 --

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

а теперь вот поясните пожалуйста что Вы тут имеете в виду, что за "хорошие" цепочки выбрасываются, плохо это или хорошо в плане проверки,

По модулю три есть один плохой остаток и два хороших.
Если используем 6*lcm, то выбрасываем плохой остаток и один хороший. Приходится считать до чисел (до $N$) в два раза больше (на самом деле, несколько больше, чем в два раза).

[Dmitriy40]

EUgeneUS в сообщении #1705875 писал(а):

Нет, у меня выше $N$ - это число в цепочке, до которого нужно считать, чтобы получить заданную вероятность.

Да, понятно, я это и имел в виду, только выразился криво, точнее думал одно, а написал другое.

EUgeneUS в сообщении #1705875 писал(а):

$0.2676$ - коэффициент фильтрации длинным ифом, если фильтровать по остаткам от модуля 3 и больше.

Очевидно опечатка, должно быть $0.2(6)\approx 0.2667$ или $0.267$.

EUgeneUS в сообщении #1705875 писал(а):

По модулю три есть один плохой остаток и два хороших.
Если используем 6*lcm, то выбрасываем плохой остаток и один хороший.

Он "хороший" только по модулю 3, а вот по модулю 2 он "плохой" и такие цепочки точно не нужны.
По модулю 6 вообще лишь один "хороший" остаток. Несмотря на то что по модулю 3 их таких два.
Почему и не понимаю с чего Вы удваиваете, когда как был один "хороший" остаток по модулю 2, так он и остался одним уже по модулю 6 (с учётом тройки), не вижу удвоения. И почему тогда не утроение (было по модулю 2, стало по модулю 6). Какая-то тут путаница, у Вас или у меня или у обоих.
А вот по остальным модулям остатки уже не перекрываются и там честное умножение количества остатков. Почему такая аномалия с 3 я не помню.

-- 14.10.2025, 16:13 --

EUgeneUS в сообщении #1705875 писал(а):

$n$ - количество кандидатов после длинного ифа (оно нужно для расчета финальной вероятности).

И давайте это назовём $k$ (Кандидатов), так как $n$ уже занято в формулах и программах (хотя я обычно использую $x$) под начальное число цепочки, тоже будет путаница.
С $i$ кстати тоже будет путаница, Вы сделали это не индексом как у нас везде, а количеством, что плохо, назовите это скажем $b$ или ещё как кроме $p,m,i,j,q,r,s,n,k$.

-- 14.10.2025, 16:22 --

EUgeneUS
Смотрите, при данном $N$ количество $i$ (без всяких оптимизаций) равно $i=N/m, m=\lcm (v)$.

Количество $k$ (кандидатов) равно $i$ если оптимизаций (длинного if) нет.

Если учитываем остатки по модулю 2, то $k=\frac{1}{2}i$.

Если учитываем остатки по модулю 3, то $k=\frac{2}{3}i$.

Но если учитываем остатки по модулю 6, то $k=\frac{1}{6}i$, а не $\frac{1}{2}\frac{2}{3}i$. Ну вот такая аномалия с 2 и 3.

Учёт следующих остатков в длинном if даёт $k=i \frac{1}{6} \prod\limits_{5\le p \le 59} \frac{p-1}{p}$.

Соответственно можно формулы развернуть для пересчёта из $k$ в $N$ (сколько надо перебрать чисел для выполнения $k$ проверок), аномалия с 6 от этого не исчезнет.

[EUgeneUS]

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

Он "хороший" только по модулю 3, а вот по модулю 2 он "плохой" и такие цепочки точно не нужны.
По модулю 6 вообще лишь один "хороший" остаток. Несмотря на то что по модулю 3 их таких два.

А вот этого я не понимаю, почему так получается.
По модулю два - один плохой из двух, по модулю три - один плохой из трёх.
В любой из шести возможных комбинаций по модулю 6 должно получаться четыре плохих и два хороших.

-- 14.10.2025, 16:29 --

Один хороший остаток по модулю шесть получается, только если по модулю три два плохих и один хороший.

[Dmitriy40]

EUgeneUS в сообщении #1705879 писал(а):

А вот этого я не понимаю, почему так получается.
По модулю два - один плохой из двух, по модулю три - один плохой из трёх.
В любой из шести возможных комбинаций по модулю 6 должно получаться четыре плохих и два хороших.

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

[EUgeneUS]

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

Количество $k$ (кандидатов) равно $i$ если оптимизаций (длинного if) нет.

$k$ - тоже не хорошо. У меня в выкладках занято. Предлагаю $l$.

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

С $i$ кстати тоже будет путаница, Вы сделали это не индексом как у нас везде, а количеством, что плохо, назовите это скажем $b$ или ещё как кроме $p,m,i,j,q,r,s,n,k$.

и $b$ - тоже не хорошо. У меня в выкладках занято. Предлагаю $x$ или $i_{M}$ ("максимальный $i$")

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

Количество $k$ (кандидатов) равно $i$ если оптимизаций (длинного if) нет.

1. $l$ (Ваше $k$) используется только в расчете финальной вероятности. Больше ни для чего оно не нужно.
2. Чтобы финальная вероятность рассчитывалась верно, в $l$ не должны учитываться цепочки, которые бракуются по остаткам простых, которые используются в паттерне. Могу объяснить почему так. Но это долго (upd: всё устройство "калькулятора шансов" надо будет рассказать).
И это не имеет никакого отношения к оптимизации, только к корректному расчету финальной вероятности.

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

Учёт следующих остатков в длинном if даёт $k=i \frac{1}{6} \prod\limits_{5\le p \le 59} \frac{p-1}{p}$.

Собственно, я его примерно так и рассчитывал (под названием "коэффициент фильтрации длинным ифом")
для 6*lcm:
$l = i_M \prod\limits_{5\le p \le 59} \frac{p-1}{p}$ (потому что 6*lcm)

а для 2*lcm:
$l = i_M \prod\limits_{3\le p \le 59} \frac{p-1}{p}$ (потому что 2*lcm)
Тут "аномалия" не учитывалась, конечно.

-- 14.10.2025, 16:49 --

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

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

Хорошо бы с этой аномалией разобраться. И почему именно с тройкой? Насколько помню, VAL говорил, что бракуется для каждого простого только один остаток.... Чуть позже поищу цитату...

-- 14.10.2025, 16:53 --

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

Соответственно можно формулы развернуть для пересчёта из $k$ в $N$ (сколько надо перебрать чисел для выполнения $k$ проверок)

Видимо, проще оперировать $i_M$, а $l$ (Ваше $k$) - пересчитывать через "коэффициент фильтрации длинного ифа".

[Dmitriy40]

EUgeneUS
По модулю 3 разрешён только один остаток, вот и никакой магии:

v=[   3698,   3971,   12,   49,   50,   5043,   362024,   529,   18,   4805,   28,   4107,   242,   841,   480,   289,   4418,   63,   4,   845,   320226   ];
print("v=",v);
print("lcm=",m=lcm(v));
{n0=lift(chinese([Mod(-j+1, v[j]) | j<-[1..#v]]));
mm=3;
print("Check by ",mm);
for(d=0,mm-1,
   n=n0+d*m;
   print1("d=",d,": ",y=[((n+j-1)/v[j])%mm | j<-[1..#v]]);
   if(#select(t->t==0,y)==0, print(" OK") , print);\\Для проверки по одиночным простым mm
   \\if(#select(t->(t<>1&&t<>5),y)==0, print(" OK") , print);\\Для проверки по mm=6
);}

v=[3698, 3971, 12, 49, 50, 5043, 362024, 529, 18, 4805, 28, 4107, 242, 841, 480, 289, 4418, 63, 4, 845, 320226]
lcm=29576058913001203166152762296391472723719200
d=0: [2, 1, 1, 1, 1, 2, 2, 2, 0, 2, 2, 1, 2, 2, 2, 1, 1, 1, 1, 1, 2]
d=1: [2, 1, 1, 1, 1, 2, 2, 2, 1, 2, 2, 1, 2, 2, 2, 1, 1, 0, 1, 1, 2]
d=2: [2, 1, 1, 1, 1, 2, 2, 2, 2, 2, 2, 1, 2, 2, 2, 1, 1, 2, 1, 1, 2] OK

Здесь расчёт в пространстве n, где сами цепочки, без всяких делений на коэффициент на месте перебираемого простого.

Для его использования надо n0 модифицировать в соответствии с d=2 и mm=3: n1=n0+d*lcm(v) и перебирать потом уже с шагом mm*lcm(v). Пересчёт из n1 в p1 для перебора по простым банален: p1=(n1+ip)/v[ip], m=lcm(v)*mm/v[ip].

-- 14.10.2025, 17:32 --

EUgeneUS
Причина аномалии с 3 в том что чисел в паттерне слишком много (больше одного), 3шт (проверяемых, с простыми), вот и не все p-1 остатков получаются допустимыми как было бы для единственного простого. С n19d252 (19 симметрично расположенных простых в интервале [0..252]) даже по модулю 17 было всего 2 допустимых остатка, остальные запрещались по одному или нескольким простым.