[seqfan] Re: Primes by rank

[T. D. Noe]

At 12:30 PM -0400 5/28/10, N. J. A. Sloane wrote:
>Dear Seq Fans, I've edited this entry to clarify the text.
>My question is, what is the sequence   a(n) = rank of n-th prime  which
>underlies this?  For which this sequence gives the records?
>Neil
>
>%I A177854
>%S A177854 2,3,11,131,1571,43717,5032843,1047774137
>%N A177854 Smallest prime of rank n.
>%C A177854 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 longest recursive primality proving chain depth is
>called the rank of P.
>%H A177854 L. Zhou, <a
>href="http://bitc.bme.emory.edu/~lzhou/blogs/?p=117">The rank of primes</a>
>%e A177854 The "trivial" prime 2 has rank 0. 3 = 2+1 takes one step to
>reduce to 2, so 3 has rank 1.
>%e A177854 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.
>%t A177854 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++ ]
>%K A177854 hard,nonn,more,nice,new
>%O A177854 0,1
>%A A177854 Lei Zhou (lzhou5(AT)emory.edu), May 14 2010
>%E A177854 Partially edited by N. J. A. Sloane, May 15 2010, May 28 2010

Rank is closely related to the Erdos-Selfridge classification of primes.
The sequence you ask for in not in OEIS.  It begins:
0, 1, 1, 1, 2, 2, 1, 2, 2, 2, 1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, \
2, 2, 2, 2, 2, 2, 2, 1, 3, 2, 2, 2, 2, 3, 2, 2, 3, 2, 2, 2, 2, 2, 2, \
2, 2, 3, 3, 3, 2, 2, 2, 1, 3, 2, 2, 3, 2, 3, 2, 2, 2, 3, 3, 3, 2, 3, \
2, 3, 2, 3, 2, 2, 2, 3, 3, 2, 2, 2, 2, 2, 2, 3, 3, 2, 3, 3, 3, 3, 2, \
2, 2, 2, 2, 2, 3, 3, 2

Here is a shorter Mma program for computing rank:
rank[1]=0; rank[2]=0; rank[3]=1; SetAttributes[rank,Listable]; rank[p_] :=
rank[p] = 1+Min[Max@@rank[First/@FactorInteger[p-1]],
Max@@rank[First/@FactorInteger[p+1]]]; rank[Prime[Range[100]]]

Tony