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

[EUgeneUS]

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

А самые перспективные паттерны содержат не 3 и не 4, а 7 проверяемых мест. Таких всего 80 штук из 1044.

Из них 24 содержат $(11^5, 7^5)$, а их уважаемый Dmitriy40 посчитал все (в том числе, и исправленными ускорителями).
Все оставшиеся перекрываются паттернами с меньшим количеством проверяемых чисел.

Кстати, таки сделал матчинг идентификаторов паттернов Хуго и Дмитрия. Вечером выложу файл на гуглодиск.

[EUgeneUS]

Закончил анализ паттернов на перекрытие.
Если объединять паттерны невзирая на уменьшение проверяемых чисел, то получается 578 штук, из них 358 не объединяются ни с кем.
Если объединять паттерны избегая уменьшения проверяемых чисел, то получается 636 штук, из них 420 не объединяются ни с кем.

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

Все оставшиеся перекрываются паттернами с меньшим количеством проверяемых чисел.

UPD: если избегать уменьшения проверямых чисел, то появляются восемь паттеттрнов с 7-ю проверяемыми числами и $(11^2, 7^5)$, которые нужно будет посчитать.

[Yadryara]

Всё-таки у нас сейчас царит такой хаос, что некоторые паттерны полностью обсчитаны уже по три раза.

Демис прислал отчёт. Спасибо.

Насколько я понял, по списку Дмитрия сверху вниз проверялись все паттерны подряд.

Самый маленький шаг в проверяемых Демисом паттернах: 3880800. Это хорошо. Ведь не только быстрые и/или перспективные надо считать.

Конечно, нотация Hugo короче, но нотация Дмитрия понятнее. Предлагаю всё-таки составить биекцию и считать нотацию Дмитрия основной.

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

Кстати, таки сделал матчинг идентификаторов паттернов Хуго и Дмитрия. Вечером выложу файл на гуглодиск.

А почему не выложить прямо в теме? Если это именно имена паттернов, а не сами паттерны, то должны поместиться.

[Yadryara]

Dmitriy40, а вот эта десяточка у Вас есть?

LCM42688800-1278841-8:402913432496226575641: 4, 16, 8, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 16, 16, valids=10, maxlen=10

[EUgeneUS]

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

Всё-таки у нас сейчас царит такой хаос,

Источники хаоса вижу в следующем:
1. Часть коллег берет номера паттернов по нумерации уважамого Хуго (или Хуго их выделяет для расчета), но в эти номера никак не отражают свойства паттернов.
2. Отсутствует стратегия расчета, которая учитывала бы свойства паттернов.

У с учетом не нулевой вероятности найти цепочку с меньшими числами такая стратегия нужна.
Кроме того, остаётся откртым вопрос об объединении паттернов с пересечениями. Это может дать экономию по времени в 1.5-2 раза.

На всякий случай, под "программой Hugo" понимается код уважаемого Hugo, не важно под какую систему скомпилированный (под Windows или под *nix).

-- 07.11.2022, 13:26 --

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

Dmitriy40, а вот эта десяточка у Вас есть?

Эта десятка у меня могла бы найтись, но я считаю 20 таких паттернов только до 2,5е20

[Yadryara]

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

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

Именно поэтому я и предложил взять за основу нумерацию Дмитрия.

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

Кроме того, остаётся откртым вопрос об объединении паттернов с пересечениями.

Давайте хотя бы биекцию сделаем. Например:

1. 554400-31545-4 — ​​​​​​​b085
...
... 14642258400-2398005945-4 — ​​​​​​​b101
...
1044. 19488845930400-18637583330169-6 — ​​​​​​​b ?

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

Эта десятка у меня могла бы найтись, но я считаю 20 таких паттернов только до 2,5е20

Приплыли. Вы с Демисом одно и то же считаете. Хотя и не совсем.

[EUgeneUS]

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

Давайте хотя бы биекцию сделаем. Например:

