Маркдаун

[wrest]

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

| Параметр | Значение |
|----------|----------|
| **Версия** | 2.1 |
| **Дата** | 2026-04-19 |
| **Статус** | Утверждено к реализации |
| **Целевой компилятор** | `gp2c -g` (PARI/GP → C) |

---

## 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. Термины и обозначения

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

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

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

| $\tau_R$ | 4 | 8 | 12 | 2 | 6, 3 |
|----------|---|---|----|---|------|
| $w(\tau_R)$ | 1.00 | 0.55 | 0.05 | 0.15 | **0.0 (отсев)** |

### 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. Вспомогательные функции

| Функция | Вход | Выход | Назначение |
|---------|------|-------|------------|
| `analyze_chains(res, k_max, verbose)` | matrix, int, int | int(1/0) | Построчная статистика: плотности по позициям, распределение совпадений, оценка корреляции CRT |
| `generate_crt_pool(L, T, max_logLcm, max_mod, K, seed, verbose)` | int, int, real, int, int, int, int | matrix | Основной генератор с контролем `lcm` и динамическим подбором структур |
| `search_chains_fast(res, target, max_k, verbose)` | matrix, int, int, int | int | Оптимизированный поиск с прогресс-баром и ранним выходом |

## 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-условий.**