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

[Yadryara]

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

Лучше это проверки КМК37-11 или хуже пока не понял

Ну вообще-то по моему паттерну в таком диапазоне находилось в среднем
61 12-ка против 3-х у Вас;
5 13-к против 0 у Вас.

И даже 1 14-ка против 0 у Вас.

Очень трудно всё же найти 13 огромных простых.

[Dmitriy40]

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

Ну вообще-то по моему паттерну в таком диапазоне находилось в среднем

Это некорректное сравнение потому что разные условия в PARI программе. Напомню, у меня по Вашему паттерну работали две программы с идентичным .exe и вторая находила сильно реже и меньше цепочки, например интервал $6-10\cdot10^{40}$ обсчитан обеими и найдены: 3x13 и 53x12 первой против 2x13 и 2x12 второй.
По этому паттерну PARI программа аналогична второй (тоже проверяет всю середину цепочки). Плюс это зависит от интервала. По $0-5 \cdot 10^{40}$ данных по второй программе по Вашему паттерну у меня нет, она начала с $6\cdot10^{40}$, а вот например в интервале $12-17\cdot10^{40}$ по Вашему паттерну нашлось 7шт 10-ок, 4шт 11-ок, 1шт 12-ка, 1шт 13-ка (подробно выложу как досчитается до 20e40). Лучше это или хуже КМК37-13 непонятно, диапазон то другой. Вот досчитает по этому паттерну за сутки до $10^{41}$, будет предмет для сравнения (а лучше подождать и ещё пару дней до 20e40).
Наиболее адекватно можно сравнить отобрав только полнокомплектные 13-ки, которые имеют неправильные числа лишь в непроверяемых местах. Вот только таковых пока слишком мало (или вообще нет).

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

Очень трудно всё же найти 13 огромных простых.

Это да, но нам то нужно 15 чисел. Учитывая равновероятность простых в любой позиции нет оснований объявлять какой-то паттерн более эффективным чем другой в смысле величины 15-ки. А вот на скорость перебора вариант паттерна (и порядок проверки в PARI) может влиять.
Вообще вопрос сравнения эффективности разных паттернов как-то плохо изучен (или я не уследил за полётом мысли).

[Yadryara]

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

46080 всего. Хм, это совпадает с цифрой VAL.

У меня получилось столько же:

Паттернов-28 $3\cdot4\cdot6!\cdot2 = 17280$.
Паттернов-98 $4\cdot5\cdot6!\cdot2 = 28800$.

[Dmitriy40]

Что же, совпадение чисел у всех радует, значит понимание достигнуто.

Про 46080 паттернов. Если делать под каждый отдельную программу в наиболее быстром варианте, то это займёт 500ГБ (по 11М на паттерн). Даже если немного пожертвовать скоростью, то всё равно 70ГБ. И компилиться будет неделю. Мрак. Проблемой будет и переслать такой объём (не любое облако даст столько места). Буду думать что с этим делать.


Досчиталось у меня до 20e40, приведу все 11-ки и длиннее, их немного:
134989811440858525301353576324460990457945: 48, 12, 24, 12, 24, 12, 12, 12, 6, 12, 12, 12, 12, 12, 12, valids=11
140783780841573755558638128602953002465945: 12, 12, 48, 12, 24, 12, 12, 12, 48, 12, 12, 12, 12, 12, 24, valids=11 - полнокомплектная
146891315986018074970906350629819535979545: 48, 12, 48, 12, 96, 12, 12, 12, 48, 12, 12, 12, 12, 12, 12, valids=11
152872807047827449506942290709232202784345: 24, 12, 48, 12, 96, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, valids=12
160472961212184823743152187567743195621145: 12, 12, 12, 12, 6, 12, 12, 12, 12, 12, 12, 12, 12, 12, 24, valids=13 - полнокомплектная
163841422650473597435554477935491645136345: 48, 12, 12, 12, 6, 12, 12, 12, 48, 12, 12, 12, 12, 12, 24, valids=11
173666571425194475258026833243738386832345: 24, 12, 12, 12, 24, 12, 12, 12, 24, 12, 12, 12, 12, 12, 48, valids=11
175040018405938483177801142525585768563545: 48, 12, 96, 12, 48, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, valids=12
176973375123784294327748146348838735952345: 48, 12, 24, 12, 48, 12, 12, 12, 12, 12, 12, 12, 12, 12, 96, valids=11
193723163702203398277886730252656261376345: 24, 12, 12, 12, 48, 12, 12, 12, 6, 12, 12, 12, 12, 12, 48, valids=11
198418049725171774006473215615797618161945: 12, 12, 18, 12, 48, 12, 12, 12, 48, 12, 12, 12, 12, 12, 48, valids=11 - полнокомплектная

