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

[Dmitriy40]

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

Надеюсь уважаемый Dmitriy40, который вроде бы знает С, это прокомментирует.

Ну, судя по его объяснениям и примеру с $T(6,3)$ (исходники не смотрел), товарищ пытается единым махом перекрыть все возможные низины, рекурсивно получая все возможные паттерны и выходя по каждому из них на примерно нашу же проверку (только не по isprime, а сразу по numdiv). Насколько корректно (перекрывая все возможности и строго по возрастанию чисел) генерятся паттерны я не смотрел. Учитывая молчание о проверках по модулям коэффициентов $q_i$ в одном паттерне возможно он делает много лишней работы (для искомых простых выше первой степени), но это не факт, надо разбираться.

Немного похожим образом я проверял что для $T(6,15)$ нет меньших решений с большим простым $p^{11}$ (просто перебрал их все и проверил количество делителей вокруг) и частично $p^5q$ (тут кажется перебрал лишь $p$ больше нескольких тысяч). Как Hugo надеется перебрать все $q$ при скажем $100<p<1000$ мне непонятно, разве что очень сильно повезёт. Даже увеличивая шаг проверки через КТО для всех коэффициентов в паттерне всё равно остаются миллиарды и триллионы попыток для каждого паттерна, которых тоже миллионы. Возможно такой подход хорошо работает для не слишком больших чисел, но для $T(6,15)$ (и 14, и 13) мне кажется мало реальным. Впрочем как и Ваша попытка перебрать все полторы сотни комплектов паттернов с заменой квадратов простых.

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

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

Специально просил объяснить на простейшем примере. Как было найдено вот это число?

https://oeis.org/A292580/a292580_2.txt писал(а):

T(6,8) 18652995711772 Hugo van der Sanden 2022-01-12

Заметьте насколько малО это число, жалкие $10^{13}$, до них можно перебрать просто все возможные $p^{11}, 2^3 p^2, 2^5 p$ и проверить количество делителей вокруг. Но с 664e35 такое уже не проходит ...

[Huz]

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

(только не по isprime, а сразу по numdiv)

The check $\tau(v_i) = t_i$ is done pretty efficiently, with special cases for $t=2$ and $t \equiv 1 \pmod{2}$; it also finds only one (prime power) factor at a time, so can return immediately if a factor is incompatible with the desired $t$ - this is the is_tau() function provided at https://github.com/danaj/Math-Prime-Util-GMP/pull/30/commits/296e073c63.

I also order them (squares, then primes, then semiprimes, then the rest) so that fastest and least likely are tested first.

-- 09.06.2022, 02:06 --

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

Надеюсь в порядке возрастания чисел

Not in ascending order. So it's very helpful to have a good upper bound before attempting a full minimization run.

[Dmitriy40]

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

[EUgeneUS]

VAL
Относительно $k \equiv 6 \pmod{12}$.
А что говорит практика: из каких паттернов для них находятся пятерки?
1. Бывает ли в пятёрке $n_0$? Или всё укладывается в $n_1 ... n_5$?
2. Если $n_0$ бывает в пятерках, то бывает ли так, что $n_0$ делится на $16 \cdot 9 \cdot 25 = 3600$?
3. Если и так бывает, то какие позиции занимает цепочка в этих случаях ($n_7 ... n_3$ или $n_0 ... n_4$) ?

Пока доказано, что
а) семёрок - не более чем конечное количество (на все такие $k$)
б) если шестерки существуют, то они имеют вид: $n_7 .... n_4$, при этом $n_0$ обязательно делится на $3600$.

А дальше некоторый ступор у меня:
а) то ли дальше упираться в несовместимость $n_0 \equiv 0 \pmod{3600}$ и $n_2 = 2 x^2$, $n_3=3y^2$ (мы пока использовали только вид числа делителей, но ещё не использовали, что у всех чисел число делителей д.б. одинаковым).
б) то ли попытаться "отрезать" от цепочки $n_4$ или $n_7$....

[EUgeneUS]

