login
This site is supported by donations to The OEIS Foundation.

 

Logo

"Email this user" was broken Aug 14 to 9am Aug 16. If you sent someone a message in this period, please send it again.

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

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.

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

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]][[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++ ]

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 | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy .

Last modified August 20 20:09 EDT 2017. Contains 290837 sequences.