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

[VAL]

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

Подробности вечером.

Ждем...

-- 20 май 2022, 14:31 --

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

UPD: исключил "экзотику" в общем виде. Последний вариант исключился через ныне доказанную гипотезу Каталана.

То бишь, теорему Михайлеску.
Мы с Василием Дзюбенко при доказательстве того, что $M(2pq)\le3$ при $gcd(p-1,q-1)>4$, тоже опирались эту теорему.

[VAL]

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

при доказательстве того, что $M(2pq)\le3$ при $gcd(p-1,q-1)>4$, тоже опирались эту теорему.

Я это написал не для того, чтобы похвастаться (ну или не только для того ), а с целью предотвратить лишнюю работу: проверку конкретных значений $k=2pq$, для которых $M(k)\le 3$ доказано. Эти $k$ есть в моих таблицах. 70 я туда тоже уже внес.

Про статью.
Еще не начали, а название уже устарело. Какие там "Long runs", когда для 70 это всего 3. Так что, "Long runs..." не годится.
Парадоксально, но факт: вполне подходит "The longest runs of consecutive equidivisible numbers". Ведь цепочка из 3-х чисел по 70 делителей не слишком длинная, но при этом наидлиннейшая из возможных.
(Впрочем, новое название годится лишь до тех пор, пока Антон не найдет и обоснует минимальный пентадекатлон. Тогда придется еще раз смещать акценты )

Я полагал, что мы разместим статью для совместного редактирования в Papeeria (такой опыт у меня есть). Но после бесплодных многочисленных попыток откомпилировать там последние версии таблиц, по-видимому надо мигрировать на OverLeaf (таблицы я в итоге обновлял там).

[EUgeneUS]

IIb. Окончательное решение вопроса с "экзотическими" факторизациями $n_0$

(продолжаем раздел II вот этого поста).

1. Для вот этих вариантов:

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

а) $a^{2p-1} = 2^{q-4} \pm 1$
б) $a^{2q-1} = 2^{p-4} \pm 1$

Гипотеза Каталана (теорема Михайлеску) разрешает только решения $3^2 - 2^3 =1$
Что даёт: $a=3$, $p-4 = 3$, $2q-1=2$ (и перестановка $p \leftrightarrow q$). При этом $q = 3/2$, что не является простым
Это запрещает факторизации $n_0$ вида $2^{p-1} a^{2q-1}$ (и перестановка $p \leftrightarrow q$).

2. Остается только: $a = 2^{pq-4} \pm 1$
Подставим это в соответствующую факторизацию и запишем уравнение $n_0 = n_2 - 2$:
$2^{pq - 2} (2^{pq-4} \pm 1) +1 = B$, где $B = n_2/2$ (и это полный квадрат)

2.1 Если тройка делит $B$, то по модулю $3$ запрещается плюс в $\pm$

3. Запишем это так:
$4 A (A - 1) - (B-1) = 0$, где $A = 2^{pq-4}$. Отметим, что это нечетная степень двойки.

-- 20.05.2022, 17:30 --

4. Решим квадратное уравнение относительно $A$. Есть только один положительный корень:
$2A = 1 + \sqrt{B}$. Отметим, что $2A = 2^{pq-3}$, и это четная степень двойки, а значит - полный квадрат.

5. Тогда:
$(\sqrt{2A} -1)(\sqrt{2A} +1) = \sqrt{B}$

6. $\sqrt{B}$ может иметь вид (смотрим, что может стоять в $n_2$):

6.1. $\sqrt{B} = 3^{(pq - 1)/2}$, тогда с необходимостью:
$(\sqrt{2A} -1) = 1$
$(\sqrt{2A} +1) = 3$
Откуда: $3^{(pq - 3)/2} = 1$ и $pq = 3$. Что противоречит $p, q \geqslant 5$

6.2. $\sqrt{B} = c^{(p-1)/2} d^{(q-1)/2}$
При этом либо $c$, либо $d$ больше трех. Для определенности будем считать $d > 3$
Тогда:
$(2^{(pq-3)/2}-1)(2^{(pq-3)/2} +1) = c^{(p-1)/2} d^{(q-1)/2}$

