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

[VAL]

$M(288)\ge 11$

(Оффтоп)

1420180697852173297985681539017661191839460656266755747591539040550140

По-прежнему ускользает цепочка по 192 делителя. Других новых $k$ пока в разработке нет.

[VAL]

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

I found that showing $M(60) < 24$ required checking 7-smooth moduli up to 784[..]

Thanks!
I've understood (or I think, I've understood )

[mathematician123]

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

Set 3: 0 mod 210 > 360150; 0 mod 420 > 144060; 0 mod 480 > 245760; 0 mod 630 > 216090; 0 mod 672 > 344064.

It looks like checking 0 mod 420 and 0 mod 630 are not needed, because they are covered by checking 0 mod 210.

[Huz]

mathematician123 в сообщении #1559811 писал(а):

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

Set 3: 0 mod 210 > 360150; 0 mod 420 > 144060; 0 mod 480 > 245760; 0 mod 630 > 216090; 0 mod 672 > 344064.

It looks like checking 0 mod 420 and 0 mod 630 are not needed, because they are covered by checking 0 mod 210.

Yes, I didn't try to minimize it - I'm sure a much smaller set of constraints would be enough to prove it. I've been thinking about writing code to find a minimal set of constraints, but I'm not sure there's much additional value.

Note however that 420 and 630 are valid from a lower limit than 210, so they do actually give a bit more information (unlike, for example, 30 mod 72 from the second set which is entirely redundant after 30 mod 36 has been ruled out).

[VAL]

Наконец-то пало последнее $k$ из списка ранее запланированных. $M(192)\ge 12$

(Оффтоп)

13703205113201047361251765256017663365003499478698928120

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

[VAL]

К статье.
Прикинул Absract. Он получается сильно похож на аннотацию к нашей с Василием статье. Что естественно: мы ведь просто продвинулись дальше в том же направлении (тех же направлениях).

Цитата:

We improve upper bounds for the length of runs of consecutive positive integers each with exactly $k$ divisors for some given classes of even $k$ and some concrete values of $k$. We have found exact values of the maximum possible runs for many fixed values of $k$. In particular, we exhibit the run of 15 consecutive positive integers each with exactly 12 divisors. Also we have found the long runs of consecutive equidivisible integers for some $k$, including the longest (to date) run of 20 consecutive numbers with 48 divisors.

Чуть подробнее.
После введения пойдут оценки сверху для $M(12t\pm 2)$ и $M(12t+6)$ (это вотчина Дениса и Евгения). При этом длинное доказательство $M(2pq)\le3$ будет вынесено в отдельную статью, а в нашей мы на нее сошлемся и приведем схему доказательства (мы с Евгением и Денисом согласовали этот момент).
Далее напишем об обесценивании (в свете новых теоретических результатов) конкретных троек и приведем полные списки тех $k$, для которых доказано $M(k)=5$ и $M(k)=7$

В следующем разделе планируется привести улучшенные верхние оценки для конкретных $k$, кратных 12, полученные Hugo.
Hugo, we will glad to see You among the authors.

Далее расскажем о том, как удалось доказать $M(12)=15$. Здесь на авансцену выходит Дмитрий. Полагаю, следует остановиться на математической идее ускорителей, а программистские тонкости осветить обзорно. Впрочем, тут последнее слово за Дмитрием.

Далее напишем, что наиболее значительный эффект ускорители дают, когда для большого количества чисел в искомой цепочке осуществляется проверка на простоту. В нашем случае, это числа сравнимые с 12 по модулю 24. Для чисел кратных 24 эффект меньше. В частности, рекордные цепочке для них, представленные в приводимой таблице, получены без применения ускорителей. Но, возможно, применение ускорителей позволить улучшить и эти рекорды.

Далее приводим цепочку из 20 чисел по 48 делителей и отмечаем, что это самая длинная на сегодняшний день цепочка. Наверное, следует привести и первое число для цепочки из 18 чисел по 24 делителя (разумеется, ранее уже приведено число, открывающее цепочку из 15 чисел по 12 делителей, а может и вся цепочка). Остальные длинные цепочки представлены только своими $k$ и $L(k)$ в таблице.

