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

[Huz]

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

Хуго обновил файл 14 июня, но в него не вошли цепочки длинной 7 и 8 на 84 делителя, которые нашел Дмитрий сразу, как сделал ускорители на 84 делителя.

I haven't seen those, can you point me at the message?

Цитата:

I think I've proven M(84) <= 21, I'll see if I can work out where that came from.

For $M(84) \ge 22$, we are constrained to have:
- no value 24 (mod 32) or 16 (mod 32)
- no value 30 (mod 36)
- no value 40 (mod 48)
- no value 42 (mod 72) or 66 (mod 72)

I believe that covers all possibilities, so $M(84) \le 21$.

[EUgeneUS]

Huz в сообщении #1557713 писал(а):

I haven't seen those, can you point me at the message?

It was here in the off-topic tag.

[Dmitriy40]

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

(В частности, мне казалось, что цепочку из 11 чисел по 60 делителей мы нашли, но я не нашел сообщения о том, что мы ее нашли )

Вот:

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

Нашлась ещё одна 11-ка на делителей.

При просмотре найденных 8-к. Нашлась кандидатная в 11-ки (в 107е82).

L4-374:1073464368467510673718389440406762554155813393898734560563445827897753610345174122491:  0, 60,  0, 60, 60, 60, 60, 60, 60, 60, 60,  valids=9, maxlen=8, ALL, FOUND!

Проверка показали, что вместо нулей - правильные 60-ки. Но всё таки прошу перепроверить.

Снизу до это 11-ки у меня не посчитано три круга по 1е82, которые досчитаются часа через 4-5.

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

Подтверждаю:

1073464368467510673718389440406762554155813393898734560563445827897753610345174122491
+0:60   [13, 4; 41, 2; 662887620736492266347, 1; 33729243606242474655632485340966479200098121800448422033, 1]
+1:60   [2, 2; 31, 4; 7339571, 1; 39592250699095497684683690041641901985917920955593821543111109138443653, 1]
+2:60   [3, 4; 47, 2; 7277484263660982902234651, 1; 824376539055533281907121702882630599072705007893811767, 1]
+3:60   [2, 1; 23, 4; 61, 2; 515450094648426918179290702936591526041177653141335054528399663874545895527, 1]
+4:60   [5, 1; 29, 4; 67, 2; 67620134790243669112668668881439068140999705545246005682886225971244044011, 1]
+5:60   [2, 14; 3, 1; 21839688486074029006314889331192272016516385780817353527088334714716666877139773, 1]
+6:60   [7, 4; 43, 2; 12460967, 1; 19404694794397553877010605075520300192706802664354975624471778233158959, 1]
+7:60   [2, 1; 19, 4; 53, 2; 1466194191908009955009644901011127569272112427545215823236532541441293498041, 1]
+8:60   [3, 1; 17, 4; 59, 2; 1230741003798957157236158053599361522144934426859147053823523499079215933033, 1]
+9:60   [2, 2; 5, 4; 1117, 1; 384409800704569623533890578480487933448814107036252304588521334967861633068997, 1]
+10:60  [11, 4; 37, 2; 43777, 1; 1223397104450063693092212012224224426794517196786386065925298538629031197, 1]
19min, 22,956 ms

[Dmitriy40]

Если браться за сложную задачу, то я бы предпочёл искать пятнашку с 36 делителями, по крайней мере можно точно доказать верхнюю границу. Но какие группы паттернов там более перспективны я не знаю (а сделать ускорители на все комбинации, как было с 12-ю делителями, невозможно). В конце апреля уже пытался это считать, по паттернам VAL, числа порядка $10^{85}$, но за 4 потоко-суток счёта не было даже ни одной цепочки ALL с 10-ю проверяемыми числами, не говоря уж про кандидатов в 14 или 15, 10 проверяемых чисел в таком диапазоне слишком редки оказываются.

[EUgeneUS]

Huz
The $n+0$ for $(84, 10, 850...492)$ was factorized in the PARI/GP. Check, please.

(Result)

[2, 2; 31, 6; 31154486779520765415558794143312798051383856489, 1; 7686432755996636863062215476182853500475978363999847, 1]
850110906168382371216057545387082625772983773608338698713882862297162247190308993041704075477374723603562492

