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

[Yadryara]

У меня и ласточки перестали находиться. Временно, конечно.

Те 30 комплектов, выбранные по 3-м pqrs-местам с приводом 3!x7! в свою очередь разделил на 16 и 14 комплектов по p и pq-местам. И провел сравнительный анализ:

Посчитано       Найдено             Сред.            Средн.
комплектов     цепочек             ариф.              valids
               16            691               43.2               15.06
                 7            273               39.0               14.83

Да, пока 16 комплектов, где на месте с простым стоит 169, а не 49, показывают лучшие результаты и по среднему количеству найденных цепочек и по средневзвешенному valids. Фильтрацию конечно делал одну и ту же.

Детализация:

Серия            Комплекты           Привод        Интервал       Обсчитано
1-2-17-3-10!     5,6 11-16           3! x 7!       0 — 1e55           16/16
                 125-130,135,136

Valids   8    9   10   11   12   13   14   15   16   17   18   19   20   21

691      1    1    3   11   49   78  131  130  144   69   46   16   10    2

                                           15.06


Серия            Комплекты           Привод        Интервал       Обсчитано
1-2-17-3-10!     60,63-65,68-70      3! x 7!       0 — 1e55            7/14

Valids   8    9   10   11   12   13   14   15   16   17   18   19   20   21

273                6   10   22   38   42   49   48   30   16    8    4

                                      14.83

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

По-прежнему жду от VAL либо цитату с неоднократно упоминавшейся просьбой, либо снятия претензий.

[EUgeneUS]

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

По-прежнему жду от VAL либо цитату с неоднократно упоминавшейся просьбой, либо снятия претензий.

[Dmitriy40]

[Yadryara]

Если это решит проблему я могу и три поставить, хотя и не люблю эти МЛ-ки.

По теме-то есть что сказать? Например, как побыстрее управляться с полупростыми числами? Или это надо в теме про факторизацию спрашивать?

[Yadryara]

Так 860271072720571112089954456681650511473773778437340720921 это не просто дрофа. Это я наконец-то первый раз вижу на поле 24 числа с 48 делителями. Обозначение первых степеней простых убрал чтобы сузить:

   1 1  11111111 11111111111111   24

[7481; 6781163771; 21149997412639; 801790882208722046306745012517]              16
[2; 127; 237951187; 969483867300553043; 14681591660522910086485318751]          32
[3; 5; 83; 3331; 904419973; 49070555117; 362783949313; 12884042703559625029]   256
[2, 2; 13; 59617; 62091476733061; 4469200813334134629015641689822860709]        48
[1169474143; 73937792749; 319168905035293; 31171495622472361806467]             16
[2; 3, 2; 7; 5641; 1210343590887255597608712933203966581791720170122573]        48
[46411; 262709; 178968887; 19415909101; 20305055221121755002775964563]          32
[2, 3; 5; 73; 85297; 174334575231074092139; 19812313139798565057963999997]     128
[3; 31, 2; 81239; 111577; 32919363398893017996476773331341136736817229]         48
[2; 19, 2; 13790611; 19144758359921656373239; 4512993673222426036265969]        48
[11; 53, 2; 766439; 70819643; 512931731396103198688595409166650792301]          48
[2, 2; 3; 337; 390009391; 545442668044520835578571253914068376766186931]        48
[5, 2; 7; 129937; 2771207473; 13651972160586211328026610847810539405491]        48
[2; 17, 2; 189817; 257918797978609556207999; 30401105738150440803649049]        48
[3, 5; 71; 1581415340473; 31530056574047674311640801251612176996683]            48
[2, 5; 491; 9319; 5875360747673783703357740929455071310098661971101]            48
[13; 37, 2; 22991104835169059; 2102464528939192132154955897705531823]           24
[2; 3; 5; 23, 2; 54207376983022754385000280824300599336721725169334639]         48
[43, 2; 12743; 1569121; 937272657151337864561; 24825862347992713504093]         48
[2, 2; 7; 671939833; 3133529219; 14591943941300681900264548263905102797]        48
[3; 61, 2; 197; 7525066123; 51984976060691094594690078333609955616761]          48
[2; 11, 2; 4763800651; 46853449882763393; 15926663346457465617522763489]        48
[5; 41, 2; 2551; 497576650599307; 80635661101840067615689716852362311]          48
[2, 3; 3, 2; 6985609; 1710403394083646171106028393280565388615711756757]        48
[67, 2; 103; 10501; 778391; 227625034816878323165034540495942794303021]         48
[2; 47, 2; 832177393; 9752952964090163; 23991509005296887137248661799]          48
[3; 7, 2; 2194309795492103; 17425040545322227; 153054550340303809360277]        48
[2, 2; 5; 41956027; 1942321475954478841; 527824877585752134694783499621]        48
[19; 29, 2; 72889; 948268296949; 778919362472373271423603588256200739]          48
[2; 3; 13, 2; 7355428628923; 115342504922792486004388044402567148172911]        48
[17; 59, 2; 211; 643; 107149203435455970683223642222913189099643379983]         48

