20180403, 22:43  #1 
"Jeppe"
Jan 2016
Denmark
A2_{16} Posts 
Search primes of form 2*n^n ± 1
\(2n^n\pm 1\) may be prime. I just noticed two sequences in OEIS:
which list all \(n\) such that \(2n^n+1\), respectively \(2n^n1\), is prime. The search limit given in OEIS is \(n=35000\) and \(n=4000\), respectively. Has anyone who reads this searched these forms before, and to what limit? Maybe a new prime can be found (incredible optimist)? And clearly it will be a provable prime (as a neighbor to a number whose full factorization is trivial). /JeppeSN 
20180403, 23:24  #2 
"Forget I exist"
Jul 2009
Dumbassville
8,369 Posts 

20180404, 00:56  #3 
"Dylan"
Mar 2017
210_{16} Posts 
I did a small n range of 2*n^n1 (ie n = 4000 to n = 5000) to get a gauge of the speed of a PRP test of this form and to see how many tests would have to be run. Using the following command line
Code:
pfgw64 f lresidues.txt 2ktothekminus1.pfgw 
20180404, 01:23  #4 
"Mark"
Apr 2003
Between here and the
7×857 Posts 
I believe that my old MultiSieve sieved numbers of this form, k*b^b+/1.

20180404, 21:57  #5 
"Forget I exist"
Jul 2009
Dumbassville
8,369 Posts 
For easy elimination, it comes down to when (p+1)/2 or (p1)/2 can be residue a power can take on mod prime p.
Last fiddled with by science_man_88 on 20180404 at 22:15 
20180406, 22:00  #6 
Feb 2017
Nowhere
3,779 Posts 
For odd primes p, the behavior of n^{n} (mod p) is kind of interesting. We have
(n+p)^{n+p} == n^{n+p} == n^{n+1} (mod p), so that (n+k*p)^{n+k*p} == n^{n+k*p} == n^{n+k} (mod p), so that (n+(p1)*p)^{n+(p1)*p} == n^{n+(p1)*p} == n^{n+p1}, so that (n+(p1)*p)^{n+(p1)*p} == n^{n} (mod p) for every positive integer n. That is, n^{n} (mod p) is periodic, and (p1)*p is a period. For any k, 0 < k < p, there will be solutions to n^{n}  1 == 0 (mod p) with n == k (mod p). If k (mod p) has even multiplicative order, there will be solutions to n^{n} + 1 == 0 (mod p) with n == k (mod p). 
20180407, 13:47  #7  
Feb 2017
Nowhere
3,779 Posts 
Quote:
(r + k*p)^{r+k*p} (mod p) are r^{1+k} (mod p). These residues form a group. So the question of whether 2*n^{n} == 1 (mod p) for some n == r (mod p) is, whether 2 (mod p) is in the group generated by r (mod p). Since the multiplicative group of nonzero residues (mod p) is cyclic, the question becomes whether the multiplicative order of 2 (mod p) divides the multiplicative order of r (mod p). Similarly, the question of whether 2*n^{n} == 1 (mod p) for some n == r (mod p) becomes whether the multiplicative order of 2 (mod p) divides the multiplicative order of r (mod p). 

20180408, 16:19  #8 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2
5·1,831 Posts 
How 'bout this one?
2*82992^82992+1 is prime. 
20180408, 16:56  #9  
"Mark"
Apr 2003
Between here and the
176F_{16} Posts 
Quote:


20180408, 17:49  #10 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2
5×1,831 Posts 
I am not sure how frequent this use for this code branch would be.
The depth was around 29.3 bits after a day or two sieving (on 1 core up to n<=250k) so I am sure that it did save some time; factors for these are general, so I now checked a default PFGW sieving would have been ~26 bits (~83,000 candidates times 04 minutes = ...quite a bit of time saved). 
20180408, 21:12  #11  
"Jeppe"
Jan 2016
Denmark
162_{10} Posts 
Quote:
Are you continuing the search? And did you consider the minus form as well? /JeppeSN 

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Primes of the form (b+1)*b^n+1 and b^n+(b+1)  sweety439  sweety439  162  20200515 18:33 
Primes of the form n+phi(n)  carpetpool  carpetpool  3  20170126 01:29 
Infinitely many primes of a form?  PawnProver44  Homework Help  1  20160315 22:39 
Primes of the form a^(2^n)+b^(2^n)  YuL  Math  21  20121023 11:06 
Primes of the form 2.3^n+1  Dougy  Math  8  20090903 02:44 