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

[Yadryara]

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

Отзеркаливание в моем понимании это ... отзеркаливание, то есть прочтение справа налево.
Но, судя по Вашему вопросу, Вы вкладываете в это слово какой-то другой смысл.

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

То есть если попросту отпалиндромить все числа, будет совершенно легальный паттерн? Тогда нет проблем.

-- 16.10.2025, 13:08 --

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

Yadryara
Вероятность найти цепочку (для текущей схемы расчета), если считать все $9!$ шаблонов:

На слово не верю, а проверять пока лень. И на будущее просьба:

Не использовать сторонние ресурсы, а постить инфу прямо на форуме, например, через TikZ или [code][/code].

[Dmitriy40]

У меня за ночь 9ч посчиталось с ускорителем 400 кругов паттерна M48n21p3 (3-0-13-5) по 1e9 i (относительно lcm(v)=2.9576e43) в каждом, примерно до 1.183e55, наиболее длинные лишь 7шт valids=16.
Т.е. глубокий поиск по одному паттерну невыгоден. Что было и так ясно, но прямая проверка интереснее.

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

Есть подозрение, что тут имеем "аномалию", как с тройкой - более одного запрещенного остатка для какого-нибудь простого.
Это как-то можно проверить?

Так ведь эта проверка и есть длинный if для чисел до 59 и следующий цикл с T[],P[] для чисел до 523. И понятно что для чисел выше длины паттерна запрещённых остатков не может быть больше проверяемых мест (потому что на остальные места такие простые попадать могут).
Выходит это уже проверено и использовано. Соответственно вопрос непонятен.

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

Пока на малой статистике: количество проверок $i_m$ и число, до куда надо считать ($N$) - больше в 5.3 - 5.4 раза, чем для 3p.

Спасибо! Получается даже с ускорителем считать 4-0-12-5 невыгодно.

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

Вот именно об этом я и писал недавно:

Да, я тоже это вспомнил с Ваших слов, но проверка в свете новых видений ускорения PARI кода не помешала.

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

Демис, на PARI программа уже есть, 3-й день подряд считаю.

Я считаю она нуждается в доработке:
1. Сделать границы перебора в терминах n, я показывал как. Только уточнить формулы, проверить надо ли учитывать ip и p1 или оно корректно съедается округлением (и лучше задать на пару shag больше чем что-то пропустить).
2. Сделать запись цепочек в файл лога (оставив самые длинные и на экран тоже), есть же команда write в комплект к print, ей и пользоваться. Тогда на экран можно показывать дополнительную информацию, например прогресс и тот же ETA (мегаполезно!).
3. Сделать сохранение решения в отдельный файл с "громким" именем, типа M48n21-FOUND!.txt.
4. Возможно сделать многопоточную версию, под gppthread64-2-17-2.exe (можно регулировать количество потоков), хотя у меня оно и медленнее нескольких gp64-2-17-2.exe, но может кому-то удобнее считать одной программой многопоточно пусть даже и медленнее возможного. Правда parforperm нету, но по потокам можно побить и по другому, например parforeach, либо все 9! перестановок сохранить в вектор и parfor по нему идти вместо parforperm. Стоит добавить и более корректную остановку всех потоков при обнаружении решения.

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

Для $D(48,21)$ типовые вероятности для одного места при некоторых больших $N$:

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

Вероятность найти цепочку (для текущей схемы расчета), если считать все $9!$ шаблонов:

Тоже спасибо, наконец данные для оценки.

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

Остаются открытыми вопросы:
1. А существуют ли паттерны типов "4-0-13-4 (9)" и "5-0-13-3 (9)"?
2. А может быть, для четырех и пяти простых существуют ещё лучшие паттерны, с ещё большим количеством $pqr$?

Тоже пороюсь.

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

По-хорошему, надо бы:
1. Построить pcoul'ом полную систему паттернов.

Нереально: вывод паттернов с тремя и более проверяемыми местами у меня занял больше суток и под гиг текста. А паттернов 5-0 среди них лишь каждый 6000-й. Паттерны 4-0 каждый 66-й. Паттерны 3-0 каждый 15-й. Правда какие были ещё условия фильтрации не уверен.
Т.е. сделать конечно можно и нужно, но не pcoul, а сразу из генератора получать лишь нужные типы паттернов, не сильно сложно, вопрос какие типы нужны.

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

Выбор был между 20-ю, 32-я и 40-а.

А использовать ускорители готовы или комп не позволяет (может там и не винда)?

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

И не думаю, что ошибсяя на потора порядка (хотя для этого паттерна статистика не собиралась).

Это не полтора порядка, а лишь вдвое, 0.3 порядка.

-- 16.10.2025, 14:49 --

Для ускорения программ поиска теперь нужен как можно более быстрый тест простоты (даже не факторизации), пусть даже часто ошибающийся, ispseudoprime (и Mod(2,p)^p-1) слишком медленны. Попытаться на асме написать быстрый вариант Mod()^p конкретно под числа до 1e57 что ли ... Но моя прикидка где-то выше медленнее на порядок чем ispseudoprime, значит надо использовать продвинутые методы умножения по модулю, и то не факт что получится сильно быстрее.
Основное отсеивание происходит на первом же factor(,2^15) для непроверяемых ускорителем мест. И думаю тормозит при этом именно ispseudoprime для анализа остатка после factor. Если бы ispseudoprime сделать на асме, то ускорителем можно будет проверять и непроверяемые места (pq, pqr, pqrs) ровно как это делается на PARI и что в основном всё и отсеивает.

