mersenneforum.org > Math Other ways of finding WR primes
 Register FAQ Search Today's Posts Mark Forums Read

 2019-11-24, 20:30 #1 jshort   "James Short" Mar 2019 Canada 100012 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. Lucas-Lehmer primality test). 2) Mersennes are far more likely to be prime compared to what the Prime Number Theorem would predict since any prime integer $q$ that divides $2^{p} - 1$ is forced to be of the form $1 + k \cdot 2 \cdot p$. For simplicity, lets call the above conditions #1 and #2. Empirical evidence suggests that Wagstaff numbers ($\frac{2^{p} + 1}{3}$) "beat" Mersenne numbers on condition #2 above. For instance, for all prime exponents $p < 10^{4}$, 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 $1 + k \cdot 2 \cdot p$. 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, $2^{2^{n}} + 1$, satisfy condition #1 above because they are a Proth number (ie $k \cdot 2^{n} + 1, k < 2^{n}$) 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 $2^{n}$ bits long in size, any potential prime factor is restricted to being of the form $1 + k \cdot 2^{n+2}$. This is essentially "twice as restrictive" as the Mersenne condition of having to be of the form $1 + k \cdot 2 \cdot p$. Unfortunately Fermat integers grow double-exponentially. For this reason it is believed that there are no more prime Fermat numbers after $F_{4} = 65537$ However what if we generalize the Fermat number? Definition: $F_{n,p} = \frac{2^{2^{n} \cdot p} + 1}{2^{2^{n}}+1$ When prime $p < 2^{n}$ 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 $1 + k \cdot 2^{n+1} \cdot p$. Empirical testing shows that the congruence restriction is even stronger than the above and is in fact $1 + k \cdot 2^{n+2} \cdot p$. Example: $F_{5,3} = \frac{2^{96 + 1}}{2^{32} + 1}$. This is a Proth number because it can be written as $1 + (2^{32} -1) \cdot 2^{32}$. 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 $1 + k \cdot 2^{n+2} \cdot p$ condition if we are willing to relax the Proth condition that $k < 2^{n}$ for integers of the form $1 + k \cdot 2^{n}$. Primitive factors of numbers of the form $2^{n} + 1$ 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 $F_{n,p}$ have to be of the form $1 + k \cdot 2^{n+2} \cdot p$. Conjecture #2 - If a primitive factor of $2^{n} + 1$ where n is a Highly Composite Number "almost" satisfies Proth's condition (that is, it can put in the form $1 + k \cdot 2^{m}$ where $k$ isn't too much larger than $m$), we deterministically establish its primality almost as quickly.
 2019-11-24, 20:59 #2 Batalov     "Serge" Mar 2008 Phi(4,2^7658614+1)/2 7×1,373 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 pre-factored 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.
 2019-11-24, 21:25 #3 a1call     "Rashid Naimi" Oct 2015 Remote to Here/There 87C16 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 Near-Multiple-Squares (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 2019-11-24 at 21:29
2019-11-24, 21:26   #4
sweety439

"99(4^34019)99 palind"
Nov 2016
(P^81993)SZ base 36

23×389 Posts

Quote:
 Originally Posted by jshort 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. Lucas-Lehmer primality test). 2) Mersennes are far more likely to be prime compared to what the Prime Number Theorem would predict since any prime integer $q$ that divides $2^{p} - 1$ is forced to be of the form $1 + k \cdot 2 \cdot p$. For simplicity, lets call the above conditions #1 and #2. Empirical evidence suggests that Wagstaff numbers ($\frac{2^{p} + 1}{3}$) "beat" Mersenne numbers on condition #2 above. For instance, for all prime exponents $p < 10^{4}$, 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 $1 + k \cdot 2 \cdot p$. 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, $2^{2^{n}} + 1$, satisfy condition #1 above because they are a Proth number (ie $k \cdot 2^{n} + 1, k < 2^{n}$) 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 $2^{n}$ bits long in size, any potential prime factor is restricted to being of the form $1 + k \cdot 2^{n+2}$. This is essentially "twice as restrictive" as the Mersenne condition of having to be of the form $1 + k \cdot 2 \cdot p$. Unfortunately Fermat integers grow double-exponentially. For this reason it is believed that there are no more prime Fermat numbers after $F_{4} = 65537$ However what if we generalize the Fermat number? Definition: $F_{n,p} = \frac{2^{2^{n} \cdot p} + 1}{2^{2^{n}}+1$ When prime $p < 2^{n}$ 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 $1 + k \cdot 2^{n+1} \cdot p$. Empirical testing shows that the congruence restriction is even stronger than the above and is in fact $1 + k \cdot 2^{n+2} \cdot p$. Example: $F_{5,3} = \frac{2^{96 + 1}}{2^{32} + 1}$. This is a Proth number because it can be written as $1 + (2^{32} -1) \cdot 2^{32}$. 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 $1 + k \cdot 2^{n+2} \cdot p$ condition if we are willing to relax the Proth condition that $k < 2^{n}$ for integers of the form $1 + k \cdot 2^{n}$. Primitive factors of numbers of the form $2^{n} + 1$ 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 $F_{n,p}$ have to be of the form $1 + k \cdot 2^{n+2} \cdot p$. Conjecture #2 - If a primitive factor of $2^{n} + 1$ where n is a Highly Composite Number "almost" satisfies Proth's condition (that is, it can put in the form $1 + k \cdot 2^{m}$ where $k$ isn't too much larger than $m$), we deterministically establish its primality almost as quickly.
