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

[wrest]

Спасибо mihaild , вот конвертация ТЗ на генератор паттернов в форумные теги.
Напомню, что это на основе опыта генерации паттернов для D(24,6).

Техническое задание: Адаптивный пуловый генератор CRT-условий (gp2c-совместимая версия, ред. 2.1)

$$ \begin{array}{|l|l|} \hline \textbf{Параметр} & \textbf{Значение} \\ \hline \textbf{Версия} & 2.1 \\ \textbf{Дата} & \text{2026-04-19} \\ \textbf{Статус} & \text{Утверждено к реализации} \\ \textbf{Целевой компилятор} & \texttt{gp2c -g} (\text{PARI/GP} \rightarrow \text{C}) \\ \hline \end{array} $$

---

1. Цель
Разработать алгоритм, генерирующий пул ранжированных CRT-систем $\{(x_0^{(k)}, M^{(k)}, \{M_i^{(k)}\})\}_{k=1}^K$, оптимизированных для поиска цепочек длины $L$ с заданным количеством делителей $\tau(x+i)=T$. Алгоритм должен динамически подбирать структуру модулей под любое $T \ge 2$, контролировать реальный шаг перебора через $\log(\text{lcm}(M_i))$ и полностью компилироваться в gp2c без предупреждений.

2. Термины и обозначения

$$ \begin{array}{|l|l|l|l|} \hline \textbf{Термин} & \textbf{Обозначение} & \textbf{Тип} & \textbf{Определение} \\ \hline \text{Длина цепочки} & L & \texttt{int} & \text{Количество последовательных чисел} \\ \text{Целевое } \tau & T & \texttt{int} & \text{Требуемое количество делителей} \\ \text{Модуль позиции } i & M_i & \texttt{int} & \texttt{conds[k][i]}\text{, гарантирует } \tau(M_i) \mid T \\ \text{Остаточное } \tau & \tau_R^{(i)} & \texttt{int} & T / \tau(M_i)\text{. Допустимый набор: } \{2,4,8,12\} \\ \text{Бюджет шага} & B_{\text{lcm}} & \texttt{real} & \texttt{max\_logLcm}\text{. Ограничивает } \log(\text{lcm}(M_0,\dots,M_{L-1})) \\ \text{Начальное смещение} & x_0 & \texttt{int} & \text{Решение CRT: } x_0+i \equiv 0 \pmod{M_i} \\ \text{Шаг CRT} & M & \texttt{int} & \text{lcm}(M_0,\dots,M_{L-1}) \\ \text{Вес вероятности} & w(\tau_R) & \texttt{real} & \text{Эмпирический приоритет остатка} \\ \hline \end{array} $$

3. Математическая модель

3.1. Допустимые остатки и веса
Эмпирически установлено, что остатки $\tau_R=3$ и $\tau_R=6$ требуют редких структур ($p^2$ или $p_1p_2^2$) и катастрофически снижают плотность поиска. Они жёстко отсекаются.

$$ \begin{array}{|l|l|l|l|l|l|} \hline \tau_R & 4 & 8 & 12 & 2 & 6, 3 \\ \hline w(\tau_R) & 1.00 & 0.55 & 0.05 & 0.15 & \textbf{0.0 (\text{отсев})} \\ \hline \end{array} $$

3.2. Бюджет по НОК
Шаг перебора определяется $M = \text{lcm}(M_0,\dots,M_{L-1})$. Алгоритм обязан вычислять и ограничивать log(lcm(M_i)). Контроль через $\sum \log M_i$ не допускается как математически неточный.

3.3. Корреляции CRT
Структура CRT создаёт положительную корреляцию делителей соседних чисел. Совместная вероятность оценивается как:

$$P_{\text{chain}} \approx \prod_{i=0}^{L-1} P(\tau(R_i)=\tau_R) \cdot \rho^{\frac{L(L-1)}{2}}, \quad \rho \approx 1.05\dots1.08$$

4. Архитектура и этапы алгоритма

