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

[wrest]

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

1. Оптимальность по первому критерию - это "функция" только свойств паттерна.
2. Конечно, более правильный, что ли, второй критерий. Но оптимальность по этому критерию - это "функция" не только свойств паттерна, но и программы поиска цепочек.

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

[Dmitriy40]

wrest в сообщении #1723308 писал(а):

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

А это может противоречить скорости нахождения (не перебора) цепочек: проще всего проверять цепочки с максимальным количеством мест p (только огромное простое и всё), проверка простоты быстрее факторизации, но такие паттерны дают намного большие lcm и потому резко падает вероятность обнаружить цепочку за фиксированное количество проверок. Т.е. такие паттерны оказываются не оптимальными. Зато отсекать такие цепочки - выгоднее всего.

При наличии проверок на простые до 2^20, проще отсекать цепочки имеющие только места p и pq, причём вторые должны иметь меньший делитель до 2^20 - тогда останется лишь isprime и всё, медленная факторизация не нужна. Тогда такие паттерны выгоднее чем с pqr и более - отсутствием факторизации.

[Yadryara]

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

Похоже, что именно поэтому у меня, при сравнении скоростей нахождения D(96,13) опять победила цепочка с одним простым. Не с нулём и не с двумя, а именно с одним.

[Yadryara]

И тогда уж статистику по 8 посчитанным длинам покажу здесь.

Кортеж           Серия    2^       Комплектов      Счёт     Найдено      Время     Скорость
                                    посчитано   от 0 до     D(96,L)     секунд     корт/сут
D(96,6)    0-1-5-0-0-2!   15   3!*4!*1     24      1e25        292         57       442611
D(96,7)    0-1-6-0-0-3!   16   2!*5!*1     48      1e27        100         51       169412
D(96,8)    1-0-7-0-0-3!   17   2!*6!*1*1  130      1e34        112        240        40320
D(96,9)    1-0-8-0-0-4!   17   2!*6!*1*1  130      1e37        108        461        20241
D(96,10)   1-0-9-0-0-4!   17   3!*7!*1*1  400      1e41        163       2722         5174
D(96,11)   1-0-A-0-0-5!   18   3!*7!*1*1  600      1e44        235       9816         2068
D(96,12)   0-0-C-0-0-5!   18   3!*7!       90      1e46        123      30612          347
D(96,13)   1-0-C-0-0-5!   18   3!*8!*1*1 1198      1e51       (139)     21583+1%       551 Э

А — 10
С — 12

L — длина кортежа

D(96,13) — 6-поточный счёт

Э — применялась экстраполяция, была посчитана 1/7 часть комплектов.

Если кто-то сомневается, вот 139 кортежей D(96,13). Начальное число, valids по полю и по полосе.

(139)

