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

[VAL]

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

[..] for now, I'm particularly interested in satisfying myself that $M(70) = 3$[..]

Hugo, I also couldn't find the whole proof of $M(70)\le3$. Only separate pieces in two different themes. It turned out that it was easier to deduce the proof myself than to assemble it from pieces. But my proof exists only on paper.

[Dmitriy40]

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

Сделал схему паттернов на 4 проверки на простоту (вторая таблица в том же файле).

А почему во второй таблице есть 61, но нет 59?

[VAL]

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

А почему во второй таблице есть 61, но нет 59?

Исключительно по моему недосмотру.
Конечно, следует заменить 61 на 59. Кардинально ничего не изменится (может даже оказаться, что цепочка с 61 найдется раньше), но числа станут чуть поменьше, а вероятности чуть побольше.

[EUgeneUS]

Huz
VAL

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

It turned out that it was easier to deduce the proof myself than to assemble it from pieces

I didn't assemble the proof for $M(70) \le 3$, because I was switched to prove $M(2pq) \le 3$.
The idea of the proof is the same, but it's more simple for $M(70) \le 3$ because
a) It doesn't require to eliminate finite enumerations (Lemmas from 2 to 6, numbering as in the English draft)
b) For some hard cases it was possible to find a modulo comparison. F.e. it was possible for case basing on the Lemma 7.

-- 18.06.2022, 21:45 --

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

I note that "Доказательство" is not translated for some reason,

Thanks!
It requires some LaTeX tuning, it'll be correct in the next version.

[mathematician123]

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

Yes, you're right. This is the hole in the proof instead of the whole proof
I think it can be closed basing on analogue of the "Лемма 1" in the Russian draft (Lemma 2 in the English draft).
The text needs to be added, of course.

Да, случай $n_0 = 2^{pq-1}t$ мы упустили. В этом случае теорема Михайлеску не работает. Но в этом случае получается, что $t = 2^{pq-4} \pm 1$. По крайней мере, доказательство $M(70) \le 3$ остаётся в силе. В общем случае, думаю, доказать невозможность этого случая будет несложно. Как минимум, случай с плюсом невозможен из-за делимости на 3.

-- 18.06.2022, 22:19 --

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

Thanks, it sounds like a great result; for now, I'm particularly interested in satisfying myself that $M(70) = 3$ for the purposes of the A292580 a-file (which runs only to n=100), so I'm most eager to see whichever might be the simplest proof of that. :)

In the case $k = 70 = 2 \cdot 5 \cdot 7$ it will be $gcd(5-1, 7-1) = 2$. Therefore, in this case, the only known proof is EUgeneUS proof.

[EUgeneUS]

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

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

А случай с минусом из-за делимости на 9.
Я прикинул уже, как это доказать - там всё сведется к одной из Ваших лемм.
Завтра постараюсь найти время оформить.

[mathematician123]

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

Hugo, I also couldn't find the whole proof of $M(70)\le3$.

Полное доказательство есть в нашем проекте в Papeeria. С ним что-то не так? Как мы сегодня выяснили, в лемме 1 пропущен случай $n_0 = 2^{pq-1}t$. Но в этом случае получается, что $t = 2^{pq-4}-1$. Доказательству $M(70) \le 3$ это не мешает, нужно всего лишь проверить невозможность $n_0 = 2^{34} \cdot (2^31-1)$. Для произвольных $p, q$ доказательства невозможности этого случая пока нет. Но скорее всего уже завтра оно появится.

[VAL]

Нашлась 5-ка по 354 делителя.

Сделал заготовку на 14 чисел по 72 делителя. Завтра протестирую и опубликую.

[Dmitriy40]

VAL
Сравнил два отдельных (произвольно выбранных) паттерна по Вашим таблицам, далее p5 для 5-ти проверяемых чисел и p4 для четырёх.
Сравнивать стал по времени, дал им обоим примерно по часу и вывел в лог всё что найдётся при совпадении этих 4-х или 5-ти проверяемых мест, причём остальные проверил до упора, полностью (и именно это и заняло 98% общего времени). За этот час p5 сделал вшестеро больше итераций (6e9 против 1e9, цикл был именно по этим итерациям), выдал в 4.8 раза больше кандидатов (8.3млн против 1.7млн), из них через фильтр проверяемых мест прорвалось в 1.4 раза меньше цепочек (930 против 1370), valids=15 выдали оба по одной, но p5 выдал ещё и одну valids=16, valids=14 выдали примерно поровну (10шт p5 и 11шт p4), valids=13 тоже поровну (34шт и 31шт соответственно), valids=12 тоже поровну (64шт и 60шт), меньшие нафик.
Отдельно проверил чистое время выполнения ускорителей, вообще без последующего анализа кандидатов, время составило 105с для p5 и 12с для p4 (вшестеро меньше итераций!).

В итоге никакой особо значимой разницы я не вижу, за час реального времени результат оказался весьма схожим. Несмотря на сильное отличие результатов по вероятностям и частотам и количеству итераций. Что будет при замене полной проверки делителей на частичную трудно сказать (а проверять лень, вариантов много), но по идее p5 выгоднее: он работает незначительно медленнее, но фильтрует сильно лучше, оставляя намного (вшестеро) меньше работы тормозному PARI.
И квадриллионов снова не заметил, максимум десяток ...

[Dmitriy40]

Наконец нашлась и семёрка со 164-ю делителями, с 5-ю проверяемыми числами и более часа на разложение 6-го числа. Так что $M(164)=7$.

