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

[VAL]

Предчувствия меня не обманули.
$M(960) \ge 8$

(Оффтоп)

n = 18233150106751594934095860237972791065024638577675048543922089989514178332475145002136963594010620
n + 1 = 11^4 × 23^2 × 43 × 109 × 50671 × 603475507 × 154095200254723473565278605390554699 × 106593839592109309232112178824383238349 
n + 3 = 3^14 × 47 × 113 × 157 × 4217110056559 × 30345164338923580646724638178984377 × 35725947725463250142285220045395972747
n + 5 = 5^4 × 31^2 × 59 × 127 × 311 × 3918191195879633 × 8479189926488758457322409 × 392104830971977691182345762296835562997522787

[VAL]

Вдогонку.
$M(960) \ge 9$

(Оффтоп)

n = 1184001624110765541589408164261562985661796476003023664026411290699800724379690887941409179468419683338010620
n + 7 = 7^4 × 37^2 × 59 × 61 × 3607 × 8637779 × 59055478699677123568093365141216184793 × 54395931527248754942430148584466124386748979580073

[VAL]

"Потеряшка" 960 продолжает наверстывать упущенное.

$M(960) \ge 10$

(Оффтоп)

n = 22232703876002162291278856002391563675314856913497159734078054207219653527099460859021612148552969845409741413119770620
n + 3 = 3 × 13^4 × 53^2 × 107 × 227 × 23209049717856522817291873 × 211321975568528050022675752555180700381 × 775415047485269570980615757666953440049937 
n + 5 = 5^4 × 47^2 × 67 × 71 × 1709 × 4560319456098092443 × 26151803241551263174231649194001 × 16609036116944687679869085527914479448739780485033975843
n + 9 = 3^2 × 19^4 × 89 × 137 × 293 × 1062529699425143740399139 × 108532680984247290175073596983691 × 46010353170056341988550481713296532586794020102761

Кстати, это некий локальный рекорд. Столь длинных цепочек для таких больших $k$ еще не было.

To be continued?

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

[VAL]

Благодаря новой таблице от 25.08 (кстати, ее, кроме Дмитрия, так никто и не скачал) случаи, для которых длинные цепочки находятся легко, видны невооруженным глазом.
На поиск приведенной ниже ушло менее 2 часов на всё про всё!
Всё - это создание шаблона, предварительная программа на maple, программа на PARI, поиск кандидатур, проверка перспективных вариантов на Aplertron'е (для других цепочек с аналогичной длиной и порядком чисел, только последние два этапа могут растянуться на недели).

$M(1944) \ge 8$

(Оффтоп)

n = 45551655702483610275536591313180733705879731384580542657994881697163569777153802259396703316380851633211789048764580656427096392099999998
n + 5 = 13^2 × 17^2 × 29^2 × 37^2 × 61^2 × 40106901409 × 347121111198979528054462632479 × 15637249590521620184622376082468738982367101676169790681440412280538621453403229517

Правда, больше таких лайтовых случаев, похоже, не осталось.

[VAL]

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

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

Воспользуюсь любезным предложением. Дозрел.

209662857453191172208774166556488590112931394712279012594955823904346331202445705641007789417542899809691474514127837942488639051212991896037675302171 (150 digits) (Composite)
55662212514374333854411247602870129064983737899272183727285204718917424705504387281480220130365957114197485014500556797138352686863076223979929623467 (149 digits) (Composite)

Разложение на два простых множителя хотя бы одного из вышеприведенных чисел дает цепочку из 8-и последовательных чисел с 1260-ю делителями.

3918379656357389606873359047195893747533485686015905036602677399573158885722032566725698392305436953685570352466693456774399905281974881795857 (142 digits) (Composite)
6478197682160135533232676025010796587683078229933245253455083741332424828397724440663355684763020130070666446674154783674124103294478717003233 (142 digits) (Composite)

А здесь разложение на два простых множителя каждого из вышеприведенных чисел дает цепочку из 8-и последовательных чисел с 1620-ю делителями.

[Dmitriy40]

Первое число за 12ч метод ECM не осилил, собрался работать ещё минимум 34ч, оборвал, сейчас запущу без предпроверки по ECM, сразу NFS.

[VAL]

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

Первое число за 12ч метод ECM не осилил, собрался работать ещё минимум 34ч, оборвал, сейчас запущу без предпроверки по ECM, сразу NFS.

Возможно второе число победить легче. Оба с неделю крутились у меня Alpertron'ом, занимая по одному потоку.
Устояли оба, но при этом второе разложение успело добраться до 8 тысяч кривых, а первое только для шести с половиной.
Это довольно любопытно. Чаще всего для чисел одного порядка расхождения в количестве использованных кривых идут на единицы, иногда на десятки.
А тут более полутора тысяч.

[VAL]

