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

[Yadryara]

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

Напомню (чтобы не затерялось в теме): считали втроём — я, EUgeneUS, RTM, а Yadryara активно занимался математикой и находил мои косяки.

Вообще-то впятером. Убедившись, что Вы вслед за мной всё пересчитываете, досчитал 1440 паттернов до $3\cdot10^{37}$ и только потом перестал считать и занялся вероятностями, что было весьма интересно и полезно.

Итак. Средняя частотность для 15-ки в диапазоне $0-10^{38}$ — одна на 44 миллиарда попыток. Был сделан 91 миллиард попыток. То есть все возможные в рамках КМК37-11 попытки в указанном диапазоне.

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

Но не повезло именно с 1-й(пока наименьшей) пятнашкой. Она нашлась только после проверки 60-ти с лишним миллиардов попыток, считая с самого низа.

1-я пятнашка — после 60 ярдов;
2-я пятнашка — после 69 ярдов;
3-я пятнашка — после 83 ярдов.

И вот можно попытаться побить этот и другие рекорды. Я наконец-то скомпилил новые 46080 паттернов для подкласса 11-23. И уже протестировал их в работе.

Дальше два варианта.

Либо попытаться все проги выложить в облако, как сделал Dmitriy40. Правда, я сам ни разу этого не делал.

Либо каждый компилит у себя. Этот вариант гораздо лучше. Может быть заточен под конкретный комп и не требует столько трафика. Инструкция не самая простая, но надеюсь, Dmitriy40 подскажет желающим.

[Dmitriy40]

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

Вообще-то впятером.

Что считал VAL никому неизвестно, он только совсем недавно коротко сказал какие 82 паттерна считаются (но непонятно докуда), ну и в выложенную статистику его данные в принципе не вошли (и за полным отсутствием, и за выборочностью, 82 из 46080).
Что считали Вы у меня тоже не было ни информации, ни статистики (логов), потому упомянул как упомянул.
За EUgeneUS я тоже кусочек пересчитывал (потому что лень было править формат лога, проще подождать несколько часов и получить уже всё единообразно), и что с того, вот мне честно проще потратить лишние часы счёта (3+ дня на 1e37 по 64 группам, значит на 2 группы на 3e37 надо лишних 8-10 часов) лишь бы не заморачиваться с перезапуском счёта для части паттернов. И за RTM пересчитывал оборванные куски по 1e35, и для сравнения/контроля, и чтобы не лезть в нормально работающую систему для незначительного уменьшения времени счёта. И за собой куски пересчитывал, когда не уследил и второй комп всю ночь и полдня молотил уже насчитанное (заодно и сравнил, всё конечно совпало).

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

Либо каждый компилит у себя. Этот вариант гораздо лучше. Может быть заточен под конкретный комп и не требует столько трафика. Инструкция не самая простая, но надеюсь, Dmitriy40 подскажет желающим.

С этим вариантом не согласен: и не хочу каждому объяснять как компилить асм исходники; и у всех могут получиться чуть разные исполняемые файлы (в том числе и любимое Вами количество попыток разное тогда может быть); и чтобы оптимизировать под конкретный комп надо провести несколько десятков тестов (а мне соответственно объяснять как именно, у себя их проводил сотни и только тогда выбрал более-менее оптимальные варианты) и это тоже может привести к разному качеству фильтрации (количеству попыток); и 1ГБ трафика на все 46080 прог не так уж много (меньше любого фильма если не с ютуба); ну и остаётся риск что-то испортить в исходнике и получить плохо или совсем неработающие проги (и не узнать об этом, та куча проверок что расписал Вам лишь малая часть необходимых, в расчёте что асм код Вы трогать не будете, а PARI код лишь очень аккуратно (только в документированных местах или косметически, пример с 719 паттернами прекрасно иллюстрирует лёгкость ошибиться, в том числе и мне), ещё и поэтому не хочу выкладывать это всё публично).
Потому если будет интерес народа, то готов и выложить у себя в облаке, и скомпилить несколько других вариантов (все 156 не просить ). Хотя по прежнему не понимаю смысла, ведь минимальность так не докажем, лучше уж поискать что-то полезное.

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

Очень парадоксальное заявление!
Хотя, если иметь в виду составление паттерна... В принципе у меня имеется готовый. Но я для M(36) могу составить. Проблема-то не в этом.

