НОД(2^n+1,n!-1)=1 или 2n+1, третьего не дано

[maxal]

Руст писал(а):

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

$$X_m=\prod_{d|m, d-odd}(2^{m/d}+1)^{\mu (d)}.$$

Во внутреннем цикле пробегаем по нечётным k и вычисляем $a_k=(km)!\mod X_m$, если $(a_k-1,X_m)>1$, то $n=km$ исключительное число для всех простых делителей $p|(a_k-1,X_m)$. При этом время от времени вычисляем $b_k=(a_k,X_m)$ и сокращаем $X_m$ на простые делители $b_k$.
Я этот алгоритм не стал реализовать, хотя по нему можно было найти указанные исключительные n гораздо быстрее.

У меня есть несколько вопросов по этому алгоритму:
В каких пределах бежит $k$ ?
Что значит "время от времени" ?
И почему этот алгоритм быстрее "обычного" перебора простых p и поиска подходящих n (в пределах до $p-1$) ? Например, сколько элементарных операций потребуется этому алгоритму, чтобы найти решение $p=4327489, n=3652374.$ ?

[Руст]

maxal писал(а):

У меня есть несколько вопросов по этому алгоритму:
В каких пределах бежит $k$ ?
Что значит "время от времени" ?
И почему этот алгоритм быстрее "обычного" перебора простых p и поиска подходящих n (в пределах до $p-1$) ? Например, сколько элементарных операций потребуется этому алгоритму, чтобы найти решение $p=4327489, n=3652374.$ ?

1. По k пробегаем, пока $km<X_m$, точнее можно до половины (учитывая симметрию факториала по модулю p) при этом надо учесть, что X_m время от времени сокращается на простые делители и поэтому максимальное значение это $(p-1)/2$, где p максимальный делитель. На самом деле можно искуственно сократит скажем пока km<10^9.
Время от времени, это связано с сокращением $X_m$ можно через каждые 1000 шагов, можно через 10000 - это регулируется с вероятностями появления не очень больших простых делителей этого числа.
Этот алгоритм дал бы все найденные исключения уже в течение первого часа счёта. Дело в том, что истинные полупорядки числа 2 по модулям полученных простых чисел не большие, для последнего насколько помнится 66 а для самого большего порядка 10000.

[maxal]

Руст писал(а):

Дело в том, что истинные полупорядки числа 2 по модулям полученных простых чисел не большие

А зачем тогда огород городить? Можно просто взять простые делители $2^m + 1$ (или $X_m$) из Cunningham Project и осуществить поиск подходящих $n$ для них. Другими словами, с помощью Cunningham Project можно быстро факторизовать $X_m$ для $m$ в пределах тысячи.

Но все равно такой поиск упирается в $\Theta(p)$ умножений по модулю $p$, так что для больших $p$ особо не разгуляешься.

Вот набросал прожку на PARI/GP:

