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

[Huz]

Dmitriy40
Thank you.

[Yadryara]

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

В том числе отмечается, что плохие числа цепочек являются степенями двойки. Этот вопрос уже был исследован нами с Дмитрием. Правда, на большей высоте, до $10^{35}$.

Вероятность того, что число ровно с 12 делителями встретится само, составляет примерно 1 раз на 530-600 попыток, что примерно в 130-140 раз ниже, чем вероятность встретить на этом же месте произведение пары различных простых.

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

Что касается высоты $10^{22}$.

Известно что до $10^{22}$ имеется $4\,118\,054\,813$ квадратов простых чисел. Добавив все степени простых выше второй, получим примерно то же число, то есть $4,12$ ярда.

Также известно что до $10^{22}$ имеется $201\,467\,286\,689\,315\,906\,290$ простых чисел.

Всё-таки $201467286689$ ярдов это несколько больше чем $4,12$ ярда. Таким образом числа состоящие из произведения простых в первой степени каждое будут встречаться гораздо чаще, чем числа, где хотя бы одно простое в разложении имеет степень выше первой.

Не правда ли, gris ?

[gris]

Yadryara, а меня-то за что?
Хотя отметиться в такой теме, даже на уровне простодушного зрителя, очень приятно. Мне самому исследования вести не дано свыше, но да, некоторые простенькие закономерности сам подмечаю и радуюсь, что мой велосипедик напоминает здешний вездеход.
И это хорошо.

[Yadryara]

gris в сообщении #1568113 писал(а):

Yadryara, а меня-то за что?

gris, видел Ваши наблюдения в кое-каком блоге

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

Тоже не может: $5^5x=32p-1$ неразрешимо в простых $x,p$ по модулю 6.

Пока не смог проверить. Вроде нет запрета.

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

Тут тоже есть хитрости: $15x^2$ на месте $32p-1$ допустимо, а на месте $32p+1$ нет (по модулю 8).

По модулю 64 всего два места возможны: $32p-1$ и $32p+7$.

https://www.wolframalpha.com/input?i=x%3D15p%5E2+mod+64

[Yadryara]

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

По модулю 64

А по модулю 192 Альфа не хочет считать...

gris в сообщении #1568113 писал(а):

Мне самому исследования вести не дано свыше,

Прибедняться-то и я умею

[Dmitriy40]

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

А по модулю 192 Альфа не хочет считать...

Я руками перебираю два варианта (32 и 160 или 1 и 5), смотри например ссылку ниже.

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

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

Тоже не может: $5^5x=32p-1$ неразрешимо в простых $x,p$ по модулю 6.

Пока не смог проверить. Вроде нет запрета.

Давайте проверим, может и ошибся.
$5^5x=5x=\{1,5\}\pmod 6$ ($x=3\pmod 6$ не учитываю), $32p-1=2p-1=\{1,3\}\pmod 6$. Хм, да, $x=5, p=1\pmod 6$ подходит. Значит ошибся.

-- 29.10.2022, 14:25 --

