[seqfan] Re: Primes by rank

[Lei Zhou]

The longest branch of the shortest proving tree?

At 01:06 PM 5/28/2010, you wrote:
>2010/5/28 N. J. A. Sloane <njas at research.att.com>
>
> >
> > 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<http://bitc.bme.emory.edu/%7Elzhou/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
> >
> >
> >
> > _______________________________________________
> >
> > Seqfan Mailing list - http://list.seqfan.eu/
> >
>
>I think that the definition is wrong, it should be "The shortest recursive
>primality proving chain depth is called the rank of P." and not the longest.
>Otherwise for example the rank of 5 would be 2 (and implying that a(2)=5),
>because 5+1=2*3, and the rank of 3 is 1. Using the shortest in the
>definition gives 1, because 5-1=2^2 and 2 has rank of 0.
>
>_______________________________________________
>
>Seqfan Mailing list - http://list.seqfan.eu/