[seqfan] Re: Primes by rank

Robert Gerbicz robert.gerbicz at gmail.com
Fri May 28 19:06:35 CEST 2010


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.



More information about the SeqFan mailing list