2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему На страницу Пред.  1 ... 57, 58, 59, 60, 61, 62, 63 ... 215  След.
 
 Re: Пентадекатлон мечты
Сообщение19.05.2022, 08:51 
Аватара пользователя


11/12/16
13833
уездный город Н
EUgeneUS в сообщении #1554921 писал(а):
И ещё вопрос: что варианты цепочек $n_6, n_7, n_0$, для случая $n_6 = 2 p^{34}$ запрещены - тоже проверено?

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

 Профиль  
                  
 
 Re: Пентадекатлон мечты
Сообщение19.05.2022, 10:33 
Заслуженный участник


20/08/14
11709
Россия, Москва
EUgeneUS в сообщении #1554921 писал(а):
Я этот вывод не очень хорошо понимаю, но считаю верным :wink:
Давайте чуть подробнее.
Что тройка должна быть в $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]
Общий остаток только нулевой.

 Профиль  
                  
 
 Re: Пентадекатлон мечты
Сообщение19.05.2022, 16:30 
Аватара пользователя


11/12/16
13833
уездный город Н
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$, для которых "возможны неожиданности", а это путь к нахождению таки четной максимальной цепочки.

 Профиль  
                  
 
 Re: Пентадекатлон мечты
Сообщение19.05.2022, 17:38 
Аватара пользователя


11/12/16
13833
уездный город Н
И ещё ремарка по поиску $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}$
б) а буде такое случится может оказаться, что и другие числа цепочки - подходящие.

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

 Профиль  
                  
 
 Re: Пентадекатлон мечты
Сообщение19.05.2022, 18:27 
Заслуженный участник


20/08/14
11709
Россия, Москва
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 делителей.

 Профиль  
                  
 
 Re: Пентадекатлон мечты
Сообщение19.05.2022, 19:14 
Аватара пользователя


11/12/16
13833
уездный город Н
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$ проверить по модулям степеней тройки. Может и запретится этот паттерн "наглухо".

 Профиль  
                  
 
 Re: Пентадекатлон мечты
Сообщение19.05.2022, 20:21 
Аватара пользователя


11/12/16
13833
уездный город Н
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$...

 Профиль  
                  
 
 Re: Пентадекатлон мечты
Сообщение19.05.2022, 21:38 
Заслуженный участник


20/08/14
11709
Россия, Москва
Разумеется $1$ не простое.

Кроме того Вы же сами сказали:
EUgeneUS в сообщении #1554936 писал(а):
Теперь $a, b,c ,d$ - различные простые нечётные числа.
Так что $a=1$ совершенно правильно не нашлось.

 Профиль  
                  
 
 Re: Пентадекатлон мечты
Сообщение19.05.2022, 22:16 
Заслуженный участник


27/06/08
4062
Волгоград
EUgeneUS в сообщении #1554936 писал(а):
Некоторые мысли про доказательство невозможности четверки для $k=2pq$, для любых $p,q \geqslant 5$.
Отличная работа!
Даже мне все понятно (надеюсь) :-)
На общее доказательство для всех случаев и не рассчитывал.
Но реально перейти от конкретных случаев к классам случаев.

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

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

 Профиль  
                  
 
 Re: Пентадекатлон мечты
Сообщение19.05.2022, 23:04 
Заслуженный участник


20/08/14
11709
Россия, Москва
VAL в сообщении #1554952 писал(а):
Все известные мне тройки последовательных чисел с количеством делителей, сравнимым с $\pm2$ по модулю 12, имеют вид $n_7,n_0, n_1$. А существуют ли тройки вида $n_1, n_2, n_3$? Пусть даже без претензии на четверку.
Существуют: $n=499676189295206188273623586457252641$.
Ещё вариант: $n=2\cdot4001688637356824879^{10}-1$.

 Профиль  
                  
 
 Re: Пентадекатлон мечты
Сообщение20.05.2022, 00:24 
Заслуженный участник


20/08/14
11709
Россия, Москва
А вот вариантов $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$.

 Профиль  
                  
 
 Re: Пентадекатлон мечты
Сообщение20.05.2022, 00:26 
Заслуженный участник


27/06/08
4062
Волгоград
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$.
А вот это уже хорошо! Понятно где искать четверки.

 Профиль  
                  
 
 Re: Пентадекатлон мечты
Сообщение20.05.2022, 00:47 
Заслуженный участник


20/08/14
11709
Россия, Москва
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$.

 Профиль  
                  
 
 Re: Пентадекатлон мечты
Сообщение20.05.2022, 10:35 
Аватара пользователя


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

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

 Профиль  
                  
 
 Re: Пентадекатлон мечты
Сообщение20.05.2022, 12:31 
Аватара пользователя


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

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 3218 ]  На страницу Пред.  1 ... 57, 58, 59, 60, 61, 62, 63 ... 215  След.

Модераторы: Karan, Toucan, PAV, maxal, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group