У Демиса, кстати, ласточка-то нашлась. По крайней мере одна. Это 140-й комплект:

29177983803895884720374780061598318253377196549074454417

[Dmitriy40]

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

Например, как побыстрее управляться с полупростыми числами?

Думаю нет смысла: проще найти ещё 100500 других цепочек в надежде что попадётся лёгкое разложение чем пытаться разложить полупростое число.

[EUgeneUS]

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

Думаю нет смысла: проще найти ещё 100500 других цепочек в надежде что попадётся лёгкое разложение чем пытаться разложить полупростое число.

Сомнительное утверждение.
Например для цепочек D(48,23) вероятность найти цепочку за одну проверку (после фильтрации на плохие остатки) - лежит в промежутке $2\cdot 10^{-14}...2\cdot 10^{-13}$.
С другой стороны, если 22 числа из 23 удачно совпали, а ещё одно не проходит тест на простоту, но не раскладывается, то вероятно оно "полупростое". И если ожидается именно полупростое, то вероятность, что это найденная цепочка - очень высока.

Если её бросить. то до следующей такой нужно перелопатить не "100500 других цепочек", а мегатонны шлака. И никто не даст гарантии, что у неё все полупростые быстро разложатся.

[Dmitriy40]

Разумеется цепочки <22-правильных-из-23> выгодно разложить до конца (но возможно в отдельном потоке сторонними программами). Хотя и numdiv PARI справляется с такими числами вполне быстро, вообще не вижу в чём тут проблема.

Yadryara
Но исходный вопрос вообще непонятно о чём: ни сколько таких мест pq, ни какой величины числа, ни с какой скоростью генерятся такие цепочки и такие числа - не указано никаких данных для анализа/обдумывания. Опять Вы вместо написания нормального вопроса чрезмерно сокращаете в надежде непонятно на что (начать очередную волну переуточнений и перевопросов). А потом снова будете удивляться почему все проигнорировали непонятные вопросы и молчат ...

[wrest]

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

(но возможно в отдельном потоке сторонними программами). Хотя и numdiv PARI справляется с такими числами вполне быстро,

Ну да, вы же в диапазоне $10^{50}$ ищете, а там на сторону отдавать особого выигрыша и не получишь...

[Yadryara]

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

Опять Вы вместо написания нормального вопроса

Это тоже уже обсуждалось. Если бы я был готов задать нормальный вопрос, я бы его задал. А так это пока на уровне смутной идеи, что возможность ускорить счёт всё ещё есть. Ранее некоторые из этих смутных идей (далеко не только в этой теме) давали результаты, какие-то, разумеется, не давали.

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

Но исходный вопрос вообще непонятно о чём: ни сколько таких мест pq, ни какой величины числа,

Это-то как раз многократно повторено. Если сейчас считается серия 1-2-17-3-10!, значит ровно 2 числа pq.

А про величину чисел и wrest до сих пор примерно помнит. Если счёт идёт на высоте до 1e55-56, соответственно числа на 2-5 порядков поменьше.

[Dmitriy40]

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

Это-то как раз многократно повторено. Если сейчас считается серия 1-2-17-3-10!, значит ровно 2 числа pq.