Этап 1: Инициализация и пул простых

• Предвыделение статических матриц pool_conds[K,L], pool_lcm[K], pool_scores[K].
• Генерация массива простых до primepi(max(2000, L+500)).

Этап 2: Распределение малых простых

• Для каждого $p \le \min(L, 60)$ выбирается offset с минимальным числом конфликтов делимости.
• offset рандомизируется среди допустимых для обеспечения разнообразия пула.
• $p$ назначается позициям, где $T \bmod \tau(M_i \cdot p) == 0$.

Этап 3: Добивка с контролем lcm

• Цикл продолжается, пока log(pool_lcm[k]) < max_logLcm.
• На каждом шаге ищется позиция с максимальным $\tau_R > 8$.
• Подбирается наименьшее $p > L$, не использованное в текущей системе.
• Проверяется: log(lcm(current_lcm, p^e)) <= max_logLcm и допустимость нового $\tau_R$.
• При успехе обновляется pool_conds[k] и pool_lcm[k].

Этап 4: Решение CRT и фильтрация

• Последовательное применение chinese(). При несовместности $\gcd(M_i,M_j) \nmid |i-j|$ система помечается score = -1.0.
• Жёсткий фильтр: если хотя бы одна позиция имеет $\tau_R \in \{3,6\}$ или $\tau_R > 12$, система отбраковывается.
• Скор рассчитывается как $S_k = \frac{\sum w(\tau_R^{(i)}) \cdot \prod_{p \le L, p|M_i}(1-1/p)}{\log(M)}$.

Этап 5: Сортировка и дедупликация

• Пул сортируется по убыванию $S_k$.
• Удаляются дубликаты по паре $(x_0, M)$. Хвост матрицы обнуляется.

5. Требования к gp2c-совместимости (Фактические)

1. Комментарии: Запрещён синтаксис //. Использовать только /* ... */ или \ для конца строки.
2. Управление потоком: Ключевое слово continue отсутствует в GP. Использовать next.
3. Динамические структуры: В строгом режиме gp2c -g не рекомендуется использовать List(), mapcreate(), concat() в горячих циклах. Предпочтительны статические vector()/matrix() с предварительным выделением памяти.
4. Область видимости: Все переменные должны быть объявлены в my(...) в начале тела функции.
5. Синтаксис выражений:
   
   • Стандартное деление / допустимо без явного приведения типов.
   • Конструкции if(cond, action); полностью валидны.
   • Критично лишь корректное закрытие всех скобок (), {} и [], а также отсутствие разрыва операторов if(...) символом новой строки внутри списка аргументов.

6. Выходные данные
Матрица размера K × (5 + L):
[ [L, T, x0, M, score, M_0, ..., M_{L-1}], ... ]
Отсортирована по убыванию score. Недействительные системы имеют score = -1.0 или нулевые строки.

7. Вспомогательные функции

$$ \begin{array}{|l|l|l|l|} \hline \textbf{Функция} & \textbf{Вход} & \textbf{Выход} & \textbf{Назначение} \\ \hline \texttt{analyze\_chains} & \text{matrix, int, int} & \text{int(1/0)} & \text{Построчная статистика: плотности по позициям, распределение совпадений, оценка корреляции CRT} \\ \texttt{generate\_crt\_pool} & \text{int, int, real, int, int, int, int} & \text{matrix} & \text{Основной генератор с контролем lcm и динамическим подбором структур} \\ \texttt{search\_chains\_fast} & \text{matrix, int, int, int} & \text{int} & \text{Оптимизированный поиск с прогресс-баром и ранним выходом} \\ \hline \end{array} $$

8. Критерии успеха

