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

[VAL]

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

Действительно, где-то на второй минуте выдача была такая:

0.13283096000000000000000000000000000000

2907131999263647241639125071485412894901874802299547

# [1, 1, 1, 0, 0, 1, 1, 1, 0, 1, 1, 0, 1, 1, 1, 1, 1] 16

А единственная 20-ка вроде бы такая:

17668887847524548413038893976018715843277693308027547

Там же явно указано, что это не 20-ка, а цепочка с 16-ю нужными значениями из 20.
На какой минуте должна быть выдача 20-ки, не знаю.
НО знаю, что она должна получиться при

i=346594514032

[Dmitriy40]

И это очевидно:
$\frac{\frac{17668887847524548413038893976018715843277693308027547+7}{3234}-144989573913151252516120361049319706881}{15763313547330727349557157245556968800}=346594514032$

[gris]

просьба о маленьком уточнении: для каких значений запускать выложенную программу для D(48,21)?

[VAL]

Посильная задача для YAFU

(2 prime factors wanted)

6347372256112498141357253730259338197286119480038997383621953418481191834695719843750518754445148879177074339714424062288297889938031238958354212563 (148 digits) = pq?

-- 30 сен 2025, 18:05 --

gris в сообщении #1703936 писал(а):

просьба о маленьком уточнении: для каких значений запускать выложенную программу для D(48,21)?

Вообще-то, я выкладывал ее в качестве примера, но если хотите посчитать, то с i1 = 532000000000.
Параметр i2 можно подобрать наиболее удобным для Вас (чтобы не слишком часто и перезаряжать, но и в бесконечность не уходить).

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

-- 30 сен 2025, 18:40 --

По поводу попыток найти цепочку из 21-го числа.

Использовать подход трехлетней давности можно. Но перспективы - так себе.
Если только сильно повезет...
Или если подключить к проекту сотни три, четыре компов...
Но где их взять? В свое время я обращался в PrimeGrid (с предложением поискать пентадекатлон). Но они меня ответом не удостоили, пришлось самим искать.

Альтернативный путь - что-то усовершенствовать.
Антон заинтриговал, но пока не совсем ясно чем.
Мне представляется перспективным приспособить к поиску ускорители Дмитрия. Но для этого лучше подходит цепочка для $k=24$.
На мой пост реакция пока вялая.

[VAL]

А тем временем новый мировой рекорд у нас практически в руках.

(2 prime factors wanted)

1469035077330523717823819437322710869573299159750359872924688970048335110314229657181856324448601945545811642213208873589581 (124 digits) = pq?

[Yadryara]

Сегодня некогда было по-нормальному разобраться с прогой по D(48,20).

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

Там же явно указано, что это не 20-ка, а цепочка с 16-ю нужными значениями из 20.

Нет, не явно. Но да, я заподозрил, что это никакая не 20-ка, а лишь дырявая 16-ка.

Сначала положил i1 = 346584514032, то есть за 10 лямов до цели, затем i1 = 346494514032, то есть за 100 лямов.

Сначала тестировал в PARI и было ощущение, что загрузка программы занимает немалое время. Затем наконец-то удалось запустить из консоли. Да, работает быстрее чем из PARI:

Интервал               Консоль               PARI
10  млн               44.8 sec           49.4 sec
100 млн         7min, 19.0 sec     7min, 26.1 sec

То есть скорость у меня где-то 71-73 минуты на ярд или 8е8/ч или 800 лямов в час. Это всё в одном потоке.

Буду вникать дальше.

[EUgeneUS]

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

Альтернативный путь - что-то усовершенствовать.
Антон заинтриговал, но пока не совсем ясно чем.
Мне представляется перспективным приспособить к поиску ускорители Дмитрия. Но для этого лучше подходит цепочка для $k=24$.
На мой пост
реакция пока вялая.

ИМХО: цепочки с $k=24n$ можно попытаться улучшить, в смысле поискать более длинные. Путь представляется такой:

1. Нужно искать не по одному шаблону, а по многим шаблонам с таким же "качеством".
2. Под "качеством шаблона" я понимаю
а) одинаковый (и максимально "хороший") набор неизвестных $p, pq, pqr ...$
б) одинаковый LCM.

Для примера, если правильно понимаю.
Из шаблона из этого поста просто перестановкой квадратов получается $9! = 362880$ шаблонов.
Так искать нужно по ним по всем.
UPD: а ещё при поиске пентадекатлона были "правые" и "левые" шаблоны.

Максимально "хороший" набор неизвестных $p, pq, pqr ...$ - это минимизация количества чисел с мЕньшим количеством простых множителей в пользу чисел с бОльшим количеством простых множителей.
Но для каких-то цепочек всё равно будут неизвестные простые $p$. И вот в этом случае использовать ускорители Дмитрия.