513010374173615737346742159125320990784157920663544     13   13
686999755860458669183870617905771923630923559217144     13   13
13737482433796329746088536764485237758012800612344     13   13
615511478243145299537992702240930831534428797745144     13   13
51170566526279212558591848400602313175786952599544     14   13
367810001296653320908117175339171352290160174897144     14   13
69869044133020692972076792187025883052929656829944     14   13
275065557340460092074232416644215486329359537149944     14   13
394131136561179299884186369193109188208340953700344     16   13
361757751260714160592163994901062745942790814820344     14   13
763915674045780953622700206406369632953035894679544     13   13
707720827155132986685736939803970498368665802033144     13   13
296111149301028892668070390924455564003607949821944     13   13
105880965145850868423957448035782891665606776829944     13   13
716524474605894676992817235621703189155421246359544     13   13
595988773700139997578036992021696426523621734807544     13   13
418284002591987558004283990148234660734605370161144     13   13
56509939169095393400072876691251190686596636669944     14   13
929726112169015003594299581315636490850706099505144     14   13
496413477711579911329515676599987057683111311972344     14   13
842667589222588775535820487880661829935193931671544     14   13
994973940489300350776360553749228594850272789809144     13   13
799551812655283375427766747891813327588267761764344     13   13
743089641103856795358726757669274063106188004657144     13   13
877930275690025542172038080196168204446801218967544     15   13
724340698652055509622713843463785696249546039293944     13   13
939759836547691035502429891740744661992818420221944     14   13
586435918328907236580912702736355897555264258557944     15   13
968750816523381119458786420609487408147497753905144     14   13
136752637402563270287441969001291861432166855165944     14   13
156444317208081904465260386021449649100624477489144     14   13
588225149533693859607968202426342851362290072061944     13   13
744654961853041499818830679869675892816002880612344     14   13
29416365777480311343326396672481897142499625469944     13   13
981347366861868651948366830747168187126636282263544     13   13
718420607304728853230475027701659075116984484247544     13   13
94559750008645209700241171166925873768344563812344     14   13
416344781234712637360865354077644015831934364260344     13   13
809354692018187567626756698699530100170310719793144     13   13
406945757269680623622799355481998164034336378980344     14   13
770509945834137942726810714243367928441142760957944     15   13
153207361008064614826565143809551977102054539057144     13   13
85950473223044131773969517057880472546995851261944     13   13
12959268002532792206303680827214467741104516605944     13   13
753337885506775985052366714187068053268632947300344     14   13
953352473130207539683863326918338928651001938327544     13   13
972410031383693542642712055793133268730594159511544     13   13
23068098844354483864490153437270537756800820631544     13   13
276563369260943550960627980655356838205436141668344     14   13
553691290140938490079450760834080475187316928817144     13   13
413586156587414137131044458211075694984906800433144     13   13
209426713144017952076925301346182377673630844413944     14   13
414013031792602729827542140667108724834795212797944     14   13
452544072067058542371133969786741246540275659773944     13   13
736180596528590129421221830724933086395165839255544     13   13
931276054069934418441279947511737257862264664983544     14   13
180404261944378417897243543320512536445504415229944     14   13
544278340768351833741063695555940112557707263281144     14   13
353034542362013767634148871985212760830242883991544     13   13
658378757103160208280233461217081999530877843044344     14   13
799349854694899698214686309092562406462070471063544     13   13
27263431619991691530458280045485198678215194724344     14   13
429009487804585296646107981460528243048464312829944     13   13
429009487804585296646107981460528243048464312829944     13   13
6566560009536746772839029526756379023381487613944     13   13
130244221177107089605176374835078337426479691261944     14   13
360243173342322291659898417498978669139943521175544     14   13
680337169067352803624934362191260684848712335869944     14   13
762286616971029326471791059541473806653346275223544     13   13
685412770154412382274530546605913392921992910129144     14   13
775125561837436337524225752919501399855788611581944     13   13
355982799537543708732367179424861131521145041303544     13   13
365384435678254214494954475218327800108384803735544     13   13
585113337014896162372074174921500077420400948836344     15   13
364551321015904058125087199026150488788613812529144     14   13
369201906463017841747786758797119284880269065725944     14   13
962512570523982663381739551633222077611696536369144     14   13
169135317443393206209774439216248747579087908759544     14   13
939154726732321973309998709707358408297697755543544     14   13
691510696807210206007549280692995340567719323236344     13   13
745580331873400727258087567219271338337880352663544     13   13
677218240711603304724411078345353555657662330161144     13   13
755263948233791351691448341476373184822168711473144     14   13
132965415923284571767341390020880767838935631767544     13   13
623066570902348629292105744817707484531457000753144     13   13
274247522561492900068996525185428858950997001623544     13   13
828269008453413860359337821644009024108130024343544     13   13
908433528363345344324974373198120276079034493437944     14   13
127712755440707342144640489528666270922257359869944     13   13
581037828712425612775118236642228416465027401725944     14   13
407170036713298542982505743184212303231435661207544     13   13
757669168534739201990194409713149981109906709399544     13   13
836410421542075300653778868950338423520412550551544     14   13
854123922285561605512195737931250106547280033687544     13   13
214364651558711958534174781088460913179745100797944     14   13
279412236153041152432655275935311613735327106967544     13   13
739747321065995189410336466282799187848844992407544     14   13
952550431637646500965418911882960016900986004068344     14   13
518661738915425670620840963293551291808848637847544     14   13
835366074444542901260600873452910010421871515953144     13   13
443499141898882772831951071681391835977652877924344     13   13
755970890469044474148407981073900663152261792049144     14   13
206528401074746139221420997637254276333136812849144     14   13
20242127036241756634895628148661231742295409764344     14   13
65866060701428765168916607942800642071091769137144     13   13
699398571875083896951288512769833817967121552893944     13   13
531394865705661341935263532491343622852294543255544     13   13
828623105207817235398803311253294120851906965911544     13   13
575589004485400591276826073335984483472178985572344     13   13
828739919272662817165134625204814207777924179761144     13   13
749400973585749926617702254421835114531576830564344     13   13
10398544039928862611130323538017576842296741373944     13   13
308529749115625209088437592604676693726357975345144     15   13
518114469801160258238827800065462575288538296420344     15   13
839782147630822198720611471079212126168449083492344     14   13
926870713524175322756746590196074288911116624996344     13   13
631152692638959081152781728011276196043548535805944     14   13
683100439492551190667864974399609462912753580951544     14   13
550170036453659917790185477357005648681921263716344     13   13
342261952118287837657559194734281349565271338084344     14   13
342261952118287837657559194734281349565271338084344     14   13
666203429876345380426139907629525576343569297917944     13   13
756477382437373434843794660739297522235139115825144     13   13
626493354693195171342716926508380498204425604093944     13   13
539437152536204324254155808937167979929751715940344     15   13
916448863919204213968697511058211060997080146737144     14   13
719503896624348938209162384162447203872656740964344     13   13
439237371441189158376192141438351541479144071063544     14   13
904303526209802362988681403959577981579709882161144     13   13
582784098325673461329569487021558781677578365540344     14   13
688115810473824072374520314271338249936521748375544     13   13
59794353265083887841364134750267568689343543089144     13   13
176592368119082267416614372306832173399205925783544     14   13
4170145804717265786878541258713337868326257559544     13   13
306662154676603741251336193107355063017636690839544     13   13
362968281722831824966113939262507823890128454756344     14   13
175287832356221083317420440738180039275376899991544     15   13
571266323516059811771337943351240388613869449521144     14   13
446462887634800154695433799626978993805647851415544     13   13

