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

[Yadryara]

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

Это у вас 4-я. А у меня "сперва" (если отключить "терапевтику", в которой я всё ещё не уверен на 100%).

Я правильно понимаю, что вы решили всё-таки попробовать полностью самостоятельно находить цепочки?

Это очень здорово. Я так делал на первых страницах темы. И да, согласен с тем что при таком подходе нужно всё подвергать сомнению и на слово не верить.

Уточню тогда ещё больше, как у меня сейчас. Может быть у вас лучше получится.

Сначала с помощью отдельной программы — ГенПата, генерятся различные серии паттернов, идёт "полный" перебор. Ищется минимальный шаг для заявленной цели.

На выходе — болванка, то есть заготовка паттерна и список простых, которые затем будут добавляться в эту самую болванку уже в основной рабочей программе, тем самым формируя паттерн окончательно.

В случае с 24-я и 48-ю делителями это обычно только простые, которые будут возводиться в квадрат при такой расстановке. А для 96-и делителей ещё и простые, которые войдут в паттерн как есть, то есть в первой степени.

Дальше, уже в рабочей программе делаются такие фильтрации.

1-я фильтрация, по КТО.
2-я фильтрация, определение множителя при lcm паттерна по 2 и 3.
3-я фильтрация, стандартная терапевтика по простым, начиная с 5.
4-я фильтрация, проверка i по допам до 500 — 600.
5-я фильтрация, проверка псевдопростоты кандидата на перебираемом месте.
6-я фильтрация, проверка по предпростым до 2^16 — 2^19.
7-я фильтрация, проверка псевдопростоты по оставшимся после предыдущей проверки местам.
8-я фильтрация, проверка на перебор с использованием алгоритма Полларда.
9-я фильтрация, более сложная проверка и на недобор и на перебор с использованием алгоритма Полларда.
10-я фильтрация. Окончательная проверка. Это единственная проверка с факторизацией. Пока по numdiv. Остаются только непрерывные цепочки длиной не меньше искомой.

Если в паттерне не 1 простое, а 0, то 4-я и 5-я фильтрации не делаются.

[wrest]

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

2. Почему в некоторых случаях в паттерн выгодно добавлять $3^5$ или даже $3^8$, хотя это и необязательно? А вот $5^5$ и $5^8$ добавлять невыгодно (почему?).

Мне видится так, что добавление малых простых должно производиться из соображений
- их распределения по степеням. если у нас цепочка к примеру дляной 21, то в неё попадут 21/3=7 чисел которые делятся на 3, 21\9=2 числа которые делятся на 3^2. Причём, если число n делится на 3^5, то число n+3 делится только на 3^1
- бОльшие степени можно ставить (вернее одну - "по центру") если надо достичь нужного t_R на этом месте

Почему добавлять 5^5 или 5^8 в общем случае невыгодно - пока не понимаю.

Мы с Квеном пишем техническое задание на генератор паттернов
Пока достигли стабильного выхода годных порядка $2\cdot10^{-4}$ для D(24,6)
Но пока модули (расставляемые по местам в цепочке) немного великоваты, работаем над их уменьшением.
Как обкатается на D(24,6) думаю тем же алгоритмом попробовать D(96,6) а может кстати и D(72,6).

[EUgeneUS]

wrest

Обратите внимание на следующее, на всякий случай.

1.

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

2-я фильтрация, определение множителя при lcm паттерна по 2 и 3.
3-я фильтрация, стандартная терапевтика по простым, начиная с 5.

Если выбран шаг $2 \cdot lcm$, то проверка на недопустимые остатки должна делаться с 3, а не 5.

2. Тут написано что-то очень похожее на ерунду:

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

...
3-я фильтрация, стандартная терапевтика по простым, начиная с 5.
4-я фильтрация, проверка i по допам до 500 — 600.
...
Если в паттерне не 1 простое, а 0, то 3-я и 4-я фильтрации не делаются.

Проверка на недопустимые остатки никак не связана с наличием ожидаемых простых чисел в паттерне или отсутствием.
Недопустимые остатки возникают потому что КТО гарантирует, что число разделится на указанную степень простого с нужным остатком. Но не гарантирует, что число разделится ровно на такую степень, а не на бОльшую.

3. А вот выполнить проверку на isprime (а не только на ispseudoprime) при наличии ожидаемых простых нужно бы не забыть - вместо numdiv на этих местах.

[wrest]

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

