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

[Yadryara]

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

Восемь правильных остатков по модулю 125.

А какие 8, если не секрет?

Я вот вижу 4: 25, 50, 75 и 100.

[EUgeneUS]

Dmitriy40
Тут одна мысль посетила. Возможно, поможете подтвердить или опровергнуть.

Оцениваем перспективность паттернов:

1-2-18-3-(10)
1-3-18-2-(10)

Исходя из вероятности, первый - лучше. Так как вероятность попасть в $pqrs$ выше, чем вероятность попасть в $pq$.
Однако, разница между $P(pq)$ и $P(pqrs)$ небольшая. Путь будут такие типовые вероятности:
$P(pq) = 0.19$
$P(pqr) = 0.25$
$P(pqrs) = 0.21$

А теперь посмотрим с точки зрения скорости фильтрации.
1. Если на место с ожидаемым pqrs попадает
а) pq. То долго раскладываем на два множителя, потом быстро проверяем их на простоту, и бракуем.
б) pqr. То менее долго раскладываем на два множителя, потом быстро проверяем их на простоту, и опять раскладываем непростой множитель на два. Быстро проверяем их на простоту и бракуем.

2 С другой стороны, если на место с ожидаемым pq попадает
а) pqr. Раскладываем на два множителя. Проверяем на простоту. Бракуем, как не простые.
б) pqrs Раскладываем на два множителя. Проверяем на простоту. Бракуем, как не простые.

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

-- добавлено через 3 минуты --

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

А какие 8, если не секрет?

Я вот вижу 4: 25, 50, 75 и 100.

А Вы, опять проверяете по модулю число, а не итератор.
Да, по модулю пять - если проверять итератор, или по модулю 125 - если проверять числа. Будет $n-1=4$ хороших остатка.

Я про другое
Если
а) проверяем итератор, а не числа
б) проверяем по модулям до 5 включительно.
в) по модулю 3 есть два хороших остатка

Тогда по модулю $2 \cdot 3 \cdot 5 = 30$ будет $(2-1) \cdot (3-1) \cdot (5-1) = 8$ хороших остатков.

[Yadryara]

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

А Вы, опять проверяете по модулю число, а не итератор.

Мне пока лень вникать что такое итератор.

8 разрешённых остатков не по модулю 125, а по модулю $64\cdot729\cdot125$

[Dmitriy40]

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

Путь будут такие типовые вероятности:
$P(pq) = 0.19$
$P(pqr) = 0.25$
$P(pqrs) = 0.21$

[...]

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

Да, при столь близких вероятностях может быть pq выгоднее - позволяют быстрее отбросить кандидата если хоть один делитель найден.
Только Ваши рассуждения не совсем точны: случай 1а идентичен обоим случаям 2а и 2б - так и так надо найти первый делитель и по остатку бракуем. А величина этого вот делителя не зависит от формата ожидания, только от самого числа, которое одинаково для любых форматов мест. Так что слово "долго" в 1а и 1б излишне, долго будет лишь если оба делителя велики, но тогда столь же долгими будут и 2а,2б.
Остаётся лишь случай 1б. Там да, если делитель найден небольшой, то второе разложение не сильно быстрее первого.
Но тут вмешивается другой момент: достаточно много делителей не слишком большие и обнаруживаются относительно быстро. Вероятность числу не иметь делителя меньше $2^{20}$ (и больше $100$) всего
$\prod\limits_{p=101}^{2^{20}}(1-\dfrac{1}{p})\approx0.3366$
(а до 1е9 вероятность 0.22). Т.е. значительная часть разложений, особенно при задействовании ECM, относительно быстро находит небольшие делители. И в таких случаях второе разложение не должно сильно ухудшать картину, оно ведь тоже с той же вероятностью найдёт ещё один небольшой делитель ... Да и вообще случай pqr при ожидаемых pqrs не 100% вероятен, так что влияние случая 1б на общее время ещё ослаблено.
Плюс не забывайте что в пункте 1а частное надо проверять на простоту, а в пунктах 2а и 2б лишь на составное, что несколько быстрее (помнится давало 10%-15% общей скорости, но уже не помню в каком варианте проверок).
С другой стороны, замена pqrs на pq требует размещения двух простых (или куба одного), что увеличивает LCM, что замедляет все операции (особенно разложение).
Но навскидку не готов сказать какой вариант стабильно быстрее, зависит от вероятностей и реализации проверок.

(Дальше только если LCM меняется при переходе от pqrs к pq)

Но это всё про проверку одного кандидата.
А от замены pqrs на pq проверять придётся непрогнозируемо больше кандидатов. Да, Вы занимались этим расчётом, но на мой взгляд там сильны стат.флуктуации и для задачи поиска любого решения они сильнее влияют чем незначительные изменения мат.ожидания.
Вот пример для простейшего паттерна D12-3 список решений до 1е5:

? forstep(x=3,1e5,3, if(numdiv(x)<>12, next); if(numdiv(x-1)==12 && (numdiv(x+1)==12 || numdiv(x-2)==12) || numdiv(x+1)==12 && (numdiv(x+2)==12 || numdiv(x-1)==12), print1(x,", ")););
1275, 1926, 8226, 9162, 10323, 10674, 12051, 14049, 16677, 17181, 17667, 17739, 19941, 20619, 22476, 24723, 25773, 28677, 28926, 30474, 31338, 40077, 40914, 41274, 41517, 43803, 44052, 44163, 45123, 49149, 54585, 54588, 56547, 60651, 60741, 62451, 64323, 64494, 66789, 67509, 68454, 71649, 73674, 73998, 75105, 75717, 77325, 81963, 87813, 87957, 88542, 93627, 95049, 97074, 97326, 98925, 99477,