Кстати, возможно, для большей понятности надо укоротить обозначение серии и факториал переместить правее, тогда в соседнем столбце будет количество посчитанных не комплектов, а уже паттернов:

Кортеж         Серия             Паттернов   2^      Счёт     Найдено      Время     Скорость
                                 посчитано        от 0 до     D(96,L)     секунд     корт/сут
D(96,6)    0-1-5-0-0   2!*3!*4!*1       48   15      1e25        292         57       442611
D(96,7)    0-1-6-0-0   3!*2!*5!*1      288   16      1e27        100         51       169412
D(96,8)    1-0-7-0-0   3!*2!*6!*1*1    780   17      1e34        112        240        40320
D(96,9)    1-0-8-0-0   4!*2!*6!*1*1   3120   17      1e37        108        461        20241
D(96,10)   1-0-9-0-0   4!*3!*7!*1*1   9600   17      1e41        163       2722         5174
D(96,11)   1-0-A-0-0   5!*3!*7!*1*1  72000   18      1e44        235       9816         2068
D(96,12)   0-0-C-0-0   5!*3!*7!      10800   18      1e46        123      30612          347
D(96,13)   1-0-C-0-0   5!*3!*8!*1*1 143760   18      1e51       (139)     21583+1%       551 Э

[EUgeneUS]

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

А это может противоречить скорости нахождения (не перебора) цепочек: проще всего проверять цепочки с максимальным количеством мест p (только огромное простое и всё), проверка простоты быстрее факторизации, но такие паттерны дают намного большие lcm и потому резко падает вероятность обнаружить цепочку за фиксированное количество проверок. Т.е. такие паттерны оказываются не оптимальными. Зато отсекать такие цепочки - выгоднее всего.

Не совсем так. Для одного и того же lcm могут быть паттерны с различным значением "мест p". Так было, например, для $D(48,23)$, там с минимальным lcm были паттерны как минимум с 0, 1 и 2 простыми проверяемыми. Более 2 - не знаю, не отбирал и не искал такие.

Просто наиболее быстро проверяемые места - с ожидаемым p, имеют наименьшую вероятность (среди мест с ожидаемыми $p, pq, pqr, pqrs$).
Кроме того, оптимальная стратегия проверок - до первой неудачи. Если использовать такую стратегию, и положить "стоимость" проверки на простоту - ноль, тогда получим крайний случай - оптимальными паттернами будут не паттерны с максимальной вероятностью найти цепочку, а паттерны с максимально возможным количеством "мест p".
Но "стоимость" проверки на простоту не ноль, хотя и мала по сравнению с факторизациями. Поэтому должен быть где-то оптимум.
Для $D(48,23)$ этот оптимум был при одном проверяемом простом, как для скрипта на PARI\GP, так и для pcoul.
Для нуля проверяемых простых паттерны оказывались немного хуже, раза в 1.5 по ожидаемому времени нахождения цепочки.
Для двух простых оказывались сильно хуже - в разы.

[Yadryara]

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

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

А для трёх — должно быть ещё хуже. Тогда тем более непонятно:

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

В ближайшее время планирую поискать цепочки D(96,19) и D(192,15).
Последнюю я безуспешно искал полтора года (на одном компе в 8 потоков).
Но это было во времена, когда мы верили в теорию флогистона эфира оптимальности паттернов на 3 простых.

Кто это "мы"? Кто верил в теорию оптимальности паттернов на 3 простых?

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

1. Последние рекорды связаны (не только с применением pcoul, но и) с перестановкой квадратов чисел, бОльших длины цепочки непосредственно самой программой, а не извне.

Во-первых, перестановка квадратов и не только их, но и всех паттернов с определённым набором квадратов простых, была придумана и использовалась ещё 4 года назад.

Во-вторых, насколько понимаю, из 7 рекордов новой эры с применением pcoul было установлено от силы два.

Имею в виду вот эти 7 рекордов.

Для 24-х делителей — длины 19 и 20.
Для 48 делителей — длины 21, 22 и 23.
Для 96 делителей — длины 18 и 19.