[Yadryara]

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

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

Да, но нам не надо забывать, что мы ищем не одно простое, а как минимум 11 простых. Стало быть, если вероятность найти 1 простое упала в два раза, то вероятность найти 11 простых упадёт в 2048 раз.

По этой же причине, если вероятность найти 1 простое упала на 13.5%, то вероятность найти 11 простых упала в $1.135^{11} \approx 4$ раза.

Примерно это и происходит при переходе от $10^{38}$ к $10^{43}$.

Совсем недавно, 28 февраля в A006880 было опубликовано точное число простых до $10^{29}$.

Это всё равно ещё не наш основной диапазон, но зато есть прекрасное приближение: A226945. Вот его фрагмент:

38 115625126
39 112626194
40 109778913
41 107072063
42 104495503
43 102040046

Оставил по 9 значащих цифр слева. Видимо, они все верные.
Так вот, согласно этим данным, плотность простых до $10^{38}$ превышает плотность простых до $10^{43}$ в $\frac{115625126}{102040046}\approx 1.133$ раза.

Похоже, соответствующая вероятность действительно в 4 раза меньше. И мой оптимизм в отношении скорого(в течение 1-2 недель) нахождения 15-шки заметно поубавился.

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

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

Да, похоже всё-таки придётся делать перебор множества паттернов. Но об этом позже.

[Yadryara]

Dmitriy40, теперь, когда Вы поняли как формируются все возможные паттерны КМК37-11, роль координатора вполне может быть Вашей.

Подробнее позже. А пока уделю внимание крайним случаям:

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

45p 722p 841qr 12p 49qr 50p 507p 32p 961qr 18p 605p 28p 867p 1058p 1369qr

Это один паттерн из группы паттернов с наименьшими кэфами. Назову эту группу 28-605. Всего в ней 2880 паттернов.

А группу паттернов, наоборот, с наибольшими кэфами назову 28-6845. И прошу сделать прогу для проверки паттерна из этой группы:

45 722 169 12 49 50 2883 32 121 18 6845 28 2523 1058 289

Для удобства здесь куары на тех же местах: 3-м, 5-м, 9-м и 15-м.

[Yadryara]

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

Про 46080 паттернов.

Возможно, будет удобнее, если раздробить это количество на более мелкие части. Я ранее уже разделил на П-28 и П-98. Например, 17280 вариантов П-28 можно разделить ещё на 8 частей:

П28-605-507 $1\cdot2\cdot1\cdot1\cdot(2\cdot6)\cdot(5\cdot4)\cdot3! = 2880$

П28-605-169 $1\cdot2\cdot1\cdot1\cdot(6\cdot5)\cdot(4\cdot3)(2\cdot2!) = 2880$


П28-363-845 $1\cdot2\cdot1\cdot1\cdot(1\cdot6)\cdot(5\cdot4)\cdot3! = 1440$

П28-363-507 $1\cdot2\cdot1\cdot6\cdot(1\cdot1)\cdot(5\cdot4)\cdot3! = 1440$

П28-363-169 $1\cdot2\cdot1\cdot6\cdot(1\cdot5)\cdot(4\cdot3)(2\cdot2!) = 2880$


П28-121-845 $1\cdot2\cdot1\cdot1\cdot(6\cdot5)\cdot(4\cdot3)\cdot2! = 1440$

П28-121-507 $1\cdot2\cdot1\cdot6\cdot(2\cdot5)\cdot(4\cdot3)\cdot2! = 2880$

П28-121-169 $1\cdot2\cdot1\cdot6\cdot(5\cdot4)\cdot(3\cdot2)\cdot1 = 1440$

[Dmitriy40]

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

И прошу сделать прогу для проверки паттерна из этой группы:
45 722 169 12 49 50 2883 32 121 18 6845 28 2523 1058 289

