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

[Dmitriy40]

VAL
Держите, ровно по Вашему паттерну для $k=132$, хватило пары часов счёта в один поток (хотя $k=132$ с меньшей величиной нашлась за 40 минут):
$M(156)\ge8$:

(Оффтоп)

184765725510622981997339725582495167558850184262092026705051892231177342492648907795981988607883040618900509277343744

[VAL]

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

VAL
Держите, ровно по Вашему паттерну для $k=132$, хватило пары часов счёта в один поток (хотя $k=132$ с меньшей величиной нашлась за 40 минут):
$M(156)\ge8$:

(Оффтоп)

184765725510622981997339725582495167558850184262092026705051892231177342492648907795981988607883040618900509277343744

Отлично!
Все согласно прогнозу. Но быстрее, чем я ожидал.
Так и 204 может пойматься.

-- 11 июл 2022, 00:14 --

Выкладываю таблицу для поиска цепочки из 9 чисел по 180 делителей.
По ожидаемому количеству проверок прогноз благоприятный.
Но факторизация будет притормаживать.
Возможно, имеет смысл ограничивать ее по времени, дожидаясь благоприятных случаев.
А может быть, стоит добавить три множителя, чтобы во всех 9 позициях проверять на простоту.

[mathematician123]

VAL
$M(132) \le 21$ и $M(156) \le 21$. Доказательство такое же как и в случае $k = 84$. То есть, $M(k) \le 21$, если $k \equiv 4 \pmod{8}$ и $k$ не делится на 5.

[VAL]

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

$M(132) \le 21$ и $M(156) \le 21$. Доказательство такое же как и в случае $k = 84$

Как раз, собирался задаться этим вопросом. Вы меня опередили.

-- 11 июл 2022, 00:38 --

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

То есть, $M(k) \le 21$, если $k \equiv 4 \pmod{8}$ и $k$ не делится на 5.

Но лучше все же написать: $M(k) \le 21$, если $k \equiv 12 \pmod{24}$ и $k$ не делится на 5.
Для остальных оценка, конечно, тоже верна, но сильно завышена

-- 11 июл 2022, 01:01 --

Изготовил таблицу для желающих поискать девятку по 132 делителя. А может, и по 156

[EUgeneUS]

По поиску цепочки 21 на 48 делителей.
Примено за полторы недели просчиталось до 550e52, после чего счеты остановил.
Наблюдения за результатами такие:
1. До 300е52 довольно часто встречаются цепочки с

valids = 10

, но небольше. Было порядка 1-2 десятков.
2. После 300e52 цепочки

valids >=10

встречаются крайне редко. Но там была цепочка с

valids=14

, и это рекорд.
3. На втором проходе проверки цепочки бракуются по неподходящим числам почти всегда находящимся в первой половине. Это с одной стороны - не удивительно, так как проверка во втором проходе начинается слева. Но удручает, так как проверка дальше половины цепочки никогда не проходит
4. По грубым прикидкам для нахождения цепочки из 21 делителя за разумное время нужно сильное увеличение мощностей. На порядок, а лучше на два.
5. Или более внимательно посмотреть на паттерн, и там что-то поправить.

При поиске 20-ки на 48 делителей по программам уважаемого VAL без ускорителей и примерно вдвое меньшими мощностями, нашлась одна цепочка на 18 подошедших чисел, и несколько на 17. А тут даже такого нет.

Если у кого-то будет желание посмотреть на статистику - могу выложить логи на dropbox.

[VAL]

$M(240)\ge11$

(Оффтоп)

53606077646947080279175185156757665904278172728867836847860251242062936930270213376458750

-- 11 июл 2022, 11:18 --

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

По поиску цепочки 21 на 48 делителей

Рекомендую (хотя бы временно) переключиться на более реалистичные задачи.
Я выкладывал довольно много таблиц с шаблонами паттернов. С хорошими прогнозами получения соответствующих цепочек за приемлемое время.
Для части из них, AFAIR, Дмитрий сделал программы. Сейчас уже точно не помню для каких. Но он, наверное, помнит (да и теме инфа где-то есть).

[Dmitriy40]

$M(132)\ge9$:

(Оффтоп)

1492528153239676641134781494617568263978916682787474567227693728415576746670484477977554685472370753315893574218748

[EUgeneUS]

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