3. А вот выполнить проверку на isprime (а не только на ispseudoprime) при наличии ожидаемых простых нужно бы не забыть - вместо numdiv на этих местах.

Принимаем как справедливую гипотезу, что ispseudoprime не ошибается

-- 20.04.2026, 14:27 --

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

Если выбран шаг $2 \cdot lcm$, то проверка на недопустимые остатки должна делаться с 3, а не 5.

До выбора шага отличного чeм НОК всех модулей, я пока не дошёл.

[Yadryara]

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

Тут написано что-то очень похожее на ерунду:

Опечатка. Уже сам заметил и поправил:

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

Если в паттерне не 1 простое, а 0, то 4-я и 5-я фильтрации не делаются.

Рад что вы внимательно читаете.

-- 20.04.2026, 14:36 --

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

Мы с Квеном пишем техническое задание на генератор паттернов
Пока достигли стабильного выхода годных порядка $2\cdot10^{-4}$ для D(24,6)

То есть на миллион i по одному паттерну у вас с Квеном находится 200 цепочек D(24,6)? Или это надо как-то по-другому понимать?

[wrest]

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

То есть на миллион i по одному паттерну у вас с Квеном находится 200 цепочек D(24,6)? Или это надо как-то по-другому понимать?

Да, ~20 на сто тысяч (я смотрю только первые сто тысяч).
Но есть и побольше например[242, 507, 32, 3125, 18, 49] это более 40 на сто тысяч.
Пока совершенствуемся, работаем в направлении увеличения выхода годных при уменьшении бюджета.

[EUgeneUS]

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

- бОльшие степени можно ставить (вернее одну - "по центру") если надо достичь нужного t_R на этом месте

В целом это верно, но слишком обще.

Пусть строим паттерн для $k=12 \cdot 2^n$
А тогда, кроме хороших $pqr$, будут не очень хорошие $pq, pqrs$ и совсем нехорошие $pqrst, pqrstu$ и так далее, в зависимости от $n$.
Тогда если место с $3^2$ попало на $pqrst$, то заменой на $3^5$ мы "сдвигаем" его в $pqrs$. Ценой увеличения $lcm$ в $3^3 = 27$ раз, что будет меньше, чем если бы туда подставлять минимальное свободное простое.

Пусть строим паттерн для $k = 12 \cdot 3 \cdot 2^n$, например, 72.
Теперь в каждом месте у нас должно быть два квадрата простых.
Но если одну $3^2$ заменить на $3^8$, то это сразу "закроет" оба квадрата в этом месте. Ценой увеличения $lcm$ в $3^6 = (3^3)^2 = 27^2$. Что будет сильно меньше, чем если бы туда подставлять квадрат минимального свободного простого.

-- 20.04.2026, 14:53 --

Если подобное делать с 5-кой, то цена постановки $5^8$ вместо $5^2$ - увеличение $lcm$ в $125^2$ раз. А тут лучше поставить квадрат минимального свободного простого. Обычно они существуют меньше $125$.

Yadryara

(Оффтоп)

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

Рад что вы внимательно читаете.

Мне на Вашу радость без разницы, в общем-то.
Вдруг Вы не знали, да забыли.

[Yadryara]

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

Как обкатается на D(24,6) думаю тем же алгоритмом попробовать D(96,6) а может кстати и D(72,6).

Так вы писали про цепочки длиной 20-30 (поищу цитату). А для 72 делителей разве ж реально такую найти?

Да и мне труднее будет с вами разговаривать, ибо я 72 делителя ни разу не смотрел. Если не хотите D(96,6), то уж лучше тогда D(48,6). Вот, нашёл свою большую просьбу:

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

wrest
Большая просьба. Именно просьба. Найдите самостоятельно какие-нибудь короткие цепочки. Скажем, длины 6. Очень желательно с числом делителей 24, 48 или 96.

[wrest]

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

А для 72 делителей разве ж реально такую найти?

Да и мне труднее будет с вами разговаривать, ибо я 72 делителя ни разу не смотрел.

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

-- 20.04.2026, 16:43 --

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

Если подобное делать с 5-кой, то цена постановки $5^8$ вместо $5^2$ - увеличение $lcm$ в $125^2$ раз.

В ТЗ есть требования соблюдать общий бюджет на lcm в каких-то рамках (задаваемых пользователем пока что). Соответственно, алгоритм должен отказаться от 5^8 если это выходит за общий бюджет. Но есть так же и ограничение на один модуль (тоже задаётся пользователем). То есть если 5^8 выводит конкретный модуль или общий бюджет за ограничения, он не должен появляться в паттерне.

