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

[Yadryara]

VAL в сообщении #1560066 писал(а):

Вроде, мы все это уже обсуждали.

Обсуждали, но конечно не всё.

Выделил болдом и шрифтом важное:

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

Правильно ли я понимаю, что самый колоссальный эффект как раз для 12-15? Ибо имеется не менее 11 одиночных искомых простых в паттернах.

А возможны ли паттерны для 12-15 где меньше 11-ти одиночных искомых простых ?

А возможны ли паттерны для 48-20 где меньше 3-х одиночных искомых простых ?

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

-- 13.07.2022, 13:10 --

VAL в сообщении #1560066 писал(а):

Пятнашку по 96 делителей кто-нибудь ищет?

Я другую 15-ку ищу.

[VAL]

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

Денис сделал выше дополнение по $k=108$. То есть тоже можно считать доказаным $M(108) \le 15$.

Я это и имел в виду.
Спасибо!

-- 13 июл 2022, 13:16 --

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

А возможны ли паттерны для 12-15 где меньше 11-ти одиночных искомых простых ?

По-видимому, нет.
Мы, вроде бы, это доказали.
"Вроде бы" - поскольку за давностью точно не помню.

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

А возможны ли паттерны для 48-20 где меньше 3-х одиночных искомых простых ?

Не знаю.
Дело в том что для цепочек, где две проверки на простоту точно проходят, они настолько проигрывают по скорости алгоритмам с тремя проверками, я для 28-20 я их, возможно, и не искал.
Сейчас гляну.

-- 13 июл 2022, 13:38 --

VAL в сообщении #1560075 писал(а):

Сейчас гляну.

Глянул.
И на 48-20, и на 48-21 легко делаются паттерны и на 2 проверки на простоту, и на 1, и на 0.

[Huz]

VAL в сообщении #1560058 писал(а):

$T(48,14)\le 312318006809070608880247466427347491827017724$.

Congrats. :)

-- 13.07.2022, 11:25 --

VAL в сообщении #1560066 писал(а):

Какова текущая оценка для 252? Полагаю, 23 явно завышена. 21?

My bisect program gives 21, checking 3-smooth moduli up to 72: disallow 16, 24 mod 32; 30 mod 36; 40 mod 48; 42 mod 72.

[Dmitriy40]

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

А в (3.2) есть три совпадения:
1. $t=7$, $w=q=17$, $p = 307$. Кстати, этот случай нашел уважаемый Dmitriy40 выше. Но там потребовалось 576 проверок, а сейчас всего две.
2. $t=9$, $w=q=71$, $p=5113$
3. $t=27$, $w=q=18874367$, $p=356241748525057$
Похоже одно (редко - два) решения могут находиться и для каких-то простых $t$. Хорошо бы проверить на системамх с длинной арифметикой...

Других решений нет вплоть до $t<10^4$:

{for(t=0,10^4,
   w=9*2^t+1; if(ispseudoprime(w) && ispseudoprime(w^2+w+1), print("t=",t+6,", w=",w,", p=",w^2+w+1));
   w=9*2^t-1; if(ispseudoprime(w) && ispseudoprime(w^2+w+1), print("t=",t+6,", w=",w,", p=",w^2+w+1));
)}

-- 13.07.2022, 14:59 --

VAL в сообщении #1560075 писал(а):

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

А возможны ли паттерны для 12-15 где меньше 11-ти одиночных искомых простых ?

По-видимому, нет.
Мы, вроде бы, это доказали.
"Вроде бы" - поскольку за давностью точно не помню.

Это доказывается легко: расположение двойки фиксировано и она сразу даёт 5 проверяемых мест, тройку как ни располагай всё равно даст 3 проверяемых места, пятёрка минимум два места, семёрка минимум одно, остальные можно расположить без увеличения проверяемых мест, итого минимум 11. Это если все большие искомые простые в первой степени.

[VAL]

Huz в сообщении #1560077 писал(а):