Я выкладывал довольно много таблиц с шаблонами паттернов. С хорошими прогнозами получения соответствующих цепочек за приемлемое время.

Последовательность $k=12n$ - бесконечна. Поэтому я поставил для себя "границу интересов" - до $k=100$ , может быть с некоторыми дополнительными $k>100$, где будет реально найти самую длинную цепочку (но пока $k=48$ вне конкуренции в этом смысле).

По цепочкам с 48-ю делителями. Всё таки довольно странно, что при поиске 20-ки без ускорителей у меня находились и 17-ки, и даже одна 18-ка. А с ускорителями при поиске 21-ки, только 14-ка в единственном экземпляре.
Понятно, что если упереться и посчитать числа, для которых количество делителей не определено, то там будет не 14-ка, а больше. Но всё таки...
Может какой-то переход "количества в качество", как для 36 делителей при переходе от 13-ки к 14-ке и пятнашке. Может ещё что.

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

Для части из них, AFAIR, Дмитрий сделал программы.

Не помню, чтобы Дмитрий выкладывал ускорители для новых цепочек после ускорителей для 48 делителей. Могш пропустить, конечно.

[mathematician123]

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

Создал проект в Overleaf: https://www.overleaf.com/read/xnyryzfvyjrj
.

Доделал раздел с утверждениями. Теперь там собраны все верхние оценки для $M(k)$, доказанные на данный момент. Если заметите, что я что-то упустил, пишите, исправлю.

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

Рекомендую (хотя бы временно) переключиться на более реалистичные задачи

А насколько реально найти 16 чисел, имеющих по 60 делителей (если такие цепочки вообще существуют)? У меня есть гипотеза, что в случае $k \equiv 12 \pmod{24}$ цепочки длиной 16 и больше возможны только если $k$ делится на 5. А для $k = 60$ ограничений гораздо меньше и существование 16 последовательных чисел, имеющих по 60 делителей, выглядит вполне возможным.

[EUgeneUS]

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

Если заметите, что я что-то упустил, пишите, исправлю.

1. Думаю, нужно также разместить результаты, которые были получены ранее, но которые перекрываются результатами, полученными в этой теме, но ещё не опубликованными. В частности:
$M(2p) \le 3$ for all prime $p > 3$
$M(2pq) \le 3$ for all primes $p, q$ such that $gcd(p-1,q-1) > 4$
$M(6p) \le 5$

2. Гипотезы:
$M(2pq) \le 3$ for all prime $p,q > 3$
$M(k) \le 3$ for $k = \pm 2 \pmod{12}$
$M(k) \le 5$ for $k = 6 \pmod{12}$

Были явно высказаны Владимиром где-то в недрах этой темы (а может быть и ранее). ИМХО, это тоже нужно отметить в Вашей сводке, несмотря на то, что две из них доказаны, а третья доказана частично.

-- 11.07.2022, 13:46 --

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

А насколько реально найти 16 чисел, имеющих по 60 делителей (если такие цепочки вообще существуют)?

1. По очень грубой прикидке, каждое новое число в цепочке трубует увеличения вычислений в 10 раз.
2. Сейчас найдена 11-ка, она искалась с ускоритиелями в течение 1-2 недель. Вычислительная мощность: 3-4 декстопа, не самых современных. Всего было около 10-12 потоков.
3. Надо увеличить цепочку на 6 позиций, значит вычислительная сложность вырастет в миллион раз. Также должна вырасти и вычислительная мощность, чтобы посчиталось за обозримое время. То есть 10-20 миллионов потоков. Это грубо и, скорее всего, занижено.

[VAL]

$M(192)\ge13$
Цепочка начинается с 51682648914977199298909295047775375066936643254684981244.

-- 11 июл 2022, 14:04 --

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

$M(132)\ge9$:

Я так понимаю, что на очереди 9 чисел по 156 делителей?
А паттерны для 10 чисел готовить?

-- 11 июл 2022, 14:11 --

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

А насколько реально найти 16 чисел, имеющих по 60 делителей (если такие цепочки вообще существуют)?

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

[Dmitriy40]

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

Не помню, чтобы Дмитрий выкладывал ускорители для новых цепочек после ускорителей для 48 делителей. Могш пропустить, конечно.