[EUgeneUS]

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

У меня за ночь 9ч посчиталось с ускорителем 400 кругов паттерна M48n21p3 (3-0-13-5) по 1e9 i (относительно lcm(v)=2.9576e43) в каждом, примерно до 1.183e55, наиболее длинные лишь 7шт valids=16.
Т.е. глубокий поиск по одному паттерну невыгоден. Что было и так ясно, но прямая проверка интереснее.

У меня есть наглядные графики, как количество паттернов (одинакового типа) влияет на
а) количество общих проверок.
б) до куда нужно считать.
Тренды выше указывал, но на графиках нагляднее. Выложу несколько позже.

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

Спасибо! Получается даже с ускорителем считать 4-0-12-5 невыгодно.

Это ещё уточню по более полной статистике для 4-0-12-5. Но чудес там не будет, точно.

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

а сразу из генератора получать лишь нужные типы паттернов, не сильно сложно, вопрос какие типы нужны.

1.1. С минимальным количеством простых. (3 - минимальное?).
1.2. Плюс 1 и плюс 2 простых к минимальному. Чтобы было с чем сравнить.
3. Для каждого количества простых (в порядке приоритета):
а) минимальный LCM (после расстановки необязательных простых в квадрате!)
б) максимальное количество pqr, за счет pqrs и pq
в) максимизируем pqrs за счет pq (они примерно равнозначны, но pqrs немного лучше).

[Yadryara]

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

Т.е. глубокий поиск по одному паттерну невыгоден.

Учитывая, что многие люди не понимают о чём речь идёт, такая терминология может людей только запутывать. Вот vicvolf, например, опять не понял о чём речь, да и Демис, уж не знаю, понимает ли теперь.

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

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

2. Сделать запись цепочек в файл лога (оставив самые длинные и на экран тоже), есть же команда write в комплект к print, ей и пользоваться.

Конечно я это уже сделал. И другие исправления внёс. Уже около тысячи приближений найдено, куда же без логов-то... И я же ведь написал имя файла в который будет 9-й комплект записываться.

Всё никак не проанализирую статистику: и ленюсь, и жду когда досчитается оставшееся.

Да, думал про многопоточную версию, но пока отложил. Я так понял, что Ваши (72?) асм-проги уже совсем скоро на помощь придут.

[EUgeneUS]

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

Так ведь эта проверка и есть длинный if для чисел до 59 и следующий цикл с T[],P[] для чисел до 523. И понятно что для чисел выше длины паттерна запрещённых остатков не может быть больше проверяемых мест (потому что на остальные места такие простые попадать могут).
Выходит это уже проверено и использовано. Соответственно вопрос непонятен.

Объясню подробнее.
$b_1$ - это коэффициент во сколько раз вероятнее найти простое после решета Эратосфена, чем в "нетронутом" $\mathbb{N}$.

В общем виде считается он так: $1/b_1 = \prod\limits_{i}^{} (1-1/p_i)$, где $p_i$ - простые, которые используются в решете.
Если считаем по всем простым до $59$, то получаем: $1/b_1 = 0.131587352, b_1 = 7.599514588$

Применение паттерна - это по сути и есть применение решета Эратосфена, так как после применения паттерна не должно быть ни одного лишнего простого множителя, из простых, используемых в паттерне. Ни в какой позиции цепочки.
Это гарантируется (должно гарантироваться):
1. Собственно паттерном.
2. 6*lcm (для 2 и 3).
3. Длинным ифом.
4. А про все проверки после большого ифа забываем - это важно.

Причем $b_1$ от места в цепочке не зависит.

А на практике со сбором статистики $b_1$ получается всё время меньше, если усреднить по всем 21 позициям. Не намного, в третьем знаке. Но меньше.
Почему?
Гипотеза: для некоторых простых (интересуют только до $59$ включительно) существует более одного "плохого" остатка (как для тройки, например, где их часто бывает два), а в длинном ифе проверятся только один.
Других гипотез, чтобы объяснить эту аномалию у меня нет.

[DemISdx]

(бла-бла-бла)

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

да и Демис, уж не знаю, понимает ли теперь.

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

(бла-бла-бла v.2.0)

И кстати насчет:

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

Дважды пытался ответить.
Оба раза ответ загадочным образом исчез

Тоже аналогичное было (надеюсь, что аналогичное).
Но, как мне кажется, это именно из-за появившихся новых постов.
Просто обратите внимание, там сообщение системы при этом выскакивает, что новое сообщение уже было опубликовано.
Сам текст, в редакторе, при этом сохраняется.
У меня раза с третьего только мое сообщение "пролезло".

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

Могу выслать 9-й комплект Вам

Высылайте. Попробую. Ресурсов не много, но что-то есть...

[EUgeneUS]

Обещанные графики.
Это для 3-х простых.
Вроде бы всё из картинок понятно, если что - спрашивайте

[Huz]

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

2. Не нашел в архивах (после чисток ) виндовую версию pcoul.

You can always find it via https://github.com/hvds/divrep, check "Releases" half way down on the right hand side.

I'm not sure exactly what you need for your Excel file, but if you send me an email with the definition I suspect I can easily provide it as a CSV file. (Keeping up with the forum via translation is hard work.)