В заключение приводим гипотетические утверждения и отмечаем, какие их них станут доказанными при условии справедливости abc-гипотезы, гипотезы Диксона, гипотезы Шинцеля...

Полагаю авторский коллектив должен состоять из 6 человек: Антон, Денис, Дмитрий, Евгений, Hugo и ваш покорный слуга.
В проекте статьи не нашлось места конкретике от Антона (про минимальные цепочки речь не ведется), но я уверен, что без координирующей роли Антона наш авторский коллектив не сложился бы в принципе. А без его дотошности среди наших результатов было бы в разы больше ошибок, чем сейчас.

Отдельная статья про $M(2pq)\le3$ практически готова.
Впрочем, и основная тоже. Осталось только написать

[Dmitriy40]

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

Далее напишем, что наиболее значительный эффект ускорители дают, когда для большого количества чисел в искомой цепочке осуществляется проверка на простоту. В нашем случае, это числа сравнимые с 12 по модулю 24. Для чисел кратных 24 эффект меньше.

Первое предложение верно, второе и третье нет. Например для 24 делителей существуют паттерны длиной 31 число и с 23 проверяемыми числами и всего с 6-ю (и тех и других десятки). Так что количество проверяемых чисел зависит не только и не столько от $k$, сколько от конкретного варианта расстановки малых простых.

Плюс максимальный эффект ускорителей совершенно не обязательно конвертируется в минимальное время нахождения решения: сами же знаете что вероятность найти конкретный вариант (фиксированные малые простые и одно огромное искомое) сильно меньше найти один из триллионов возможных вариантов (несколько больших простых). Так что зависимость пользы от ускорителей сложнее, не просто линейная, а сначала с ростом количества проверяемых чисел растёт, но потом падает. И где находится оптимум зависит от очень многих факторов, из которых $k$ не самый важный.

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

Далее расскажем о том, как удалось доказать $M(12)=15$. Здесь на авансцену выходит Дмитрий. Полагаю, следует остановиться на математической идее ускорителей, а программистские тонкости осветить обзорно.

Вот тут немного не понял: где там математика-то? Как только дошли до формул $p=p_0+km$ так вся математика закончилась и дальше уже именно программистские соображения по эффективному их вычислению.
Другое дело что разумеется код приводить нет необходимости, да и совсем уж мелкие (но полезные) оптимизации упоминать, остановиться на общих моментах.
Я себе это вижу как отдельный небольшой (пара-тройка абзацев, полстранички) раздел про эффективный поиск (вычисление) цепочек. Но доказывать в нём переход от коэффициентов в паттерне к формуле $p=p_0+km$ через КТО меня как-то напрягает (не уверен что осилю), тут надеюсь скорее на вас.

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

Наконец-то пало последнее $k$ из списка ранее запланированных.

Кстати, давно хотел спросить: а почему получаются пропуски, не все $k$ проверены? Например не найдены $k=156, 204, 228, 252, 264, 276, 300$. То же $k=156$ не должно быть сильно сложнее $k=132$, всего лишь степень повысить с 10 до 12 ...

[Huz]

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

Hugo, we will glad to see You among the authors.

Sure; I'm not sure how best to make that work, but I can try to write up a description of the various types of constraint for which my program searches, and maybe a brief description of how it combines those to come to a conclusion. Is it the plan to produce a paper in Russian, or simultaneously also in English?

[EUgeneUS]

В проекте в Papeeria сделал четыре каталога:
1. "M(2pq) <= 3 eng" - черновик статьи по этой теме. Английский вариант.
2. "M(2pq) <= 3 rus" - черновик статьи по этой теме. Русский вариант.
3. "M(k) Common eng" - черновик "общей" статьи. Английский вариант.
4. "M(k) Common rus" - черновик "общей" статьи. Русский вариант.

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

Дмитрий (Dmitriy40), Hugo (Huz), Антон Yadryara - просьба сообщить свой электронный адрес (мне в личные сообщения на форуме), на котором зарегистрирован ваши аккаунты в Papeeria. Я включу вас в коллаборацию проекта.