Есть рекорд!
Не такой значимый (чем значимый?!) как $M(12)=15$ или $M(48) \ge 20$, но тоже не проходной.
$M(5832) \ge 8$

(Оффтоп)

n = 78944350508263691197230158385024385094534584500693621329037190269888324352948253663483963119363674640995999065385963410942931313152739082929533248839282745552012338299999998
n + 2 = 3^8 × 41^2 × 53^2 × 73^2 × 163^2 × 2234251615877 × 1460564577202620652680199559767714349951163073 × 
5515155886553880657117292322532086438718065772522110797275219123982011366492303053490629793860851 

Таких длинных цепочек для столь больших $k$ еще не было.
Предыдущая цепочка длиной 8 была максимум для $k=5040$.

Уверенность, что восьмерка для $k=5832$ найдется без сверхусилий, возникла у меня как следствие той легкости, с которой была найдена цепочка для $k=1944$.
Для этого (и, как я правильно предполагал, аналогичного ему случая $k=5832$) кандидаты в отыскиваются очень легко. На поиск такой кандидатуры в среднем уходит раз 20 меньше времени, чем, например, на поиск кандидата в восьмерки для $k=1620$. Хотя, казалось бы, и размер рассматриваемых чисел сопоставим и канонические разложения $k$ похожи.

[Dmitriy40]

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

сейчас запущу без предпроверки по ECM, сразу NFS.

Считает уже неделю в 4 потока, 5 дней искался оптимальный полином, три дня что-то по нему просеивает, уже выдало "на гора" больше 2ГБ каких-то данных, когда завершится неизвестно.

[VAL]

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

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

сейчас запущу без предпроверки по ECM, сразу NFS.

Считает уже неделю в 4 потока, 5 дней искался оптимальный полином, три дня что-то по нему просеивает, уже выдало "на гора" больше 2ГБ каких-то данных, когда завершится неизвестно.

Это первое из присланных чисел?
То есть, 150-значные берутся только при везении.

Надеюсь, с числом

32947982581120650985939484875663571968466852208066722951068417489767894289562627798682880807611496415139742989032137639 

все срастется. Оно существенно поменьше.

Если оно распадется на 2 простых множителя, получится новый рекорд - длинная цепочка для $k=6480$.

При этом, если моя гипотеза о детерминированности алпертроновского ECM верна, у него не может быть больше двух множителей, поскольку у него нет делителей до 40 десятичных знаков, а оно 119-значное.

[Dmitriy40]

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

Это первое из присланных чисел?
То есть, 150-значные берутся только при везении.

Да, первое, 20966...
Ну, скорее быстро берутся при везении. Так-то когда-то nfs всё же найдёт делители, но вот когда - большой вопрос. Если считать что предварительный поиск лучшего полинома не должен быть короче 20% основного счёта, то за несколько недель думаю найдёт. Я не нашёл в yafu оценки ожидаемого времени для nfs алгоритмов, может плохо искал.

Остановил счёт (с возможностью потом продолжить), запустил последнее 119-значное.

И похоже Вы таки правы насчёт ecm, в yafu он тоже выполняется кажется лишь до примерно кубического корня из, а дальше уже (g)nfs или siqs. Просто там своя терминология и плохо понятно что к чему.
Впрочем и альпетрон так же действует, после неудачи ecm запускает nfs/siqs.

[Dmitriy40]

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

Надеюсь, с числом

32947982581120650985939484875663571968466852208066722951068417489767894289562627798682880807611496415139742989032137639 

все срастется. Оно существенно поменьше.

32947982581120650985939484875663571968466852208066722951068417489767894289562627798682880807611496415139742989032137639 = 2488517596499804546265588868674190589073956666522507819 × 13240003859110038964973565829087951628854127345255459597241649781
Хватило 7ч в 4 потока, из которых 2ч ушло на ECM и 1ч поиск лучшего полинома, остальное просеивание (и тоже нагенерило больше 1ГБ непонятных данных).

[VAL]

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

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

Надеюсь, с числом

32947982581120650985939484875663571968466852208066722951068417489767894289562627798682880807611496415139742989032137639 

все срастется. Оно существенно поменьше.

32947982581120650985939484875663571968466852208066722951068417489767894289562627798682880807611496415139742989032137639 = 2488517596499804546265588868674190589073956666522507819 × 13240003859110038964973565829087951628854127345255459597241649781
Хватило 7ч в 4 потока, из которых 2ч ушло на ECM и 1ч поиск лучшего полинома, остальное просеивание (и тоже нагенерило больше 1ГБ непонятных данных).

Спасибо! Отлично!
Значит, есть новое рекордное $k$, для которого найдена длинная цепочка!
$M(6480) \ge 8$

(Оффтоп)