F5,3 is Phi192(2), where Phi is the cyclotomic polynomial.

Fn,p = Phip*2^(n+1)(2)

Phin(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, ...

2019-11-24, 21:34   #5
sweety439

"99(4^34019)99 palind"
Nov 2016
(P^81993)SZ base 36

60508 Posts

Quote:
 Originally Posted by Batalov 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 pre-factored 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.
F(0,p) is prime for p = 3, 5, 7, 11, 13, 17, 19, 23, 31, 43, 61, 79, 101, 127, 167, 191, 199, 313, 347, 701, 1709, 2617, 3539, 5807, 10501, 10691, 11279, 12391, 14479, 42737, 83339, 95369, 117239, 127031, 138937, 141079, 267017, 269987, 374321, 986191, 4031399, ..., 13347311, 13372531, ...

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

 2019-11-24, 21:38 #6 sweety439     "99(4^34019)99 palind" Nov 2016 (P^81993)SZ base 36 23×389 Posts https://archive.is/20120529014233/ht...os/fermat6.htm also list the primes of the form Phin(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 2019-11-24 at 21:38
2019-11-24, 22:24   #7
jshort

"James Short"
Mar 2019

218 Posts

Quote:
 Originally Posted by Batalov 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 pre-factored 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.
Thank you for the references. I wasn't aware of Mike Oakes's work, but will definitely read up on him :)

I haven't considered $$b^{2^n} +1$$, with b > 2 because their bit-size 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 - $F_{2p}$ or just $F_{p}$ where p is prime. The primitive factors are easily found in the $F_{2p}$ case. Furthermore, most of these number appear to need to be in the form $1 + k \cdot 2 \cdot p$ (at least in the $F_{2p}$ 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 $1.61^{n}$ which mean their bit-size 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 $b^{n}$ where b < 1.61 too. I wonder if Mike Oakes or others have ever investigated this!?

2019-11-24, 22:32   #8
jshort

"James Short"
Mar 2019

17 Posts

Quote:
 Originally Posted by sweety439 https://archive.is/20120529014233/ht...os/fermat6.htm also list the primes of the form Phin(2), but is for n=p^r (p is prime, r>=1) instead of n=p*2^r (p is prime, r>=1)
Thank you for this.

2019-11-24, 22:57   #9
sweety439

"99(4^34019)99 palind"
Nov 2016
(P^81993)SZ base 36

23·389 Posts

Quote:
 Originally Posted by Batalov 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 pre-factored 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.
Well, see A085398

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

2019-11-24, 22:59   #10
sweety439

"99(4^34019)99 palind"
Nov 2016
(P^81993)SZ base 36

23·389 Posts

This is the smallest k>=2 such that Phin(k) is prime, for 1<=n<=2500
Attached Files
 least k such that phi(n,k) is prime.txt (22.0 KB, 201 views)

2019-11-25, 00:41   #11
jshort

"James Short"
Mar 2019

218 Posts

Quote:
 Originally Posted by sweety439 F(0,p) is prime for p = 3, 5, 7, 11, 13, 17, 19, 23, 31, 43, 61, 79, 101, 127, 167, 191, 199, 313, 347, 701, 1709, 2617, 3539, 5807, 10501, 10691, 11279, 12391, 14479, 42737, 83339, 95369, 117239, 127031, 138937, 141079, 267017, 269987, 374321, 986191, 4031399, ..., 13347311, 13372531, ... 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
Looking at these results F(n,p) for n = 1 - 6 it looks rather discouraging to say the least!

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 p-1 factoring algorithm to root out small and/or smooth numbers idk

 Similar Threads Thread Thread Starter Forum Replies Last Post c10ck3r Information & Answers 34 2012-08-29 16:47 Unregistered Information & Answers 9 2012-06-24 13:50 goatboy Math 1 2007-12-07 12:30 henryzz Lounge 35 2007-10-20 03:06 rogue Lounge 4 2005-07-12 12:31

All times are UTC. The time now is 21:52.

Mon Nov 29 21:52:28 UTC 2021 up 129 days, 16:21, 0 users, load averages: 2.28, 1.61, 1.55