-- 10.07.2022, 15:49 --

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

Is it the plan to produce a paper in Russian, or simultaneously also in English?

Purpose - placement on the arXiv, so the final version should be in English. We wrote in Russian and then translated into English. I think it will be right if you write immediately in English.
We will translate your part into Russian if necessary.

[VAL]

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

Sure; I'm not sure how best to make that work, but I can try to write up a description of the various types of constraint for which my program searches, and maybe a brief description of how it combines those to come to a conclusion.

I think. this is what we need.

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

Is it the plan to produce a paper in Russian, or simultaneously also in English?

EUgeniUS has already answered.

-- 10 июл 2022, 16:54 --

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

Первое предложение верно, второе и третье нет. Например для 24 делителей существуют паттерны длиной 31 число и с 23 проверяемыми числами и всего с 6-ю (и тех и других десятки). Так что количество проверяемых чисел зависит не только и не столько от $k$, сколько от конкретного варианта расстановки малых простых.

Плюс максимальный эффект ускорителей совершенно не обязательно конвертируется в минимальное время нахождения решения: сами же знаете что вероятность найти конкретный вариант (фиксированные малые простые и одно огромное искомое) сильно меньше найти один из триллионов возможных вариантов (несколько больших простых). Так что зависимость пользы от ускорителей сложнее, не просто линейная, а сначала с ростом количества проверяемых чисел растёт, но потом падает. И где находится оптимум зависит от очень многих факторов, из которых $k$ не самый важный.

Я понимаю, что все тоньше, чем я написал. Но если бы я описал все тонкости (притом что я не уверен, что это должен делать я), то это была бы уже не программа действий, а готовая статья. Про значимость $k$ напишу отдельно.

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

Вот тут немного не понял: где там математика-то? Как только дошли до формул $p=p_0+km$ так вся математика закончилась и дальше уже именно программистские соображения по эффективному их вычислению.

На термине "математика" не настаиваю. Пусть будет идейная составляющая механизма оптимизации (во завернул! ).

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

Кстати, давно хотел спросить: а почему получаются пропуски, не все $k$ проверены? Например не найдены $k=156, 204, 228, 252, 264, 276, 300$

Я полагал это понятно.

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

о же $k=156$ не должно быть сильно сложнее $k=132$, всего лишь степень повысить с 10 до 12 ...

Вот именно! Уже для 10-х степеней проверяемые числа становятся так велики, что факторизацию приходится заменять проверкой на простоту, искусственно домножая модули на относительно большие простые числа (маленькие-то уже заняты под 10-е степени).
Для $k=156$ 10-е степени придется заменить на 12-е, числа, проверяемые на простоту, станут еще больше, а значит, вероятность их простоты еще меньше. Поэтому без ускорителей поиск затянется.
Вот с ускорителями, полагаю, реально найти цепочки для 156, 252, 300 и удлинить цепочки для 108, 132 и 180 за приемлемое время (кстати, это все цепочки для $k$, сравнимых с 12 по модулю 24). Для остальных $k$ из Вашего списка, боюсь, и ускорители будут бессильны. Впрочем, это все на глазок. Можно найти эмпирические вероятности и сказать точнее.

[Dmitriy40]

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

Вот именно! Уже для 10-х степеней проверяемые числа становятся так велики, что факторизацию приходится заменять проверкой на простоту, искусственно домножая модули на относительно большие простые числа (маленькие-то уже заняты под 10-е степени).

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

-- 10.07.2022, 18:04 --

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

Для $k=156$ 10-е степени придется заменить на 12-е, числа, проверяемые на простоту, станут еще больше, а значит, вероятность их простоты еще меньше.

Ну, числа (для цепочки длиной 8) увеличатся в $(2\times3\times5\times7\times11\times13\times17\times19)^{12/10}\approx2.4\cdot10^8$ раз, вероятность цепочки снизится в 1.8 раза, не так уж кардинально. Вот дальше да, согласен.

[VAL]

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

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