Держите: https://dropmefiles.com/nTguF
Заодно обнаружил и поправил пару мелких глюков, на работу не влияющих, но иногда программа могла вылететь (утечка памяти, во всех версиях под x32, опять забыл правила вызова внешних функций).
По первому Вашему паттерну программа теперь называется Yadryara4a.exe, по второму Yadryara4b.exe.
Пример найденных цепочек по второму паттерну:
26135591908716160372965966733755081945: 12, 12,192, 12, 24, 12, 24, 12, 12, 12, 24, 12, 12, 12, 12, valids=11
177556605497874262882485491554197629145: 12,192, 12, 12, 12, 12, 12, 12, 12, 12, 24, 12, 48, 12, 12, valids=12

Дополнительно прошу провести замеры скорости работы программ Yadryara4a10k.exe и Yadryara4a4143.exe (это разные варианты оптимизации по первому паттерну), они приложены там же. Интересует кто из трёх Yadryara4a.exe, Yadryara4a10k.exe, Yadryara4a4143.exe будет быстрее на одинаковом интервале и насколько. Для теста запускать на интервале не менее $10^{37}$ из PARI, например также приложенным .gp файлом меняя в нём лишь имя используемого .exe. Время работы каждого варианта на интервале $10^{37}$ минуты две-три. Списки найденных цепочек всех трёх вариантов должны быть идентичными.

[Yadryara]

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

Интересует кто из трёх Yadryara4a.exe, Yadryara4a10k.exe, Yadryara4a4143.exe будет быстрее на одинаковом интервале и насколько.

N=236106, 80.802s / 15.959s in PARI
N=236106, 80.848s / 16.052s in PARI
N=236106, 81.765s / 16.162s in PARI

Именно в такой последовательности, как у Вас.

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

По первому Вашему паттерну программа теперь называется Yadryara4a.exe, по второму Yadryara4b.exe.

Только Yadryara4b.exe я чегой-то не обнаружил.

[VAL]

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

о 46080 паттернов. Если делать под каждый отдельную программу в наиболее быстром варианте, то это займёт 500ГБ (по 11М на паттерн). Даже если немного пожертвовать скоростью, то всё равно 70ГБ. И компилиться будет неделю. Мрак. Проблемой будет и переслать такой объём (не любое облако даст столько места). Буду думать что с этим делать.

Разумеется, не обязательно параллельно рассматривать все паттерны. Точно так же, как не обязательно упуливаться в один.
Рассматривать несколько (например, сотню) и надеяться, что повезет.

[Dmitriy40]

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

Только Yadryara4b.exe я чегой-то не обнаружил.

Позор мне, пропустил, извините. Вот: https://dropmefiles.com/iQg9a

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

N=236106, 80.802s / 15.959s in PARI
N=236106, 80.848s / 16.052s in PARI
N=236106, 81.765s / 16.162s in PARI
Именно в такой последовательности, как у Вас.

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

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

-- 11.03.2022, 17:06 --

VAL
Я Вас поздравляю! Нам откровенно повезло! Смотрите что нашлось по первому паттерну Yadryara:
241932253046233642976664116549337789441945: 48, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, valids=14
Т.е. теперь нижний порог уже не 13, а 14.

Народ, на всякий случай прошу перепроверить.

[Yadryara]

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

Простите, Вы точно не ошиблись?

Да, видимо, ошибся. Исправлял названия файлов, но не сохранял перед запуском.

N=236106, 86.457s / 16.660s in PARI
N=63235, 199.433s / 4.602s in PARI
N=236106, 119.624s / 16.520s in PARI

[Dmitriy40]

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

N=236106, 86.457s / 16.660s in PARI
N=63235, 199.433s / 4.602s in PARI
N=236106, 119.624s / 16.520s in PARI

Спасибо, вот это как раз ожидаемый результат. Отмечу что у меня разброс меньше, и третья чуть быстрее первой (в пределах 10%). Отсюда делаю вывод что для Вас надо ещё уменьшать размер .exe, даже за счёт скорости (по моим измерениям, у Вас должно быть наоборот быстрее), но сохраняя при этом качество фильтрации. Процентов 10 наверное получится выиграть. Но это не прямо сейчас.

[Yadryara]

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

241932253046233642976664116549337789441945: 48, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, valids=14
Т.е. теперь нижний порог уже не 13, а 14.

Народ, на всякий случай прошу перепроверить.

Ура. Проверено. Вы к Карлосу заглядывали?

https://www.primepuzzles.net/problems/prob_020.htm

[Dmitriy40]

Нет не заглядывал. Там же старьё, цепочки из 10, 11, 12 чисел с 12-ю делителями, а тут в теме неоднократно приводились цепочки с 13-ю числами. Да и в статье в архиве от 2018г она тоже приведена.