Тоже не помню, потому зашёл в облако и посмотрел: выложены M12n15, M36n13, M48n21, M60n11, M72n14, M84n11. Первое понятно уже устарело, как и M36n13 и M60n11, а 48,72,84 делителей вполне готовы.

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

Я так понимаю, что на очереди 9 чисел по 156 делителей?
А паттерны для 10 чисел готовить?

Пока не знаю, думаю 204 поискать, 8 или сразу 9. Всё же искать новое интереснее чем поднимать границу. Но сомневаюсь что оно найдётся быстро, всё же 155 цифр вместо 105, это же в 8 раз дольше, т.е. до недели (в одном потоке). А меня раздражает что 172 делителя никак не находятся, ни с 5-ю, ни с 7-ю проверяемыми числами, похоже на этом лёгкое нахождение семёрок вида $k=4p$ закончилось.
Паттерны Ваши пока не смотрел (кроме того решения 8 по 132, из которого получил 8 по 156, 9 по 132 уже по своим паттернам нашёл).

[mathematician123]

EUgeneUS
VAL
Понятно, Спасибо.

Я думаю, можно попробовать обобщить доказательство $M(36) \le 15$ на случай, когда $k \equiv 12 \pmod{24}$ и $k$ не делится на 5. Тут просматривается некоторая аналогия с доказательством $M(12t+6) \le 5$. Далее будут использоваться обозначения из лемм 6 и 7 отсюда. Случай $3 \mid n_8$ рассматривается также. Пусть $3 \mid n_6$. Здесь возможны два случая. Либо $9 \mid n_0$, либо $9 \mid n_6$. В первом случае получаем $n_6 = 6y^2$. Тогда $4x^2-3y^2 = 1$ --- получили уравнение Пелля. Как минимум, это уже говорит о том, что решения в этом случае, если они существуют, очень редки и искать их нет смысла. Но есть ещё второй случай $9 \mid n_6$. В этом случае $n_0 = 3pz^2$ и $n_6 = 2qy^2$ для некоторых простых $p, q$. Пользуясь этим, можно получить некоторые ограничения на $n_8 = 8x^2$.

-- 11.07.2022, 15:22 --

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

Здесь возможны два случая. Либо $9 \mid n_0$, либо $9 \mid n_6$.

Забыл написать. Есть ещё случай $9 \mid n_3$. Тогда $n_6 = 6y^2$, $n_8 = 8x^2$, $n_0 = 3pz^2$. И здесь можно применить метод из доказательства $M(12t+6) \le 5$ и свести этот случай к набору уравнений Туэ.

[VAL]

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

А паттерн попытаюсь сделать и пробный подсчет тоже. Возможно, что-то прояснится.

Фу-у-х!
Соорудил.
Похоже, $M(60)\le 17$
Цепочка из 17 чисел должна начинаться с $n_7$, где $n_i \equiv i \pmod{32}$.
У меня нет строгого доказательства, но, похоже $n_6$ (а возможно, и $n_4$) не могут иметь 60 делителей, если их 60 у $n_8$.

Что касается практических шансов, тут все как я предсказывал. Примерно на $10^{27}$ цепочек найдется одна подходящая. Но это при условии, что с ростом проверяемых чисел простые среди интересующих нас не будут встречаться все реже. Что, разумеется, неверно.

Паттерн прилагаю.

[mathematician123]

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

Далее будут использоваться обозначения из лемм 6 и 7 отсюда
.

Докажем, что $M(84) \le 15$. Почти все случаи здесь рассматриваются также, как и в леммах 6 и 7. Отдельного рассмотрения требуют только случаи $n_0 = 3pq^22^6$ и $n_0 = 3^2 \cdot 2^6 pq$. Рассмотрим эти случаи. Заметим, что $n_6 = 2ry^2$ для некоторого простого $r$. Тогда $(2x-1)(2x+1) = ry^2$. Отсюда следует, что $2x \pm 1 = z^2$. По модулю 4 случай с плюсом невозможен. Тогда $2x = z^2+1$. Пусть $z = 2w+1$. Тогда $x = 2w^2+2w+1$.
Подставим это в уравнение $8(x^2-1) = n_0$ и получим $32(w)(w+1)(w^2+w+1) = n_0$. Заметим, что сомножители в скобках попарно взаимнопросты. Тогда один из них не делится ни на $p$, ни на $q$. Тогда этот сомножитель будет $\le 2^6 \cdot 3^2$.