-- 20.04.2026, 16:54 --

Текущая версия ТЗ (work in progess), в формате markdown.
Посмотреть в красивом виде можно попробовать тут https://www.innateblogger.com/p/markdown-to-pdf.html или тут https://markdownlivepreview.dev/tools/markdown-to-pdf или что есть у вас для рендеринга  markdown с [LaTeX] включениями.
Лучше пока не особо критиковать, т.к. это на этапе отработки D(24,6)
Но теоретическую часть покритиковать можно уже сейчас.

(Оффтоп)

Используется синтаксис Text

# Техническое задание: Адаптивный пуловый генератор 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&#40;pool_lcm[k]&#41; < max_logLcm`.
- На каждом шаге ищется позиция с максимальным $\tau_R > 8$.
- Подбирается наименьшее $p > L$, не использованное в текущей системе.
- Проверяется: `log&#40;lcm&#40;current_lcm, p^e&#41;&#41; <= max_logLcm` и допустимость нового $\tau_R$.
- При успехе обновляется `pool_conds[k]` и `pool_lcm[k]`.

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

**Этап 5: Сортировка и дедупликация**
- Пул сортируется по убыванию $S_k$.
- Удаляются дубликаты по паре $&#40;x_0, M&#41;$. Хвост матрицы обнуляется.

## 5. Требования к gp2c-совместимости &#40;Фактические&#41;

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

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

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

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

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

