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

[vicvolf]

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

Паттерн "0-2-16-3(9)" ещё не считал, а для паттерна "0-4-14-3(8)":
Для $N = 1,0 \cdot 10^{50}$, вероятность найти цепочку за одну проверку $8,1 \cdot 10^{-13}$
На два порядка у Вас ошибка. Вы не учитываете, что ищем числа не в $x$, а в $x/v_i$, где $v_i$ - множитель, заданный паттерном. Но в целом мой "калькулятор шансов" так и работает: для каждой позиции цепочки вероятность считается как
$P_i = b_{n_i} P_{n_i}(N/v_i)$, где
$P_{n_i}(N)$ - асимптотики для того количества множителей ($n_i$), которое задано паттерном для i-го места.
(Которые взял из одного из первых Ваших сообщений в этой теме. За что Вам большое спасибо).
$b_{n_i}$ - множитель, указывающий во сколько раз вероятность больше асимптотики из-за "решета Эратосфена", которое опять же задаётся паттерном (набором простых, которые в нём используются).

Совершенно верно! Асимптотические оценки работают при $x \to \infty$, но для конкретного $x = 10^{50}$ существуют поправочные множители. Вероятность того, что случайное число имеет структуру "pqrs" (4 простых множителя) примерно пропорциональна:
$P_{\text{pqrs}} \sim \frac{(\log\log x)^3}{\log x}$
в то время как для "pqr":
$P_{\text{pqr}} \sim \frac{(\log\log x)^2}{\log x}$
Для $x = 10^{50}$, $\log\log x \approx 4.746$, разница составляет примерно $4.746$ раза, что может не компенсировать другие факторы.
Общее ожидаемое количество цепочек:
$N \sim \frac{x}{L} \times P_{\text{candidate}}$
Для паттерна "0-4-14-3(8)" с L в 129 раз меньше, количество кандидатов в 129 раз больше. Даже если $P_{\text{candidate}}$ у него немного хуже, он может оказаться эффективнее.

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

vicvolf в сообщении #1706371 писал(а):

Паттерн "0-2-16-3(9)" представляет собой оптимальный компромисс между вероятностью успеха и вычислительной сложностью, что делает поиск цепочек D(48,21) возможным .

Это опрометчивый вывод, и скорее всего неверный.
Во-1х. Асимптотика для $pqrs$ лучше, чем для $pqr$, однако, для интересующих порядков чисел, вероятность попасть в $pqr$ больше, чем в $pqrs$.
Во-2-х. Для поиска оптимального паттерна нужно их сравнивать друг с другом.
Вот, например, "0-2-16-3(9)" и "0-4-14-3(8)" у первого асимптотика немного получше, но у второго множитель при итераторе (lcm) в $59^2/3^3 \approx 129$ раз меньше. И какой будет лучше? Вопрос.
В-3-х. Количество цепочек, которые нужно проверить, не равно "вычислительная мощность".
Проверки на простоту выполняются во много-много раз быстрее, чем факторизация. И цепочки проверяются не путем проверки всех чисел, а только до первой неудачи в какой-нибудь позиции.
Пока всё указывает, что для реализации на PARI\GP более оптимальным будет паттерн с одним простым неизвестным.

Это критически важное уточнение! На практике:
- Проверка простоты (для позиций "p") — очень быстрая
- Факторизация (для "pq", "pqr", "pqrs") — значительно медленнее
- Ранний выход — при первой неудаче проверка цепочки прерывается
Поэтому паттерны с большим количеством позиций, требующих факторизации, могут быть менее эффективными, даже если их теоретическая вероятность выше.

[EUgeneUS]

vicvolf в сообщении #1706412 писал(а):

Для паттерна "0-4-14-3(8)" с L в 129 раз меньше, количество кандидатов в 129 раз больше. Даже если $P_{\text{candidate}}$ у него немного хуже, он может оказаться эффективнее.

Это так, и этот вопрос изучался (вот только что получены результы).

[Dmitriy40]

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

Результаты калькулятора шансов на "серебряном наборе паттернов"

Скажите, а почему pats везде одинаковое 9! ?

-- 19.10.2025, 17:10 --

EUgeneUS
Генератор закончил работу.
Улучшений от выложенных результатов нет.
Не были показаны:
v=[ 4, 23085, 182, 289, 24, 1, 110, 3, 4, 49, 18, 25, 32, 3, 2, 169, 420, 121, 2, 9, 49096];\\6-0-6-9(8)
v=[ 14440, 153, 2, 1, 12, 5, 154, 507, 32, 1, 2430, 1, 4, 147, 2, 25, 24, 121, 578, 171, 1820];\\5-0-10-6(8)
v=[ 14440, 153, 2, 11, 12, 245, 338, 3, 32, 1, 2430, 1, 28, 3, 242, 25, 24, 1, 578, 15561, 20];\\4-0-13-4(8)