Имейте терпение. Несколько часов и всё будет

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

19488845930400-18637583330169-6 — ​​​​​​​b ?

b1189

[Dmitriy40]

Хех, 50ч говорите ... Лог проверки его же моими ускорителями с однократным перебором простых (с сокращениями, время нарастающим итогом):

b1850: [45,2,1,12,49,50,363,32,1,18,5]
b1850-13 end, time: 4122.469s
b1850-17 end, time: 6144.172s
b1850-19:287834780609527920345: 12, 16, 12, 12, 12, 12, 12, 12, 12, 12, 12,192, 32, 16,  2,  valids=10, maxlen=9
b1850-19 end, time: 7646.955s
b1850-23:3476367315695605545945: 12,  8, 12, 12, 12, 12, 12, 12, 12, 12, 12, 24, 16, 16,  4,  valids=10, maxlen=9
b1850-23 end, time: 8606.041s
b1850-29:2916461522504711241945: 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 16, 96,128, 16, 24,  valids=10, maxlen=10
b1850-29 end, time: 9165.333s
b1850-61:2605102794736967832345: 12, 16, 12, 12, 12, 12, 12, 12, 12, 12, 12, 48, 16, 16, 64,  valids=10, maxlen=9
b1850-61 end, time: 11045.913s
b1850-83:3353090009360291707545: 12, 24, 12, 12, 12, 12, 12, 12, 12, 12, 12, 48, 24,128, 16,  valids=10, maxlen=9
b1850-83 end, time: 11419.058s
b1850-27919 end, time: 13252.135s
b1850-27941 end, time: 13252.478s
b1850-27943 end, time: 13252.822s
AVX2: up to 27943:6088, time: 13252.822s
PARI: up to 15305333:986120, time: 15894.893s
ALL:  up to 6726727940:1864338, time: 16244.671s

Очевидно для нескольких первых простых надо было запускать и второй перебор, было бы быстрее.
Числа 6088, 986120, 1864338 это сколько штук простых пришлось реально проверять до указанного перед ними простого. Видно что подходящих начальных чисел очень мало и полный перебор без линейной проверки занял примерно те самые расчётные 5 минут.

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

А самые перспективные паттерны содержат не 3 и не 4, а 7 проверяемых мест. Таких всего 80 штук из 1044.

Они быстрые в проверке, но вот перспективные ли ... Мне более перспективными кажутся паттерны с $11^2 7^2$ (шаг 42688800), их по верхам проверил все. И среди них них нашлись 1 уже известная одиннадцатка и 62 непрерывные десятки (и ещё 5шт выше 1e22).

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

Dmitriy40, сколько таких паттернов-7 Вы уже полностью проверили и сколько 10-к(обычных и непрерывных) нашлось?

Полностью проверены только паттерны с $11^5 7^5$ и $11^5 7^2$ (шаги 19488845930400 и 56818792800), сколько там было с 7 местами не знаю, они сократились при оптимизации списка паттернов (для второго шага, первый проверился весь за пару минут). Десяток не найдено, девяток 6шт, все с $11^5 7^2$ (речь разумеется о непрерывных).

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

Dmitriy40, а вот эта десяточка у Вас есть?
LCM42688800-1278841-8:402913432496226575641: 4, 16, 8, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 16, 16, valids=10, maxlen=10

Нету: я проверял подстановкой малых простых в квадрате на место с 5 и малых простых в квадрате на место с 3 (или с 2 если первого нет, или с 1 если и 2 нет). Эта же имеет на месте с 3 не квадрат малого простого, потому и не нашлась.
В этом паттерне нашёл лишь 5шт девяток.

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

Всё-таки у нас сейчас царит такой хаос, что некоторые паттерны полностью обсчитаны уже по три раза.

