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

[Yadryara]

kotenok gav в сообщении #1552493 писал(а):

Нет (жду конкретных указаний).

От кого Вы ждёте конкретных указаний ?

Если Вы решили заняться 12-ю делителями, обращайтесь к Dmitriy40, если другим количеством делителей — к VAL.

[VAL]

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

Если Вы решили заняться 12-ю делителями, обращайтесь к Dmitriy40, если другим количеством делителей — к VAL.

Насколько я понимаю, с 36-ю делителями тоже следует обращаться к Дмитрию. Там без ускорителей далеко не продвинуться.
А вот с 48-ю - это ко мне.
У меня есть gp-программки и для поиска цепочки из 18 чисел по 24 делителя. Но такая цепочка должна найтись и без расшаривания усилий. А поиск более длинных цепочек по 24 делителя, возможно, тоже придется ускорять.

Минимизация пятнашки по 12 делителей представляется мне абсолютно тупиковой задачей. Уменьшить-то, наверное, можно (хотя не факт). Но вот доказать минимальность - полная безнадега.
Я тут поуменьшал (по просьбе Шёнфилда) оценки для T(15, 5) и T(15, 4). Задумался о доказательстве минимальности и понял, что даже для этого гораздо более простого случая это, все равно, трудно.

[Dmitriy40]

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

Из них тогда была 1 12-ка, а нынче 2.

Это пока не показатель, я неоднократно говорил сравнивать надо по ALL цепочкам, остальные слишком сильно зависят от сторонних факторов.

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

Что касается дальнейшей определенности, то, ИМХО, надо дождаться результатов анализа от уважаемого Dmitriy40 и его решения - под какую задачу он будет делать ускорители на ASM/AVX2/SSE.

Да я могу накомпилить под любой указанный паттерн (или их группы суммарно до скажем сотни тысяч штук). Единственно, надо бы чёткое подтверждение от RTM что нужна и AVX2 версия, раз она идёт только у него. Но сначала по любому — определиться с паттернами.
Сам я вряд ли выберу подходящий паттерн (или их группу), искать по вершинам малоперспективно каким бы многообещающим паттерн ни был, а ограничить низины разумным количеством паттернов не получается (числа 21! и даже 10! неразумны).

Например, попытка размещения в M24=31 чисел лишь 2-11 позволяет сделать проверяемыми до 17-ти чисел при добавлении 10-13 простых в квадратах (т.е. 10!-13! паттернов в каждой группе), при этом 8-9 мест остаются пустыми и 5-6 мест непроверяемыми, таких групп паттернов уже 48 (из всего 25520). Даже если отрезать края и оставить лишь центр длиной 15-20 (в мало обоснованной надежде что края найдутся автоматом), всё равно паттернов слишком много и непонятно какое более-менее разумное условие наложить чтобы их стало сильно меньше.
Может и правда начать с M36=15 и попытаться уменьшить количество паттернов до минимума, невзирая на раздутие шага.
Короче сам я буду думать ещё долго (и скорее всего безрезультатно).

[VAL]

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

Может и правда начать с M36=15 и попытаться уменьшить количество паттернов до минимума, невзирая на раздутие шага.

Именно. Причем лучше не сразу 15, хотя именно это конечная цель. Но, IHMO, разумнее начать поиска более коротких цепочек. А в процессе поиска, возможно, появятся еще какие-то идеи ускорения. Как минимум статистика, показывающая какие паттерны перспективнее (скажем, с использованием $3^8$ или без).

[Yadryara]

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

Минимизация пятнашки по 12 делителей представляется мне абсолютно тупиковой задачей. Уменьшить-то, наверное, можно (хотя не факт).

Не просто можно, а скорее всего, после проверки 10 других подклассов будет найдена меньшая 15-ка. Если угодно, я приведу расчёт. Ещё попутно можно уменьшить непрерывную 14-ку. 13-ку вряд ли.

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

Это пока не показатель,

Чем богаты. Пока нашлось 9 12-к и 2 13-ки. Олловских среди них нету.

[Dmitriy40]

Выбрал для теста 4 группы паттернов M36-13 (максимально заполненных в центре), расставил в них по 3 малых простых, получил 9 проверяемых чисел, модуль/шаг примерно 8e63, запустил на диапазон 0-1e73, все 24 паттерна проверяются пару минут, интересовало качество фильтрации, оказалось практически 2000:1 (на М(12)=15 на КМК37-11 было примерно 115000:1). За полчаса перебора ALL цепочек не нашлось, лишь 5шт valids=7,maxlen=7.
Но ускорение осталось на уровне, практически 8000 раз, которые снижаются втрое при реализации проверки по индексам в PARI.

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