Думаю, с такими подходами и имеющимися мощностями цепочки для $k=24n$ можно удлинить на одну-две позиции.

UPD: по дороге, скорее всего и найденные цепочки улучшатся.

Собственно пентадекатлон так и победили:
1. Сделали кучу шаблонов с минимальным количеством неизвестных простых.
2. Искали по всем таким шаблонам.
3. Для проверки простых применяли ускорители Дмитрия.

[DemISdx]

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

А тем временем новый мировой рекорд у нас практически в руках.

Держите его , а то убежит

(тыц по 14690...)

NFS elapsed time = 4583.8925 seconds.
Total factoring time = 4953.1588 seconds


***factors found***
P60 = 460268049727859956142626776446136638272879139903836831140827
P64 = 3191694661836970094003866830455553271711964090477309272085197303

***factorization:***
1469035077330523717823819437322710869573299159750359872924688970048335110314229657181856324448601945545811642213208873589581=460268049727859956142626776446136638272879139903836831140827*3191694661836970094003866830455553271711964090477309272085197303

[VAL]

DemISdx в сообщении #1703968 писал(а):

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

А тем временем новый мировой рекорд у нас практически в руках.

Держите его , а то убежит

Не убежит!

$M(11664) \ge 8$

(Начало цепочки)

n = 2211374858375229883908948043735990057501145558622085333423743171463827730304907848076092603475314246299276580706608699443721205862749536939735468428671508668017368425929358099999998
n+2 = 2^8 × 5^8 × 101^2 × 107^2 × 521 × 2507726962972632486539 × 145403948545213914505941556640233 × 
996684929975896917035906314971999481031279004887777925681479986767666063907056220742882008485989989360261447 
n+3 = 11^2 × 19^2 × 23^2 × 37^2 × 73^2 × 89^2 × 92647 ×  12168062026302970819191961213450267 × 460268049727859956142626776446136638272879139903836831140827 × 
3191694661836970094003866830455553271711964090477309272085197303

Три года назад мы гордились длинной цепочкой для $k=5040$. В этом году после возобновления темы последовательно пали $k=5832, k=6480$ и $k=7128$. Рост относительно плавный...
А тут такой рывок!

-- 30 сен 2025, 23:54 --

Да, кстати, 63473... теперь разлагать не нужно.
33546... все еще актуально. Вот только рекорда оно теперь не даст. $k = 11664$ влезло без очереди растолкав двух соискателей рекордов

[DemISdx]

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

Рост относительно плавный...
А тут такой рывок!

Отлично!

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

63473... теперь разлагать не нужно.

Остановил.

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

33546... все еще актуально.

По состоянию на 08:03 утра, сегодня, стадию ecm число прошло (т.е. ecm считался с 28.10.25 19:27 по 01.10.25 08:03).
Началась стадия nfs.
Полагаю это еще надолго.

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

Вот только рекорда оно теперь не даст.

Не страшно.
Но раз нужно разложить, то будем предпринимать попытки это сделать...

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

влезло без очереди

Вот шустряк подвернулся...

[VAL]

DemISdx в сообщении #1703987 писал(а):

Вот шустряк подвернулся...

Полагаю, это не случайно.
Вот, например, при поиске цепочки из 9 чисел для $k=156$ именно "шустряк подвернулся". Кандидатуры, прошедшие предварительный отбор, появлялись очень редко. И я уже хотел было остановить отбор, когда одна из таких кандидатур неожиданно сработала, причем без долгих вычислений.
А для восьмерки чисел, имеющих по 11664 кандидаты появлялись с завидной регулярностью. Например, остановленное Вами 63473... тоже, скорее всего, дало бы требуемую цепочку. А еще за короткое время у меня набралось несколько пар, для которых при доходящем разложении каждого из чисел, нашлась бы искомая восьмерка.

Очевидно, это связано с каноническим разложением $k=2^4*3^6". С одной стороны, квадраты, используемые в шаблоне, не загоняют нас в какие-то совсем уж заоблачные числа, как это делали бы более высокие степени. А с другой, числа, остающиеся после отделения обязательных множителей, чаще всего имеют именно по 4 делителя. То есть макушка "колокола", о котором писал vicvolf, приходится именно туда, куда надо. И это было заранее ясно. Единственное что удивило - этот колокол оказался весьма "крутым", даже случаи по 3 и 5 множителей встречаются значительно реже, чем четверки.

А еще вполне возможно, что легкость поиска обусловлена близостью среднего геометрического простых множителей 11664 к числу $e$.

-- 01 окт 2025, 10:41 --

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

