The rank of primes

By: | Post date: May 14, 2010 | Comments: 64 Comments

Posted in categories: Fun Stuffs, Prime Search

Brillhart – Lehmer – Selfridge algorithm provides a general primality proving method as long as you can factor P+1 or P-1. Therefore, for any prime number, when P+1 or P-1 get fully factored, the primality of any factors of P+1 or P-1 can also be proven by the same algorithm recursively.

For example, prime number P0=131, P0+1=132=2^2*3*11.
P1[1]=2 is trival prime, no recursion needed, recursion depth = 0;
P1[2]=3, P1[2]-1=2 is trival prime, one recursion, recursion depth = 1;
P1[3]=11; P1[3]+1=12=2^2*3; one more recursion from 3, recursion depth = 2;
So, P=131 has total maximum recursion depth 2+1 = 3.

We define the maximum recursion depth of the primality proving sequence using Brillhart – Lehmer – Selfridge algorithm as the rank of the prime number.

In this way, we can easily find, that
2 has the rank of 0;
3 is the smallest prime ranked 1;
11 is the smallest prime ranked 2;
131 is the smallest prime ranked 3;

The following Mathematica program is used to figure the rank of prime numbers until a rank 7 prime is found:

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

The result:
1571 is the smallest prime ranked 4;
43717 is the smallest prime ranked 5;
5032843 is the smallest prime ranked 6;
1047774137 is the smallest prime ranked 7.

The result:
All Mersenne and Fermat primes have the rank of 1;
All Woodall, Cullen, General Woodall, General Cullen, General Fermat primes’ rank is one more than the rank of the highest ranked factor of k and n.

64 Comments

Leave a Reply