My bisect program gives 21, checking 3-smooth moduli up to 72: disallow 16, 24 mod 32; 30 mod 36; 40 mod 48; 42 mod 72.

Thanks!

[EUgeneUS]

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

Других решений нет вплоть до $t<10^4$:

Спасибо!
Но у Вас случай с плюсом не совсем верно задан. Должно быть так:

{for(t=0,10^4,
   w=9*2^t; if(ispseudoprime(w+1) && ispseudoprime(w^2+w+1), print("t=",t+6,", w=",w,", p=",w^2+w+1));
   w=9*2^t-1; if(ispseudoprime(w) && ispseudoprime(w^2+w+1), print("t=",t+6,", w=",w,", p=",w^2+w+1));
)}

Впрочем, уже после моего вопроса Денис предложил "обходной путь": даже если и найдутся решения для $n_0$, $n_8$ (что тут и проверяется), то 16-ку на них не составить - при достаточно больших $t$ величины чисел в предполагаемой цепочке разойдйтся так, что они не могут иметь разность меньше 16.

[Dmitriy40]

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

Но у Вас случай с плюсом не совсем верно задан. Должно быть так:

Это решений не добавило.

[Yadryara]

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

Это доказывается легко: расположение двойки фиксировано и она сразу даёт 5 проверяемых мест,

Нет, не так просто. Большинство паттернов(28800 из 46080), а именно N9 и S9 как раз содержат числа вида 4qr, а это именно одно из тех чисел, которые Вы называете непроверямыми. Потому что здесь надо найти не одиночное простое в первой степени, а именно пару простых q и r в первой степени.

Напомню свой вопрос:

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

Правильно ли я понимаю, что самый колоссальный эффект как раз для 12-15? Ибо имеется не менее 11 одиночных искомых простых в паттернах.

Так в каком случае асмовская фильтрация даёт самый колоссальный эффект? В случае 12-15 или в каком-то ещё? А кто на 2-м месте по колоссальности? На 3-м?

[VAL]

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

Нет, не так просто. Большинство паттернов(28800 из 46080), а именно N9 и S9 как раз содержат числа вида 4qr, а это именно одно из тех чисел, которые Вы называете непроверямыми.

Нет.
Речь идет об одной позиции, где двойка имеет 5-ю степень и четырех позициях с двойкой в 1-й степени.

[EUgeneUS]

Yadryara
Пусть мы строим паттерн для цепочки длиной $N$, на количество делителей $k$.
В какой степени $\alpha$ двойка входит в факторизацию $k$ - столько может быть простых чисел в первой степени в факторизации числа $n$, входящего в цепочку. Итого суммарно располагаем $\alpha N$ простыми числами.

Далее, у нас обязательно будет какое-то количество двоек в первой степени, троек, пятерок и семерок и т.д. Например, для цепочек длиной 15, двоек будет не менее 4-х, троек не менее 3, 5 - не менее двух и одна семерка. Итого 10 сразу отнимается от $\alpha N$ (для более длинных цепочек отнимать придется бОльшее число).
Далее, у нас есть двойка в большой степени. Для 12 делителей она обязана быть в 5-й степени, а это отнимает ещё одно простое число. Для 36 делителей двойка может быть в 8-й степени, это не отнимает простое число.
Обозначим $a$ - число малых простых в первой или нечетной степени, которые обязательно должны быть в факторизациях всех чисел в цепочке.
Тогда мы располагаем $N_p = \alpha N - b$ простыми числами. В каждой позиции нужно как минимум одно простое, тогда:
$N_{pq} = (\alpha- 1)N - b$ - количество позиций, где могут располагаться искомые $pq$.

Если $N_{pq} \ge N$, то у нас "избыток" простых и можно построить паттерн, где все искамые числа будут иметь вид $pq$, тогда ускорители совершенно не эффективны, ибо ускорять нЕчего.
Если $N_{pq}$ небольшое по сравнению с $N$, то нам надо искать много простых чисел. Тогда ускорители эффективны. И они тем более эффективны, чем больше $N - N_{pq} = N(2 - \alpha) + b$.
При $\alpha=2$ (то есть $k=12(2m+1)$) количество искомых простых равно в точности $b$ - количеству простых, "израсходованных" на обязательные малые простые.