А разве есть информация какие паттерны проверил сам Hugo? Вроде выше его спрашивали, он ответил, но как-то слишком коротко (хотя может я не вник), мол проверены лишь несколько десятков паттернов, но я подозреваю что проверены например все с $11^2 7^2$ потому что известная минимальная 11-ка именно такого формата (ну и ещё потому что у меня среди более 60 десяток не нашлось меньшей 11-ки, что однако не означает что её там нет).

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

-- 07.11.2022, 14:34 --

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

Эти 8 паттернов из серии 554400-3. А я всё-таки часов 16 считал один паттерн из серии 554400-4.

Указывайте пожалуйста что последняя цифра это количество проверяемых мест, а не часть моего обозначения паттерна, например так: 554400-n4 (и можно без дефиса 554400n4 если так жаждете экономить символы).
Чтобы не указывать большие шаги можно указывать степени 7 и 11, например 7p511p2n4. Совсем без букв тоже можно, но число станет малопонятным, ИМХО. Или даже 52n4.

[Yadryara]

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

Указывайте пожалуйста что последняя цифра это количество проверяемых мест, а не часть моего обозначения паттерна, например так: 554400-n4 (и можно без дефиса 554400n4 если так жаждете экономить символы).

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

1. 1-31545-4 — ​​​​​​​b085
...
... 7-2398005945-4 — ​​​​​​​b101
...
1044. 9-18637583330169-6 — ​​​​​​​b1189

Такой список уже имеет шанс поместиться в оффтопе. Без всяких Гуглодисков.

[Dmitriy40]

Номера - плохо! Неизвестно по какому они списку (у меня их много и по разному сортированных). Уж проще тогда полностью перейти на обозначения Hugo (когда будет биекция их с моими).

[EUgeneUS]

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

Полностью проверены только паттерны с $11^5 7^5$ и $11^5 7^2$ (шаги 19488845930400 и 56818792800), сколько там было с 7 местами не знаю, они сократились при оптимизации списка паттернов (для второго шага, первый проверился весь за пару минут).

Правильно ли понимаю, что
а) это перепроверено на исправленных ускорителях (про $11^5 7^5$ видел сообщение о перепроверке, а по $11^5 7^2$ или не было сообщения, или я пропустил )
б) на данный момент у Вас нет планов считать линейным перебором другие паттерны с большими LCM?

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

Хех, 50ч говорите ...

А можно ли оценить, сколько будет считаться этим методом какой-то из наихудших паттернов (с наименьшим LCM и $n=3$)?

-- 07.11.2022, 15:29 --

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

Такой список уже имеет шанс поместиться в оффтопе. Без всяких Гуглодисков.

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

[Dmitriy40]

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

Правильно ли понимаю, что
а) это перепроверено на исправленных ускорителях (про $11^5 7^5$ видел сообщение о перепроверке, а по $11^5 7^2$ или не было сообщения, или я пропустил )

Правильно.

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

б) на данный момент у Вас нет планов считать линейным перебором другие паттерны с большими LCM?

Да. И думаю Demis их уже многие проверил, надо посмотреть в логах докуда он добрался и как проверял.

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

А можно ли оценить, сколько будет считаться этим методом какой-то из наихудших паттернов (с наименьшим LCM и $n=3$)?

Можно. Перебор простых до сколько-то там миллиардов займёт от 5 до 35 минут. Это константа и зависит в какое место паттерна подставляем квадрат простого (пустое или с простым в первой степени).
Перебор ускорителями будет выполнятся для шагов менее 1e22/554400/3e5=6e10 (считаю что если количество попыток менее 3e5, то PARI справится быстрее ускорителя за счёт 0.3с на компиляцию последнего), такой шаг получается с числом $\sqrt{10^{22}/55400/6\times10^{10}}=548$, до которого 101 простое (но первые 5 уже расставлены). Время компиляции 96 ускорителей меньше минуты. Скорость проверки ускорителем с 4-мя проверяемыми местами составит скажем 4e7/с. Общее количество попыток с простыми от 13 до 548 равно $\frac{10^{22}}{554400}\sum\limits_{11<p<548}(1/p^2)=1.8\cdot10^{16}\times0.0222=4\cdot10^{14}$, на них потребуется 4e14/4e7=1e7c или 116 дней.
Время проверки в PARI простых от 548 до $\sqrt{10^{22}/554400}=1.343\cdot10^8$ (пока шаг паттерна меньше порога и надо проверять больше одного начального числа) со скоростью 1e6/c составит $\frac{1}{10^6}\frac{10^{22}}{554400}\sum\limits_{548<p<1.343\cdot10^8}(1/p^2)=1.8\cdot10^{10}\times0.00025=4.5\cdot10^6$ секунд или 52 дня.
Итого 168 дней.