Ещё одно соображение прокомментирую позже.

[wrest]

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

Но "стоимость" проверки на простоту не ноль, хотя и мала по сравнению с факторизациями. Поэтому должен быть где-то оптимум.

А стоимость проверки делимости на малые простые ещё меньше чем стоимость проверки простоты. Тут бы конечно количественно оценить, ну скажем десятки проверок делимости дешевле одной проверки простоты.

[Dmitriy40]

wrest в сообщении #1723345 писал(а):

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

Ну так в чём проблема?

? v
%1 = [833, 338, 75, 32, 2299, 18]
? pp
%2 = Mod(2014230969373, 2330253525600)
? for(k=1,10^7, x=(lift(pp)+pp.mod*k+5)/v[6]; ispseudoprime(x); )
time = 8,284 ms.
? for(k=1,10^6, x=(lift(pp)+pp.mod*k+5)/v[6]; forprime(p=23,2^10, x%p<6 ) )
time = 10,531 ms.
? primepi(2^10)-primepi(23)+1
%5 = 164

ispseudoprime выполняется в среднем 0.83мкс (умножение, сложения и одно деление считаем бесплатными), 164 делений выполняются в среднем 10.5мкс или 0.064мкс каждое, в 13 раз быстрее.
Конечно такая маленькая разница - из-за встроенных в ispseudoprime делений на малые простые, видимо они попадаются довольно часто и резко сокращают время работы ispseudoprime.
Но значит вопрос поставлен некорректно, надо сравнивать что-то как-то по другому.

[wrest]

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

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

Ну да, вопрос поставлен слишком неопределенно, согласен.
Вообще, постоянно всплывает желание "взять под контроль" механизм факторизации (во всех аспектах, включая и проверку на простоту) в pari/gp.
Ну например, вот в той программке что я адаптировал, для проверки паттерна D(48,21), там было по статитстике что-то вроде 14 делений на малые простые и одна проверка на простоту на цепочку. Но если скажем мы уже поделили на какое-то количество простых, и теперь проверяем частное на простоту, то надо бы, если при этой проверке сперва идёт деление на малые простые, не делить на те, на которые мы уже проверили и не делится. Но при этом, попытки отложить проверку остатка-частного на простоту и продолжить его деление на малые простые оканчивались катаатройическим падением производительности, почему-то.
В общем, не хватает полного контроля над процессом, а получить его чрезвычайно трудно в связи с его сложным внутренним устройством в pari/gp.

[Dmitriy40]

wrest в сообщении #1723365 писал(а):

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

Потому что до 2^15 гораздо больше 14 простых чисел, которые проверялись "в среднем".
И даже 14*14=196 (т.е. попадание второго малого делителя что позволит отбросить цепочку не вызывая isprime) гораздо больше просто 14.
Вот и падение скорости из-за резкого увеличения длины перебора.

[wrest]

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

Вот и падение скорости из-за резкого увеличения длины перебора.

Ну я-то надеялся, что из 21 числа в цепочке таки в среднем должно находиться какое-то с явным перебором по малым простым, ведь там проверка идёт одновременная по всем числам цепочки. Но нет. А вот чтобыьони там были, надо паттерн делать больше склонным к перебору чем недобору.
Ну не знаю, как-то мысли скачут у меня... Короче, надо регулировать t_R (ожидаемое количество делителей после деления на паттерн) не только исходя из вероятности попадания в нужное количество делителей, но и из скорости проверки. И тут вы, видимо с "терапевтикой" все-таки правы. Лучше -- быстрее проверять ценой потери потенциальных решений.

[Yadryara]

wrest в сообщении #1723365 писал(а):

Вообще, постоянно всплывает желание "взять под контроль" механизм факторизации (во всех аспектах, включая и проверку на простоту)

Молодец, в корень смо́трите. Надо пытаться взять под контроль. Без всяких кавычек.

Не пробовали попросить ИИ написать программу на асме?

wrest в сообщении #1723369 писал(а):

И тут вы, видимо с "терапевтикой" все-таки правы.

Как думаете, в программе в самом конце 1-й страницы, есть терапевтика?

[wrest]

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

Не пробовали попросить ИИ написать программу на асме?

На каком асме? Я же запускаю pari/gp на arm64 (под линукс-ядром, притом) чаще чем на amd64 (и тоже под линукс-ядром, в WSL2), мне на асме нинада. Максимум на Си, но и то... Возиться с длинной арифметикой - зачем если уже есть GMP, и в pari используется.

-- добавлено через 28 минут --

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

Правило "увеличение n на 2 порядка снижает вероятность в 2 раза" применяется уже после фильтрации по запрещенным остаткам.

Кстати, если делать "правильный" микс разных t_R в паттерне, то суммарная вероятность может и не снижаться: ну скажем t_R=4 будет падать, а t_R=8 будет расти.