20191124, 20:30  #1 
"James Short"
Mar 2019
Canada
2·3^{2} Posts 
Other ways of finding WR primes
I've been thinking about this for some time as to why Mersenne integers are the #1 candidate for finding WR prime numbers, and have basically come to these two reasons:
1) There is a fast deterministic primality test for them (ie. LucasLehmer primality test). 2) Mersennes are far more likely to be prime compared to what the Prime Number Theorem would predict since any prime integer that divides is forced to be of the form . For simplicity, lets call the above conditions #1 and #2. Empirical evidence suggests that Wagstaff numbers () "beat" Mersenne numbers on condition #2 above. For instance, for all prime exponents , there are 24 Wagstaff primes but only 22 Mersenne primes. Fyi  there's no proof that Wagstaff's are generally more likely to be prime than Mersenne numbers. All we know is that they are only 1/3 the size of Mersenne numbers, yet just like the Mersenne, composite prime factors are restricted to being of the form . In any case, its completely irrelevant because Wagstaff fail condition #1  there is no fast deterministic primality test for them. CANDIDATE #2  Fermat numbers Question: Does it satisfy condition #1? Ans: Yes Fermat numbers, , satisfy condition #1 above because they are a Proth number (ie ) and therefore primality can be deterministically proven using Fermat's primality test. Question: Do Fermat numbers match or beat Mersenne numbers on condition number #2? Ans: Yes Fermat numbers beat Mersenne integers on condition #2 because although they are bits long in size, any potential prime factor is restricted to being of the form . This is essentially "twice as restrictive" as the Mersenne condition of having to be of the form . Unfortunately Fermat integers grow doubleexponentially. For this reason it is believed that there are no more prime Fermat numbers after However what if we generalize the Fermat number? Definition: When prime its easy to show that this will be a Proth number. Furthermore, any prime factors of these numbers will have to be extremely restrictive. Its not too difficult to prove that any prime factor will have to be of the form . Empirical testing shows that the congruence restriction is even stronger than the above and is in fact . Example: . This is a Proth number because it can be written as . We can quickly establish its primality using the Fermat primality test. As an aside, we can actually find numbers that are more restrictive than the condition if we are willing to relax the Proth condition that for integers of the form . Primitive factors of numbers of the form where n is a "Highly Composite Number" (see: https://en.wikipedia.org/wiki/Highly_composite_number) appear to be the most "restrictive" with regards to condition #2. Anyway some conjectures I've been unable to resolve: Conjecture #1  prime factors of have to be of the form . Conjecture #2  If a primitive factor of where n is a Highly Composite Number "almost" satisfies Proth's condition (that is, it can put in the form where isn't too much larger than ), we deterministically establish its primality almost as quickly. 
20191124, 20:59  #2 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2
2×3^{3}×5×37 Posts 
Small typos aside, you have found exactly the right logic to approach the most actionable paths to the potentially largest known provable primes. Conditions #1 and #2 are correct.
To summarize, you would want to find the candidates that are a) fast to test, and b) that will have the significantly higher probability of being productive (by having restricted factors, and therefore prefactored to a much higher level). There are at least two generalizations for the Fermat numbers: 1. the "cyclotomic numbers" (like your second kind, but p does not have to be always prime)  the good choice of "p" is powers of 3. Some history. Some more history.* and 2. Generalized Fermat numbers: \(b^{2^n} +1\), with b > 2 Both are being actively searched. * If you read M.Oakes' old post, you will find that your conjectures are not conjectures. The factors, of course, are of the special form. 
20191124, 21:25  #3 
"Rashid Naimi"
Oct 2015
Remote to Here/There
2306_{10} Posts 
I think the bottleneck in finding WR Primes at the moment, is the time it takes to sieve candidates via probablystic tests which generally come down to the time it takes to do modular Exponentiation.
As such any NearMultipleSquares (not necessarily only 1 of) format that can be deterministically proven to be prime is a potentially fruitful approach. This makes me wonder why such formats are not more rigorously tested. Last fiddled with by a1call on 20191124 at 21:29 
20191124, 21:26  #4  
"99(4^34019)99 palind"
Nov 2016
(P^81993)SZ base 36
2×5^{2}×73 Posts 
Quote:
F_{n,p} = Phi_{p*2^(n+1)}(2) Phi_{n}(2) is prime for n = 2, 3, 4, 5, 6, 7, 8, 9, 10, 12, 13, 14, 15, 16, 17, 19, 22, 24, 26, 27, 30, 31, 32, 33, 34, 38, 40, 42, 46, 49, 56, 61, 62, 65, 69, 77, 78, 80, 85, 86, 89, 90, 93, 98, 107, 120, 122, 126, 127, 129, 133, 145, 150, 158, 165, 170, 174, 184, 192, 195, 202, 208, 234, 254, 261, 280, 296, 312, 322, 334, 345, 366, 374, 382, 398, 410, 414, 425, 447, 471, 507, 521, 550, 567, 579, 590, 600, 607, 626, 690, 694, 712, 745, 795, 816, 897, 909, 954, 990, 1106, 1192, 1224, 1230, 1279, 1384, 1386, 1402, 1464, 1512, 1554, 1562, 1600, 1670, 1683, 1727, 1781, 1834, 1904, 1990, 1992, 2008, 2037, 2203, 2281, 2298, 2353, 2406, 2456, 2499, 2536, 2838, 3006, 3074, 3217, 3415, 3418, 3481, 3766, 3817, 3927, ... 

