The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation. Hints (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)
 OFFSET 0,1 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). LINKS 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. EXAMPLE 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=2 has rank 0; P1=3 has rank 1; P1=11: P1+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. MATHEMATICA 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]][]]; If[maxm < thism, maxm = thism], {jm, 1, szm}]; maxp = 0; Do[thisp = Fr[fp[[jp]][]]; If[maxp maxp, res = maxp]; res++ ]; res]; i=1; While[p = Prime[i]; s = Fr[p]; [p, s] >>> "prime_rank.out"; s<7, i++ ] PROG (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 CROSSREFS 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 KEYWORD hard,nonn,more,nice AUTHOR Lei Zhou, May 14 2010 EXTENSIONS Partially edited by N. J. A. Sloane, May 15 2010, May 28 2010 Definition corrected by Robert Gerbicz, May 28 2010 STATUS approved

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

Last modified September 23 14:40 EDT 2021. Contains 347618 sequences. (Running on oeis4.)