[EUgeneUS]

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

Скажите, а почему pats везде одинаковое 9! ?

Я специально одинаковое брал, чтобы сравнивать паттерны на одинаковом количестве "размножения".
Для (8) потом дополнил 8!

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

Не были показаны:

Я их сохраню. Но, думаю, для программы на PARI/GP они точно не пригодятся.

-- 19.10.2025, 18:13 --

Вот "золотой паттерн" - 1-1-16-3(8)

результаты пробных запусков:

(Оффтоп)

"Pat";"pats";"i_m/pat";"i_m all";"n_all";"N";"P(1)";"P(win)";"Часов на 1е47";"Часов всего";"Лет"
"0-3-16-2(8)";40320;85830000;3460665600000;1411951564800;118138216085270000000000000000000000000000000000000;2,12210396061124E-012;0,9500287784;41,5;49027,3596753872;5,5967305566
"1-1-16-3(8)";40320;293200000;11821824000000;4823304192000;403566641411277000000000000000000000000000000000000;6,21156351546482E-013;0,9500146859;8,1;32688,8979543134;3,7316093555
"2-0-16-3(8)";40320;1068000000;43061760000000;17569198080000;1470017641761330000000000000000000000000000000000000;1,70594940386275E-013;0,9500741462;6,3;92611,1114309635;10,5720446839

3.73 года в один поток. 1.2 месяца в 40 потоков.
На данный момент, в паттерне с нулем простых нашлось уже 4 кандидата, а паттернах с 1 и 2 простыми - ниодного.
Может статистический выброс. А может накосячил, когда программы настраивал.
В любом случае, результаты пробных запусков нужно перепроверить.

Что интересно, вчерашние паттерны были хуже только на одну позицию в $pqr$, а показывали время в разы больше. Для одного простого в 1.5 - 2 раза.
Пробные запуски поводились для 8! паттернов. Путем "размножения паттернов" можно ещё выжать десятки процентов. До двух раз, при увеличении количества паттернов на 3 порядка, наверное.

[Dmitriy40]

Важно не только сколько кандидатов, но и насколько они хороши: 100500 valids=10 хуже 20 valids=20.

У меня по запускавшимся вариантам состояние такое (сколько простых, каких valids>16 сколько цепочек):
p0: 17х1шт, счёт 18ч
p0-8!: 18х1шт, счёт 45ч
p3: 18х2шт, 17х12шт, счёт 88ч
p5: 18х1шт, 17х2шт, счёт 67ч
Варианты p0 считались без ускорителей, на PARI. Варианты p3 и p5 - с 9 квадратами.
В общем, если не брать кучу 17-ек от p3, то все примерно одинаково (в пределах случайных выбросов).

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

Вот "золотой паттерн" - 1-1-16-3(8)

С ним (и вторым таким же) проблема: нет разрешённых остатков по модулю 7. И тупая замена $7^2 \to 7^5$ проблему не решает. Потому что проблема на месте 480p, p почему-то получается кратным 7.

[EUgeneUS]

Вот влияние количества паттернов для 1-1-16-3(8)

(Оффтоп)

"Pat","pats","i_m/pat","i_m all","n_all","N","P(1)","P(win)"
"1-1-16-3(8)",40320,293200000,11821824000000,4823304192000,403566641411277000000000000000000000000000000000000,"6,21156351546482E-013","0,9500146859"
"1-1-16-3(8)",100000,105750000,10575000000000,4314600000000,145556522650801000000000000000000000000000000000000,"6,94520294686685E-013","0,9500422316"
"1-1-16-3(8)",362880,24840000,9013939200000,3677687193600,34190298543518400000000000000000000000000000000000,"8,15105975022678E-013","0,9500985294"
"1-1-16-3(8)",1000000,7930000,7930000000000,3235440000000,10915019225088700000000000000000000000000000000000,"9,25912880038621E-013","0,9500001648"
"1-1-16-3(8)",4000000,1663000,6652000000000,2714016000000,2288988740842770000000000000000000000000000000000,"1,10435110693443E-012","0,9500746592"
"1-1-16-3(8)",10000000,591000,5910000000000,2411280000000,813465415629482000000000000000000000000000000000,"1,2425773603185E-012","0,9500234777"

Смотреть нужно на "i_m all" - это общее количество итераций. При увеличение паттернов с $8!$ до $10^7$ в два раза и падает. Плюс плюшки за счёт хорошего снижения $N$ - факторизация облегчается.

-- 19.10.2025, 18:44 --

