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. <\/p>\n
For example, prime number P0=131, P0+1=132=2^2*3*11.
\nP1[1]=2 is trival prime, no recursion needed, recursion depth = 0;
\nP1[2]=3, P1[2]-1=2 is trival prime, one recursion, recursion depth = 1;
\nP1[3]=11; P1[3]+1=12=2^2*3; one more recursion from 3, recursion depth = 2;
\nSo, P=131 has total maximum recursion depth 2+1 = 3.<\/p>\n
We define the maximum recursion depth of the primality proving sequence using Brillhart – Lehmer – Selfridge algorithm as the rank of the prime number.<\/p>\n
In this way, we can easily find, that
\n2 has the rank of 0;
\n3 is the smallest prime ranked 1;
\n11 is the smallest prime ranked 2;
\n131 is the smallest prime ranked 3;<\/p>\n
The following Mathematica program is used to figure the rank of prime numbers until a rank 7 prime is found:<\/p>\n
Fr[n_]:=
\nModule[{nm, np, fm, fp, szm, szp, maxm, maxp, thism, thisp, res, jm, jp},
\nIf[n == 2, res = 0,
\nnm = n – 1; np = n + 1; fm = FactorInteger[nm]; fp = FactorInteger[np]; szm = Length[fm];
\nszp = Length[fp]; maxm = 0;
\nDo[thism = Fr[fm[[jm]][[1]]];
\nIf[maxm < thism, maxm = thism], {jm, 1, szm}];
\nmaxp = 0;
\nDo[thisp = Fr[fp[[jp]][[1]]];
\nIf[maxp maxp, res = maxp]; res++]; res];
\ni=1;While[p = Prime[i]; s = Fr[p];[p, s] >>> “prime_rank.out”;s<7,i++]<\/p>\n
The result:
\n1571 is the smallest prime ranked 4;
\n43717 is the smallest prime ranked 5;
\n5032843 is the smallest prime ranked 6;
\n1047774137 is the smallest prime ranked 7.<\/p>\n
The result:
\nAll Mersenne and Fermat primes have the rank of 1;
\nAll 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.<\/p>\n","protected":false},"excerpt":{"rendered":"
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 […]<\/p>\n","protected":false},"author":2,"featured_media":0,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[5,6],"tags":[],"class_list":["post-117","post","type-post","status-publish","format-standard","hentry","category-to-entertain-myself","category-looking-for-a-megaprime","post-blog"],"_links":{"self":[{"href":"https:\/\/csic.som.emory.edu\/~lzhou\/blogs\/index.php?rest_route=\/wp\/v2\/posts\/117","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/csic.som.emory.edu\/~lzhou\/blogs\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/csic.som.emory.edu\/~lzhou\/blogs\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/csic.som.emory.edu\/~lzhou\/blogs\/index.php?rest_route=\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"https:\/\/csic.som.emory.edu\/~lzhou\/blogs\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=117"}],"version-history":[{"count":0,"href":"https:\/\/csic.som.emory.edu\/~lzhou\/blogs\/index.php?rest_route=\/wp\/v2\/posts\/117\/revisions"}],"wp:attachment":[{"href":"https:\/\/csic.som.emory.edu\/~lzhou\/blogs\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=117"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/csic.som.emory.edu\/~lzhou\/blogs\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=117"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/csic.som.emory.edu\/~lzhou\/blogs\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=117"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}