Я тоже применял такой подход.
Но понятно же, что с ростом чисел ждать придется все дольше.

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

вероятность цепочки снизится в 1.8 раза, не так уж кардинально

Да. Именно поэтому я и написал

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

В процессе поиска стало ясно, что реально найти длинные цепочки еще для нескольких значений $k$.

-- 10 июл 2022, 18:45 --

Про связь эффективности ускорителей для длинных цепочек с делимостью $k$ только на 12 или и на 24.

Я согласен, что этот фактор не единственный. Но в пользу его значимости убедительно говорит статистика. Из наидлиннейших цепочек для разных $k$ с помощью ускорителей найдены цепочки для 12, 36, 60 и 84. Все они имеют вид $12+24t$. Более того, я уверен что рекорды для 108, 132 и 180 найдены без ускорителей только по той причине, что их с ускорителями никто не искал.
(Кстати, настоятельно рекомендую поискать. А то таблица $k$, для которых найдены длинные цепочки, в графе "Found by" смотрится как-то уныло )

Разумеется, и для $k$, кратных 24, возможно улучшение рекордов за счет использования ускорителей. Но тут усилий потребуется несравненно больше.

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

[..] для 24 делителей существуют паттерны длиной 31 число и с 23 проверяемыми числами и всего с 6-ю (и тех и других десятки)

Интересно глянуть. Приведите.
У меня сохранился паттерн (примерно 6-летней давности) для 31 числа с 24 делителями. Сейчас взглянул - там 16 проверок на простоту. Попытался сделать поменьше - легко довел до 10. Вижу как наоборот увеличить примерно до 20.
Но как довести до 6 или наоборот до 23 - не вижу.
(Разумеется, речь не идет об искусственном накручивании степеней и добавлении лишних множителей в первой степени или наоборот отсутствии квадратов в каких-то позициях в надежде, что они случайно появятся сами.)

[Dmitriy40]

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

Интересно глянуть. Приведите.

Два первых попавшихся:
$N,50pq,2523pq,28pq,N,18pq,5pqr^2,8pq^2,363pq,338pq,2023pq,60p,361pqr,1058pq,243pq,32pq$,$5pqr^2,294p,N,44pq,3pqr^2,10pq^2,13pqr^2,72p,7pqr^2,2pqr^2,75pq,68pq,N,6pq^2,11pqr^2$ - N это совсем пустые места, в них и квадраты надо расставить 14 простых и получится 6 проверяемых чисел (только $p$) из 31.
$29^{11}p,150p,N,532p,3\times23^5p,2\times11^5p,5\times13^5p,72p,N,2pqr^2,21pq^2,340p,N,6pq^2,N,2^{11}p$,$495p,14pq^2,N,156p,N,10pq^2,3\times19^5p,8pq^2,7^{11}p,486p,5^{11}p,1012p,3\times17^5p,58pq^2,N$ - аналогично после расстановки 14 простых станет 23 проверяемых числа.

-- 10.07.2022, 19:30 --

Интересно что во всех паттернах с 6-ю проверяемыми одно из них стоит совсем на краю и если паттерн чуть подрезать, то останется всего 5 проверяемых чисел, вплоть до длины 29 чисел. И все они скучкованы в центре, шириной лишь 17 чисел. Т.е. в принципе можно искать цепочки от 17 до 29 чисел лишь с 5-ю проверяемыми.

PS. Да, переписывал руками из лога генератора паттернов, мог где-то опечататься.

[VAL]

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

Два первых попавшихся

Спасибо!
С 6-ю проверками понятно.
А с 23-я применено то самое искусственное накручивание степеней, о котором я писал.

-- 10 июл 2022, 20:25 --

$M(96)\ge13$
Ну или $T(48,13) \le 10157463065456316021274796423722774864181244$ если угодно.
Числа в цепочке относительно небольшие. Наверняка можно и еще удлинить.

[Huz]

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

$M(96)\ge13$
Ну или $T(48,13) \le 10157463065456316021274796423722774864181244$ если угодно.

Congrats - and smaller than known values for 11 and 12 too. :)