-- 14.07.2022, 10:34 --

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

При $\alpha=2$ (то есть $k=12(2m+1)$) количество искомых простых равно в точнеости $b$ - количеству простых, "израсходованных" на обязательные малые простые.

Это с некоторыми оговорками, конечно.

-- 14.07.2022, 10:38 --

VAL
Скажите, пожалуйста, как по Вашему мнение, на тех числах, в которых будут искаться следующие цепочки на 24, 48, 72 и 96 делителей - нахождение чего более вероятно: $pq$ или $pqr$?
(Вы сообщали подобную информацию, но не нашел в недрах топика )

И второй вопрос: если более вероятно нахождение $pqr$, то можно ли для этих $k$ составить паттерны, в которых
а) минимизируетася количество $pq$ (в идеале до нуля)
б) максимизируется количество $pqr$
в) а количество $p$ - уже сколько получится.
?

[Yadryara]

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

Это доказывается легко: расположение двойки фиксировано и она сразу даёт 5 проверяемых мест, тройку как ни располагай всё равно даст 3 проверяемых места, пятёрка минимум два места, семёрка минимум одно, остальные можно расположить без увеличения проверяемых мест, итого минимум 11.

Нет это не так легко. Ибо 2, 3, 5 и 7 порой попадают на уже занятые такими числами места. Надо расписывать более аккуратно.

EUgeneUS, так какова тройка призёров?

[VAL]

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

Скажите, пожалуйста, как по Вашему мнение, на тех числах, в которых будут искаться следующие цепочки на 24, 48, 72 и 96 делителей - нахождение чего более вероятно: $pq$ или $pqr$?
(Вы сообщали подобную информацию, но не нашел в недрах топика )

И второй вопрос: если более вероятно нахождение $pqr$, то можно ли для этих $k$ составить паттерны, в которых
а) минимизируется количество $pq$ (в идеале до нуля)
б) максимизируется количество $pqr$
в) а количество $p$ - уже сколько получится.
?

Как я уже неоднократно писал, $pq$ существенно хуже $pqr$, а также хуже $pqrs$.
Это касается диапазона чисел, в котором идет поиск цепочек примерно из 20 чисел.
Для более коротких $pq$ конкурентноспособно $pqrs$, но, все равно, хуже $pqr$.

По Вашему второму вопросу приоритеты такие:

Ключевую роль играет именно количество $p$ (так что распределять его по остаточному принципу неверно).
Эмпирические исследования показывают, что для длинных цепочек оптимальны 3 позиции с проверкой на простоту. Если меньше, программа будет сильно тормозить, если больше - сильно уменьшится вероятность успеха. Впрочем, я не исключаю, что паттерны с 4-я проверками на простоту для некоторых цепочек могут оказаться не хуже.

Насчет минимизации $pq$ и максимизации $pqr$ все верно.
AFAIR, во всех рекордных длинных цепочках нет ни одной позиции с $pq$.

[Dmitriy40]

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

Нет это не так легко. Ибо 2, 3, 5 и 7 порой попадают на уже занятые такими числами места. Надо расписывать более аккуратно.

Если два числа попадут на одну позицию в первой степени, то искомое большое простое окажется в квадрате, а такие случаи исключаем.
Подсчитываются именно позиции в которых ровно по одному малому простому в первой степени (или в пятой), именно в них нужно найти большое простое в первой степени.

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

Так в каком случае асмовская фильтрация даёт самый колоссальный эффект? В случае 12-15 или в каком-то ещё? А кто на 2-м месте по колоссальности? На 3-м?