Скорость AVX2 ускорителя для n=5+1 (5 мест уже есть в паттерне, одно добавляем перебором) можно взять 4e8, всего в 10 раз быстрее, т.е. 116 дней могут сократиться раз в 10, до 12 дней, но 52 дня так и останутся, ну и общий итог сократится до примерно 64 дней. Это для лучшего паттерна с шагом 554400.

Оценить время для двухкратной подстановки простых в квадратах сложнее, потом как-нибудь займусь (идея та же: пока время линейной проверки превышает расчётное время с перебором дополнительного простого (не забываем что шаг уже будет в $p^2$ раз больше) используем последнее).

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

Такой-то имеет. Но как Вы по такому списку будете выбирать паттерны по LCM и-или по количеству проверямых чисел? Например.

По отдельному файлу биекции между bXXXX и LCMX-X-X можно выбрать нужные bXXXX (командой findstr и for /f для выделения лишь bXXXX), а потом уже из общего списка выбрать нужные bXXXX (той же командой findstr, она умеет брать список искомых строк из файла или потока ввода, ключ /G). Так что при наличии файла с биекцией это не проблема.
Кстати слова в цитате не мои.

[EUgeneUS]

Файл с биекцией на гуглодиске.

Колонки:
От A до F - данные Хуго. (Паттерны выровнены по 32p)
От Q до U - служебные для расчета New-ID по данным Хуго
V - New-ID по данным Хуго
W - New-ID по данным Дмитрия
X - проверка корректности биекции
От Y до AT - данные Дмитрия (по его программе расчета паттернов и после удаления дублей)
AC ("Dmitriy40-ID-2") - это отдельно рассчитанный идентификатор, который можно и нужно рассматривать, как идентификатор группы перекрывающихся паттернов.
От AU до AY - служебные для расчета New-ID по данным Дмитрия
От AY до BF - анализ перекрывающихся паттернов (об этом чуть позже)

-- 07.11.2022, 16:39 --

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

Да. И думаю Demis их уже многие проверил, надо посмотреть в логах докуда он добрался и как проверял.

А где можно посмотреть, что Демис уже проверил и что проверяет в данный момент?

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

Кстати слова в цитате не мои.

Приношу извинения Как обычно - не под тем постом нажал кнопку "Цитата". Уже не успел поправить.

-- 07.11.2022, 16:41 --

Биекция проводилась по "New-ID", нотация которого описывалась ранее. Но не настаиваю на её использовании.

[Yadryara]

Про обозначения спорить неохота. Как Дмитрию удобно, пусть так и делает.

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

Полностью проверены только паттерны с $11^5 7^5$ и $11^5 7^2$ (шаги 19488845930400 и 56818792800)

То есть $58+96 = 154$ паттерна проверено. Осталось 7 различных меньших шагов.

Как обстоят дела с паттернами со следующим по величине шагом 14642258400?

Да, я сам ещё раз посмотрю логи Демиса. Я имею в виду проверяли ли паттерны с этим шагом Дмитрий и Евгений?

[EUgeneUS]

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

Я имею в виду проверяли ли паттерны с этим шагом Дмитрий и Евгений?

Я - нет. Но планирую (программой Хуго)