This site is supported by donations to The OEIS Foundation.



The OEIS is looking to hire part-time people to help edit core sequences, upload scanned documents, process citations, fix broken links, etc. - Neil Sloane, njasloane@gmail.com

(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A177854 Smallest prime of rank n. 2
2, 3, 11, 131, 1571, 43717, 5032843, 1047774137 (list; graph; refs; listen; history; text; internal format)



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).


Table of n, a(n) for n=0..7.

L. Zhou, The rank of primes

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.


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.


The following program runs through all prime numbers until it finds the first rank 7 prime. (It took about a week.) 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 maxp, res = maxp]; res++ ]; res]; i=1; While[p = Prime[i]; s = Fr[p]; [p, s] >>> "prime_rank.out"; s<7, i++ ]


(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


These are the primes where records occur in A169818.

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

Sequence in context: A058114 A042337 A061482 * A273598 A135161 A066100

Adjacent sequences:  A177851 A177852 A177853 * A177855 A177856 A177857




Lei Zhou, May 14 2010


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

Definition corrected by Robert Gerbicz, May 28 2010



Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy .

Last modified May 28 17:57 EDT 2017. Contains 287241 sequences.