Причем лучше не сразу 15, хотя именно это конечная цель. Но, IHMO, разумнее начать поиска более коротких цепочек.

Но я за то чтобы их искать по паттернам, подходящим и под 15-ку, а не по специально укороченным. Вдруг повезёт?

-- 14.04.2022, 22:58 --

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

Вдруг повезёт?

На самом деле повезти не может даже в принципе: для этого надо как минимум пройти всю разницу между шагом меньшего паттерна и пятнашки, а если искать 12-ку, для которой наверное ещё можно как-то вменяемо ограничить количество паттернов, то разница в шаге составит порядка квадрата произведения 6-ти простых, в худшем случае самых больших из первых 21-22, т.е. где-то 11 порядков. И это только разность шага, а когда встретится сама пятнашка ещё вопрос, в М12 она нашлась через ещё 11 порядков ...
Так что моё пожелание выше неразумно.

[Yadryara]

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

Сначала по всем 46080 паттернам. На проверенном интервале 0-1e35 нашлись 92 цепочки

64 цепочки 11+ на том же интервале. Ни одной олловской.

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

(причём все строго по разным паттернам, ни один паттерн не выдал больше одной цепочки), в том числе и пара уникальных:
N2-56-354126: 81208614941517230882469765804509145: 12, 12, 12, 12, 12, 12, 12, 12, 24, 12, 12, 12, 12, 12, 12, valids=14, ALL
S9-52-652143: 99575243234031209961434201105678041: 12, 12, 12, 24, 12, 12, 12, 12, 12, 12, 12, 12, 24, 12, 12, valids=13, ALL
Уникальность не только в размере, хотя и это что-то невероятное, но и это все найденные полнокомплектные цепочки.

Найдены две 13-ки:

M12-S2-31-124537: 19592264090488068517131913681574041
12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 24, 12, 24, valids=13

M12-S9-25-341572: 27823456256165539351766509581868441
12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 24, 12, 12, 12, 24, valids=13

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

Найдено также 22шт 12-ок

Найдено 16 штук 12-к.

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

11-ок нашлось 68 штук,

11-к нашлось 46 штук.

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

Да мне совершенно не очевидно что КМК37-11 является самым перспективным вариантом.

И до сих пор не очевидно, что КМК37-11 — самый перспективный подкласс паттернов?

[RTM]

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

Единственно, надо бы чёткое подтверждение от RTM что нужна и AVX2 версия, раз она идёт только у него. Но сначала по любому — определиться с паттернами.
Сам я вряд ли выберу подходящий паттерн (или их группу), искать по вершинам малоперспективно каким бы многообещающим паттерн ни был, а ограничить низины разумным количеством паттернов не получается (числа 21! и даже 10! неразумны).

Дмитрий, да, моя виртуальная машина готова к запуску двух потоков с поддержкой AVX2.

[EUgeneUS]

Очередная порция ИМХО.

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

И до сих пор не очевидно, что КМК37-11 — самый перспективный подкласс паттернов?

Очевидно, что КМК37-11 - перспективный класс паттернов. Это стало совсем очевидным после нахождения в нем трех 15-ек.
Но вот, что он самый очевидный - всё ещё не очевидно.
Даже если признать, что он эффективнее того класса, который Вы сейчас исследуете (что далеко не факт, опять же), нет никаких оснований утверждать, что он самый эффективный.

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

На самом деле повезти не может даже в принципе: для этого надо как минимум пройти всю разницу между шагом меньшего паттерна и пятнашки, а если искать 12-ку, для которой наверное ещё можно как-то вменяемо ограничить количество паттернов, то разница в шаге составит порядка квадрата произведения 6-ти простых, в худшем случае самых больших из первых 21-22, т.е. где-то 11 порядков. И это только разность шага, а когда встретится сама пятнашка ещё вопрос, в М12 она нашлась через ещё 11 порядков ...
Так что моё пожелание выше неразумно.

Не согласен.
1. Меньшие цепочки должны находиться более часто, чем большие. Вне зависимости от того, каким набором паттернов пользоваться.
2. Просто потому что для меньшей цепочки нужно меньшее количество простых чисел, попавших на свои места.
3. Конечно, меньшие цепочки, найденные таким способом будут (скорее всего) далеки от цепочек с минимальными числами, но они обязаны находиться при поиске больших цепочек.
4. Если меньшие цепочки не будут находиться за "разумное" время, то и большая не найдется.

