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

[Dmitriy40]

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

Можете скинуть готовый такой паттерн (с расставленными квадратами простых, и правильной степенью тройки)?

Использовался такой:
v=[243, 50, 49, 12, 289, 338, 1815, 2888, 529, 126, 841, 20, 2883, 2738, 1681, 96, 64715, 48598, 117, 4, 2809];
Используются только нечётные i, n=n0+i*lcm(v), n0=117063213130347184288773192252690001832049.

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

а с 1 и 2 простыми что-то интересное из паттернов не нашлось?

Такие не искались.
Генератор паттернов работал 8ч для списка всех 5-0 и 6-0. Всего нашлось 24316шт 5-0 и 368шт 6-0. При этом по 8 квадратов простых имеют 367 паттернов, все 5-0. 16002 паттерна требуют по 10 квадратов простых и 8315 паттернов с 9 квадратами простых.

-- 17.10.2025, 13:26 --

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

А куда бы они делись?

Вопрос не куда бы делись, а что находятся довольно длинные даже при столь медленной проверке. Т.е. не сказать бы что паттерн совсем никудышный.

-- 17.10.2025, 13:31 --

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

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

а с 1 и 2 простыми что-то интересное из паттернов не нашлось?

Такие не искались.

Запустил для поиска 0-0, 1-0, 2-0. Сразу нашлись варианты 2-0-14-5(8). Причём как с квадратом на месте с неизвестным простым (одним из двух), так и без оного, т.е. туда можно поставить 53^2 для уменьшения m в переборе простых.

[EUgeneUS]

Сделал грубую оценку - сколько простых выгодно.

Параметры модели:

Стоимость isprime   1
Стоимость factor   100
P(p)   0.06
P(not p)   0.3

Варьировал "Стоимость factor". получилось так:

1:100 - 2p
1:1000 - 2p
1:10000 - 3p
1:100000 - 4p
1:1000000 - 5p

Модель грубая: на каждом шаге считалось, что уровень фильтрации равен вероятности. Простые проверяются вначале, конечно.
Но показательно.
Не знаю, какое отношение стоимости проверки на простое к стоимости факторизации будет правильно выбрать...

-- 17.10.2025, 14:03 --

Или так, если P(not p) изменить на близкую к вероятности $pqrs$:

Стоимость isprime   1
Стоимость factor   1000000
P(p)   0.06
P(not p)   0.23

1:100 - 2p
1:1000 - 3p
1:10000 - 3p
1:100000 - 5p
1:1000000 - 6p

-- 17.10.2025, 14:53 --

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

Запустил для поиска 0-0, 1-0, 2-0. Сразу нашлись варианты 2-0-14-5(8).

Минимальное количество необязательных простых в квадрате - 8 штук.
И у всех таких паттернов будет одинаковый lcm.

(расчет)

Всего надо 21 квадрат.
Обязательные простые от 5 до 19 дают минус 6 квадратов (по одному на одно простое - не больше).
Расстановка двоек даёт минус 4 квадрата (обязательно должно быть $2^5$).
Расстановка троек даёт минус 3 квадрата (обязательно должно быть $3^5$).
$3^5$ вместо необязательного простого в квадрате выгодно, так как $3^4=81 \ll 59^2$

То есть условие "(8)" (расставляем восемь квадратов) можно "прибивать гвоздями" - искать только среди таких.
А вот условие "количество pq равно ноль" не нужно прибивать гвоздями. Нам нужно условие "количество pqr" - максимально. И только уже среди таких минимизируем количество $pq$ (в пользу $pqrs$).

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

Итого оптимальные паттерны (для дальнейшего исследования):

A-B-C-D(8), где
А - от 2 до 5, наверное. В зависимости скорости работы проверки на простые по сравнению с факторизацией. Можно и 6 - 7 посмотреть.
C - максимальное (для каждого фиксированного A).
B и D - в общем-то любые из оставшихся. Но если будет выбор, лучше чтобы B поменьше, D - побольше.

[Dmitriy40]

За 2ч (наверное 20%-25% общего) работы генератора паттернов вариантов 0-0 и 1-0 не нашлось.
Есть варианты 2-0-16-3(9) и 2-0-15-4(8 или 9).
Остановил.

Если убрать условие на второй 0, то паттернов миллионы, за пару минут насыпается сотня мегов текста. Надо как-то ужесточить условия отбора.

[EUgeneUS]

1. Ставим условие - расставлять ровно восемь простых в квадрате (условие по $LCM=2^5 \cdot 3^5 \cdot 5^2 \cdot 7^2 \cdot 11^2 \cdot 13^2 \cdot 17^2 \cdot 19^2$ будет более мягким).