Да, проще составить паттерн, меньше разных вариантов для каждого числа (например удобно что везде должен быть ровно один квадрат).
Один?! Зачем один? Один (и несколько тысяч) и я могу составить. Надо все или около того — как показала практика полезнее поиск по всем низинам, чем поиск на нескольких вершинах (ведь они были проверены в тысячи раз дальше низин, и не нашлось). Ну или хорошо обоснованный выбор некоторых из всех (у меня обосновать не получается кроме как сделать весь центр непрерывным).
Вот вместо непонятно зачем поиска чуть меньшей М(12)=15 лучше бы поставить реальную задачу (например поиск М(24)=20..22, требуемая 31 выглядит нереальной) и наброситься всем кагалом на неё.

[VAL]

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

Один?! Зачем один? Один (и несколько тысяч) и я могу составить.

Из одного несколько тысяч (миллионов, миллиардов) легко получаются перестановкой взаимозаменяемых модулей.

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

Вот вместо непонятно зачем поиска чуть меньшей М(12)=15 лучше бы поставить реальную задачу (например поиск М(24)=20..22, требуемая 31 выглядит нереальной) и наброситься всем кагалом на неё.

С этим полностью согласен. С поправкой на то, что начинать нужно с цепочки из 19 чисел.
18-ти тоже пока нет, но я уверен, что доберусь до нее и без кагала

[EUgeneUS]

Очередное ИМХО по вопросу "что искать?".

Ответ на этот вопрос зависит от трех других.

1. Чем располагаем?
Насколько понимаю, имеющиеся вычислительные мощности понятны, и они малы. В перспективе можно поискать ещё простаивающие компы и GPU из топа 5-9 летней давности (более новые или у геймеров, или криту считают). Это может дать увеличение располагаемой вычислительной мощности в разы, может быть на порядок. Но не более. Для бОльшего нужно выходить на другой организационный уровень.
То есть ориентируемся на имеющуюся вычислительную мощность с потенциальным ростом в 2-5 раз, может быть на порядок, но не более.

2. Что искать интересно?
В порядке понижения интереса
а) Максимально длинные цепочки: $M(24)=31, $M(36)=15, $M(48)=31$
б) Цепочки, начинающиеся с (доказано) минимального числа.
в) Улучшения нижней границы для $M(24), $M(36), $M(48)$
г) Улучшения нижней границы для уже найденных цепочек. Например, улучшение для М(12)=15. Без доказательства, что улучшения минимальные.

3. Что найти реально?
Насколько понимаю, пункты 2а и 2б уважаемыми VAL и Dmitriy40 оцениваются, как нереальные.
Наиболее реальные задачи - это из пункта 2г, но они же и наименее интересные.
Остаётся пункт 2в.

-- 13.04.2022, 11:48 --

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

С этим полностью согласен. С поправкой на то, что начинать нужно с цепочки из 19 чисел.

Может быть имеет смысл начать сразу с бОльшей цепочки (но которую найти реально), а меньшие получать как дополнительный сопутствующий эффект? Как получилось с 14-кой на 12 делителей.

[Dmitriy40]

VAL
Подскажите пару моментов по M24?
1. Считаете ли оправданным ставить 3,5,7 (и может и 11) в 11-й степени ради уменьшения количества вариантов паттернов? В ваших цепочках недавно видел и 28-ю степень.
2. Стоит ли оставить одно (два? три?) больших (т.е. искомых) простых в квадрате? Они хоть и будут огромными, но используя Вашу идею выше о модулях можно попробовать их поискать, собственно по ним тогда и перебирать.

EUgeneUS
В общем да.
Добавлю, в пункте 1 можно поискать (почти) бесплатные облачные кластеры, на тысячи потоков (или десятки тысяч потоков GPU), думаю сотню-другую usd наскребём ради задачи с почти гарантированным результатом. Но платить например 20usd только за годовую лицензию на винду (как в одном месте видел) ради недели счёта за 5usd меня жаба душит.
В пункте 2в можно помнить про ненулевой шанс что невероятно крупно повезёт и вдруг найдётся и максимально длинная цепочка.
В 2г улучшения всё же верхней границы (на величину чисел), не нижней (на длину цепочек).

-- 13.04.2022, 11:56 --

Бонус для 2г: в T(6,10) (12 делителей длиной 10) не может быть простых в пятой степени больше 1000, таких решений до известной цепочки 7.1е20 просто нет.

-- 13.04.2022, 12:03 --

И для информации: для M(12)=15 до 1e38 из 46080 паттернов цепочки с 11 и более совпадений дали лишь 26640 паттернов, а цепочки ALL (совпали все искомые числа) лишь 711 паттернов из 46080. Это к вопросу стоит ли искать лишь по малой части всех возможных паттернов, так вероятность нахождения резко снижается.