1. gp2c: gp2c-run -g script.gp выполняется без ошибок и предупреждений. Время компиляции < 2с.
2. Математика: Пул содержит только системы с $\tau_R \in \{2,4,8,12\}$. Бюджет log(lcm) не превышен. CRT-совместность гарантирована.
3. Производительность: При $L=6, T=24, \log M \approx 28$ генерация пула $K=20$ занимает < 10 мс в скомпилированном виде. Поиск 50 цепочек на $10^5$ шагов занимает < 3 сек.
4. Стабильность: Детерминированность при seed, корректная работа для $T \in \{24, 36, 48, 96, 192\}$, $L \le 12$.
5. Анализ: analyze_chains выводит статистику по каждой системе отдельно, позволяя выявлять "узкие" позиции ($\tau_R$ с низкой плотностью).

9. Эмпирические ограничения и рекомендации

• Для $T=24$ оптимальна конфигурация $\tau_R = [4,4,4,4,4,4]$ или $[4,4,4,4,8,8]$ с $\log(\text{lcm}) \approx 26\text{--}29$.
• При $T > 96$ или $L > 10$ рекомендуется увеличивать K до 30–50 и ослаблять max_logLcm на 10–15%.
• Алгоритм использует жадную эвристику с оценкой lcm. Для $T > 192$ возможна частичная деградация плотности; в таких случаях предпочтительно увеличивать pool_size, а не бюджет.

---
✅ Документ готов к использованию как эталонная спецификация для разработки, компиляции и сопровождения пулового генератора CRT-условий.

[Yadryara]

wrest в сообщении #1722859 писал(а):

Математика: Пул содержит только системы с $\tau_R \in \{2,4,8,12\}$

Ну, как видите, мы традиционно работаем только с 1-ми степенями простых. Так что 2, 4, 8 для 24-х делителей (лучше обозначить D), 2, 4, 8, 16 для 48 делителей, 2, 4, 8, 16, 32 для 96 делителей и так далее.

Неслучайно же у меня в обозначении серии через дефис идут только 5 чисел (не считая того что с факториалом). Это как раз и есть количество мест с 2, 4, 8, 16, 32.

[EUgeneUS]

wrest
По Вашему ТЗ нашел весьма спорное место.
Но прежде, чем его обсуждать нужно договориться о терминах. Хотя бы в рамках этой ветки обсуждения.

"Батчем" будем называть структуру, когда расставлены только обязательные простые, то есть простые меньше или равные длине цепочки.
"Паттерном" будем называть структуру, когда расставлены обязательные простые, а также необязательные простые (большие длины цепочки) в степенях больше единицы.

Так вот,
а) для для некоторых цепочек количество "батчей" будет сотни миллионов, может даже больше. Но с этим ещё как-то можно жить при некоторых ухищрениях.
б) а для некоторых цепочек количество паттернов может быть огромным количеством на один батч! Например, для $D(36,14)$ подставляется 17 квадратов простых и количество паттернов на один "батч" - $17!$

Да, и не нужно генерировать паттерны: как расставлять степени необязательных простых и как их перебирать - вполне понятно из структуры батча и реализуется в программе поиска цепочек, а не в программе генерации паттернов\батичей.

В вот теперь странное место:

wrest в сообщении #1722841 писал(а):

| Остаточное $\tau$ | $\tau_R^{(i)}$ | `int` | $T / \tau(M_i)$. Допустимый набор: $\{2,4,8,12\}$ |
...
Эмпирически установлено, что остатки $\tau_R=3$ и $\tau_R=6$

С одной стороны, Вы исключаете $\tau_R=6$. Хотя для генерации батчей оно вполне подходит.
С другой стороны, Вы допускаете $\tau_R=12$, которая даёт очень плохую $p^2qr$, и не подходит для паттерна.

Итого.

1. Рекомендую строить - батчи, а не паттерны. Хотя бы потому что Вы хотите универсальный генератор, а набор паттернов для многих цепочек будет генерироваться до погасания звезд.
2. Тогда допустимые остаточные $\tau_R$ - любые чётные. Нечетные выбрасываются.
3. Так как строим батчи - контроль "бюджета" lcm - излишен.
4. Что будет полезно, как писал ранее - ограничивать степени обязательных простых, которые могут использоваться в батчах. Вида: "$2$ - не более $2^8$, $3$- не более $3^5$, ...., остальные: не более, чем в квадрате".