-- 15.04.2022, 08:36 --

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

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

Как-это, как-это?
Очень надеюсь, что с появлением ускорителей к счету подключитесь и Вы, и уважаемый VAL, который если и не отдаст на это все 22 потока, то хотя бы 4-8.
Также опыт поиска $M(12)=15$ показал, что очень важно:
а) аккумулировать статистику
б) анализировать её с целью оценки ожидаемого времени счёта (в чём, опять же надеюсь, снова примет участие уважаемый Yadryara)

[Yadryara]

Болд мой.

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

Очевидно, что КМК37-11 - перспективный класс паттернов. Это стало совсем очевидным после нахождения в нем трех 15-ек.
Но вот, что он самый очевидный - всё ещё не очевидно.
Даже если признать, что он эффективнее того класса, который Вы сейчас исследуете (что далеко не факт, опять же), нет никаких оснований утверждать, что он самый эффективный.

Ну здрасьте, приехали! И это на 39-й странице! Есть все основания утверждать, что он самый эффективный.

Ну давайте по порядку. Вот уже на 2-й странице(на 2-й!!) подробное и понятное объяснение:

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

По одному числу в каждом наборе кратно 49, 121, 169, 289, 361, 529, 841, 961, 1369. При этом в наборах нет третьего числа, кратного 7, и вторых чисел, кратных 11 и 13 (последние теоретически могли бы присутствовать, но их допущение резко снижает эмпирическую вероятность успеха, поскольку в интересующем нас диапазоне произведения двух простых встречаются гораздо чаще, чем простые).

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

Прочитав это я понял, что самая перспективная концепция именно эта, которую я позже назвал КМК37-11. И уверенность, что именно в рамках этой концепции вероятность найти 15-шку максимальна, только укреплялась.

Вы не согласны с процитированным? Как это нет никаких оснований ??

[EUgeneUS]

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

Как это нет никаких оснований ??

Тут скорее спор\замечание о терминах и модальностях.
Есть основания полагать\предполагать, что данная система паттернов самая эффективная (в некотором смысле). Но не утверждать.

[Dmitriy40]

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

И до сих пор не очевидно, что КМК37-11 — самый перспективный подкласс паттернов?

Нет не очевидно. Шаг наименьший (и только из КМК вариантов), но насколько жёстко связана перспективность с величиной шага непонятно.
Почему считаю шаг не наименьший: поставив $3^2$ на любое свободное место и подняв степень до $3^5$ мы уменьшим количество дополнительных простых в квадрате на одно, т.е. шаг изменится в $3^3/37^2 < 1/50$ раз. Выгодно даже и $5^2$ заменить на $5^5$ так как $31^2>5^3$. И даже $29^2>7^3$. Сделав все эти замены получим не $6! = 720$ паттернов на группу, а $3! = 6$ и шаг станет не $4.4\cdot10^{26}$, а $4.6\cdot10^{23}$, почти в тысячу раз меньше.
Более того, я вовсе не уверен что недопустимы ни один из вариантов паттернов с искомым огромным простым в квадрате (вот кубы и пятую степень нет, их несложно проверить), их в паттерн до 7-ми штук влезает, некоторые запрещены по модулю 8, но не все и по видимому не во всех вариантах, а ведь это позволяет расставить малые простые не в квадратах или пятой степени, а в кубах, что тоже значительно уменьшит шаг.
И какой из вариантов более перспективен (особенно в плане нахождения близкой к минимальной пятнашки) — вопрос открытый. VAL что-то там оценивал, почему и сосредоточились на КМК, но что как и какие результаты осталось непонятным (вывод Maple меня не убедил из-за непонятности). И даже более, по его оценкам выходило

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

Действительно для 28 подходящих случаев больше (814 против примерно 700).

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

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

Не согласен.

Есть огромная разница между поиском пятнашки и меньших по паттернам для пятнашки и поиском скажем именно тринадцатки по паттернам для тринадцатки: во втором случае многие (если не почти все) паттерны просто не допускают расширение цепочки, даже теоретически. Но за счёт этого их на порядки меньшее количество вариантов. Потому искать конкретно тринадцатку конечно лучше по паттернам для тринадцатки, но вероятность при этом найти и что-то длиннее ничтожна (если вообще не исключена полностью). Из-за последнего я и хотел использовать лишь паттерны, допускающие и расширение цепочки ... Вероятность нахождения 13-ки меньше, зато не исключена вероятность 15-ки.