[VAL]

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

Может быть имеет смысл начать сразу с бОльшей цепочки (но которую найти реально), а меньшие получать как дополнительный сопутствующий эффект? Как получилось с 14-кой на 12 делителей.

Тут есть важные нюансы.

Моя программка для поиска 20 чисел по 48 делителей имеет целый ряд предварительных фильтров (что значительно ускоряет процесс).
В то же время эта программка может не найти цепочку из 19 чисел, если с помощью предварительных фильтров она будет отбракована, как тупиковая для 20 чисел.

Впрочем, пожалуй, эта трудность обходима. Исключение из предварительных фильтров друх крайних чисел цепочки не сильно замедлит программу.

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

[Yadryara]

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

Что считали Вы у меня тоже не было ни информации

Была. Ссылки приводить?

Я считаю, что надо было упомянуть, что считали впятером, но данные в том файле только на основании логов трёх участников.

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

, в расчёте что асм код Вы трогать не будете, а PARI код лишь очень аккуратно (только в документированных местах или косметически, пример с 719 паттернами прекрасно иллюстрирует лёгкость ошибиться, в том числе и мне),

Да, я старался быть внимательным, аккуратным и осторожным, что и позволило мне заметить 719 вместо 720 и исправить. Но Вашей коронной фразы "спасибо за дотошность" я так и не услышал

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

Вот вместо непонятно зачем поиска чуть меньшей М(12)=15

Поиск чуть большей М(12)=15, которым Вы занимались, ещё менее понятен.

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

любимое Вами количество попыток разное тогда может быть

Кстати, несколько часов специально считал количество попыток. Оно оказалось не на 23%, а на 27% меньше, чем в КМК37-11.

$\text{КМК37-11}\hspace{1cm}9.11$ млрд на интервал длиной 1е37
$\text{11-23}\hspace{1.86cm}7.15$ млрд на интервал длиной 1е37

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

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

Полагаю, надо пока что наброситься на подкласс 11-23. Я уже начал считать и улучшил результат всепаттерного запуска для КМК37-11:

Непрерывная 12-ка.

Паттерн M12-N9-26-423157;

2989076058514753458059558224665945;

12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 48, 24, 48.

Правда, VAL, как я понимаю, находил ещё меньшую непрерывную 12-ку.

[EUgeneUS]

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

И для информации: для M(12)=15 до 1e38 из 46080 паттернов цепочки с 11 и более совпадений дали лишь 26640 паттернов, а цепочки ALL (совпали все искомые числа) лишь 711 паттернов из 46080

Смотреть на "урожайность" отдельных паттернов, при том, что у нас находок (записей в логах) меньше, чем самих паттернов - особого смысла нет.
Я пытался анализировать "урожайность" групп паттернов (которых 64 штуки). Там довольно интересно:
а) "урожайность" по "valids=11" заметно различна. Раза в полтора между минимальной и максимальной.
б) Однако, наиболее "урожайные" по "valids=11" отнюдь не совпадают с наиболее урожайными по "valids=12 и т.д.

Так что согласен с выводом:

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

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

[VAL]

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

1. Считаете ли оправданным ставить 3,5,7 (и может и 11) в 11-й степени ради уменьшения количества вариантов паттернов? В ваших цепочках недавно видел и 28-ю степень.

Полагаю, что не стоит. Это приведет к росту проверяемых чисел и шага, что не есть хорошо.
При поиске цепочки из 19 чисел по 48 делителей, я, тем не менее, отводил несколько потоков, для паттернов с большими степенями 3-ки и 5-ки. Но результат дал паттерн без таковых.

28-е степени (не одна, а семь штук) использовались для поиска цепочки из 7 чисел по 116 делителей. В данном случае без них не обойтись (116 кратно 29). Именно поэтому я и считаю нахождение данной цепочки своим значительным достижением.
Очень просто пишется программа для поиска поиска такой цепочки с использованием 7 раз на простоту. Но вероятность такого события крайне мала. Приходится выкручиваться и пытаться разлагать на множители огромные числа.

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

2. Стоит ли оставить одно (два? три?) больших (т.е. искомых) простых в квадрате? Они хоть и будут огромными, но используя Вашу идею выше о модулях можно попробовать их поискать, собственно по ним тогда и перебирать.

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

[Dmitriy40]

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

Я считаю, что надо было упомянуть,

Поправил.

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

Поиск чуть большей М(12)=15, которым Вы занимались, ещё менее понятен.

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

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

Этот вопрос понял не до конца.

