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

[EUgeneUS]

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

И ещё вопрос: что варианты цепочек $n_6, n_7, n_0$, для случая $n_6 = 2 p^{34}$ запрещены - тоже проверено?

Конечно, проверено. Это же первый шаг
$2 x^2 \equiv 2 (mod 8)$ для всех нечетных $x$.

[Dmitriy40]

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

Я этот вывод не очень хорошо понимаю, но считаю верным

Давайте чуть подробнее.
Что тройка должна быть в $n_0$ или в $n_2$ считаем доказанным.
В $n_0$ она может входить в 4-х вариантах, в 4-й или 6-й или 1-й степени (этих два варианта).
Два из них, где она в первой степени, переобозначаем общим видом $2^4 3 x^2$ с разным значением $x$ для двух вариантов ($x=q^3$ и $x=2q^2$) и приравниваем к $n_2-2=n_0 \to 2p^{34}-2=2^4 3 x^2 \to p^{34}-1=24x^2$, последнее решаем вольфрамом (не знаю как руками) и получаем решения лишь $p=\pm1,x=0$, что не подходят.
Другие два, где тройка в 4-й или 6-й степени, разберу 6-ю: $n_0=2^4 3^6 q$, снова приравниваем к $n_2-2=2^4 3^6 q \to 2p^{34}-2=2^4 3^6 q \to p^{34}-1=2^3 3^6 q \to (x-1)(x+1)=2^3 3^6 q$, а отсюда берутся ограничения на величину $q\le 2^3 3^6 +1$ (мне же выше подробно объяснили почему), значит максимум $q_{max}=2^3 3^6 +1$ и максимум $n_0_{max}=2^3 3^6 q_{max}=2^3 3^6 (2^3 3^6 +1)<2^{30}$, что не подходит так как $n_2=2 p^{34}>2^{34}$. Аналогично с $2^6 3^4 q$, тут $q$ и $n_0$ ещё меньше.

-- 19.05.2022, 11:04 --

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

последнее решаем вольфрамом (не знаю как руками)

Кажется можно так: по модулю 137 решения возможны только если $x=0\pmod{137}$, но $q^3=0\pmod{137}\to q=137$, которое проверяется прямо и не подходит $\sqrt[34]{24\cdot137^6+1}<3<p$. С $2q^2=0\pmod{137}\to q=137$ аналогично.

UPD. Обоснование решений только при $x=0\pmod{137}$ (вычисляю $n_0/2$ двумя способами, через само $n_0$ и через $n_0=n_2-2$):

? v1=vector(137,i,-1); v2=v1; for(i=0,#v1-1, v1[i+1]=(24*i^2)%#v1; v2[i+1]=(i^34-1)%#v1); print(Set(v1)); print(Set(v2));
[0, 3, 5, 6, 10, 12, 13, 20, 21, 23, 24, 26, 27, 29, 31, 33, 35, 40, 41, 42, 43, 45, 46, 47, 48, 51, 52, 53, 54, 55, 57, 58, 62, 66, 67, 70, 71, 75, 79, 80, 82, 83, 84, 85, 86, 89, 90, 91, 92, 94, 95, 96, 97, 102, 104, 106, 108, 110, 111, 113, 114, 116, 117, 124, 125, 127, 131, 132, 134]
[0, 36, 99, 135, 136]

Общий остаток только нулевой.

[EUgeneUS]

Dmitriy40
Спасибо!

Некоторые мысли про доказательство невозможности четверки для $k=2pq$, для любых $p,q \geqslant 5$.
Если кратко, можно составить общую схему доказательства\проверки. Но вот с общим доказательством как-то не складывается..

Подробнее (начну сначала, поэтому будут озвучены также давно установленные известные факты).

I. Общие факты. И классификация факторизаций.
$k=2pq$ дает 5 факторизаций чисел в цепочке ($a, b, c$ - различные простые числа):
1. $a b^{p-1} c^{q-1}$
2. $a b^{pq - 1}$
3. $a^{2pq-1}$
4. $a^{2p-1} b^{p-1}$
5. $a^{2q-1} b^{q-1}$

Это даёт десять мест для размещения двойки, то есть десять вариантов факторизации с двойкой. Выпишем их все, попутно классифицируя.
Теперь $a, b,c ,d$ - различные простые нечётные числа.

1. $n_2$
1.1. $2 c^{p-1} d^{q-1}$
1.2. $2 c^{pq - 1}$

Эти факторизации
а) имеют вид $2x^2$, где $x$ - нечетно, поэтому:
б) могут располагаться в позиции $n_2$ и не могут в позиции $n_6$, так как $2 x^2 \equiv 2 (\mod 8)$
в) обеспечивают, что тройка может быть только в позициях $n_0$ или $n_2$, но не в $n_1$, так как $2 x^2 \equiv {0;2} (\mod 6)$