-- 21.04.2026, 15:06 --

"Эмпирический" приоритет остатка, Вы можете связать с количеством простых в первой степени в остатке.

Например, количество делителей остатков $\tau_R = 4, 12, 20 ...$ будут иметь одинаковый "приоритет остатка". Так как после подстановки степеней более 1, во всех них останется $pq$.

[Yadryara]

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

Вида: "$2$ - не более $2^8$

Не согласен. Для 96 делителей активно используется $2^{11}$. Посмотрите рекордные цепочки длиной 18 и 19.

Да что там рекордные, я уже начиная с D(96,12) активно использую $2^{11}$. Правда, не уверен что это самый быстрый вариант, но шаг точно минимальный, потому что 64 меньше чем 67, 71, 73 и так далее, которые тоже ставятся в паттерн.

[wrest]

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

С другой стороны, Вы допускаете $\tau_R=12$, которая даёт очень плохую $p^2qr$, и не подходит для паттерна.

Да, это надо тоже исключить, т.е. оставить только степени двойки. $p^2qr$ и $p^2q^3$ должны быть слишком редки чтобы тратить на них время.

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

-- 21.04.2026, 15:32 --

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

Так вот,
а) для для некоторых цепочек количество "батчей" будет сотни миллионов, может даже больше. Но с этим ещё как-то можно жить при некоторых ухищрениях.
б) а для некоторых цепочек количество паттернов может быть огромным количеством на один батч! Например, для $D(36,14)$ подставляется 17 квадратов простых и количество паттернов на один "батч" - $17!$

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

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

-- 21.04.2026, 15:47 --

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

4. Что будет полезно, как писал ранее - ограничивать степени обязательных простых, которые могут использоваться в батчах. Вида: "$2$ - не более $2^8$, $3$- не более $3^5$, ...., остальные: не более, чем в квадрате".

Да, это ограничивается бюджетом. Но не только Генератор так же принимает в качестве параметра максимальное значение одного модуля в паттерне, и 5^5 например туда попадать не должно по этой причине.

[EUgeneUS]

wrest в сообщении #1722864 писал(а):

. $p^2qr$ и $p^2q^3$ должны быть слишком редки чтобы тратить на них время.

Для батчей $\tau_R=12$ допустимо, а часто - необходимо.

wrest в сообщении #1722864 писал(а):

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

Вы попадете на какой-то батч, который даст $17!$ паттернов, которые будете перебирать до морковкиного заговения, и так и не узнаете, есть ли другой lcm

wrest в сообщении #1722864 писал(а):

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

Не совсем верно поняли мотивацию. Вот так верно:
"Давайте искать в генераторе батчи, а не паттерны, так как
а) в общем случае перебрать все паттерны невозможно из-за их огромного количества
б) это не нужно"

Все "генераторы", которые упоминались в теме работают именно так - ищут батчи.
И у Хуго в pcoul (точно - сам пользовался), и, насколько понимаю, у Дмитрия, и у Yadryara.

-- 21.04.2026, 15:58 --

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

EUgeneUS в сообщении #1722862

писал(а):

Вида: "$2$ - не более $2^8$ 

Не согласен. Для 96 делителей активно используется $2^{11}$. Посмотрите рекордные цепочки длиной 18 и 19.

Вы, если чего-то не понимаете из написанного - так спросите (хотя не факт, что Вам отвечу), а не пишите ерунду.
Над словом "вида" подумайте.

-- 21.04.2026, 16:07 --

wrest
Ещё вот на что обратите внимание.

1. Пусть на каких-то найденных примерах мы назначили какой-то паттерн оптимальным (чтобы это не означало).
2. Оптимальная стратегия поиска - это искать по максимальному количеству таких паттернов.
3. А значит нам нужно найти их все.