По проверке времени расчета.
Расчет для оценки времени нужно запускать
а) на одинаковом количестве паттернов для каждого типа паттернов, так сравнивать удобно. Я проверял на $8!$.
б) на диапазоне $N$ - как посчитано для данного типа паттерна и для данного количества паттернов. Я прямо $N$ из калькулятора и подставлял, как начальное значение.

-- 19.10.2025, 18:46 --

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

С ним (и вторым таким же) проблема: нет разрешённых остатков по модулю 7. И тупая замена $7^2 \to 7^5$ проблему не решает.

Беда....
И двумя простыми 2-0-16-3(8), похоже, что-то подобное.

-- 19.10.2025, 18:48 --

Жаль, конечно, если с 16 $pqr$ не найдутся.
Вчерашние 2-1-14-4(8) и 1-2-15-3(8) заметно худшее время показывали, раза в 1.5-2.

-- 19.10.2025, 18:56 --

Если 1-x-16-y(8) не найдутся, то, вероятно, "золотым паттерном" будет 1-2-15-3(8). Но его нужно ещё с 1-1-16-3(9) сравнить, тот может и получше оказаться.

Если 2-x-16-y(8) не найдутся, то, хорошо бы для сравнения 2-х-15-y(8).

[vicvolf]

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

vicvolf в сообщении #1706412 писал(а):

Для паттерна "0-4-14-3(8)" с L в 129 раз меньше, количество кандидатов в 129 раз больше. Даже если $P_{\text{candidate}}$ у него немного хуже, он может оказаться эффективнее.

Это так, и этот вопрос изучался (вот только что получены результы).

Мой первоначальный вывод действительно был слишком упрощённым и оптимистичным.

Пересмотренный анализ оптимальности паттернов

Факторы, которые я недооценил:

1. Баланс между L и P_candidate
- Меньший L даёт больше кандидатов: $ N \sim x/L \times P_{\text{candidate}} $
- Для "0-4-14-3(8)" с L в 129 раз меньше, это компенсирует худшую асимптотику

2. Практическая скорость проверки
- Проверки на простоту (для "p") vs факторизация (для "pq", "pqr", "pqrs")
- Ранний выход при первой неудаче
- Для PARI/GP паттерны с одним "p" могут быть оптимальнее

3. Конечные значения x vs асимптотика
- Для $ x = 10^{50} $ асимптотические оценки могут не отражать реальное положение
- Вероятности для разных структур ("pqr" vs "pqrs") сравнимы по порядку величины

Новые данные и их значение

Эмпирическое сравнение паттернов — единственный способ определить действительно оптимальную стратегию.

Что показывают практические исследования:
- Сравнительный анализ паттернов необходим для определения лучшего
- Теоретическая асимптотика — лишь один из факторов
- Эмпирические замеры скорости проверки критически важны

Исправленный вывод
На основании ваших замечаний и новых данных:

1. Паттерн "0-2-16-3(9)" не является однозначно оптимальным — он представляет лишь один из возможных компромиссов

2. Для практической реализации в PARI/GP более перспективны:
- Паттерны с меньшим L (даже в ущерб асимптотике)
- Паттерны с минимальным количеством позиций, требующих факторизации
- Паттерны, позволяющие эффективный ранний выход

3. Окончательный выбор оптимального паттерна требует:
- Эмпирического сравнения нескольких кандидатов
- Учёта конкретных характеристик вычислительной системы
- Анализа реальной скорости проверки, а не только теоретической вероятности

[EUgeneUS]

Сейчас такие лидеры гонки (в порядке призовых мест):
0-3-16-2(8)
1-2-1-3(8)
1-1-16-3(9)

Оценка времени на пробных запусках:

(Оффтоп)

Pat   pats   i_m/pat   i_m all   n_all   N   P(1)   P(win)   Часов на 1е47   Часов всего   Лет
0-3-16-2(8)   40320   85830000   3460665600000   1411951564800   118138216085270000000000000000000000000000000000000   2,12210396061124E-012   0,9500287784   41,5   49027,3596753872   5,5967305566
1-2-15-3(8)   40320   419000000   16894080000000   6892784640000   576720404761865000000000000000000000000000000000000   4,34760768324158E-013   0,9500489796   11,5   66322,8465476145   7,5711012041
1-1-16-3(9)   362880   28140000   10211443200000   4166268825600   4993621928836050000000000000000000000000000000000000   7,19217581815023E-013   0,9500360628   1,5   74904,3289325407   8,5507224809

Если округлить $5,5967305566$ до 6 лет. То получается на 40 потоков 1.8 месяца.
В принципе подъёмно. И это оценка на моём медленном компе.