А вот список первых/минимальных решений при поиске с размещённым 29 или 31 или 37 или 41:

? forstep(x=29,1e5,29, if(numdiv(x)<>12, next); if(numdiv(x-1)==12 && (numdiv(x+1)==12 || numdiv(x-2)==12) || numdiv(x+1)==12 && (numdiv(x+2)==12 || numdiv(x-1)==12), print1(x,", ")););
1276, 9164, 10324, 16675, 20619, 22475, 44051, 45124, 66787, 87812, 87957, 97324,
? forstep(x=31,1e5,31, if(numdiv(x)<>12, next); if(numdiv(x-1)==12 && (numdiv(x+1)==12 || numdiv(x-2)==12) || numdiv(x+1)==12 && (numdiv(x+2)==12 || numdiv(x-1)==12), print1(x,", ")););
10323, 22475, 28675, 43803, 44051, 64325, 73997, 81964,
? forstep(x=37,1e5,37, if(numdiv(x)<>12, next); if(numdiv(x-1)==12 && (numdiv(x+1)==12 || numdiv(x-2)==12) || numdiv(x+1)==12 && (numdiv(x+2)==12 || numdiv(x-1)==12), print1(x,", ")););
1924, 10323, 19943, 28675, 31339,
? forstep(x=41,1e5,41, if(numdiv(x)<>12, next); if(numdiv(x-1)==12 && (numdiv(x+1)==12 || numdiv(x-2)==12) || numdiv(x+1)==12 && (numdiv(x+2)==12 || numdiv(x-1)==12), print1(x,", ")););
24723, 64493, 66789, 77326,

Видите, с 29 и 37 повезло, подошли первые же решения, а с 31 и тем более с 41 не повезло, пришлось проверять в 8 и 19 раз дальше. И если 31 ещё выгодно (проверяем с х10 шагом и хватило х8 интервала), то с 41 уже невыгодно (проверяем с х14 шагом, а проверить пришлось х19 интервала).
Для более сложных паттернов или размещением нескольких простых в несколько мест зависимость думаю будет ухудшаться.
Так что нет, поиск в высоту, как с необходимостью получается при замене pqrs на pq, менее выгоден поиска в ширину. Даже если сами паттерны будут проверяться чуть быстрее.

[EUgeneUS]

Dmitriy40
Спасибо за развернутый ответ.

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

С другой стороны, замена pqrs на pq требует размещения двух простых (или куба одного), что увеличивает LCM, что замедляет все операции (особенно разложение).

Нет, нет. LCM не увеличивается. Там разница вида "подставить только $17^2$ близко к центру" или "подставить $17^2$ и $17$ ближе к краям".
А "форсированное" изменение позиции на хорошую, с добавлением нового простого и ростом LCM не окупается, да.

-- добавлено через 5 минут --

Huz
The hypothetical issue with possible skipped batches I mentioned in this message is now resolved.
After a few hours, I checked again and found "missing" batches in the output file.
The output delay ranged from 30 minutes to several hours. In any case, this isn't a pcoul issue, but rather a pipeline or output file lock issue.

But another small bug was discovered. With the -a2 -fr switches, the batch numbering in stdout overflows.
Here is an example, after filtering with a Python script:

...
4214906383,2^2.17,3,2.19^2,5^2.7,2^3.3^5,13,2,3,2^2.5,11,2.3.7^2,1,2^5,3^2.5,2,1,2^2.3,7.17^2,2.5.13^2,3,2^3.11^2,19.23^2,2.3^2,5,10750412587284770400,2,0,0,8,0,10,1,3,0,0
282352016,2^2.7,17.23^2,2.3^2,13^2.19,2^3.5^2,3.11^2,2,7,2^2.3,5,2,3^5,2^5,1,2.3.5.7^2,1,2^2.11.13,3,2.17^2,5,2^3.3^2,7,2.19^2,3,10750412587284770400,2,0,0,8,0,10,1,3,0,0
...

The overflow is also observed in the regular log file.

305 b4284972891: 2^2.7 19 2.3 5.11^2 2^3 3^5.17 2.13^2 7^2 2^2.3.5 . 2 3 2^5 5 2.3^2.7.11 . 2^2 3 2.5^2 13 2^3.3.19^2 7 2.17^2 3^2.5 (85336.95s) [0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0]
305 b16473739: 2^2.3 . 2.5^2 3.19 2^3 . 2.3^2.7 5 2^2 3.11^2 2.13^2 . 2^5.3.5 7.17^2 2 3^2 2^2 5 2.3 . 2^3.7^2.11 3 2.5.19^2 13 (85869.14s) [0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0]

-- добавлено через 16 минут --

2 All

Генерация паттернов с помощью pcoul перевалила экватор, и можно подвести итоги.
Найдено (без учёта зеркальных):

1. 1-2-19-2(10) - 10 шт.
2. 1-2-18-3(10) - 210 шт.
3. 1-3-18-2(10) - 718 шт.

Для приведения к "комплектам" Yadryara нужно умножить на 4. Всё совпало.

Ещё нашлись такие забавные батчи:
4. 0-4-18-2(10) - 158 шт.
5. 1-3-18-2(11), нет $3^5$ - 83 шт.
6. 1-3-18-2(11), есть $3^5$ - 631 шт.
7. 1-4-18-1(11), есть $3^5$ - 107 шт.
8. 1-3-19-1(11), есть $3^5$ - 55 шт.

[Dmitriy40]

Более 4млрд паттернов это конечно сильно!
Хорошо что не придётся столько ускорителей делать.

[EUgeneUS]

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

Более 4млрд паттернов это конечно сильно!

Это ещё сильно уменьшено, на несколько порядков, путем ограничения степеней ключом

"-px3^5,1^11,1^23,1^47"

А размер выходного файла управляется фильтром на Питоне.