Пусть есть 500 батчей, в каждом $11!$ паттернов, итого: $19958400000$ паттернов.
Их надо найти все, из какого-то безумного количества других. И как-то с этим количеством паттернов работать при поиске цепочек.

Гораздо удобнее найти все 500 батчей из сотен миллионов батчей. А потом перебирать $11!$ квадратов необязательных простых уже в программе поиска цепочек.

[Yadryara]

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

Вы, если чего-то не понимаете из написанного - так спросите

Я обычно так и делаю. Если мне что-то непонятно, так и говорю. Вполне возможно, что и в этом, и в каких-то других случаях я что-то неправильно понял.

Спрашиваю: почему нужно ограничивать степень 2-ки 8-кой, а не 11-кой? Ведь wrest писал не только о 96-ти, но и о 192-х делителях.

[EUgeneUS]

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

Спрашиваю: почему нужно ограничивать степень 2-ки 8-кой, а не 11-кой?

Отвечаю вопросом на вопрос - а с чего Вы так решили?
Подсказка: Вы проигнорировали подсказку.

[wrest]

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

Для батчей $\tau_R=12$ допустимо, а часто - необходимо.

Да, это понятно. Если мы в t_R=12 батча собираемся сами вставить квадрат необязательного простого, а не ждать этой милости от природы, то t_R паттерна перестанет делиться на три и всё будет хорошо.

-- 21.04.2026, 16:14 --

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

Вы попадете на какой-то батч, который даст $17!$ паттернов, которые будете перебирать до морковкиного заговения, и так и не узнаете, есть ли другой lcm

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

[EUgeneUS]

wrest в сообщении #1722872 писал(а):

Ненене, сейчас генератор ищет не более заданного количества кандидатов.

беда.

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

Пусть есть 500 батчей, в каждом $11!$ паттернов, итого: $19958400000$ паттернов.
Их надо найти все, из какого-то безумного количества других.

Это вполне близкие к реальным числа при поиске одной из недавних рекордных цепочек.

[wrest]

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

2. Оптимальная стратегия поиска - это искать по максимальному количеству таких паттернов.
3. А значит нам нужно найти их все.

Это до меня пока что ещё не дошло.
Понимаете, текущая (у меня) реализация поиска до начала поиска строит две таблицы (два вектора, массива) -- с остатками от деления n0 (результата КТО) и m (НОКа) на простые до примерно от 2^20 до 2^24 а это соответственно от 10^5..10^6 элементов в каждой таблице (векторе) и нужно два длинных деления на каждое табличное простое.
Вкоде это выглядит так:

\\ вычисляем остатки по всем малым простым диапазона, используются как константы
my(pr:vecsmall=Vecsmall(primes([pat_prime_lim,lim]))); \\ вектор с простыми
my(pr_q=#pr):small; \\ и сколько их там оказалось
my(pmods_n0:vecsmall=vectorsmall(pr_q,i,n0%pr[i])); \\вектор с остатками по простым по n0
my(pmods_m:vecsmall=vectorsmall(pr_q,i,m%pr[i])); \\ вектор с остатками по простым по m

Там pat_prime_lim это нижняя граница простых, около 100
lim - верхняя граница, это параметр, может быть до 2^24

Это некоторый обмен памяти на скорость. И это занимает время. Я не знаю/не помню сколько надо проверить цепочек чтобы оправдать построение этих векторов, но конечно не единицы. Поэтому я пока что не готов к концепции ускорения генерации паттернов: это поменяет алгоритм проверки в сторону замедления.

-- 21.04.2026, 16:29 --

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

беда.

Так это в русле "попробуйте сами сделать несколько паттернов"

[Yadryara]

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

Подсказка: Вы проигнорировали подсказку.

А, ну понял вроде. Вы говорили не о топовых количествах делителей, а о 36, 72. Про 108 вряд ли..

wrest, да, я же только совсем недавно выше написал, у меня ГенПат, грубо говоря, работает только по обязательной программе, формирует только болванку.

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

[wrest]

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

да, я же только совсем недавно выше написал, у меня ГенПат, грубо говоря, работает только по обязательной программе, формирует только болванку.

Я понимаю, что за 300 страниц этой темы вы, возможно, перепробовали все что можно и у вас теперь всё ясно и прекрасно. Вот поэтому, в том числе, я и не хотел сюда влезать. Возможно, я ещё немного побуду, да и пойду по другим темам. Вы, по крайней мере меня к этому подталкиваете (не со зла, конечно). Я только не понимаю зачем вы так усердно пытались меня сюда затащить, чтобы потом указывать, что вы так уже делаете? Так напишите тогда выжимку из этих 300 страниц, с чувством-толком-расстановкой. С теорией, результатами исследования, к чему пришлии и на чём сейчас затык. А затык, если я верно вижу, сейчас на том, что всё что можно уже нашли, и больше не найти потому, что не хватает гигагерцев в процессорах. Если это так - ну тему можно закрывать тогда, да?

[Yadryara]

wrest в сообщении #1722876 писал(а):

Я понимаю, что за 300 страниц этой темы вы, возможно, перепробовали все что можно и у вас теперь всё ясно и прекрасно.

Так я же только сегодня процитировал своё мнение:

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

И, чем чёрт не шутит, возможно придут какие-то идеи, которые не пришли в голову другим.

Ведь рекорды продолжают падать (в том числе и в этом году!) не потому, что компы стали сильно быстрее чем 3-4 года назад, а потому что понимание приёмов решения задач участниками весьма и весьма неидеально, даже если они не первый год ими занимаются.

Это моё мнение не изменилось. Но конечно мы многое попробовали.

wrest в сообщении #1722876 писал(а):

Я только не понимаю зачем вы так усердно пытались меня сюда затащить,
чтобы потом указывать, что вы так уже делаете?

Мне представляется что слово "затащить" не только грубоватое, но и неуместное.

wrest в сообщении #1722876 писал(а):

Так напишите тогда выжимку из этих 300 страниц, с чувством-толком-расстановкой. С теорией, результатами исследования, к чему пришлии и на чём сейчас затык.

Да, это можно и нужно написать. Отчасти это уже сделано.

[EUgeneUS]

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

А, ну понял вроде. Вы говорили не о топовых количествах делителей, а о 36, 72. Про 108 вряд ли..

нет

wrest в сообщении #1722874 писал(а):

Это до меня пока что ещё не дошло.

Сначала безотносительно реализации программы поиска цепочек.

1. Сначала безотносительно реализации программы поиска цепочек.
С ростом чисел ($N$) в цепочках-кандидатах вероятность найти цепочку падает (грубо) как $\frac{1}{(\ln N)^l}$, где $l$ - длина цепочки.
2. Как писал выше - для длинных цепочек работает грубое эмпирическое правило: "увеличиваем числа в цепочке на два порядка - снижаем вероятность нахождения цепочки в два раза".

Если ищем по 100 паттернам, а не по одному - увеличиваем вероятность в два раза, а значит снижаем необходимое количество проверок тоже в два раза. $10^4$ - 4 раза, $10^6$ - 8 раз и т.д.
Это всё грубые оценки, более точные можно получить через калькулятор шансов, но для понимания - достаточно.

2. При реализации расчета цепочек для каждого паттерна требуются подготовительные действия. Которые нужно "размазать" на большое количество цепочек. На сколько - вопрос?
При пробных запусках скрипта на PARI\GP для недавних рекордных цепочек выход на линейный рост (время от величины диапазона итератора) происходил где-то на 10000. Дмитрий при обсуждении ускорителей для $D(36,14)$ называл единицы миллионов, насколько помню.

3. Но количество проверок для нахождения длинных цепочек $10^{14}...10^{16}$, а значит даже при $10^6$ проверках на паттерн, хорошо бы иметь $10^8 ... 10^{10}$ паттернов.
Часто оптимальных паттернов столько нету, поэтому и написал выше - надо найти их все.