А что Вы собственно понимаете под эффектом фильтрации? Во сколько раз уменьшается количество проверок (что самое объективное в смысле зависимости только от самих ускорителей)? Или скорость нахождения цепочек ALL? Или скорость нахождения полных решений?
Поясню, на первый вопрос можно ответить даже не привлекая сами ускорители, полностью симулировав их эффект прямо на PARI, для любых паттернов.
Ответы на второй и третий вопросы зависят от алгоритма допроверки в PARI и к самим ускорителям отношения имеют косвенное. И основные тормоза счёта именно тут, не в ускорителях. Во всяком случае для длинных цепочек или для большого количества делителей, для $M(12)$ эффект ещё не столь сильно выражен (всего в несколько раз).
Плюс плохо изучен вопрос что лучше, много паттернов или глубже их проверять, похоже тут тоже всё зависит от величины чисел и количества делителей.

В принципе, если брать только коэффициент фильтрации ускорителей, т.е. во сколько раз меньше стало кандидатов после ускорителей относительно количества шагов, то очевидно чем больше проверяемых чисел используется, тем больше этот коэффициент. А так как скорость работы ускорителей не зависит от величины чисел, но зависит от количества проверяемых мест (скорость несколько растёт с их увеличением, так как реже приходится делать длительную проверку на делимость на всё большие простые), то при прочих равных количество проверяемых мест лучше увеличивать. Вот только увеличение проверяемых мест обычно приводит к увеличению величины проверяемых чисел (и количества возможных паттернов), что тормозит допроверку в PARI и с какого-то момента пересиливает повышение эффективности ускорителей. И этот момент кардинально зависит от алгоритмов долпроверки в PARI и даже от конкретной реализации алгоритма (я выше где-то говорил как замена цикла foreach на длинный if ускорила счёт аж втрое, хотя алгоритм совершенно не поменялся). Потому и непонятно о какой эффективности Вы спрашиваете, ведь даже с одними и теми же ускорителями и одними и теми же паттернами она (скорость нахождения цепочек) может отличаться в разы и на порядки (например при поиске $M(296)$ я в PARI проверял лишь легко разложимые числа, которым хватало 7с разложиться если и не полностью, то до получения факта возможности 296 делителей, при этом кандидаты руками допроверялись по 10-15 минут на разложимость оставшихся мест и лишь примерно после полутора сотен кандидатов было обнаружено решение, если же разложимость проверялась бы в PARI, то время нахождения увеличилось бы с 4.5 суток до порядка месяца, а полного разложения даже первых кандидатов не дождались бы и за годы).

[Yadryara]

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

А что Вы собственно понимаете под эффектом фильтрации?

Увеличение скорости обсчёта тех же самых паттернов на тех же самых интервалах:

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

x64: 16910с / 14.9с (из них 2.9с в PARI) = 1135x
x32: 39070с / 38.2с (из них 7.2с в PARI) = 1023x

Для 12-15 ускорение было более чем тысячекратным, для 48-20 — 6-кратным. Как обстоят дела с другим количеством делителей и с другой длиной?

[Dmitriy40]

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

Как обстоят дела с другим количеством делителей и с другой длиной?

