Search primes of form 2*n^n ± 1
 

[$]2n^n\pm 1[/$] may be prime. I just noticed two sequences in OEIS:
[LIST][*]0, 1, 12, 18, 251, ... [URL="https://oeis.org/A110932"](A110932)[/URL][*]2, 3, 357, 1400, ... [URL="https://oeis.org/A110931"](A110931)[/URL][/LIST]
which list all [$]n[/$] such that [$]2n^n+1[/$], respectively [$]2n^n-1[/$], 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

[QUOTE=JeppeSN;484199]

which list all [$]n[/$] such that [$]2n^n+1[/$], respectively [$]2n^n-1[/$], is prime.[/QUOTE]
No, haven't
But, mod 3 we get:

n=1 mod 3; 1ⁿ is always 1 mod 3 so 2*1ⁿ+1 is 0 mod 3
n= 2 mod 3
Case1 n is even, 2*2ⁿ+1 is 0 mod 3
Case2 n is odd, 2*2ⁿ-1 is 0 mod 3

Etc.

I did a small n range of 2*n^n-1 (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[/CODE]
I found no primes of that form, so a(5) > 5000 for A110931. The residue file and factors found are attached to this post. Just 90 PRP tests were needed with the default factoring limit in PFGW, so I wonder if an efficient sieve program could be made for the form 2*n^n+/-1?

I believe that my old MultiSieve sieved numbers of this form, k*b^b+/-1.

For easy elimination, it comes down to when (p+1)/2 or (p-1)/2 can be residue a power can take on mod prime p.

For odd primes p, the behavior of n[sup]n[/sup] (mod p) is kind of interesting. We have

(n+p)[sup]n+p[/sup] == n[sup]n+p[/sup] == n[sup]n+1[/sup] (mod p), so that

(n+k*p)[sup]n+k*p[/sup] == n[sup]n+k*p[/sup] == n[sup]n+k[/sup] (mod p), so that

(n+(p-1)*p)[sup]n+(p-1)*p[/sup] == n[sup]n+(p-1)*p[/sup] == n[sup]n+p-1[/sup], so that

(n+(p-1)*p)[sup]n+(p-1)*p[/sup] == n[sup]n[/sup] (mod p) for every positive integer n.

That is, n[sup]n[/sup] (mod p) is periodic, and (p-1)*p is a period.

For any k, 0 < k < p, there will be solutions to n[sup]n[/sup] - 1 == 0 (mod p) with n == k (mod p).

If k (mod p) has even multiplicative order, there will be solutions to n[sup]n[/sup] + 1 == 0 (mod p) with n == k (mod p).

[QUOTE=science_man_88;484311]For easy elimination, it comes down to when (p+1)/2 or (p-1)/2 can be residue a power can take on mod prime p.[/QUOTE]
We see from my last post to this thread, that for each integer r, 0 < r < p, the residues

(r + k*p)[sup]r+k*p[/sup] (mod p) are r[sup]1+k[/sup] (mod p).

These residues form a [i]group[/i]. So the question of whether

2*n[sup]n[/sup] == 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[sup]n[/sup] == -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).

How 'bout this one?
[URL="http://primes.utm.edu/primes/page.php?id=124574"]2*82992^82992+1[/URL] is prime.

[QUOTE=Batalov;484775]How 'bout this one?
[URL="http://primes.utm.edu/primes/page.php?id=124574"]2*82992^82992+1[/URL] is prime.[/QUOTE]

I see that you used MultiSieve. I hope that it saved you some time. Is sieving this form a candidate for mtsieve? It would probably take me only a day or two to write it.

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 0-4 minutes = ...quite a bit of time saved).

[QUOTE=Batalov;484775]How 'bout this one?
[URL="http://primes.utm.edu/primes/page.php?id=124574"]2*82992^82992+1[/URL] is prime.[/QUOTE]

Good one! I hoped this would catch your interest.

Are you continuing the search? And did you consider the minus form as well?

/JeppeSN