Что касается поиска 11-ки для 84 делителей. У меня досчитается до 1300e105 за день-два, после чего остановлю.
Числа становятся уже такие длинные, что, даже если найдутся кандидаты в 11-ку (что вполне вероятно за несколько недель счёта), то может оказаться так, что как минимум одно неразложившееся число будет иметь произведение больших простых знаков по 50. А искать их примерно тоже самое, что взламывать RSA с 256-битным ключом

Кстати, для другого кандидата в 10-ку два неразложившихся числа у меня разлагаются уже более недели безрезультатно.

11-ку можно было бы поискать, если паттернов будет много (тысячи), и снова пройтись по низинам до 1000e105.

-- 17.06.2022, 17:15 --

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

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

"Я за любой кипиш, кроме голодовки"

Но, имхо, поиск 14-ки, а тем более 15-ки для 36 делителей за разумное время при наличных мощностях выглядит сомнительным
Надо переманить уважаемого VAL "на тёмную сторону силы"

[Huz]

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

Huz в сообщении #1557713 писал(а):

I haven't seen those, can you point me at the message?

It was here in the off-topic tag.

Thanks, filed for the next update.

-- 17.06.2022, 15:03 --

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

The $n+0$ for $(84, 10, 850...492)$ was factorized in the PARI/GP. Check, please.

Thanks, confirmed - and congratulations (with apologies for the delay). :)

[Dmitriy40]

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

Числа становятся уже такие длинные, что, даже если найдутся кандидаты в 11-ку (что вполне вероятно за несколько недель счёта), то может оказаться так, что как минимум одно неразложившееся число будет иметь произведение больших простых знаков по 50. А искать их примерно тоже самое, что взламывать RSA с 256-битным ключом

Если кандидатов в 11-ку будет много (десятки), то среди них могут быть и с не слишком большим одним из делителей, цифр в 20, такие PARI разложит быстро.
Другой вариант: делать все числа проверяемыми, тогда достаточно isprime, но вероятность нахождения цепочек снижается (ещё и числа немного подрастают, на несколько порядков).
Для больших чисел (сотня цифр и более) трудно сказать что выгоднее, у меня вон 164 делителя под 240 цифр шестёрки нашлись за несколько часов что так что так, а семёрки уже две недели нет ни так ни так.

-- 17.06.2022, 19:04 --

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

11-ку можно было бы поискать, если паттернов будет много (тысячи), и снова пройтись по низинам до 1000e105.

Так ведь паттернов уже и сейчас 4608 ... Можно конечно сделать и 20млн паттернов (с одинаковым шагом/модулем), но это объём (1300ГБ) и время компиляции (месяца четыре) — считаю это нереальным.

-- 17.06.2022, 19:07 --

VAL
Кстати да, та 11-ка не первая, первая была тут.

[VAL]

Нашлась семерка по 364 делителя. (В который раз самый медленный из компов в моем распоряжении опередил более быстрые. Может, на остальных счет свернуть? )

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

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