2. $n_0$ - большая нечетная степень двойки:
2.1. $2^{2p-1} a^{q-1}$
2.2. $2^{2q-1} a^{p-1}$
2.3. $2^{2pq-1}$

Эти факторизации запрещаются, так как имеют вид $2 x^2$, что приводит в уравнении $n_2 - n_0 = 2$, к тому что, разность квадратов должна быть единицей, что невозможно.

3. $n_0$ - "экзотичные"
Характеризуются тем, что с большой четной степенью двойки стоит степень только одного простого числа. А также тем (увидим ниже), что если в них и есть решения, то только ограниченное количество.

2.1. $2^{p-1} a^{2q-1}$
2.2. $2^{q-1} a^{2p-1}$
2.3. $2^{pq - 1} a$

4. $n_0$ - "каноничные"
4.1 $2^{p-1} a^{q-1} b$
4.2 $2^{q-1} a^{p-1} b$

-- 19.05.2022, 16:49 --

II. Исключение "экзотичных" факторизаций.

Применение "фокуса" с сокращением степени двойки приводит к шести уравнениям (по два на каждую факторизацию, $\pm$ даёт два уравнения для каждой строки):
а) $a^{2p-1} = 2^{q-4} \pm 1$
б) $a^{2q-1} = 2^{p-4} \pm 1$
в) $a = 2^{pq-4} \pm 1$

Далее алгоритм следующий:
1. Проверяем, что для всех шести уравнений нет решений для простого $a$. Что впрочем не гарантируется.
2. Если решений нет - "экзотические" факторизации запрещены.
3. Если решений есть
а) их надо подставить в соответствующую факторизацию
б) добавить $2$ (перешли к $n_2$).
в) факторизовать получившееся число.
4. Если факторизация не дала $2pq$ делителей, то "экзотические" факторизации запрещены.
5. Если факторизация дала $2pq$ делителей, то нашли $n_0$ и $n_2$ по $2pq$ делителей. Нужно проверить остальные числа в цепочке, вдруг нашлась.

То есть на каждый набор $p, q$ имеем конечное (и ограниченное) число проверок.
Но отрицательный результат, вообще говоря, не гарантируется.

-- 19.05.2022, 16:51 --

Notes:
1. Может быть и получится доказать запрет "экзотичных" факторизаций в общем случае.... У меня не получилось.
2. Проверка легко алгоритмизируется. И системами компьютерной алгебры может быть выполнена до весьма больших $p, q$.

-- 19.05.2022, 17:19 --

III. Исключение "каноничных" факторизаций.

Тут сложнее, поэтому очень схематично.

1. Доказываем, что тройка может быть только в $n_2$, но не в $n_0$.
а) Насколько понимаю, для этого требуется конечный набор проверок, но этот набор проверок будет каждый раз разный, для разных наборов $p, q$.
б) Более того, никто не гарантирует, что все проверки пройдут и тройка не может оказаться в $n_0$. Буде такое случится, это нужно рассматривать отдельно.

2. Фокус с сокращением степени двойки приведет к неким уравнениям, которые связывают $b$ с некой степенью $a$.
Таких уравнений будет четыре на каждый каноничнеый паттерн, итого восемь.
Часть из них возможно будет отброшена сразу из-за неразрешимости в целых или простых числах.

3. Для каждого не отброшенного случая, в нужно подставить в разложение выражение для $b$, после чего скомпоновать получившиеся выражение с факторизацией $n_2$.
Это утроит количество вариантов.

4. Далее оставшиеся варианты нужно отбрасывать, подбирая модули, по которым они запрещаются.
Хорошие результаты дают модули в виде степени тройки (для это определяли её точное место), семерка, и степени двойки.

Notes: насколько это можно формализовать, чтобы "скормить" системам компьютерной алгебры - не знаю. Наверное можно.
Буде такое получится, можно будет доказывать $M(2pq) = 3$ автоматически для огромного количества наборов $p, q$. Плюс будут выдаваться наборы $p, q$, для которых "возможны неожиданности", а это путь к нахождению таки четной максимальной цепочки.

[EUgeneUS]

И ещё ремарка по поиску $M(2pq) = 4$
Наиболее перспективно выглядит:

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

в) $a = 2^{pq-4} \pm 1$

Насколько понимаю, числа справа довольно часто являются простыми. А это гарантирует:
а) что $n_0$ - подходящее.
б) что в $n_2$ находится $2 x^2$