2. Далее (в нотации A-B-C-D(8)) для каждого A
а) запоминаем какое C и собираем паттерны с таким C
б) с меньшим С - игнорируем.
в) если нашли ещё большее С - всё, что собрали со старым C забываем, собираем с новым C.

3. Если всё равно мегабайты текста, то для каждого A (и текущего C для для данного A)
а) запоминаем D.
б) с меньшим D - игнорируем.
в) если нашли ещё большее D - всё, что собрали со старым D забываем, собираем с новым D.

4. Если всё равно мегабайты текста, то выводим один пример для каждой смены C или D. Тогда точно на 10 страниц текста войдет, не больше.

5. "A" лучше не ограничивать (количество искомых простых), ни сверху, ни снизу.

[EUgeneUS]

Dmitriy40
План действий видится таким (для обсуждения):

1. Нужно найти набор "серебряных паттернов": для каждого "A", которое существует для 8 расставляемых квадратов простых, найти ровно один пример, удовлетворяющий условиям:
а) "C" максимально при заданном "A"
б) "D"максимально при заданных "A" и "C".
Их будет не более 21 (скорее, окажется меньше 10, но это не точно).

2. Для каждого из этих паттернов я соберу статистику и отдам в "калькулятор шансов". Будем знать:
а) до какого числа надо считать (в зависимости от числа паттернов, одинакового типа).
б) сколько итераций нужно (тоже в зависимости от числа паттернов, одинакового типа).
Данные предоставлю в том же виде, как тут публиковал для пары паттернов с (9) (csv).

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

4. По результатам находим "золотой паттерн" - прогнозируемое время на котором будет минимально.

5. Если на этом этапе решим, что 8! одинаковых паттернов мало, и нужно больше, то нужно будет поискать их снова, но уже с конкретными значениями A, B, C, D. (Если не сохраняли на первом шаге).

6. Дальше смотрим на прогнозное время и принимаем решение - считать, или что.

[Dmitriy40]

Запустил генератор паттернов с указанными условиями, что-то выдаёт. Коррекцию $3^2 \to 3^5$ не делал, добавим руками. Пока меньше мега текста. Но ему надо часов 8.
За 10 минут работы лучшие для каждого A:
0-3-15-3(8)
1-1-16-3(8)
2-0-15-4(8)
3-0-12-6(8)
4-0-10-7(8)
5-0-7-9(8)

[vicvolf]

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

Следующий шаг: цепочки ищутся не просто так, а заведомо неподходящие откидываются с помощью расстановок обязательных простых и применения китайской теоремы об остатках.

А можно пример?

[EUgeneUS]

Посчиталась статистика по паттерну

v=[ 4, 37791, 1058, 25, 20184, 961, 98, 363, 20, 1369, 18, 1681, 32, 194145, 338, 2209, 12, 2809, 31790, 243, 20216];\\ 5+0+8+8(8)

Результат:

(Оффтоп)

Тип паттерна;pat;i_m/pat;i_m all;n_all;N;P(1);P(win)
5-0-8-8(8);1;84700000000000000;84700000000000000;34557600000000000;116582859743997000000000000000000000000000000000000000000000;8,6714903164002E-017;0,9500463117
5-0-8-8(8);10;6565000000000000;65650000000000000;26785200000000000;9036203945919040000000000000000000000000000000000000000000;1,11848588737288E-016;0,9500077267
5-0-8-8(8);100;506500000000000;50650000000000000;20665200000000000;697157242743030000000000000000000000000000000000000000000;1,44986283366273E-016;0,9500219087
5-0-8-8(8);1000;38870000000000;38870000000000000;15858960000000000;53501484749105000000000000000000000000000000000000000000;1,8892894756656E-016;0,9500242116
5-0-8-8(8);10000;2967000000000;29670000000000000;12105360000000000;4083841143570890000000000000000000000000000000000000000;2,47536082197345E-016;0,9500390405
5-0-8-8(8);40320;623000000000;25119360000000000;10248698880000000;857510290679159000000000000000000000000000000000000000;2,92346671463327E-016;0,9500220317
5-0-8-8(8);100000;225200000000;22520000000000000;9188160000000000;309970011975946000000000000000000000000000000000000000;3,26179426898189E-016;0,950062785
5-0-8-8(8);362880;53050000000;19250784000000000;7854319872000000;73019134704055300000000000000000000000000000000000000;3,8163515812454E-016;0,9500875399
5-0-8-8(8);1000000;16990000000;16990000000000000;6931920000000000;23385392999586100000000000000000000000000000000000000;4,32389717924951E-016;0,9500778723
5-0-8-8(8);10000000;1273000000;12730000000000000;5193840000000000;1752183948861080000000000000000000000000000000000000;5,76829242396758E-016;0,9500113247
5-0-8-8(8);100000000;94800000;9480000000000000;3867840000000000;130484712138794000000000000000000000000000000000000;7,74560531733779E-016;0,9500071962

