A177854 Smallest prime of rank n.

2, 3, 11, 131, 1571, 43717, 5032843, 1047774137, 7128418089643

Offset: 0

Author

Lei Zhou, May 14 2010

Keywords

• hard
• nonn
• more
• nice

Comments

The Brillhart-Lehmer-Selfridge algorithm provides a general method for proving the primality of P as long as one can factor P+1 or P-1. Therefore for any prime number, when P+1 or P-1 is completely factored, the primality of any factors of P+1 or P-1 can also be proved by the same algorithm. The shortest recursive primality proving chain depth is called the rank of P (cf. A169818).

Examples

			The "trivial" prime 2 has rank 0. 3 = 2+1 takes one step to reduce to 2, so 3 has rank 1.
P=131: P+1=132=2^2*3*11. P1[1]=2 has rank 0; P1[2]=3 has rank 1; P1[3]=11: P1[3]+1=12=2^2*3; is one step from 3 and has recursion depth = 2. So P=131 has total maximum recursion depth 2+1 = 3 and therefore has rank 3.
		

Links

• J. Brillhart, D. H. Lehmer and J. L. Selfridge, New primality criteria and factorizations of 2^m+-1, Math. Compl. 29 (1975) 620-647.
• Wikipedia, Lucas-Lehmer-Riesel test.
• Lei Zhou, The rank of primes.

Crossrefs

These are the primes where records occur in A169818.

Cf. A005113, A056637. - Robert G. Wilson v, May 28 2010

Programs

Mathematica

(* The following program runs through all prime numbers until it finds the first rank n prime. (It took about a week for n = 7.) *) Fr[n_]:= Module[{nm, np, fm, fp, szm, szp, maxm, maxp, thism, thisp, res, jm, jp}, If[n == 2, res = 0, nm = n - 1; np = n + 1; fm = FactorInteger[nm]; fp = FactorInteger[np]; szm = Length[fm]; szp = Length[fp]; maxm = 0; Do[thism = Fr[fm[[jm]][[1]]]; If[maxm < thism, maxm = thism], {jm, 1, szm}]; maxp = 0; Do[thisp = Fr[fp[[jp]][[1]]]; If[maxp < thisp, maxp = thisp], {jp, 1, szp}]; res = Min[maxm, maxp] + 1 ]; res]; target=0; Do[p = Prime[i]; s = Fr[p]; If[s == target, Print[p]; target++], {i, Infinity}]

PARI

rank(p)=if(p<8, return(p>2)); vecmin(apply(k->vecmax(apply(rank, factor(k)[,1])), [p-1,p+1]))+1
print1(2); r=0;forprime(p=3,, t=rank(p); if(t>r, r=t; print1(", "p))) \\ Charles R Greathouse IV, Oct 03 2016

Extensions

Partially edited by N. J. A. Sloane, May 15 2010, May 28 2010

Definition corrected by Robert Gerbicz, May 28 2010

a(8) from Florian Baur, Sep 05 2024