[Yadryara]

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

Шаг наименьший (и только из КМК вариантов), но насколько жёстко связана перспективность с величиной шага непонятно.

Это-то как раз понятно. Я же привёл статистику. Большой иф специально настроил так же как у Вас.

if(
\\! (z[1]>0 && !ispseudoprime((n+0)/v[1])) ||
\\! (z[2]>0 && !ispseudoprime((n+1)/v[2])) ||
\\! (z[3]>0 && !ispseudoprime((n+2)/v[3])) ||
(z[4]>0 && !ispseudoprime((n+3)/v[4])) ||
(z[5]>0 && !ispseudoprime((n+4)/v[5])) ||
(z[6]>0 && !ispseudoprime((n+5)/v[6])) ||
(z[7]>0 && !ispseudoprime((n+6)/v[7])) ||
(z[8]>0 && !ispseudoprime((n+7)/v[8])) ||
(z[9]>0 && !ispseudoprime((n+8)/v[9])) ||
(z[10]>0 && !ispseudoprime((n+9)/v[10])) ||
(z[11]>0 && !ispseudoprime((n+10)/v[11])) ||
(z[12]>0 && !ispseudoprime((n+11)/v[12])) ||
\\! (z[13]>0 && !ispseudoprime((n+12)/v[13])) ||
\\! (z[14]>0 && !ispseudoprime((n+13)/v[14])) ||
\\! (z[15]>0 && !ispseudoprime((n+14)/v[15])) ||

Шаг возрос на 23%, количество попыток уменьшилось на 27%, количество найденных цепочек(всех, 11-к и 12-к) тоже уменьшилось примерно на на 27%.

Но я продолжаю собирать стату.

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

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

Насчёт кубов у нас уже было два разговора. Приведите, пожалуйста, конкретный пример с кубом.

[VAL]

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

$3^3/37^2 < 1/50$ раз. Выгодно даже и $5^2$ заменить на $5^5$ так как $31^2>5^3$. И даже $29^2>7^3$. Сделав все эти замены получим не $6! = 720$ паттернов на группу, а $3! = 6$ и шаг станет не $4.4\cdot10^{26}$, а $4.6\cdot10^{23}$, почти в тысячу раз меньше.

Вы пишете это не в первый раз.
Но я этого не понимаю.
Приведите, пожалуйста, соответствующие паттерны.

Как я уже говорил, я понимаю, как, увеличив степень малого простого числа, уменьшить число нетривиальных простых, в случае, когда k (количество делителей) имеет более одно простого множителя отличного от 2. Например, для 36. Но для 12, 24, 48, насколько я понимаю, это не работает.

[Dmitriy40]

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

Это-то как раз понятно. Я же привёл статистику. Большой иф специально настроил так же как у Вас.

Я говорил не только о КМК паттернах.

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

Вы пишете это не в первый раз.
Но я этого не понимаю.
Приведите, пожалуйста, соответствующие паттерны.

Может и я чего-то не понимаю. Но генератор выдаёт такие паттерны. Как пример:
$3^5p,50p,1859p,12p,X,98p,15p^2,32p,X,18p,X,20p,21p^2,242p,X,lcm=194788994400$
Расставив ещё и простые $17,19,23,29$ в квадратах получим шаг $9041096985906491906400\approx9\cdot10^{21} < 4.4\cdot10^{26}$.
Простые в квадратах $p^2$ по модулю 8 проходят, по остальным не уверен, может такой паттерн и чем-то запрещён.
И да, с $3^5$ не бывает паттернов без $p^2$.
С подстановкой ещё и $5^5$ фокус не проходит, шаг увеличивается (почему-то всё равно требуются 4 дополнительных простых).

-- 15.04.2022, 13:02 --

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

Насчёт кубов у нас уже было два разговора. Приведите, пожалуйста, конкретный пример с кубом.

Да потому что они очевидным образом не КМК, которые Вы только и желаете обсуждать. Пример:
$117p,50p,X,12p,X,98p,15p^2,32p,X,18p,11^3p^2,20p,21p^2,338p,X,lcm=79358479200$
Расставив $17,19,23,29$ получим шаг $3683409883147089295200\approx3.68\cdot10^{21}<4.4\cdot10^{26}$.
Я не помню доказательства что такого рода паттерны совершенно точно не дают решений, или дают их намного менее вероятно (тем более что перебирать их можно и не линейно как КМК, а по $p^2$), или что они не дадут пятнашку менее найденных по КМК.