? default(primelimit,10^6)
? allocatemem(2^30)
? \r cunn2.gp
? X(m) = local(r=1); fordiv(m/2^valuation(m,2),d,r*=(2^(m/d)+1)^moebius(d)); r
? test(p,m=0) = if(m==0,m=znorder(Mod(2,p));if(m%2,return(0));m\=2); local(r=Mod(1,p),t=0); for(i=2,p-1-m,r*=i; if(i!=(p-1)/2&&i==Mod(m,2*m)&&r==1,print1(" ",i);t=1));t
? for(m=1,10^4, print1(Strchr(13),m); f=factorint(X(m))[,1]; for(i=1,#f, if(f[i]<10^9&&test(f[i],m),print(" ",f[i])) ))

Посмотрим, может чего нового найдет.

P.S. cunn2.gp берется из cunngp.tgz тут.

[Руст]

На самом деле в этой задаче факторизация $X_m$ не требуется. Во первых и так время от времени сокращая на $gcd(X_m,(km)!)$ мы уменьшаем его на малые делители и считаем не до очень больших n.
Вот факторизация чисел $c^m-1$ действительно нужно в решении задачи $n|2^n-c$, обсуждённой здесь ранее. На самом деле для доказательства бесконечности числа решений и их нахождения достаточно проверить по конечному числу m (думаю достаточно данных в указанной ссылке для с=3) и бесконечности составных чисел Ферма

$$a(c^m)^{2^k}+1)$$

,
здесь a=1 для чётного c (не особый случай $c\not =\pm 2^k$) и a=1/2 для нечётного c.
Я в уме построил эффективный алгоритм построения решений этой задачи и для доказательства их бесконечности. Сдерживала меня необходимость факторизации больших чисел указанного вида.

[maxal]

Руст писал(а):

На самом деле в этой задаче факторизация $X_m$ не требуется. Во первых и так время от времени сокращая на $gcd(X_m,(km)!)$ мы уменьшаем его на малые делители и считаем не до очень больших n.

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

Руст писал(а):

Вот факторизация чисел $c^m-1$ действительно нужно в решении задачи $n|2^n-c$, обсуждённой здесь ранее. На самом деле для доказательства бесконечности числа решений и их нахождения достаточно проверить по конечному числу m (думаю достаточно данных в указанной ссылке для с=3) и бесконечности составных чисел Ферма

$$a(c^m)^{2^k}+1)$$

,
здесь a=1 для чётного c (не особый случай $c\not =\pm 2^k$) и a=1/2 для нечётного c.
Я в уме построил эффективный алгоритм построения решений этой задачи и для доказательства их бесконечности. Сдерживала меня необходимость факторизации больших чисел указанного вида.

Приведи подробности своего алгоритма (лучше в исходной теме) - обсудим...

[maxal]

maxal писал(а):

Посмотрим, может чего нового найдет.

Проверил все $m\leq 775$ и все простые делители $X_m$ меньшие $10^9$ - ничего нового кроме уже известного $p=4327489$ не найдено. Потом попробую для больших $m$...

Кстати, если считать, что значения факториалов по модулю простого числа равномерно распределены, то вероятность для $p$ быть искомым равна примерно $\frac{1}{\mathop{ord}_p(2)}$. В виду того, что
$$\sum_p \frac{1}{\mathop{ord}_p(2)} > \sum_p \frac{1}{p} = +\infty$,
можно ожидать, что количество решений бесконечно.

[Руст]

Точнее вероятность нахождения с полупорядком m есть $\frac{a(m)}{2m}$, где a(m) ведёт себя примерно $a(m)=\sum_{p-odd, \ p|2^m+1}(1-2^{-p})$, соответственно расходимость даже более высокая. Именно из этих соображений я сказал о бесконечности числа исключений.
Что касается алгоритма, я упустил одну деталь. Лучше не вычислять $X_m$, а работать непосредственно с $2^m+1$, дело в том, что существенная часть операций есть умножение по модулю этого числа. Умножать по модулю $2^m+1$ гораздо проще (умножаем обычным образом n имеет не больше 32 разрядов и разряды превосходящие m убираем сверху и вычитываем снизу), При этом некоторый пересчёт с лихвой компенсируется простотой вычисления по этому модулю.

[Руст]

Провёл громоздкие вычисления функции $g(n)=gcd(2^n+1,n!-1)$. Убедился, что g(n)=1 или $g(n)=2n+1$, если последнее является специальным простым $p=3\mod 8$ за единственным исключением при $n\le 225000$: $g(221799)=521881$.
Нашёл так же все особые пары (p,n) простыx чисел $p|g(n)$ при $p\le 225 000 000$. Если (p,n) особая пара с нечётным n, то пара (p,p-1-n) так же особая пара и их лучше считать одной парой. Вот список найденных пар
$p=521881,n=221799$,
$p=774593,n=338884$,
$p=4327489, n=3652374$,
$p=21764537, n=8161701$,
$p=28807001, n=10802625$,
$p=213 833 929, n=80 187 723$.
Примечательно, что $ord_2(p-1)=3 \ or \ 6$, в зависимости от того нечётно или чётно n.
Действительно ли это всегда так - для меня загадка.