Вот что заметил из свойств уравнения $3x^2 - 2y^2 = 1$, если $n_0$ делится на $3600$, то оно обязательно делится на $11$. (Пока это только наблюдение, доказать будет не сложно, но муторно - там период, с которым остатки повторяются, $30$).
Отсюда сразу следуюет:
а) $M(6p) \le 5 $, так как для $11$ в $n_0$ просто нет места.
б) В случае $M(6pq)$, все необходимые простые числа собраны. И достаточно перебора максимум четырех варантов для каждой пары $p, q$. А скорее перебор можно исключить, сравнивая величины $n_0$ и $n_2, n_3$.

[Yadryara]

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

Немного похожим образом я проверял что для $T(6,15)$ нет меньших решений с большим простым $p^{11}$ (просто перебрал их все и проверил количество делителей вокруг)

11-ю степень и я отсечь могу Всего-то 400 простых:

kpr=0;
{forprime(i=1,2747,kpr=kpr+1;n=i^11;
if (numdiv(n-1)==12 || numdiv(n+1)==12,
print(kpr,"  ",i,"    ",numdiv(n-2),"  ",numdiv(n-1),"  ",
numdiv(n),"  ",numdiv(n+1),"  ",numdiv(n+2))))}
quit;

Не то что 15-шки, ни одной тройки даже нет. Только 7 пар.

[mathematician123]

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

Вот что заметил из свойств уравнения $3x^2 - 2y^2 = 1$, если $n_0$ делится на $3600$, то оно обязательно делится на $11$. (Пока это только наблюдение, доказать будет не сложно, но муторно - там период, с которым остатки повторяются, $30$).

Для делимости $n_0$ на 11 достаточно того, что $n_0$ делится на 3.

Обозначим $(x_i, y_i)$ все решения уравнения $3x^2-2y^2 = 1$, где $(x_0, y_0)=(1, 1) $, $(x_{i+1}, y_{i+1})=(5x_i+4y_i, 6x_i+5y_i)$. Остатки по модулю 11 для $(x_i, y_i)$ повторяются с периодом три, причём, если $i$ даёт остатки 0 или 2 от деления на 3 то $x-1$ делится на 11 и, следовательно, $n_0$ делится на 11. При этом $i$ не может давать остаток 1 от деления на 3, так как тогда $x$ делилось бы на 3, а $n_0$ не делилось бы на 11.

-- 09.06.2022, 14:11 --
del

-- 09.06.2022, 14:20 --

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

б) В случае $M(6pq)$, все необходимые простые числа собраны.

Это значит, что в этом случае $n_0 = 2^a 3^b 5^c 11^d$, причём одно из чисел $a, b, c, d$ равно единице. Тогда (в предположении, что делимость $n_0$ на 25 доказана) $n_0 = 11z^2$. Получаем систему уравнений $2x^2-2 = 11z^2$ и $3x^2-3 = 11z^2$, которая имеет конечное количество решений.

[EUgeneUS]

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

Для делимости $n_0$ на 11 достаточно того, что $n_0$ делится на 3.

да, действительно. Тот же финт, как и раньше, но сдвинут на два.

ещё вот какая история.
Опять же, исходя из остатков решений уравнения $3x^2 - 2 x^2 = 1$, семерка может быть либо в $n_0$, либо в $n_5$. Это в общем случае.

А это значит, что любое простое в факторизации $n_2$ и $n_3$ (кроме двойки и тройки в первой степени) больше любого простого в факторизации $n_0$ (это для частного случая $k=6pq$), чего должно хватить, чтобы показать что $n_0$ сильно меньше $n_2$ и-или $n_3$. Но это всё "повторение пройденного" - доказательство $M(6pq) \le 5 $ уже имеется, насколько понимаю.

Интресно, что из этих фактов можно выжать для общего случая $k \equiv 6 \pmod{12}$, или для других частных случаев...

[VAL]

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

VAL
Относительно $k \equiv 6 \pmod{12}$.
А что говорит практика: из каких паттернов для них находятся пятерки?
1. Бывает ли в пятёрке $n_0$? Или всё укладывается в $n_1 ... n_5$?

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