Как и ожидалось: уменьшение lcm весьма позитивно отразилось на $N$ (до куда считаем) (по сравнению с 4-0-12-5 (9) и даже с 3-0-13-5 (9)).
Но увеличение количества простых, и уменьшение количества $pqr$ весьма негативно отразилось на количестве итераций.

-- 17.10.2025, 19:57 --

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

А можно пример?

А вот он как раз выше.

(Оффтоп)

$v=$ - это так называемый "паттерн" (или "шаблон"). Там уже расставлены числа в 21 позиции таким образом, что неизвестные множители имеют такую структуру:

pqrs   p   pqr   pqrs   p   pqrs   pqr   pqr   pqr   pqrs   pqr   pqrs   pqr   p   pqr   pqrs   pqr   pqrs   p   pqrs   p

где $p,q,r,s$ - некие простые числа (тут - больше 53).
Далее кандидаты в цепочки перебираются так:

n_1 = 170305930721447823273922715124956629359572 + 1376421012325824450708631856367543401678400 * i

$n_1$ - начальное число в цепочке.

[Dmitriy40]

Я тут прикинул на глазок как сделать isprime (точнее Mod(a,p)^p) на асме под числа до 1e57, выходит примерно 150e3 проверок в секунду.
Ускоритель для 3 проверяемых мест из каждых 100млн i за 2с возвращает 435e3 кандидатов, чтобы их проверить по одному простому в каждом надо 3с. Предположим первая же проверка отфильтрует практически все кандидаты и скорость дальнейших проверок учитывать не будем. Тогда вместо текущих 10с на 100млн будет 5с. Всего вдвое быстрее. При том что PARI выполняет порядка 90e3 таких же проверок в секунду. Как-то маловат выигрыш от ассемблера.

А в 5-0-8-8(8) нашлась valids=18:
1460610853586595400072587815954120541072766095436080488850: 48, 48, 96, 48, 48, 48, 48, 12, 48, 96, 48, 48, 48, 48, 48, 48, 48, 48, 48, 48, 48, valids=18

[Yadryara]

Статистику я всё-таки собрал. Частично покажу.

Приближения         Средневзвешенный valids  Приближений
Только 52-значные                     11.87          251
Только 51-значные                     12.18         1115
Только 50-значные                     11.96         1017

1017 — это пока без учета зеркальных комплектов. Вот расклад:

Valids   5 6  7  8  9  10  11  12  13  14 15 16 17 18 19     Всего
Прибл.   1 2 11 37 58 139 164 190 189 127 57 31  9  1  1      1017

Кстати, в зеркальных комплектах нашлось немало дырявых 18-к — 5 штук. Здесь они хорошо видны, ибо только они заканчиваются на 34:

Start                                                      Location              Vlds
17668887847524548413038893976018715843277693308027547      11111111111111111111    20  Vl
26775093546337571754412744723988589091340703171346         1111111 1111111111 11   19  An
85214054718602387929373909199904790013177732572016804946   1111111 1111111111 11   19  Vl
120331053898175383312075133358643262841647885054683227346  111111111 1111111 111   19  Na
51684540038790306040313810619606026245800104809434         11 111111 1111111 111   18  An
58045879910726776483522940313416806455648990735834         1 11111 1111111111 11   18  An
72909466110460584674297272553362643585315288960146         1111111 1111 11 11111   18  An
82702393061651749407237510142718298553252873153434         1 11 11111111 1111111   18  An
92072158530190103532533856196718999336407704755034         1 11111 11111111 1111   18  An
94857011757111332377197688601839701940798725351834         1111111111111 11  111   18  An
154631495973083613535277148109710834053326309716946        111  11111111111111 1   18  An
585605360962144936768057576267008749038198122219346        1111111 111 1111111 1   18  An
606402818949710702556903161178143151197645296548946        11111 1 1111111111 11   18  An
628680904801738074581702744562430440461822260856146        11111 111111111 111 1   18  An
7463656036994854901626760003614676193212978675835346       111111111  1111 11111   18  An
16948256634087746076068267461645252005741587516704870546   1111111  11111111 111   18  Dm
29825395661688231658603848650736899419196053570174356946   111111111111111 11  1   18  Vl
90715763859608616730714175556209422588238079327693680146   1111111111111111 1  1   18  Vl
107379224505589048964595089898468182968439621246614942546  1 1111111111111  1111   18  Na
1460610853586595400072587815954120541072766095436080488850 11 1111 1 11111111111   18  Dm

Да, приходится ужимать текст из-за большущей длины чисел. Но двухбуквенные сокращения имён и раньше использовались, в том числе на 100-й странице и возражений не было.

Новое приближение с valids=19 взято отсюда