Максимально "хороший" набор неизвестных $p, pq, pqr ...$ - это минимизация количества чисел с мЕньшим количеством простых множителей в пользу чисел с бОльшим количеством простых множителей.
Но для каких-то цепочек всё равно будут неизвестные простые $p$. И вот в этом случае использовать ускорители Дмитрия.

Три года назад мы эмпирически пришли к выводу, что оптимальный шаблон для писка длинных цепочек рассчитан на проверку на простоту трех чисел.
Но в такой ситуации ускорители Дмитрия мало что дают. Ну нашли мы триллион кандидатов, а теперь искать среди них те, где 18 оставшихся чисел разложатся как надо... Вариант для $k=24$ тупиковый, поскольку наиболее вероятное разложение оставшихся чисел $pqr$ или $pqrs$, а нам надо массу $pq$.

А вот шаблон на 9 простых может реально помочь (хотя может и не помочь, надо проверять). Без ускорителей мы будем сутки искать кандидатуру, проходящую отбор по простым. А если ускорим эту стадию, то останется 12 чисел, 6 из которых требуют разложения $pq$, а другие 6 - $pqr$. Тоже не сахар, но в тысячи раз вероятнее, чем 18 чисел.

В общем надо пробовать. Возможно, сначала не для цепочки длиной 21, а хотя бы 19, что будет не абсолютным рекордом, а только рекордом для $k=24$.

[EUgeneUS]

VAL
Не буду утверждать, что вот такая оценка качества шаблона верная:

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

Максимально "хороший" набор неизвестных $p, pq, pqr ...$ - это минимизация количества чисел с мЕньшим количеством простых множителей в пользу чисел с бОльшим количеством простых множителей.

Возможно, с учетом потенциального использования ускорителей Дмитрия, будет правильным минимизировать $pq$ в пользу $p$ (ускорители) и $pqr$ (более вероятно, чем $pq$).

Но в чем уверен на 146%:
если
а) какой-то шаблон признали "хорошим"
б) и таких шаблонов (с тем же распределением $p, pq, pqr ...$ и тем же LCM) много.
то нужно вести поиск по всем таким шаблонам.

Аргументация такая:
1. С ростом $N$ вероятность найти цепочку в одной проверке будет падать примерно как $A(\frac{1}{\ln N})^k$, то есть, чем длиннее цепочку ищем, тем быстрее она будет падать.
2. Улетаем в область больших чисел - сложнее и дольше делать факторизацию.

Поэтому нужно искать "по низам". Чем больше одинаково "хороших" шаблонов используем - тем медленнее растёт $N$, тем больше вероятность найти цепочку в одной проверке. И тем быстрее делается единичная проверка (а значит больше проверок в единицу времени).

[VAL]

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

Но в чем уверен на 146%:
если
а) какой-то шаблон признали "хорошим"
б) и таких шаблонов (с тем же распределением $p, pq, pqr ...$ и тем же LCM) много.
то нужно вести поиск по всем таким шаблонам.

Аргументация такая:
1. С ростом $N$ вероятность найти цепочку в одной проверке будет падать примерно как $A(\frac{1}{\ln N})^k$, то есть, чем длиннее цепочку ищем, тем быстрее она будет падать.
2. Улетаем в область больших чисел - сложнее и дольше делать факторизацию.

Поэтому нужно искать "по низам". Чем больше одинаково "хороших" шаблонов используем - тем медленнее растёт $N$, тем больше вероятность найти цепочку в одной проверке. И тем быстрее делается единичная проверка (а значит больше проверок в единицу времени).

Если Вы заметили с этим я (и никто другой) и не спорит
Приводимые мной одиночные таблицы и раньше и сейчас - это некие образцы, а не единственно возможные варианты.
Более того, вполне возможны и замены типа $59^2$ на $61^2$, которое в исходной таблице отсутствует.

[EUgeneUS]

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

Если Вы заметили с этим я (и никто другой) и не спорит

Не спорят - полдела
Я как бы агитирую таки попробовать поискать длинные цепочки таким путем

[EUgeneUS]

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

Более того, вполне возможны и замены типа $59^2$ на $61^2$, которое в исходной таблице отсутствует.

$61^2 / 59^2 \approx 1.069$
LCM увеличивается, но не значительно.

Более того
$67^2 / 59^2 \approx 1.29$
LCM увеличивается уже заметно, но всё ещё такой паттерн даст много проверок "по низам".

Более того
$71^2 / 59^2 \approx 1.45$
$73^2 / 59^2 \approx 1.53$
И где-то тут можно остановиться

В общем - прекрасный метод сильно увеличить количество паттернов, не сильно ухудшая их "качество".