Huz
The program crashed several times by mistake (I don't know why, Windows doesn't write, just closes), then I go to sleep, and it crashed again an hour later, while the calculations stop (the main thread is waiting for the completion of all computing threads, and one of those crashed, but did not close, Windows is waiting for the user's reaction), in as a result, 6 hours are lost. But so far, for an hour and a half, he continues to count further after the next crash, apparently the computing stream was closed, and the main and the rest continued to work. While we continue to wait and hope.

PS. Special thanks are not needed, we do one thing, why not help, since there is an opportunity.

[Dmitriy40]

Huz

(Оффтоп)

7391622761940698662746728973350213034032662696649247351095119038886449805300917369378639370896627858127081417819831909241656831 = 5435929018082409998939362310401594629856068170235263 * 1359771758857179373408354906131533529998508206567011371214232880208377636737

It took 22.5 hours of pure counting time.

[Huz]

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

Huz

(Оффтоп)

7391622761940698662746728973350213034032662696649247351095119038886449805300917369378639370896627858127081417819831909241656831 = 5435929018082409998939362310401594629856068170235263 * 1359771758857179373408354906131533529998508206567011371214232880208377636737

It took 22.5 hours of pure counting time.

Super, thanks again. That means also that I can finally complete the table I originally sent to Yadryara a few months ago calculating $\log(D(4p,k)) / \log(p_k\#)$:

p\k     1      2      3      4      5      6      7
3    5.91   3.68   2.10   1.85   1.58   1.91   1.96
5    7.91   4.78   3.65   4.52   4.51   4.23   4.60
7    9.91   6.68   7.02   6.72   6.76   6.84   6.73
11  13.91  11.37  10.81  10.86  10.95  11.07  10.94
13  15.91  13.46  12.95  12.86  12.96  13.20  13.10
17  19.91  16.66  16.80  17.27  16.82  17.22  17.26
19  21.91  18.69  18.75  19.02  19.19  19.41  19.13
23  25.91  23.09  23.13  23.06  23.26  23.31  23.39

.. which continues to seem a lot more regular than it has any right to be (except for $k=1$, which has every right to be).

Of my original target to find $D(n,k)$ for all $n \le 100$, I now miss only 3 values with $n=100$ and 10 values with $n \equiv 6 \pmod{12}$; all other missing values have $n \equiv 0 \pmod{12}$ (of which 63 have known upper bound, and 74 more may exist with no known upper bound).

Цитата:

Special thanks are not needed

I try to show appreciation when I feel it.

[Dmitriy40]

Strangely, it seemed to me that for $n<100$, all upper bounds were found, with the exception of chains longer than 7. I remember that I even helped this a little... I must have misunderstood something.

[EUgeneUS]

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

I must have misunderstood something.

Насколько понимаю,
$D(n, k)$ - это начало "минимальной" цепочки (то есть цепочки с минимальными числами из всех таких) длиной $n$ из чисел с $k$ делителями.
Или $D(n, k) = T(2n, k)$ в терминах A292580

-- 30.10.2022, 03:50 --

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

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

От "линейного" поиска при минимизации цепочек никуда не деться, к сожалению.
Выше пытался минимизировать количество паттернов, для которых нужно будет делать "линейный" поиск для цепочек 11+. Но исключить его не получится в любом случае.
Пока у меня получается так:
1. Кроме отдельного случая для цепочки длинной 11, нужно искать непрерывную 9-ку в позициях $n_{-4}...n_{4}$
2. И далее её проверять - даёт ли она более длинные цепочки.

В этой девятке:
1. Два варианта расстановок троек.
2. Два варианта расстановок пятерок, при этом на два альтернативных места расставляются только $5^2$
3. Два места, куда может быть поставлено или $7$ или $7^2$ и одно место, где может быть только $7^2$

Итого $2 \cdot 2 \cdot (2 \cdot 2 +1) = 40$ паттернов.
Шаг получается небольшой: $32 \cdot 9 \cdot 25 \cdot 7 = 50400$
"Проверяемых чисел", где надо искать одно простое - 4, 5 или 6 (в зависимости от расстановок $5$ и $7$)

И у меня большие сомнения, что при таких условиях сможем за обозримое время дойти до известной 11-ки (а для неё будет ещё группа паттернов для позиций $n_{-7} ... n_3$ и симметричные) или 12-ки.

[EUgeneUS]

UPD: наличие в цепочках чисел, кратных $5^5$, может быть исключено. А вот вместо $7^2$ можно ставить $7^5$, то есть добавляется ещё четыре паттерна.

[Huz]

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

Strangely, it seemed to me that for $n<100$, all upper bounds were found, with the exception of chains longer than 7. I remember that I even helped this a little... I must have misunderstood something.

Yes: all upper bounds are found except some chains longer than 7, all of which have $n \equiv 0 \pmod{12}$ where $n$ is the required number of divisors.

Of the chains that theoretically may exist, there are 74 cases for which no upper bound has been found. There are 76 additional cases for which an upper bound is known, but a minimum value has not yet been proved - and the majority of those also have $n \equiv 0 \pmod{12}$. Only 13 cases with $n \le 100, n \not \equiv 0 \pmod{12}$ still lack a proven minimum.

[Yadryara]

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

Насколько понимаю,
$D(n, k)$ - это начало "минимальной" цепочки (то есть цепочки с минимальными числами из всех таких) длиной $n$ из чисел с $k$ делителями.

Ровно наоборот.

У Huz

$D(n, k)$ — это начало цепочки длиной ровно $k$ чисел имеющих по $n$ делителей каждое.

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

Или $D(n, k) = T(2n, k)$ в терминах A292580

Здесь верно.

Hugo поменял обозначения по сравнению со статьёй Иво и Роджера 1989-го года, где использовалось обозначение $D(k,m)$.

И VAL, следуя этой статье, неоднократно просил обозначать количество делителей буквой $k$.

Но путаница всё равно продолжается.

Хотя общность записей имеется хотя бы в том, что первое число в скобках это количество делителей, а второе — длина непрерывной цепочки.

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

1. Кроме отдельного случая для цепочки длинной 11,

Но сейчас-то больше интересует именно 11-ка.

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

наличие в цепочках чисел, кратных $5^5$, может быть исключено.

Имеете в виду исключено перебором?

[EUgeneUS]

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

Имеете в виду исключено перебором?

Да. Но "квадратичным" перебором - перебором решений уравнения вида $32p \pm d = Aq^2$, при известных $d, A$.
По оценкам уважаемого Dmitriy40 это можно сделать за разумное время для цепочек длиной 11 и 12.

Вот расстановка пятёрок для варианта расстановок троек на левой верхней картинке в этом посте.
Для правой верхней - симметрично.

Для цепочки длиной девять в позициях $n_{-4} .. n_4$
1. В позициях $n_{-2}, n_0, n_4$ пятерки быть не может. Это проверяется однократными проверками.
2. Значит в позиции $n_{-1}$ пятерки быть не может (это неверно для цепочек длиной 11 в позициях $n_{-7} .. n_3$)
3. Значит в $n_{-2} .. n_2$ пятерка может быть только в позициях $n_1, n_2$. Причем степень её может быть либо первой, либо квадрат.
4. Но если она в какой-то из этих позиций в первой степени, то приходим к уравнению с неизвестным $q^2$ и проверяем перебором.

Для цепочек длиной 11 в позициях $n_{-7} .. n_3$
1. В позициях $n_{-2}, n_0$ пятерки быть не может. Это проверяется однократными проверками.
2. Значит в позициях $n_{-7}, n_{-5}, n_{3}$ пятерки быть не может
3. В позициях $n_1, n_2$ пятёрка может быть только в квадрате (это проверили раньше).
4. А значит в позициях $n_{-4}, n_{-3}$ пятёрка может быть только в первой степени.
5. Остаётся только позиция $n_{-6}$ и $n_{-1}=n_{-6}+5$. Если в $n_{-6}$ пятерка в первой степени, то опять приходим к неизвестному $q^2$ и "квадратичному" перебору.
6. Значит возможен только один вариант: в $n_{-6}$ - квадрат пятерки, а в $n_{-1}$ - пятёрка в первой степени.

Конечно, часть из этих "квадратичных" переборов (но не все) скорее всего может быть исключена по модулям. Но в данных выкладках это не учитывалось.

-- 30.10.2022, 08:47 --

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

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

Вот тут уважаемый Dmitriy40 исключает варианты $10p^2$

А значить в выкладках выше "квадратичный перебор" остаётся только для случаев $32p \pm 1 = 15 q^2$

[Yadryara]

С пятёрками вообще ситуация сложная. Давайте пока по 5-й степени пятёрки.

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

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

наличие в цепочках чисел, кратных $5^5$, может быть исключено.

Имеете в виду исключено перебором?

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

Да. Но "квадратичным" перебором - перебором решений уравнения вида $32p \pm d = Aq^2$, при известных $d, A$.
По оценкам уважаемого Dmitriy40 это можно сделать за разумное время для цепочек длиной 11 и 12.

То-то и оно, что здесь квадратичный перебор не сработает. По той простой причине, что 12 делителей имеют числа вида $3125p$. Где здесь квадрат??