20191124, 21:34  #5  
"99(4^34019)99 palind"
Nov 2016
(P^81993)SZ base 36
2·5^{2}·73 Posts 
Quote:
F(1,p) is prime only for p = 3 (because of the algebra factors) F(2,p) is prime for p = 3, 5, 7, 23, 37, 89, 149, 173, 251, 307, 317, 30197, 1025393, ... F(3,p) is prime for p = 5, 13, 23029, 50627, 51479, 72337, ... F(4,p) is prime for p = 239, ... F(5,p) is prime for p = 3, 13619, ... F(6,p) is not prime for all p <= 2^12 

20191124, 21:38  #6 
"99(4^34019)99 palind"
Nov 2016
(P^81993)SZ base 36
111001000010_{2} Posts 
https://archive.is/20120529014233/ht...os/fermat6.htm also list the primes of the form Phi_{n}(2), but is for n=p^r (p is prime, r>=1) instead of n=p*2^r (p is prime, r>=1)
Last fiddled with by sweety439 on 20191124 at 21:38 
20191124, 22:24  #7  
"James Short"
Mar 2019
Canada
2×3^{2} Posts 
Quote:
I haven't considered \(b^{2^n} +1\), with b > 2 because their bitsize is even bigger to when 2 is used as a base. I have done a tad of investigating into divisibility sequences which grow exponentially, but at a rate that's between 1 and 2 though. For example, the Fibonacci numbers  or just where p is prime. The primitive factors are easily found in the case. Furthermore, most of these number appear to need to be in the form (at least in the case). The congruence restrictions don't appear quite as strict as a generalized Fermat number, however the nice part is that Fibonacci numbers grow exponentially proportional to which mean their bitsize is considerably more restrictive compared to any integer base b > 1. There are possibly other Lucas sequences which are divisibility sequences which could grow exponentially with respect to some where b < 1.61 too. I wonder if Mike Oakes or others have ever investigated this!? 

20191124, 22:32  #8  
"James Short"
Mar 2019
Canada
2×3^{2} Posts 
Quote:


20191124, 22:57  #9  
"99(4^34019)99 palind"
Nov 2016
(P^81993)SZ base 36
2×5^{2}×73 Posts 
Quote:
A085398(prime(n)) = A066180(n) for n>=1 A085398(2*prime(n)) = A103795(n) for n>=2 A085398(2^(n+1)) = A056993(n) for n>=0 A085398(3^(n+1)) = A153438(n) for n>=1 A085398(2*3^(n+1)) = A246120(n) for n>=0 A085398(2^(n+1)*3) = A246119(n) for n>=0 A085398(2^(n+1)*3^2) = A298206(n) for n>=0 A085398(2^(n+1)*3^(n+1)) = A246121(n) for n>=0 A085398(5^(n+1)) = A206418(n) for n>=1 Also, A205506 is a subsequence of A085398 for n = 2^i*3^j with i,j >= 1 A181980 is a subsequence of A085398 for n = 2^i*5^j with i,j >= 1 

20191124, 22:59  #10 
"99(4^34019)99 palind"
Nov 2016
(P^81993)SZ base 36
E42_{16} Posts 
This is the smallest k>=2 such that Phi_{n}(k) is prime, for 1<=n<=2500

20191125, 00:41  #11  
"James Short"
Mar 2019
Canada
2×3^{2} Posts 
Quote:
I knew that as n increase the number of primes drops drastically, however for n > 3, the frequency of primes really looks as if its fallen off of a cliff! I guess one could try to sieve out some smaller prime factors using a p1 factoring algorithm to root out small and/or smooth numbers idk 

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Finding VERY large primes  c10ck3r  Information & Answers  34  20120829 16:47 
Best Work for Finding Primes  Unregistered  Information & Answers  9  20120624 13:50 
Finding primes using modular stacking  goatboy  Math  1  20071207 12:30 
Finding primes from 1 upwards  henryzz  Lounge  35  20071020 03:06 
Finding primes with a PowerPC  rogue  Lounge  4  20050712 12:31 