Тогда с необходимостью:
либо $(2^{(pq-3)/2}-1) = d^{(q-1)/2}$
либо $(2^{(pq-3)/2}+1) = d^{(q-1)/2}$

Что запрещено гипотезой Каталана (теоремой Михайлэску), так как $d \ne 3$

Остался вариант: тройка не делит $n_2$, а делить $n_0$. Но это запрещено, так как $a = 2^{pq-4} \pm 1$ заведомо больше $3$, при $p, q, \geqslant 5$

ЧТД. "Экзотика" запрещена.

-- 20.05.2022, 17:41 --

А ещё у меня получилось, что тройка не может стоять в $n_2$ и для "каноничных" факторизаций $n_0$ (для любых $p, q \geqslant 5$
Но об этом позже. Проверьте, пожалуйста, исключение "экзотики".

-- 20.05.2022, 17:56 --

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

Это даёт десять мест для размещения двойки,

Это мне напоминает "10 негритят". Очень похоже, что удастся уконтропупить всех.

[EUgeneUS]

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

Что запрещено гипотезой Каталана (теоремой Михайлэску), так как $d \ne 3$

А также потому что $(pq-3)/2 \geqslant 16$ для любых простых различных чисел, больше или равных пяти.
Это даже проще. Не нужно накладывать условие, что $d>3$.

[EUgeneUS]

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

А ещё у меня получилось, что тройка не может стоять в $n_2$ и для "каноничных" факторизаций $n_0$ (для любых $p, q \geqslant 5$

Это было опрометчивое заявление. Не получилось

[EUgeneUS]

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

Мы с Василием Дзюбенко при доказательстве того, что $M(2pq)\le3$ при $gcd(p-1,q-1)>4$, тоже опирались эту теорему.

вроде бы удалось доказать, что $M(2pq)\le3$ при $gcd(p-1,q-1)>2$.

Что интересно, пока "общим" подходом не удается доказать $M(2pq)\le3$ для $p=5, q=7$.

[VAL]

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

Проверьте, пожалуйста, исключение "экзотики".

Посмотрел. Но выскажусь пока аккуратно: правдоподобно.

-- 21 май 2022, 16:11 --

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

вроде бы удалось доказать, что $M(2pq)\le3$ при $gcd(p-1,q-1)>2$

С учетом усилий Дюнша с Эгглтоном и наших с Дзюбенко имеет место классическое отрубание хвоста у кошки по частям.

[EUgeneUS]

VAL
и ещё вроде бы удалось доказать, что для проверки, что $M(2pq) \le 3$ каждой пары $p, q$ достаточно конечного перебора.

[VAL]

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

и ещё вроде бы удалось доказать, что для проверки, что $M(2pq) \le 3$ каждой пары $p, q$ достаточно конечного перебора.

И от хвоста остался совсем маленький кусочек.

[EUgeneUS]

VAL
Начну набивать тут доказательство для проверки.
Оно опирается на исключение "экзотических паттернов" в $a_0$, и ниже рассматривается только "каноничный".
1. После сокращения на одну двойку он записывается так (с учетом, что в $n_2$ стоит удвоенный полный квадрат):
$2^{p-2} a^{q-1}b = B^2 -1 $, где $B = \sqrt{n_2/2}$

После того, как провернём известный фокус с сокращение степени двойки получим четыре варианта уравнений, связывающих $a^{q-1}$ и $b$

(Оффтоп)

подробно не пишу. Но вывод этих вариантов нужно обязательно проверить. Если нужно - напишу более подробно.

2а. $b = \frac{a^{q-1} + 1}{2^{p-4}}$
Этот вариант запрещается по модулю 4: вверху стоит число делящееся на 4, а внизу - нечетная степень двойки, следовательно $b$ - тут получается дробным, а не простым.

2б. $b = \frac{a^{q-1} - 1}{2^{p-4}}$

Запишем его так:
$2^{p-4}b = a^{q-1} - 1 = (a^{(q-1)/2} - 1)(a^{(q-1)/2} + 1)$
Тогда $2^{p-4} = (a^{(q-1)/2} \pm 1)$
Случаи $p > 7$, $q > 5$ запрещаются теоремой Михайлэску.
Случай $p = 7$, $q = 5$, согласно теореме Михайлэску, требует $a=3$. И тогда $b = 91$
И он действительно подходит - $2^5 3^6 \cdot 9 + 2$ - это, действительно удвоенный полный квадрат". Но дальнейшую проверку он не подходит.
Случай $p=q=5$ рассматривать не будем, так как считаем $p,q$ различными.

2в. $b = 2^{p-4} a^{q-1} + 1$
Проверяем по модулю три:
$2^{p-4} a^{q-1} + 1 \equiv 0 (\mod 3)$, значит $b \equiv 0 (\mod 3)$.
Значит $b=3$, тогда $3 = 2^{p-4} a^{q-1} + 1$, что очевидно не может выполняться для принятых ограничений на $a, p, q$.

2г. Остается только вариант $b = 2^{p-4} a^{q-1} - 1$.
Подставим его в паттерн и рассмотрим подробнее....

-- 21.05.2022, 19:12 --

3.
$2^{p-2}a^{q-1} [2^{p-4} a^{q-1} - 1] = (\sqrt{B}+1)(\sqrt{B}-1)$
Перепишем его так:
$[2^{p-3}a^{q-1}] [2^{p-3} a^{q-1} - 2]= (\sqrt{B}+1)(\sqrt{B}-1)$
Справа в скобках стоят последовательные четные числа, и справа в скобках стоят последовательные четные числа.
А значит большее число слева должно быть равно большему слева (и меньшие тоже).

Запишем это в таком варианте:
$[2^{(p-3)/2}a^{(q-1)/2}]^2 - 1 = \sqrt{B}$

Отметим, что слева все степени чётные, а значит это полный квадрат (минус единица из него).

Это основной результат. Далее будут выводы из него.

-- 21.05.2022, 19:34 --

4.
а) $\sqrt{B}$ не может быть никакой целой степенью более единицы никакого целого положительного числа.
Это запрещается теоремой Михайлэску.
Отсюда сразу
б) $n_2/2 = c^{pq-1}$ - запрещается.
в) в случае $n_2/2 = c^{q-1}d^{p-1}$:

$[2^{(p-3)/2}a^{(q-1)/2}]^2 - 1 = c^сd^{(p-1)/2}$

Требуется, чтобы: $gcd((q-1)/2, (p-1)/2)=1$

г) Случай $a=3$ проверяется конечным перебором $c$ и $d$ (с учетом перестановки $p \leftrightarrow q$ слева).
д) После исключения случая $a=3$, $c$ или $d$ должны быть равны $3$ (для определенности считаем, что $d$.

Тогда:
$ (2^{(p-3)/2}a^{(q-1)/2} - 1) (2^{(p-3)/2}a^{(q-1)/2} + 1) = 3^{(s-1)/2}с^{(t-1)/2}$,
где $s = {p,q}, s = {q,p}$
Слева стоит произведение чисел, у которых общий делитель равен единице. Это может быть только в случаях:

$ (2^{(p-3)/2}a^{(q-1)/2} \pm 1) = 3^{(s-1)/2}$

Так как справа стоит ограниченное число (при фиксированных $p, q$), то этот варианты перебираются конечным перебором.

[EUgeneUS]

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

Мы с Василием Дзюбенко при доказательстве того, что $M(2pq)\le3$ при $gcd(p-1,q-1)>4$, тоже опирались эту теорему.

$gcd(p-1,q-1)= 2$ даёт $\sqrt{B} = C^2$, $gcd(p-1,q-1)= 3$ даёт $\sqrt{B} = C^3$, где $C$ - некое целое число.
С вашим доказательством я не разбирался, если честно. Но меня гложут смутные сомнения, что оно близко к приведенному выше.
Просто Вы с Василием Дзюбенко не проверили, что единственное решение уравнения Каталана тоже запрещается.
Ну и, выше был построен алгоритм для проверки конечным перебором, что $M(2pq)\le3$ для заданных $p, q$

-- 21.05.2022, 19:52 --

Исправление опечаток

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

$[2^{(p-3)/2}a^{(q-1)/2}]^2 - 1 = c^d^{(p-1)/2}$

Читать: $[2^{(p-3)/2}a^{(q-1)/2}]^2 - 1 = c^{(q-1)/2}d^{(p-1)/2}$

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

$ (2^{(p-3)/2}a^{(q-1)/2} - 1) (2^{(p-3)/2}a^{(q-1)/2} + 1) = 3^{(s-1)/2}с^{(t-1)/2}$,

Читать: $ (2^{(p-3)/2}a^{(q-1)/2} - 1) (2^{(p-3)/2}a^{(q-1)/2} + 1) = 3^{(s-1)/2}c^{(t-1)/2}$

-- 21.05.2022, 19:54 --

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

$2^{p-2} a^{q-1}b = B^2 -1 $, где $B = \sqrt{n_2/2}$

Читать:
$2^{p-2} a^{q-1}b = B -1 = (\sqrt{B}-1)(\sqrt{B}+1)$, где $B = n_2/2$

-- 21.05.2022, 20:29 --

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

$2^5 3^6 \cdot 9 + 2$

Читать как: $2^5 \cdot 3^6 \cdot 91 + 1 = (1457)^2$

[VAL]

Вставил исправления опечаток в исходный текст, Так будет проще читать (но я еще не читал).

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

VAL
Начну набивать тут доказательство для проверки.
Оно опирается на исключение "экзотических паттернов" в $a_0$, и ниже рассматривается только "каноничный".
1. После сокращения на одну двойку он записывается так (с учетом, что в $n_2$ стоит удвоенный полный квадрат):
$2^{p-2} a^{q-1}b = B -1 = (\sqrt{B}-1)(\sqrt{B}+1)$, где $B = n_2/2$

После того, как провернём известный фокус с сокращение степени двойки получим четыре варианта уравнений, связывающих $a^{q-1}$ и $b$

(Оффтоп)

подробно не пишу. Но вывод этих вариантов нужно обязательно проверить. Если нужно - напишу более подробно.

2а. $b = \frac{a^{q-1} + 1}{2^{p-4}}$
Этот вариант запрещается по модулю 4: вверху стоит число делящееся на 4, а внизу - нечетная степень двойки, следовательно $b$ - тут получается дробным, а не простым.

2б. $b = \frac{a^{q-1} - 1}{2^{p-4}}$

Запишем его так:
$2^{p-4}b = a^{q-1} - 1 = (a^{(q-1)/2} - 1)(a^{(q-1)/2} + 1)$
Тогда $2^{p-4} = (a^{(q-1)/2} \pm 1)$
Случаи $p > 7$, $q > 5$ запрещаются теоремой Михайлэску.
Случай $p = 7$, $q = 5$, согласно теореме Михайлэску, требует $a=3$. И тогда $b = 91$
И он действительно подходит - $2^5 \cdot 3^6 \cdot 91 + 1 = (1457)^2$ - это, действительно удвоенный полный квадрат". Но дальнейшую проверку он не подходит.
Случай $p=q=5$ рассматривать не будем, так как считаем $p,q$ различными.

2в. $b = 2^{p-4} a^{q-1} + 1$
Проверяем по модулю три:
$2^{p-4} a^{q-1} + 1 \equiv 0 (\mod 3)$, значит $b \equiv 0 (\mod 3)$.
Значит $b=3$, тогда $3 = 2^{p-4} a^{q-1} + 1$, что очевидно не может выполняться для принятых ограничений на $a, p, q$.

2г. Остается только вариант $b = 2^{p-4} a^{q-1} - 1$.
Подставим его в паттерн и рассмотрим подробнее....

-- 21.05.2022, 19:12 --

3.
$2^{p-2}a^{q-1} [2^{p-4} a^{q-1} - 1] = (\sqrt{B}+1)(\sqrt{B}-1)$
Перепишем его так:
$[2^{p-3}a^{q-1}] [2^{p-3} a^{q-1} - 2]= (\sqrt{B}+1)(\sqrt{B}-1)$
Справа в скобках стоят последовательные четные числа, и справа в скобках стоят последовательные четные числа.
А значит большее число слева должно быть равно большему слева (и меньшие тоже).

Запишем это в таком варианте:
$[2^{(p-3)/2}a^{(q-1)/2}]^2 - 1 = \sqrt{B}$

Отметим, что слева все степени чётные, а значит это полный квадрат (минус единица из него).

Это основной результат. Далее будут выводы из него.

-- 21.05.2022, 19:34 --

4.
а) $\sqrt{B}$ не может быть никакой целой степенью более единицы никакого целого положительного числа.
Это запрещается теоремой Михайлэску.
Отсюда сразу
б) $n_2/2 = c^{pq-1}$ - запрещается.
в) в случае $n_2/2 = c^{q-1}d^{p-1}$:

$[2^{(p-3)/2}a^{(q-1)/2}]^2 - 1 = c^{(q-1)/2}d^{(p-1)/2}$

Требуется, чтобы: $gcd((q-1)/2, (p-1)/2)=1$

г) Случай $a=3$ проверяется конечным перебором $c$ и $d$ (с учетом перестановки $p \leftrightarrow q$ слева).
д) После исключения случая $a=3$, $c$ или $d$ должны быть равны $3$ (для определенности считаем, что $d$.

Тогда:
$2^{p-2} a^{q-1}b = B -1 = (\sqrt{B}-1)(\sqrt{B}+1)$, где $B = n_2/2$,
где $s = {p,q}, s = {q,p}$
Слева стоит произведение чисел, у которых общий делитель равен единице. Это может быть только в случаях:

$ (2^{(p-3)/2}a^{(q-1)/2} \pm 1) = 3^{(s-1)/2}$

Так как справа стоит ограниченное число (при фиксированных $p, q$), то этот варианты перебираются конечным перебором.

-- 21 май 2022, 20:55 --

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

Просто Вы с Василием Дзюбенко не проверили, что единственное решение уравнения Каталана тоже запрещается.

С чего Вы взяли?! Конечно, смотрели!

А в целом там история была такая. Василий принес мне доказательство того, что $M(2pq)\le 3$. Над которым мы бьемся (в смысле, Евгений бьется, при болельщиках ). Но в его доказательстве была ошибка. После исправления удалось сохранить доказательство только при $gcd(p-1,q-1)>4$. Хотя у меня и были подозрения, что это ограничение можно обойти.

[EUgeneUS]

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

Но в его доказательстве была ошибка. После исправления удалось сохранить доказательство только при $gcd(p-1,q-1)>4$. Хотя у меня и были подозрения, что это ограничение можно обойти.

История повторяется

Вот этот вариант (цитирую по исправленному тексту):

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

2б. $b = \frac{a^{q-1} - 1}{2^{p-4}}$

запрещается по модулю 4.

А вот этот вариант оказался не рассмотренным:

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

2а. $b = \frac{a^{q-1} + 1}{2^{p-4}}$

Если его подставить в паттерн, то получится:
$2 a^{q-1} (2 a^{q-1} +2) = (\sqrt{B}-1)(\sqrt{B}+1)$, и

$2 a^{q-1} = \sqrt{B}-1$,
Что для $\sqrt{B} = C^2$ приводить к уравнению Пелля с $n=2$, у которого куча решений.
А как доказывать для более высоких степеней тоже не знаю

[VAL]

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

История повторяется

Так что, уже не смотреть? Я только собрался с силами...

[Dmitriy40]

Ещё мелкая опечатка:

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

Тогда:
$ (2^{(p-3)/2}a^{(q-1)/2} - 1) (2^{(p-3)/2}a^{(q-1)/2} + 1) = 3^{(s-1)/2}с^{(t-1)/2}$,
где $s = {p,q}, s = {q,p}$

Видимо последняя строка должна быть $s = \{p,q\}, t=\{q,p\}, s \ne t$.