[Yadryara]

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

valids=15 выдали оба по одной, но p5 выдал ещё и одну valids=16,

Это про 48 делителей? А непрерывная 15-шка то нашлась? Ведь белое пятно именно здесь было:

$\tikz[scale=.0785]{ \fill[green!60!blue] (10,210) rectangle (80,220); \draw[step=10cm] (0,210) grid +(200,20); \node at (15,225){\text{3}}; \node at (25,225){\text{4}}; \node at (35,225){\text{5}}; \node at (45,225){\text{6}}; \node at (55,225){\text{7}}; \node at (65,225){\text{8}}; \node at (75,225){\text{9}}; \node at (85,225){\text{10}}; \node at (95,225){\text{11}}; \node at (105,225){\text{12}}; \node at (115,225){\text{13}}; \node at (125,225){\text{14}}; \node at (135,225){\text{15}}; \node at (145,225){\text{16}}; \node at (155,225){\text{17}}; \node at (165,225){\text{18}}; \node at (175,225){\text{19}}; \node at (185,225){\text{20}}; \node at (195,225){\text{21}}; \node at (5,215){\text{48}}; \node at (15,215){\text{5e6}}; \node at (25,215){\text{1e8}}; \node at (35,215){\text{2e9}}; \node at (45,215){\text{8e10}}; \node at (55,215){\text{3e12}}; \node at (65,215){\text{1e13}}; \node at (75,215){\text{6e14}}; \node at (85,215){\text{2e17}}; \node at (95,215){\text{1e18}}; \node at (105,215){\text{9e18}}; \node at (115,215){\text{3e25}}; \node at (125,215){\text{9e30}}; \node at (145,215){\text{1e42}}; \node at (155,215){\text{6e42}}; \node at (165,215){\text{7e44}}; \node at (175,215){\text{5e48}}; \node at (185,215){\text{1e52}}; }$

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

Сделал заготовку на 14 чисел по 74 делителя.

И как Вы так ухитряетесь-то? Или всё же по 72 делителя?

[VAL]

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

Наконец нашлась и семёрка со 164-ю делителями

Отлично!

Цитата:

с 5-ю проверяемыми числами и более часа на разложение 6-го числа.

А куда же 7-е делось?

Цитата:

Так что $M(164)=7$.

Пришлите, пожалуйста само стартовое число для пополнения таблицы.

[EUgeneUS]

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

Therefore, in this case, the only known proof is EUgeneUS proof.

FGJ, it isn't my only. The author of the Lemmas that eliminate the finite enumerations (Lemmas from 2 to 6) is mathematician123.

Huz
I added case $n_0=2^{pq - 1} t$ into the Lemma 1 ("elimination of the exsotic factorizations").
This required small adding into the Lemma 2.

New version is here

Hugo, thank you very much for a your quick eye and accuracy!

-- 19.06.2022, 08:28 --

VAL
mathematician123

В русском тексте также добавил (в нашем проекте в Papeeria).

[VAL]

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

Сравнил два отдельных (произвольно выбранных) паттерна по Вашим таблицам, далее p5 для 5-ти проверяемых чисел и p4 для четырёх.
Сравнивать стал по времени, дал им обоим примерно по часу и вывел в лог всё что найдётся при совпадении этих 4-х или 5-ти проверяемых мест, причём остальные проверил до упора, полностью (и именно это и заняло 98% общего времени). За этот час p5 сделал вшестеро больше итераций (6e9 против 1e9, цикл был именно по этим итерациям), выдал в 4.8 раза больше кандидатов (8.3млн против 1.7млн), из них через фильтр проверяемых мест прорвалось в 1.4 раза меньше цепочек (930 против 1370)

До этого места думал, что понимаю о чем речь...

Цитата:

valids=15 выдали оба по одной, но p5 выдал ещё и одну valids=16

А тут понял, что ничего не понял
Что такое valids?
Раньше я думал, что это количество чисел, имеющих нужное число делителей и разложившихся за ограниченное время. (В остальных позициях в приводимых Вами ранее фрагментах вывода стояли нули. Вряд ли это количество делителей). Но ведь Вы делали полное разложение.
Значит, это 15 (соответственно 16) подходящих чисел из набора длиной 21? Но тогда это означает, что до 21 числа нам как до Луны (причем на аэростате)
А если это количество подходящих из тех, что не проверялись на простоту, тогда где радость по поводу нового мирового рекорда ($5+16=21$)?
Или это длина непрерывного куска? Но это вроде бы было maxlen...

-- 19 июн 2022, 08:51 --

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

Это про 48 делителей?

Конечно (оказывается не один я ничего не понимаю )

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

А непрерывная 15-шка то нашлась?

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

-- 19 июн 2022, 08:57 --

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

New version is here

9 страниц! Я все жду, когда Вы сократите доказательство, чтобы посмотреть его детально. А оно все растет...
В среду планирую все же плотно за него взяться.

-- 19 июн 2022, 09:00 --

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

И как Вы так ухитряетесь-то? Или всё же по 72 делителя?

Спасибо! Поправил.

[Yadryara]

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

Что такое valids?

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

Значит, это 15 (соответственно 16) подходящих чисел из набора длиной 21?

Если Dmitriy40 не менял терминологию, то да, именно это.

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

Или это длина непрерывного куска? Но это вроде бы было maxlen...

Да, именно в таких смыслах valids и maxlen употребляются с самого начала.

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