1. **gp2c:** `gp2c-run -g script.gp` выполняется без ошибок и предупреждений. Время компиляции < 2с.
2. **Математика:** Пул содержит только системы с $\tau_R \in \{2,4,8,12\}$. Бюджет `log&#40;lcm&#41;` не превышен. 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` выводит статистику **по каждой системе отдельно**, позволяя выявлять "узкие" позиции &#40;$\tau_R$ с низкой плотностью&#41;.

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

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

[Dmitriy40]

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

До выбора шага отличного чeм НОК всех модулей, я пока не дошёл.

Это как раз просто: смотрите, пусть нам надо найти p (или pq, pqr, pqrs, pqrst, без разницы), оно обязательно нечётное, но при переборе i мы будем получать то чётное p, то нечётное, ведь в m закодирован просто множитель при p, (не)чётность самого p при этом в lcm никак не учитывается. Потому раз нам нужны лишь нечётные p, то всегда можно идти с шагом 2m (и с правильного n0 в зависимости от коэффициента при p).
Аналогичные рассуждения можно провести и для 3 чтобы не получать p кратных 3. Для многих паттернов получится лишь один остаток по модулю 6 допустимым (иначе получаются или чётные p, или кратные 3, где-то на просторах паттерна, не обязательно всегда в одном месте) и тогда можно идти с шагом 6m.

Вот пример на паттерне-рекордсмене:

? v=[50,363,4,169,18,245];
? pp=chinese(vector(6,i,Mod(-i+1,v[i])))
%2 = Mod(267921950, 901800900)
? st=0*10^5; len=1e5; q=vector(6); s=vector(7); for(k=st,st+len-1, n=lift(pp)+pp.mod*k; q+=(w=[numdiv(n+t)==24|t<-[0..5]]); s[vecsum(w)+1]++); print(q); print(s); print(vecprod(q)/len^5*1.)
[32555, 37816, 17676, 26215, 26865, 35892]
[11944, 30862, 32714, 18106, 5516, 801, 57]
55.006200548910718245633600000000000000
? for(i=0,9, x=lift(pp)+pp.mod*i; print(i,": ",[(x+t-1)/v[t]|t<-[1..#v]]))
0: [5358439, 738077, 66980488, 1585337, 14884553, 1093559]
1: [23394457, 3222377, 292430713, 6921437, 64984603, 4774379]
2: [41430475, 5706677, 517880938, 12257537, 115084653, 8455199]
3: [59466493, 8190977, 743331163, 17593637, 165184703, 12136019]
4: [77502511, 10675277, 968781388, 22929737, 215284753, 15816839]
5: [95538529, 13159577, 1194231613, 28265837, 265384803, 19497659]
6: [113574547, 15643877, 1419681838, 33601937, 315484853, 23178479]
7: [131610565, 18128177, 1645132063, 38938037, 365584903, 26859299]
8: [149646583, 20612477, 1870582288, 44274137, 415684953, 30540119]
9: [167682601, 23096777, 2096032513, 49610237, 465785003, 34220939]

Это числа, остающиеся на местах после деления на числа из паттерна, их и надо факторизовать.
Видите что на месте +2 каждый второй раз возникают чётные числа? Они уж точно не простые и не являются произведением нечётных простых. Т.е. такие i нам не подходят гарантированно. Т.е. чётные i можно пропускать. Т.е. идти с шагом 2m.
И тогда для первых 10^5 разных i получим следующее:

? st=0*10^5; len=1e5; q=vector(6); s=vector(7); for(k=st,st+len-1, n=lift(pp)+pp.mod*(2*k+1); q+=(w=[numdiv(n+t)==24|t<-[0..5]]); s[vecsum(w)+1]++); print(q); print(s); print(vecprod(q)/len^5*1.)
[32144, 37273, 30172, 26585, 26363, 35128]
[10590, 28491, 32957, 19945, 6753, 1171, 93]
88.998622779746145730025216000000000000

Для любых 3 последовательных нечётных i не получается два варианта или чётных или кратных 3 чисел чтобы можно было проверять лишь один вариант из 6, значит с шагом 6m идти нежелательно (будем пропускать примерно половину цепочек).
Нежелательно, но вполне можно:

? st=0*10^5; len=1e5; q=vector(6); s=vector(7); for(k=st,st+len-1, n=lift(pp)+pp.mod*(6*k+1); q+=(w=[numdiv(n+t)==24|t<-[0..5]]); s[vecsum(w)+1]++); print(q); print(s); print(vecprod(q)/len^5*1.)
[31297, 36457, 30334, 27089, 38089, 34445]
[9097, 26739, 32973, 21547, 7953, 1573, 118]
123.00763072919106541707336700000000000
? st=0*10^5; len=1e5; q=vector(6); s=vector(7); for(k=st,st+len-1, n=lift(pp)+pp.mod*(6*k+3); q+=(w=[numdiv(n+t)==24|t<-[0..5]]); s[vecsum(w)+1]++); print(q); print(s); print(vecprod(q)/len^5*1.)
[31398, 36624, 30582, 26899, 38334, 34332]
[8830, 26769, 33051, 21877, 7835, 1501, 137]
124.49531881966446278017735680000000000
? st=0*10^5; len=1e5; q=vector(6); s=vector(7); for(k=st,st+len-1, n=lift(pp)+pp.mod*(6*k+5); q+=(w=[numdiv(n+t)==24|t<-[0..5]]); s[vecsum(w)+1]++); print(q); print(s); print(vecprod(q)/len^5*1.)
[31646, 36931, 30456, 26902, 1460, 34534]
[14134, 33992, 32230, 15500, 3746, 395, 3]
4.8279978029431989580711680000000000000

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

Аналогично можно проверить и шаг 30m (и вообще любой). Для него лучший результат даёт вариант 30m+13:

? st=0*10^5; len=1e5; q=vector(6); s=vector(7); for(k=st,st+len-1, n=lift(pp)+pp.mod*(30*k+13); q+=(w=[numdiv(n+t)==24|t<-[0..5]]); s[vecsum(w)+1]++); print(q); print(s); print(vecprod(q)/len^5*1.)
[38287, 35674, 30829, 27752, 37303, 33644]
[8274, 25646, 33011, 22541, 8596, 1778, 154]
146.65884330652005308725329280000000000

Разумеется чем больше шаг, тем фактически лучше применённая фильтрация и тем в общем больше цепочек можно получить за то же количество i.

Вот примерно поэтому и плохо сравнивать по количеству цепочек на выходе в зависимости от количества i, лучше сравнивать в зависимости от количества m, т.е. в конкретном диапазоне натуральных чисел, ведь в нём объективное количество цепочек вне зависимости от алгоритма их перебора/поиска. А при сравнении по количеству i мы будем сравнивать в разных диапазонах, а ведь там ещё и вероятности простоты чисел плывут (тем более при переборе с начала i).

[EUgeneUS]

wrest
По поводу ТЗ.
Ваш вариант не смотрел, но могу кое-чего сказать.

1. Как по заданному количеству делителей строить сразу хорошие паттерны я не знаю, и не думаю, что кто-то знает.
2. Поэтому вряд ли получится обойтись без полного перебора вариантов.
3. На этапе построения полного перебора вариантов, можно сразу выбрасывать паттерны, которые требуют нечётного количества делителей, хотя бы в одной позиции (после применения паттерна).
3b. Ещё удобно ограничивать максимальные степени простых чисел в паттерне.
например: 2 - не более чем в 8-й, 3-не более чем в 8-й, остальные - не более, чем в квадратах.
4. Далее в зависимости от длины цепочки и количества делителей может получиться или тысячи паттернов или сотни миллионов паттернов. Поэтому какая-то фильтрация должна быть. Но эта фильтрация
а) должна указываться "руками"
б) и будет сильно разной для разных цепочек. Даже для цепочек с одним количеством делителей, но разной длины.
5. А как сделать фильтрацию "руками", если (пока) неизвестно какие вообще паттерны бывают? Поэтому на первом проходе имеет смысл посчитать число паттернов по структурам.
6. Один из вариантов, удобный для реализации, но не очень удобный для дальнейшего использования:
а) завести вектор, у которого каждый элемент - количество чисел в цепочке с заданным количеством делителей после применения паттерна.
б) и считать количество паттернов с каждым вариантом такого вектора.
7. И уже глядя на то, какое будет распределение этих векторов ставить ограничения "руками" и вторым проходом собирать паттерны в файл, выводя вместе с паттернами их структуру.

[VAL]

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

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

Цитата:

3. А вот выполнить проверку на isprime (а не только на ispseudoprime) при наличии ожидаемых простых нужно бы не забыть - вместо numdiv на этих местах.

Принимаем как справедливую гипотезу, что ispseudoprime не ошибается

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

[wrest]

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

Это как раз просто: смотрите, пусть нам надо найти p

Я эту лексику немного не догоняю, мы же ищем цепочки, количество делителей в числах которых равно чему-то. Причем -- во всех числах цепочки, а не каком-то конкретном. Я понимаю, что это какое-то сокращение для чего-то очевидного...

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

Аналогичные рассуждения можно провести и для 3 чтобы не получать p кратных 3.

Если p простое, то оно же ничему не кратно, а не только 2 и/или 3. И мы для того и используем КТО, чтобы начать с правильной "базы" и НОК по модулям чтобы правильно шагать?

[EUgeneUS]

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

Я эту лексику немного не догоняю, мы же ищем цепочки, количество делителей в числах которых равно чему-то. Причем -- во всех числах цепочки, а не каком-то конкретном. Я понимаю, что это какое-то сокращение для чего-то очевидного...

У нас есть паттерн.
Причем слово паттерн - обозначает две разные штуки.
(Предпринимались попытки обозначать их разными терминами, на успеха не имели)
1. Расставленные обязательные простые.
2. Расставленные обязательные простые плюс расставлены необязательные простые в степенях больше 1.

Когда мы применим паттерн в смысле пункта 2, то остатки отделения чисел в паттерне, будут иметь вид произведения какого-то количества простых чисел в первой степени, которые принято обозначать как $p, pq, pqr, pqrs, pqrst ...$.

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

Если p простое, то оно же ничему не кратно, а не только 2 и/или 3. И мы для того и используем КТО, чтобы начать с правильной "базы" и НОК по модулям чтобы правильно шагать?

КТО даёт гарантию, что число в цепочке кандидате разделится на число в паттерне. В том числе на максимальную степень простого числа, которая используется в паттерне. Но не даёт гарантии, что число в цепочке не разделится на бОльшую степень простого, чем нужно.

На примере из поста Дмитрия.
В позиции $+2$ в паттерне стоит $4 = 2^2$. И квадрат двойки - максимальная степень двойки в паттерне.
КТО гарантирует, что число в этой позиции разделится на $4$. Но оно может разделиться и на $8, 16, 32 ...$
А нам в этой позиции нужно число которое разделится на $4$ и даст нечетное число.
Поэтому один из остатков по модулю $2$ - запрещен.

Аналогично с другими простыми числами - каждое простое число, использованное в паттерне, даёт один запрещенный остаток по модулю этого простого числа.
Для тройки бывает 2 или 1 запрещенных остатков. Это как-то связано со степенью 3-ки, которая используется в паттерне.

[wrest]

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

И тогда для первых 10^5 разных i получим следующее:

Ага, то есть мы выбором шага можем повысить частоту (вероятность успеха) конкретных мест в цепочке.
Это интересно.