Можно в паттерне оставить в какой-то позиции например $2\cdot3^3$, тогда там нужно будет найти $p^2$, но это самое $p$ будет цифр эдак из 40-50. Зато меньше чисел придётся подставлять, что уменьшает и количество вариантов паттернов и соответственно шаг, и перебирать можно по этому $p^2$ (через модули, не напрямую).

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

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

Зато это уменьшает количество требуемых простых на 1 или 2. А раз они минимум в квадратах, то например $83^2\times89^2>3^{11}$, т.е. подстановка $3^{11}$ в пустую позицию шаг наоборот уменьшает. Даже замена одной из $5^2$ на $5^{11}$ увеличивает шаг в $5^9$ раз, зато можно не подставлять 83 и 89 и шаг уменьшится $83^2\times89^2/5^9\approx28$. Правда это для 31-ки и числа несколько наобум, для 20-ки будет хуже и возможно шаг будет возрастать, её ещё не смотрел.
Т.е. варианты не раздувать шаг вроде бы есть, но насколько реже будут решения плохо понимаю.
Зато исключение 21-го подставляемого простого числа уменьшает количество вариантов паттернов в 21 раз ... Вот как бы найти баланс между количеством вариантов и вероятностью нахождения ...

[VAL]

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

Зато это уменьшает количество требуемых простых на 1 или 2. А раз они минимум в квадратах, то например $83^2\times89^2>3^{11}$, т.е. подстановка $3^{11}$ в пустую позицию шаг наоборот уменьшает.

Такого рода соображения я использовал. Но они не касаются поиска цепочек с числами по 24 и 48 делителей.
А для 36 да, возможна такого рода замена.

[Yadryara]

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

Прогнал по кругу все паттерны на интервале $0-1\cdot10^{34}$, нашлись лишь вот такие цепочки (менее 11 совпадений не сохранял):

А я и 10-ки сохранял. И тоже прогнал по кругу все паттерны(другого подкласса 11-23) на интервале $0-1\cdot10^{34}$. Нашлись 19 штук 10-к, 8 11-к и 2 12-ки. 10-ки показывать пока не буду.

M12-N2-53\M12-N2-53-135724.out:4012803348113686766640911157624345: 48, 24, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 48, 12, 48, valids=11
M12-N2-56\M12-N2-56-213754.out:9596243549541493732502450275555545: 12, 12, 24, 12, 12, 12, 12, 12, 12, 12, 12, 12, 24, 24,192, valids=11
M12-N9-26\M12-N9-26-423157.out:2989076058514753458059558224665945: 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 48, 24, 48, valids=12
M12-S2-21\M12-S2-21-745132.out:8038838579853581177537348650646041: 24, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 24, 48, 12, valids=12
M12-S2-26\M12-S2-26-547213.out:4551285034843270509935510461415641: 12, 48, 12, 12, 12, 12, 12, 12, 12, 12, 24, 12, 6, 12, 24, valids=11
M12-S2-26\M12-S2-26-713245.out:164980076432705690483474731098841: 12, 24, 12, 12, 12, 12, 12, 12, 12, 12, 48, 12, 48, 12, 24, valids=11
M12-S2-46\M12-S2-46-735412.out:5937646996927943325209494092950041: 12, 96, 24, 12, 12, 12, 12, 12, 12, 12, 48, 12, 48, 12, 12, valids=11
M12-S9-21\M12-S9-21-251473.out:5552116870747315493954923809642841: 12, 12, 48, 24, 12, 12, 12, 12, 12, 12, 12, 12, 24, 48, 12, valids=11
M12-S9-32\M12-S9-32-542371.out:355721191940875630054583532935641: 12, 12, 48, 12, 12, 12, 12, 12, 12, 12, 12, 12, 24, 24, 48, valids=11
M12-S9-43\M12-S9-43-475312.out:9117152737312148487932481956222041: 12, 24, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 96, 48, 24, valids=11

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

Ни одной полнокомплектной. И всего 11 штук на 46080 паттернов.

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

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

Очередное ИМХО по вопросу "что искать?".

Спасибо за анализ этого вопроса. Правильно ли я понимаю, что в итоге так и не определились? И ни Вы, ни RTM, ни kotenok gav сейчас ничего не ищете?

[EUgeneUS]

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

И ни Вы, ни RTM, ни kotenok gav сейчас ничего не ищете?

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

[kotenok gav]

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

И ни Вы, ни RTM, ни kotenok gav сейчас ничего не ищете?

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

[VAL]

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

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

Сколько потоков Вы готовы выделить под проект? (Каждая gp-программка занимает одит поток.)