Вот это совсем не факт: могло в pqr/pqrs найтись один/два небольших делителя, а потом затык на pq ... Соответственно и числа могут быть поменьше, пусть и не сильно.
И вопрос о разложении pq (да и pqr с pqrs) уже возникал и никакой внятной идеи не было.
Если бы ECM гарантировал отсутствие делителя можно было бы его запустить до кубического корня (что впрочем обычными средствами PARI нельзя) и оставить pq недоразложенным, но ECM ничего не гарантирует ...
Ну и повторю, я не думаю что в текущей реализации с кучей циклов с factor сильно тормозит процесс именно разложение мест pq (потому что обычно там оказывается вовсе не два делителя и потому вполне логично такие цепочки просто пропустить если не разложилось быстро, либо, если остальные места подошли, то раскладывать до упора, благо числа не сильно велики и это не занимает годы и даже дни).

-- 15.01.2026, 19:55 --

Что могу предложить: переписать цикл линейного перебора forstep(n=n0,n0+k*m-1,m, forprime(p=23,2^15, if(nf(n,p)[]>nu[], next(2)); print(n); ); (т.е. фильтрации по простым до 2^15, но без проверки остатка на простоту) на асме. Но как показывает опыт коэффициент такой фильтрации невысок и допроверять придётся слишком много, т.е. большого выигрыша скорости не ожидается. Делать на асме isprime это убиться и оно вроде не получается быстрее PARI (тем более если взять готовую либу zmp или любую другую).

[DemISdx]

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

готовую либу zmp

Что это такое?
(Или имелось ввиду gmp...)

[Dmitriy40]

DemISdx
Да я просто не помню как она называется. Это спутал с префиксом mpz из кода pcoul.
Любая либа с длинной арифметикой, от неё же ничего этакого не требуется, только сложение/вычитание и сдвиг вправо, если будут умножение по модулю и тем более степень по модулю вообще прекрасно.

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

[EUgeneUS]

Думаю, D(48,23) найдётся в течение года в числах до 3e54.

Не буду утверждать, что это будет первая найденная цепочка, как видели ранее - чудеса случаются.

[Yadryara]

А между тем, Демис таки поймал ещё одну дрофу. Итого их 12 штук. По сравнению с прошлым топом новенькие на 10-м и 12-м местах:

Start                                                     Location              Valids
3763919492009990910466562016703823421391962461493338      1111111111111111111111    22  De
9204926595955930659029610200709650474407650679458585      1111111111111111111111    22  Vl
12928151557178753218526554700017805780952517953844761     1111111111111111111111    22  Vl
91961526307286709380597649336434597932204049205291537     1111111111111111111111    22  Na
8495059548859626592773879865662858605488940747161295961   1111 111111111111111111   22  An
15760230758531706844376995032385338075337309353237290641  1111111111111111 111111   22  Vl
28893938757640056767463957562407174763516782266088647641  111111111111111 1111111   22  Vl
37152278459502258166977636243836236680185687545208740441  11 11111111111111111111   22  Vl
53266808345089279788448860804694037142466315516054607641  1111111111111111111111    22  Vl
71516188146874034885536899855322175423199142340325196817  11111111111111 11111111   22  De
77428134413524643861438454446089927227486300953208762841  111111111111111111111 1   22  An
860271072720571112089954456681650511473773778437340720921 11111111 11111111111111   22  Vl

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

Что могу предложить: переписать цикл линейного перебора forstep(n=n0,n0+k*m-1,m, forprime(p=23,2^15, if(nf(n,p)[]>nu[], next(2)); print(n); ); (т.е. фильтрации по простым до 2^15, но без проверки остатка на простоту) на асме.

Спасибо за предложение.

Только этого перебора уже давно нет в программе. Мы ведь обсуждали. Применяется короткая арифметика по 20-й степени 2-ки, а не по 15-й. Я тестировал. Оптимальна была 20-21 степень, а не 15-я.

И, если уж Вы возьмётесь за асм, то я клоню к тому, чтобы делать делать на асме проверку 3-х чисел: одного простого и двух полупростых. На кубы, видимо, надо пока плюнуть.