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

[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.)

[Dmitriy40]

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

1.1. С минимальным количеством простых. (3 - минимальное?).

С чего бы? Есть и с нулём мест $p$. Например вот 0-6-7-8(8) (в скобках сколько квадратов простых требуется):
v=[ 9, 50, 49, 12, 289, 338, 1815, 2888, 1, 126, 1, 20, 3, 2, 1, 96, 35, 22, 117, 4, 1]
И с одним и с двумя.

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

а) минимальный LCM (после расстановки необязательных простых в квадрате!)

При сохранении количества расставляемых квадратов простых lcm остаётся одинаковым. Именно поэтому я их не учитываю в "базовых" паттернах. А при изменении количества легко пересчитывается умножением/делением на квадрат простого(-ых).

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

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

Согласен, в горы.
Просто "поиск в глубину" и "поиск в ширину" - устоявшая терминология у программистов (например говорят глубина рекурсии вместо высоты). И я постоянно сбиваюсь на привычное.

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

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

Не сказал бы: 9! программ я могу накомпилить хоть сейчас, но это занятие на неделю и больше. А вот насчёт объединения я пока лишь раздумываю.
Да и ускорение 6 раз мне как-то не нравится, хочется больше. И над этим думаю. Но толку пока нет.

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

Гипотеза: для некоторых простых (интересуют только до $59$ включительно) существует более одного "плохого" остатка (как для тройки, например, где их часто бывает два), а в длинном ифе проверятся только один.

Ну так проверьте её! Я же выкладывал работающий код для подсчёта остатков всех 21 числа (не обращая внимания на комменты справа от вектора), меняете mm на нужное простое и перезапускаете и смотрите какие остатки будут на всех местах паттерна после деления на v[j]. Где будут нули там число оказалось кратным mm.

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

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

Что-то цифры более оптимистичные: для i (до длинного if) с левого графика с P>0.95 (серая линия) на один паттерн надо порядка 2e15 штук (стоит сетку делать почаще), при том что 1e9 штук у меня в одном потоке с ускорителем считаются 85с, значит на все 2e15 надо 2e15/1e9*85с=5.4 года. В один поток. Вместо полсотни лет по предыдущей оценке, разница заметно больше 6-ти кратной от применения ускорителя.

А 1e15 попыток i будет достаточно при примерно 400 паттернах, которые будут проверяться очевидно в 400 раз медленнее одного, а объём проверок упал лишь вдвое, т.е. время вырастет в 200 раз?! Раньше говорили выгоднее больше паттернов, а тут что вижу ...

-- 16.10.2025, 17:08 --

Huz
The latest version 2023-04-17 15:35 I know of is missing there.
There was also a version on 2023-04-16 13:07, which is also missing.

[DemISdx]

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

Кстати, подоспели еще два числа. Для YAFU совсем пустяковые.
Тем более, что если одно разложится как надо, другое можно не трогать (они для одного и того же $k$)
(2 prime factors wanted)
Код:
38804...88137 (136 digits) = pq?

Готово:

(Результат по 38804...)

NFS elapsed time = 21899.7505 seconds.
Total factoring time = 21900.1487 seconds


***factors found***
P60 = 567603168432476980091953008703632841603775561512865720516291
P76 = 6836483990413877127279034790983327369712289266086653351276391266794364495107

***factorization:***
3880409973896820239227497169313840857498544480513383386846750680906144024741982113907070533030961378371860775088753842277017271583288137=567603168432476980091953008703632841603775561512865720516291*6836483990413877127279034790983327369712289266086653351276391266794364495107

[EUgeneUS]

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

А 1e15 попыток i будет достаточно при примерно 400 паттернах, которые будут проверяться очевидно в 400 раз медленнее одного, а объём проверок упал лишь вдвое, т.е. время вырастет в 200 раз?! Раньше говорили выгоднее больше паттернов, а тут что вижу ...

На графиках $i$ - суммарное по всем паттернам. То есть $i$ для одного паттерна умножить на количество паттернов.

-- 16.10.2025, 18:08 --

Таблица с сравнением паттернов.
Вместо 300000 считал для 9!, поэтому тут чуть лучше стало.
Остальное ожидаемо.
За кучи нулей извините, так экспорт в csv в OpenOffice работает.

pat - количество паттернов
i_m/pat - количество итераций на паттерн
i_m all - количество итераций суммарное (на все паттерны)
n_all - количество кандидатов после длинного ифа
N - до куда считать
P(1) - вероятность найти цепочку в районе N за одну проверку
P(win) - вероятность найти цепочку при выполнении такого объема. Выводилась в 0.95

(Оффтоп)