n = 1254790348592958203865764076751649207300559616538144463690455609795933156293386119619116617710302672283029736605540205608729193128529917966733195978993068799999998
n + 2 = 2^14 × 5^8 × 127^2 × 139420849 × 2646227649753534131893 × 2488517596499804546265588868674190589073956666522507819 × 
13240003859110038964973565829087951628854127345255459597241649781
n + 3 = 11^4 × 31^2 × 43^2 × 53^2 × 61^2 × 3447462796704049 × 5727587968673383 × 1268308304122464625046493317 × 
184260620206042978762699655820078745825674933355322819831458784537916012821252880824419 
n + 6 = 2^2 × 19^4 × 71^2 × 73^2 × 83^2 × 740461 × 41526439 × 42903098550452838089217670693 × 
9859675755920210092335653412525696300235835558428564014026008821180589123201408504641679473403395645263

И еще пара обновлений:

$M(672) \ge 8$

(Оффтоп)

n = 1858798988492338083552605815500142567539365990586231151230145237275915677079848714903684109375

$M(3888) \ge 8$

(Оффтоп)

n = 765781835700096628090651101804814525529336349984754196245604774675376177485012728263220455001019758986446817385368969738789702348073240899999998

Для этих цепочек все проверочные разложения выполняются легко (что для второго числа довольно неожиданно).

[Dmitriy40]

VAL
Возвращаясь к детерминированности ECM (гарантирует ли отсутствие делителя в заданном диапазоне). В одной из статей (на неё и вики ссылается) обнаружил фразу (внизу стр.98) :

Цитата:

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

Получается информация в разных источниках разнится.

-- 12.09.2025, 22:40 --

Ещё порадовала фраза из результатов про QS (квадратичного решета, в пересказе) "линейного ускорения от многопоточности достигнуть не удалось так как ... метод работал достаточно быстро и в один поток".

-- 12.09.2025, 23:09 --

А в описании к YAFU есть такие фразы:

Цитата:

A note on the “t-level” terminology used in factor(). Something that has
received, say, "t30", has had enough ecm curves run on it so that the probability
that a factor of size 30 has been missed is exp(-1) (about 37%). Likewise,
t35 indicates that factors of size 35 are expected to be missed about 37%
of the time (at which point a 30 digit factor would only be expected to be
missed ~5% of the time).

Т.е. вероятность пропуска делителя (на стадии ECM) очень даже не нулевая, а аж треть.

[Dmitriy40]

Ещё информация, другая реализация ECM:

       digits D  optimal B1   default B2           expected curves
                                                       N(B1,B2,D)
                                              -power 1         default poly
          20       11e3         1.9e6             74               74 [x^1]
          25        5e4         1.3e7            221              214 [x^2]
          30       25e4         1.3e8            453              430 [D(3)]
          35        1e6         1.0e9            984              904 [D(6)]
          40        3e6         5.7e9           2541             2350 [D(6)]
          45       11e6        3.5e10           4949             4480 [D(12)]
          50       43e6        2.4e11           8266             7553 [D(12)]
          55       11e7        7.8e11          20158            17769 [D(30)]
          60       26e7        3.2e12          47173            42017 [D(30)]
          65       85e7        1.6e13          77666            69408 [D(30)]

          Table 1: optimal B1 and expected number of curves to find a
          factor of D digits with GMP-ECM.

After performing the expected number of curves from Table 1, the
probability that a factor of D digits was missed is exp(-1), i.e.,
about 37%. After twice the expected number of curves, it is exp(-2),
i.e., about 14%, and so on.

Example: after performing 8266 curves with B1=43e6 and B2=2.4e11
(or 7553 curves with -dickson 12), the probability to miss a 50-digit
factor is about 37%.

Т.е. даже после проверки указанного количества кривых вероятность пропуска делителя составляет 37%.

Числа из правой колонки (74, 214, 430, 904, 2350) кстати видны (и на экране и в логе) при работе YAFU когда она делает претест методом ECM.

-- 13.09.2025, 14:07 --

Ради интереса запустил этот другой ECM тест для числа (которое уже почти неделю считается методом NFS, 3ГБ данных нагенерило, если правильно догадался, то надо ещё часов 10)

(Длинное число 149 цифр)

55662212514374333854411247602870129064983737899272183727285204718917424705504387281480220130365957114197485014500556797138352686863076223979929623467

с B1=1e7, работала 24с (по одной кривой) и, что и интересно, выдала ожидаемое время поиска делителя:

Expected number of curves to find a factor of n digits:
35      40      45      50      55      60      65      70      75      80
144     835     5613    43291   374852  3596840 3.8e+07 4.3e+08 5.5e+09 7.2e+10
...
Expected time to find a factor of n digits:
35      40      45      50      55      60      65      70      75      80
58.99m  5.70h   1.60d   12.31d  106.60d 2.80y   29.61y  335.28y 4253y   56455y

Т.е. за полтора дня (в одном потоке) можно обнаружить делитель до кубического корня, а вот найти методом ECM любой из двух делителей практически нереально.