mersenneforum.org  

Go Back   mersenneforum.org > Great Internet Mersenne Prime Search > Math > Number Theory Discussion Group

Reply
 
Thread Tools
Old 2019-11-24, 20:30   #1
jshort
 
"James Short"
Mar 2019
Canada

2·5 Posts
Default 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.
jshort is offline   Reply With Quote
Old 2019-11-24, 20:59   #2
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(3,3^1118781+1)/3

100011000110112 Posts
Cool

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.
Batalov is offline   Reply With Quote
Old 2019-11-24, 21:25   #3
a1call
 
a1call's Avatar
 
"Rashid Naimi"
Oct 2015
Out of my Body

2×34×11 Posts
Default

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
a1call is offline   Reply With Quote
Old 2019-11-24, 21:26   #4
sweety439
 
sweety439's Avatar
 
Nov 2016

32·199 Posts
Default

Quote:
Originally Posted by jshort View Post
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, ...
sweety439 is offline   Reply With Quote
Old 2019-11-24, 21:34   #5
sweety439
 
sweety439's Avatar
 
Nov 2016

110111111112 Posts
Default

Quote:
Originally Posted by Batalov View Post
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
sweety439 is offline   Reply With Quote
Old 2019-11-24, 21:38   #6
sweety439
 
sweety439's Avatar
 
Nov 2016

32×199 Posts
Default

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
sweety439 is offline   Reply With Quote
Old 2019-11-24, 22:24   #7
jshort
 
"James Short"
Mar 2019
Canada

128 Posts
Default

Quote:
Originally Posted by Batalov View Post
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!?
jshort is offline   Reply With Quote
Old 2019-11-24, 22:32   #8
jshort
 
"James Short"
Mar 2019
Canada

2·5 Posts
Default

Quote:
Originally Posted by sweety439 View Post
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.
jshort is offline   Reply With Quote
Old 2019-11-24, 22:57   #9
sweety439
 
sweety439's Avatar
 
Nov 2016

33778 Posts
Default

Quote:
Originally Posted by Batalov View Post
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
sweety439 is offline   Reply With Quote
Old 2019-11-24, 22:59   #10
sweety439
 
sweety439's Avatar
 
Nov 2016

32·199 Posts
Default

This is the smallest k>=2 such that Phin(k) is prime, for 1<=n<=2500
Attached Files
File Type: txt least k such that phi(n,k) is prime.txt (22.0 KB, 20 views)
sweety439 is offline   Reply With Quote
Old 2019-11-25, 00:41   #11
jshort
 
"James Short"
Mar 2019
Canada

2·5 Posts
Default

Quote:
Originally Posted by sweety439 View Post
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
jshort is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Finding VERY large primes c10ck3r Information & Answers 34 2012-08-29 16:47
Best Work for Finding Primes Unregistered Information & Answers 9 2012-06-24 13:50
Finding primes using modular stacking goatboy Math 1 2007-12-07 12:30
Finding primes from 1 upwards henryzz Lounge 35 2007-10-20 03:06
Finding primes with a PowerPC rogue Lounge 4 2005-07-12 12:31

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

Thu Apr 9 21:46:53 UTC 2020 up 15 days, 19:19, 0 users, load averages: 1.48, 1.72, 1.82

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.