[mathematician123]

Докажем, что $M(6pq) \le 5$.

Как было показано ранее, если существует шестёрка, то $2 \cdot 3 \cdot 5 \mid n_0$. Также было показано, что $11 \mid n_0$:

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

Для делимости $n_0$ на 11 достаточно того, что $n_0$ делится на 3.

Обозначим $(x_i, y_i)$ все решения уравнения $3x^2-2y^2 = 1$, где $(x_0, y_0)=(1, 1) $, $(x_{i+1}, y_{i+1})=(5x_i+4y_i, 6x_i+5y_i)$. Остатки по модулю 11 для $(x_i, y_i)$ повторяются с периодом три, причём, если $i$ даёт остатки 0 или 2 от деления на 3 то $x-1$ делится на 11 и, следовательно, $n_0$ делится на 11. При этом $i$ не может давать остаток 1 от деления на 3, так как тогда $x$ делилось бы на 3, а $n_0$ не делилось бы на 11.

Таким образом, $n_0 = 2^a 3^b 5^c 11^d$. Тогда из равенства $2(x+1)(x-1) = n_0$ получаем, что $\frac{x-1}{2}$ и $\frac{x+1}{2}$ являются последовательными числами, которые в разложении на простые содержат только простые 2, 3, 5, 11. Все такие числа можно найти. Алгоритм описан здесь.

-- 09.06.2022, 23:04 --

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

Алгоритм описан здесь
.

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

-- 09.06.2022, 23:08 --

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

При этом $i$ не может давать остаток 1 от деления на 3, так как тогда $x$ делилось бы на 3, а $n_0$ не делилось бы на 11.

В самом конце опечатка. Должно быть не 11, а 3.

[VAL]

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

Таким образом, $n_0 = 2^a 3^b 5^c 11^d$

А разве после этого не все очевидно без всяких ссылок?
Рассмотрим, например, $n_0+1$ и $n_0+2$. 7 может входить делителем только в одно из этих чисел.
Тогда у другого каждый простой делитель (у $n_0+2$ есть двойка в первой степени, но это сути не меняет) больше любого делителя "n_0" и они не могут быть соседями.

[mathematician123]

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

А разве после этого не все очевидно без всяких ссылок?

Да, так проще.

[EUgeneUS]

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

Все известные пятерки (а у меня их много) имеют вид $n_1,...,n_5$.

Спасибо! А тройку Вы расставляете в $n_3$ и в большойй степени (как минимум в квадрате)?

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

Рассмотрим, например, $n_0+1$ и $n_0+2$. 7 может входить делителем только в одно из этих чисел.

А это почему?
Как писал выше:

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

Опять же, исходя из остатков решений уравнения $3x^2 - 2 x^2 = 1$, семерка может быть либо в $n_0$, либо в $n_5$. Это в общем случае.

Нет ли тут противоречия? Прекрасного, чудесного, нужного нам противоречия?

[mathematician123]

VAL
Нашёл усиление леммы 2 из Вашей статьи. Пусть $k$ делится на $2^s$ и не делится на $2^{s+1}$. Тогда $M(k) \le 2(p_s\#)^2-1$, где $p_s\# = 2 \cdot 3 \cdot \ldots \cdot p_s$ - произведение первых $s$ простых чисел. При достаточно больших $s$ эта оценка сильнее, чем $M(k) \le 2^{2^s+1}$.

[EUgeneUS]

По $k \equiv 6 \pmod{12}$

Несовместимость $n_0$ c $n_2, n_3$ удалось свести к неразрешимости уравнений вида:

$$ a n^4 \pm b n^2 = c m^4 \pm d m^2 $$

Каждый $\pm$ даёт два варианта, так же есть по два набора для $a, b$ и $c, d$, итого 16 уравнений.
Вечером напишу подробности.

mathematician123
Вам не попадались статьи, о том как доказывать отсутствие нетривиальных решений в уравнениях такого вида?
Я выборочно проверил в WolframAlpha (часть из этих 16 уравнений), находятся только тривиальные решения с нулями и-или единицами.