И далее
а) $x^2$ может оказаться, вида $c^{p-1} d^{q-1}$
б) а буде такое случится может оказаться, что и другие числа цепочки - подходящие.

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

[Dmitriy40]

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

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

Если не накладывать ограничения $p\le q$, то это одно и то же уравнение.
И до $p<10^4$ оно решений не имеет:

{forprime(p=5,10000,
   y=2^(p-4); a=0;
   forprime(q=5,oo,
      if(3^(2*q-1)>y+2, break);
      if(ispower(y+1,2*q-1,&a) && ispseudoprime(a), print(p*q*2,":",p,"*",q,", a=",a,", +1"));
      if(ispower(y-1,2*q-1,&a) && ispseudoprime(a), print(p*q*2,":",p,"*",q,", a=",a,", -1"));
   );
)}

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

в) $a = 2^{pq-4} \pm 1$

А вот это решения имеет, нашлось немного, но всё же:

{forprime(p=5,50,
   forprime(q=p,500,
      x=2^(p*q-4);
      if(ispseudoprime(x+1), print(p*q*2,":",p,"*",q,", +1"));
      if(ispseudoprime(x-1), print(p*q*2,":",p,"*",q,", -1"));
   );
)}
70:5*7, -1
130:5*13, -1
4570:5*457, -1
1222:13*47, -1
8854:19*233, -1

$a$ при этом получаются преогроменными (за исключением лишь с 70-ю и 130-ю делителями) и пытаться факторизовать числа из сотен цифр как-то слишком грустно.
Для 70 делителей $n_2$ содержит 486 делителей, для 130 делителей $n_2$ содержит 54 делителя, для 1222 делителя $n_2$ содержит 62762119218 делителей.

[EUgeneUS]

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

$a$ при этом получаются преогроменными (за исключением лишь с 70-ю и 130-ю делителями) и пытаться факторизовать числа из сотен цифр как-то слишком грустно.

1. Наличие решения гарантирует, что $n_2/2$ является полным квадратом. А вычисление квадрата - это быстро.
Факторизовать можно сразу $\sqrt{n_2/2}$. Это снизит порядок числа в два раза.

2. Кроме того, факторизовать $\sqrt{n_2/2}$ до конца не обязательно. Как только нашёлся один простой делитель, можно сразу проверить, что он в нужной степени ($(q-1)/2$ или $(p-1)/2$. Если нет - то неуспех, дальше можно не проверять.

3. Если успех, то оставшееся число опять будет снижено на несколько порядков.

4. Если нашлось три и больше простых делителя, то сразу неуспех. Дальше можно не проверять.

-- 19.05.2022, 20:09 --

Кстати, для этого варианта факторизацию вообще не нужно делать.
5. Так как заведомо $a>3$, то тройка должна быть в $n_2$. Это даёт такие варианты:

а) $2^{pq - 2} a - 1 = 3^{pq - 1}$ (выше я его упустил)
б) $2^{pq - 2} a - 1 = 3^{p-1} d^{q-1}$ (и перестановка $p \leftrightarrow q$)

6. Таком образом:
а) проверяем, что $n_2/2$ делится на нужную степень тройки (их три варианта). Если нет - неуспех. Соответствующий паттерн запрещается.
б) если нужная степень тройки имеется, то проверяем, что оставшееся число - есть известная полная степень (она четная) некого целого числа. Если нет - неуспех.
б) если таки да, то вот его уже проверяем на простоту.

6. Еще можно два числа: $2^{pq - 2} (2^{pq-4} \pm 1) - 1$ проверить по модулям степеней тройки. Может и запретится этот паттерн "наглухо".

[EUgeneUS]

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

Еще можно два числа: $2^{pq - 2} (2^{pq-4} \pm 1) - 1$

Тут опять опечатка надо: $2^{pq - 2} (2^{pq-4} \pm 1) +1$

upd:
Вот этот вариант: $2^{pq - 2} (2^{pq-4} + 1) +1$ запрещается по модулю 3 (остаток всегда равен 1, как у меня получилось)
А вот этот вариант $2^{pq - 2} (2^{pq-4} - 1) +1$ проверку проходит (если брать вместо $pq-4$ любые нечётные степени двойки). Там в нём (потенциальные решения) и находятся...

-- 19.05.2022, 20:26 --

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

И до $p<10^4$ оно решений не имеет:

А тут странно, что не нашлось тривиальное решение $p=5, a=1$. Наверное, потому что

ispseudoprime(a)

не считает $1$ за простое...

-- 19.05.2022, 20:56 --

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

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