(В частности, мне казалось, что цепочку из 11 чисел по 60 делителей мы нашли, но я не нашел сообщения о том, что мы ее нашли

Она у меня нашлась, и обязательно было сообщение в этой теме. Кстати, она есть в файле Хуго с датой 18-05-2022, соответственно, близко к этой дате и было сообщенние о нахождении от меня.

Отлично!
Обновил таблицу. Теперь все максимальные цепочки имеют разную длину
А еще снял знак вопроса с $L(84)$. Кстати, 850...492 у меня так и не досчиталось

[EUgeneUS]

Huz

(Оффтоп)

Huz в сообщении #1557765 писал(а):

(with apologies for the delay)

The delay was a problem on the my side because I didn't execute factor() immediately after the 1st success numdiv()

-- 17.06.2022, 19:31 --

Dmitriy40
Кстати, а вот тут

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

Если браться за сложную задачу,

что понимается под сложной задачей?

Если имеется в виду вычислительная сложность. То улучшить на 1-2 позиции цепочки с 24 и 48 делителями и на 2-4 позиции цепочки с 72 и 96 делителями не представляется сложным. В том смысле, что с ускорителями это подъёмно за 1-3 недели на каждое количество делителей. Оценки очень грубые, конечно.

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

-- 17.06.2022, 19:39 --

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

Если кандидатов в 11-ку будет много (десятки), то среди них могут быть и с не слишком большим одним из делителей, цифр в 20, такие PARI разложит быстро.

Сложно ожидать десятки кандидатов за разумное время.
За 2 недели у меня было два кандидата в 10-ки (один сработал, по второму тяжелые числа не разложились), и один кандидат в 11-ку, но он не сработал, там фактическим оказалась 9-ка.

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

Так ведь паттернов уже и сейчас 4608 ... Можно конечно сделать и 20млн паттернов (с одинаковым шагом/модулем),

Тут, конечно, нужен какой-то разумный компромисс. Но 15-ку на 12 делителей искали на 40 тысячах паттернов. А это уже в 10 раз больше. А значит и кандидаты будут находится в 10 раз чаще (в фиксированном диапазоне чисел - в том числе в низинах, а не за заданное время). Но это если дальше этой задачей заниматься, конечно.

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

[Yadryara]

EUgeneUS, VAL, проздравляю с находками !

Давно здесь не писал, но никуда не пропал. Комп считает то же что и раньше.

[Dmitriy40]

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

что понимается под сложной задачей?

Та что займёт недели-месяцы счёта.

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

Но 15-ку на 12 делителей искали на 40 тысячах паттернов. А это уже в 10 раз больше. А значит и кандидаты будут находится в 10 раз чаще (в фиксированном диапазоне чисел - в том числе в низинах, а не за заданное время).

Но и паттернов будет в 10 раз больше и значит тот же диапазон чисел будет перебираться в 10-11 (не забываем про накладные расходы на вызов ускорителей) раз медленнее, в результате частота нахождения кандидатов (шт/месяц) может остаться той же ... Тут вопрос уже скорее везения.
Раз за две недели счёта не появилось даже двух кандидатов на 11-ку, то можно считать эту задачу сложной и поискать пока более лёгкие задачи.

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

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

Тут сложность в трёх вещах: а) выбрать группу паттернов; б) накомпилить ускорителей (вот M84n11 компилились 2000шт/час как видно по датам файлов); в) тестовый запуск, подбор шага проверки и прочих констант, алгоритма допроверки в PARI, запаковать и выложить. После выбора паттернов остальное занимает несколько часов (плюс время компиляции). 46080 паттернов для M12n15 компилились быстрее так как там порог простых был меньше и соответственно таблицы короче и потому PARI программа генерации таблиц выполнялась существенно быстрее, тут же снижать порог от 32768 нет никакого смысла. Да, это всё неоптимально и надо бы переписать, но время ... не до того.

[EUgeneUS]

Huz
About this place in the a-file:

# L(35) in range 3..4

As I wrote later we proved that $M(k) \le 3$ if $k=2pq$, where $p, q \ge 5 $ are primes.
We are planning to publish article in the arXiv this result with some other theoretical results. But it may takes for a long time.
If you have a interest I can try translate this proof to the English (with Google translator and my poor English )

-- 17.06.2022, 20:30 --

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

Раз за две недели счёта не появилось даже двух кандидатов на 11-ку, то можно считать эту задачу сложной и поискать пока более лёгкие задачи.

Согласен.

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

Тут сложность в трёх вещах: а) выбрать группу паттернов;

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

VAL
Скажите, пожалуйста, не будет ли Вам сложно сделать системы паттернов для (ещё) не найденных цепочек на 24, 48, 72 и-или 96 делителей?

[Huz]

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

As I wrote later we proved that $M(k) \le 3$ if $k=2pq$, where $p, q \ge 5 $ are primes.
We are planning to publish article in the arXiv this result with some other theoretical results. But it may takes for a long time.
If you have a interest I can try translate this proof to the English (with Google translator and my poor English )

I'm definitely interested - I think I've seen parts of it in the forum already, but I wasn't able to find the full proof in one place.

[EUgeneUS]

Huz
The link to the pdf with draft (in Russian) of the whole proof was published in this post
Well, I'll try to translate it to English with some style corrections.

[VAL]

Нашлась пятерка по 318 делителей (после изгнания троек стартовое число этой пятерки стало самым большим в полной таблице).

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

VAL
Скажите, пожалуйста, не будет ли Вам сложно сделать системы паттернов для (ещё) не найденных цепочек на 24, 48, 72 и-или 96 делителей?

Сделаю, конечно!