Тип паттерна,pat,i_m/pat,i_m all,n_all,N,P(1),P(win)
4-0-12-5 (9),1,8161000000000000,8161000000000000,3264400000000000,1448221300734020000000000000000000000000000000000000000000000,"9,17759691777637E-016","0,9500101222"
4-0-12-5 (9),10,633500000000000,6335000000000000,2534000000000000,112418599928318000000000000000000000000000000000000000000000,"1,1827923874941E-015","0,9500731283"
4-0-12-5 (9),100,48890000000000,4889000000000000,1955600000000000,8675841121539900000000000000000000000000000000000000000000,"1,53201423886432E-015","0,9500137367"
4-0-12-5 (9),1000,3756000000000,3756000000000000,1502400000000000,666526063663536000000000000000000000000000000000000000000,"1,99442381589319E-015","0,9500344915"
4-0-12-5 (9),10000,287000000000,2870000000000000,1148000000000000,50929973448330000000000000000000000000000000000000000000,"2,61034843974699E-015","0,9500473643"
4-0-12-5 (9),100000,21800000000,2180000000000000,872000000000000,3868548505962520000000000000000000000000000000000000000,"3,43577015707744E-015","0,9500129635"
4-0-12-5 (9),362880,5140000000,1865203200000000,746081280000000,912125657018921000000000000000000000000000000000000000,"4,01694325371926E-015","0,9500616565"
4-0-12-5 (9),1000000,1647000000,1647000000000000,658800000000000,292270614320242000000000000000000000000000000000000000,"4,54849768174992E-015","0,9500408832"
4-0-12-5 (9),10000000,123700000,1237000000000000,494800000000000,21951351067194400000000000000000000000000000000000000,"6,05843420851055E-015","0,9500989506"
4-0-12-5 (9),100000000,9225000,922500000000000,369000000000000,1637035002799540000000000000000000000000000000000000,"8,12220875609216E-015","0,9500680915"
3-0-13-5 (9),1,1407000000000000,1407000000000000,562800000000000,249681089343566000000000000000000000000000000000000000000000,"5,32446624526591E-015","0,9500438472"
3-0-13-5 (9),10,109800000000000,1098000000000000,439200000000000,19484707611894900000000000000000000000000000000000000000000,"6,82302015777054E-015","0,950046887"
3-0-13-5 (9),100,8530000000000,853000000000000,341200000000000,1513702695177160000000000000000000000000000000000000000000,"8,78504394103902E-015","0,9500861616"
3-0-13-5 (9),1000,659000000000,659000000000000,263600000000000,116943736951766000000000000000000000000000000000000000000,"1,13684807516898E-014","0,9500499377"
3-0-13-5 (9),10000,50650000000,506500000000000,202600000000000,8988164313420190000000000000000000000000000000000000000,"1,47883891391905E-014","0,9500197644"
3-0-13-5 (9),100000,3874000000,387400000000000,154960000000000,687465923132932000000000000000000000000000000000000000,"1,93408752478181E-014","0,9500664436"
3-0-13-5 (9),362880,916000000,332398080000000,132959232000000,162550029544987000000000000000000000000000000000000000,"2,25329766617648E-014","0,9500117485"
3-0-13-5 (9),1000000,294500000,294500000000000,117800000000000,52260905858406000000000000000000000000000000000000000,"2,54402577361125E-014","0,9500564725"
3-0-13-5 (9),10000000,22250000,222500000000000,89000000000000,3948413624018530000000000000000000000000000000000000,"3,3663909561842E-014","0,9500177807"
3-0-13-5 (9),100000000,1672000,167200000000000,66880000000000,296716782148102000000000000000000000000000000000000,"4,48205834852046E-014","0,9500933303"

[Dmitriy40]

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

На графиках $i$ - суммарное по всем паттернам.

А, другое дело.
Выходит сделав 9! ускорителей я на сервере в 20 эквивалентных потоков (реальных 64 на 32 ядрах) справляюсь месяца за 4 с P>0.95. В принципе доступно. Даже без дописываний асм программы.

[EUgeneUS]

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

Выходит сделав 9! ускорителей я на сервере в 20 эквивалентных потоков (реальных 64 на 32 ядрах) справляюсь месяца за 4 с P>0.95.

При этом все 9! паттернов должны досчитать до $1.63 \cdot 10^{53}$ (это из уточненной таблицы).

-- 16.10.2025, 18:24 --

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

Ну так проверьте её! Я же выкладывал работающий код
для подсчёта остатков всех 21 числа

Не сработал у меня почему-то. Вектора в результате все нулевые
С этим завтра уже.

-- 16.10.2025, 18:25 --

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

v=[ 9, 50, 49, 12, 289, 338, 1815, 2888, 1, 126, 1, 20, 3, 2, 1, 96, 35, 22, 117, 4, 1]

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

[Dmitriy40]

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

Надо статистику на него напустить. А как, если там нет простых?
В коде же всё на "перебираемое простое" завязано..

Перебирать не p, а n (начало цепочки). По формуле n=n0+i*lcm(v). Ну или сразу по lcm(v)*6 если допустимый остаток по модулю 6 будет лишь один.
Хм, ни одного, всегда где-то встречается $3 \pmod 6$, выходит что-то всегда делится на 3, беда ... А может и нет, это места с 9, можно на любое из них поставить 27 или 243 (lcm конечно увеличится) и тогда разрешёнными станут два остатка из трёх (или шести). Можно перебирать с шагом lcm(v)*2, а запрещённый остаток по 3 учитывать длинным if.
Только поиск такого паттерна будет супермедленным - нет быстрых isprime, придётся сразу запускать медленные factor. Но как концептуальная возможность ...

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

Не сработал у меня почему-то. Вектора в результате все нулевые

Опять моя невнимательность, там lcm(v) не записалась в m, надо поправить строчку так:
print("lcm=",m=lcm(v));
У себя то поправил, а на форуме забыл. Поправил.