Тут опять $a$ не может равняться трем.
Для "плюса" это проверяется по модулю четыре, для "минуса" - по модулю три.

А значит
а) тройка опять стоит в $n_2$
б) тогда можно подставить $a^{2p-1}$ и проверить по модулям степеням тройки....
... и получается, как в прошлый раз: "плюс" запрещен по модулю 3, "минус" - разрешен.

Получилось три варианта для проверки вместо шести.
Возможно, можно наложить более строгие условия, опираясь на простоту $a, p, q$...

[Dmitriy40]

Разумеется $1$ не простое.

Кроме того Вы же сами сказали:

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

Теперь $a, b,c ,d$ - различные простые нечётные числа.

Так что $a=1$ совершенно правильно не нашлось.

[VAL]

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

Некоторые мысли про доказательство невозможности четверки для $k=2pq$, для любых $p,q \geqslant 5$.

Отличная работа!
Даже мне все понятно (надеюсь)
На общее доказательство для всех случаев и не рассчитывал.
Но реально перейти от конкретных случаев к классам случаев.

Вот еще о чем подумалось:
Все известные мне тройки последовательных чисел с количеством делителей, сравнимым с $\pm2$ по модулю 12, имеют вид $n_7,n_0, n_1$. А существуют ли тройки вида $n_1, n_2, n_3$? Пусть даже без претензии на четверку.

PS: Пишу свое сообщение, прочитав процитированный пост. А ниже уже много комментов. Вдруг там уже все давно опровергли?

[Dmitriy40]

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

Все известные мне тройки последовательных чисел с количеством делителей, сравнимым с $\pm2$ по модулю 12, имеют вид $n_7,n_0, n_1$. А существуют ли тройки вида $n_1, n_2, n_3$? Пусть даже без претензии на четверку.

Существуют: $n=499676189295206188273623586457252641$.
Ещё вариант: $n=2\cdot4001688637356824879^{10}-1$.

[Dmitriy40]

А вот вариантов $d=12k+2, n_1,n_2,n_3$ похоже не существует: $n_3=0\pmod{27}$, но $n_2=2 p^{6k}=\{0;2;11;20\}\pmod{27}$, а надо $26$.

[VAL]

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

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

Все известные мне тройки последовательных чисел с количеством делителей, сравнимым с $\pm2$ по модулю 12, имеют вид $n_7,n_0, n_1$. А существуют ли тройки вида $n_1, n_2, n_3$? Пусть даже без претензии на четверку.

Существуют: $n=499676189295206188273623586457252641$.
Ещё вариант: $n=2\cdot4001688637356824879^{10}-1$.

Ясно!
А жаль! Это делает гипотезу отсутствия четверок еще более шаткой. А перспектива нахождения при этом по-прежнему туманна.

-- 20 май 2022, 00:28 --

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

А вот вариантов $d=12k+2, n_1,n_2,n_3$ похоже не существует: $n_3=0\pmod{27}$, но $n_2=2 p^{6k}=\{0;2;11;20\}\pmod{27}$, а надо $26$.

А вот это уже хорошо! Понятно где искать четверки.

[Dmitriy40]

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

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

А вот вариантов $d=12k+2, n_1,n_2,n_3$ похоже не существует: $n_3=0\pmod{27}$, но $n_2=2 p^{6k}=\{0;2;11;20\}\pmod{27}$, а надо $26$.

А вот это уже хорошо! Понятно где искать четверки.

Я тут не совсем прав, это может не запрещать если $12n+2$ факторизуется не как $2p$, т.е. вместо одного простого в большой степени могут быть два и более, например $d=110=2\cdot5\cdot11, d=170, d=182, d=230$ (может и для $d=50, d=98, d=242$), для таких надо ещё додумать.

-- 20.05.2022, 01:02 --

Да, для $d=110$ есть вот такое решение: $n=2\cdot5^{10}\cdot4190232441950047776490596937^4-1$.
Так что всё же далеко не все $d=12n+2, n=1\pmod8$ запрещены.

-- 20.05.2022, 01:35 --

Нашёл решение и для $d=50$: $n=2\cdot17^4\cdot201033742854206291^4-1$.

-- 20.05.2022, 12:50 --

Нашёл решение и для $d=98$: $n=2\cdot3^6\cdot383624017128165468623340914332028533^6-1$.

[EUgeneUS]

почти доказал невозможность "экзотических паттернов" для $k=2pq$, для любых $p,q \geqslant 5$.

Исключение последнего варианта упёрлось в доказательство отсутствия решений в простых числах некого уравнения. Решений там нет скорее всего даже в целых взиамно простых. Но я такое доказывать не умею
Подробности вечером.

[EUgeneUS]

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