Очень сильно по разному. Собственно именно ускорение я практически и не мерил.
Тысяча раз там была из-за 11-ти проверяемых мест и из-за меньшего порога простых в ускорителях (практически все остальные ускорители настроены на 32768 вместо 3584).
Несколько примеров (все в предположении что всё время в PARI уходит на проверку кандидатов, а накладные расходы малы):
172 делителя, 7 проверяемых мест из 7-ми, 48 паттернов, шаг 2.38e242, N=11530047, 7145.796s (5800.789s in PARI) per round 667e252 - 4.2e9 попыток на каждый паттерн, 2e11 попыток всего, 11.5e6 кандидатов, коэффициент фильтрации соответственно 17530, 2000 кандидатов в секунду в PARI, проверка 2e11 кандидатов заняла бы 100млн.с (больше трёх лет!), ускорение 14000х.
172 делителя, 5 проверяемых мест из 7-ми, 48 паттернов, шаг 5.45e239, N=3274847, 946.429s (901.748s in PARI) per round 73e248 - 1.836e8 попыток на каждый паттерн, 8.81e9 попыток всего, 3.27e6 кандидатов, коэффициент фильтрации соответственно 2700, 3630 кандидатов в секунду в PARI, проверка 8.81e9 кандидатов заняла бы 2.43млн.с или 28 суток, ускорение 2570х.
296 делителей, 2 проверяемых места из 7-ми, 48 паттернов, шаг 3.08e205, N=248671, 303.385s (300.504s in PARI) per round 1179e211 - 325000 попыток на каждый паттерн, 15.6млн попыток всего, 249 тысяч кандидатов, коэффициент фильтрации 63, 830 кандидатов в секунду в PARI, проверка 15.6млн кандидатов заняла бы 18800с, ускорение 62х.
156 делителей, 6 проверяемых мест из 8-ми, 2 паттерна, шаг 2.8e105, N=325840, 33.171s (27.021s in PARI) per round 160e114 - 3.6e8 попыток на паттерн, 7.2e8 попыток всего, 326 тысяч кандидатов всего, коэффициент фильтрации 2200, 12070 кандидатов в секунду в PARI, проверка 720млн кандидатов заняла бы 60000с, ускорение 1800х.
36 делителей, 6 проверяемых мест из 13-ти, 288 паттернов, шаг 7.74e61, N=23494006, 1566.034s (1063.630s in PARI) per round 104e70 - 1.3e8 попыток на паттерн, 3.72e10 попыток всего, 23.5млн кандидатов, коэффициент фильтрации 1580, 22085 кандидатов в секунду в PARI, проверка 3.72e10 кандидатов заняла бы 1.7млн.с, ускорение 1075х.
12 делителей, 11 проверяемых мест из 15-ти, 11520 паттернов (46080/4 потока, тогда делил по потокам так), шаг 4.4e26, N=22773549, 2574.036s (398.021s in PARI) per round 500e35 - 2.27e8 попыток на паттерн, 2.615e12 попыток всего, 22.8млн кандидатов, коэффициент фильтрации 114840, 57185 кандидатов в секунду в PARI, проверка 2.615e12 кандидатов заняла бы 45.7млн.с (полтора года!), ускорение 17765х.
По последнему примеру видно что когда основная работа приходится на ускорители, то предположение грубо неверно. А чем больше работы приходится на PARI, тем точнее ускорение совпадает с коэффициентом фильтрации (что впрочем очевидно и задано методом расчёта). Промерять реальные ускорения мне лень, каждый желающий может это сделать сам для любых выложенных ускорителей (записать время с ускорителями, заменить вызов ускорителей на заполнение массива vi числами с ii по ii+st[g]-1 и замерить время без ускорителей).
Другая иллюстрация той же мысли зависимости скорости далеко не только от паттернов и ускорителей: 272 делителя, одно проверяемое место из 7-ми, 48 паттернов, шаг 2.13e91, минимальное и максимальное время на круг (и пара промежуточных для сравнения): N=1208, 9.784s (8.378s in PARI) per round 16e94, N=1199, 27.588s (26.770s in PARI) per round 11e94, N=2442, 15.453s (13.307s in PARI) per round 17e94, N=2421, 97.981s (95.800s in PARI) per round 10e94 - времена отличаются на порядок, хотя кандидатов всего вдвое больше, а для средних двух результатов время отличается втрое-вшестеро при том же количестве кандидатов.

UPD. Плюс для достаточно больших чисел (1e70 и больше) время в PARI сильно зависит от: будем ли собирать статистику или только лишь искать решения (второе сильно быстрее), будем ли искать только максимально длинное решение или меньшей длины тоже (второе сильно медленнее), сколько работы оставим человеку (на ручную допроверку цепочек, видели выше как некоторые кандидаты сутками не раскладываются? из-за этого сложности с определением минимального решения).