mersenneforum.org  

Go Back   mersenneforum.org > Extra Stuff > Miscellaneous Math

Reply
 
Thread Tools
Old 2021-02-24, 14:07   #1
bur
 
Aug 2020

163 Posts
Default Mersenne-Woodall Primes

I saw that 2^{521} - 1 is a Mersenne prime and also the Woodall prime 512 * 2^{512} - 1.

A Mersenne number is a Woodall number if the exponent p is of the form 2^n + n. So obviously we need p to be prime for the Mersenne-Woodall number to be prime.

Just for fun I looked up which n < 101 result in a prime exponent:

Code:
n     p
1     3
3     11
5     37
9     521
15    32783
39    549755813927
75    37778931862957161709643
81    2417851639229258349412433
89    618970019642690137449562201
Of these n = 1 and n = 9 are known to result in a Mersenne-Woodall prime: 2^3 - 1 and 2^{521} - 1 or 2*2^2-1 and 512*2^{512}-1. For n = 15 the number is not prime. The next candidate 2^{(2^{39}+39)}-1 already has 165 492 990 283 digits. So it's up to future generation to find out whether or not this is the third Mersenne-Woodall prime.
bur is offline   Reply With Quote
Old 2021-02-24, 18:07   #2
sweety439
 
Nov 2016

54038 Posts
Default

This is double-exponent sequence, thus it is conjectured that the number of such primes is finite, and 2^521-1 may be the largest such prime, like 65537 may be the largest Fermat prime, and 2^127-1 may be the largest double-Mersenne prime.
sweety439 is offline   Reply With Quote
Old 2021-02-24, 18:38   #3
bur
 
Aug 2020

16310 Posts
Default

I didn't know about this conjecture. That is also why generalized Fermat numbers are supposed to only have a finite number of primes per base?


Does that conjecture have a name and is there a simple explanation? I could only find some papers about it, but with my very limited math knowledge I didn't grasp much.


And it probably doesn't say anything about the expected number of primes, or does it?
bur is offline   Reply With Quote
Old 2021-02-24, 18:41   #4
Stargate38
 
Stargate38's Avatar
 
"Daniel Jackson"
May 2011
14285714285714285714

11×59 Posts
Default

M549755813927 is divisible by 43399809724955419039.
M37778931862957161709643 has no factors <2^110.
M2417851639229258349412433 is divisible by 14507109835375550096474599.
M618970019642690137449562201 is divisible by 302234395011250596454696928877487.

Just helping out so that no one claims them to be prime (there is still that possibility for M37778931862957161709643, but it's extremely unlikely).

Last fiddled with by Stargate38 on 2021-02-24 at 18:47 Reason: forgot "."
Stargate38 is offline   Reply With Quote
Old 2021-02-24, 18:52   #5
sweety439
 
Nov 2016

1011000000112 Posts
Default

Quote:
Originally Posted by bur View Post
I didn't know about this conjecture. That is also why generalized Fermat numbers are supposed to only have a finite number of primes per base?
Yes, it is conjectured there is only finitely many generalized Fermat primes to every base (references: http://jeppesn.dk/generalized-fermat.html, https://arxiv.org/pdf/1605.01371, http://yves.gallot.pagesperso-orange...s/results.html), for example, there may be no generalized Fermat primes to base 38, and if so, then the generalized Sierpinski conjecture base 38 is false, since k=1 does not have primes.

The conjecture in post https://mersenneforum.org/showpost.p...&postcount=675 may be true, but may be false when c = 1, b = q^m, k = q^r, and the exponent of highest power of 2 dividing r >= the exponent of highest power of 2 dividing m (where (k*b^n+c)/gcd(k+c, b-1) corresponding to GFN's to even bases or half GFN's to odd bases, for the reference of half GFN's to odd bases, see http://www.fermatquotient.com/PrimSerien/GenFermOdd.txt)

Last fiddled with by sweety439 on 2021-02-24 at 19:17
sweety439 is offline   Reply With Quote
Old 2021-02-24, 18:53   #6
sweety439
 
Nov 2016

281910 Posts
Default

Quote:
Originally Posted by Stargate38 View Post
M549755813927 is divisible by 43399809724955419039.
M37778931862957161709643 has no factors <2^110.
M2417851639229258349412433 is divisible by 14507109835375550096474599.
M618970019642690137449562201 is divisible by 302234395011250596454696928877487.

Just helping out so that no one claims them to be prime (there is still that possibility for M37778931862957161709643, but it's extremely unlikely).
It is also happens for double Wagstaff numbers, W(W(p)) is composite for p = 11, 13, 17, 19, 23, 31, 61, and 79, and W(W(43)) might be prime, but it's extremely unlikely.

Last fiddled with by sweety439 on 2021-02-24 at 19:17
sweety439 is offline   Reply With Quote
Old 2021-02-26, 08:55   #7
bur
 
Aug 2020

101000112 Posts
Default

Thanks for the links, sweety439. To be honest, understanding that Boklan and Conway paper is beyond me. So the conjecture says the number of primes is not only finite, but that there are only a few, i.e. < 10 or so?

Stargate38, I'm impressed and disappointed. ;) Is that the result of TF? But how can you get so quickly to 2^110, or is TF that fast on a single candidate?

So, for n < 1300:

Code:
n     p
317   266998379490113760299377713271194014325338065294581596243380200977777465722580068752870260867389
701   10520271803096747014481979765760257331100679605646347718996561806137464308594161644227333072555176902453965937712356435426038864500367607726255629541303761699910447342256889196383327515768645434542586503471563453
735   180736893357325919804742965901096183254486650358500961579737723575212405143116703993975930943694719806137463391890175780999890999416217020648099397663164550811570949854893831716648452639533025774320471006645409943407035103
Any chance here for future generations to do some work?

Last fiddled with by bur on 2021-02-26 at 09:00
bur is offline   Reply With Quote
Old 2021-02-26, 19:49   #8
sweety439
 
Nov 2016

2,819 Posts
Default

Quote:
Originally Posted by bur View Post
Thanks for the links, sweety439. To be honest, understanding that Boklan and Conway paper is beyond me. So the conjecture says the number of primes is not only finite, but that there are only a few, i.e. < 10 or so?

Stargate38, I'm impressed and disappointed. ;) Is that the result of TF? But how can you get so quickly to 2^110, or is TF that fast on a single candidate?

So, for n < 1300:

Code:
n     p
317   266998379490113760299377713271194014325338065294581596243380200977777465722580068752870260867389
701   10520271803096747014481979765760257331100679605646347718996561806137464308594161644227333072555176902453965937712356435426038864500367607726255629541303761699910447342256889196383327515768645434542586503471563453
735   180736893357325919804742965901096183254486650358500961579737723575212405143116703993975930943694719806137463391890175780999890999416217020648099397663164550811570949854893831716648452639533025774320471006645409943407035103
Any chance here for future generations to do some work?
You can use the sense of Factors of Fermat numbers and Factors of double Mersenne numbers.

Since such numbers are too large to test the primality (even the probable-primality, such as a Miller–Rabin primality test and Baillie–PSW primality test, in fact, since the N-1 or N+1 for these numbers are immediately smooth, there are no pseudoprimes), thus we cannot know whether these numbers are primes or not, unless a divisor of the number can be found (we can only use trial division to disprove the primality of these numbers).

Note: Since these numbers are of the form Phi(n,2)/gcd(Phi(n,2),n) (where Phi is the cyclotomic polynomial, and gcd is greatest common divisor), and all numbers of the form Phi(n,2)/gcd(Phi(n,2),n) are strong-probable-primes to base 2, so don't test with that base. In generally, all numbers of the form Phi(n,b)/gcd(Phi(n,b),n) (b>=2) are strong-probable-primes to base b, so don't test with that base.

Last fiddled with by sweety439 on 2021-02-26 at 20:01
sweety439 is offline   Reply With Quote
Old 2021-02-26, 23:54   #9
Happy5214
 
Happy5214's Avatar
 
"Alexander"
Nov 2008
The Alamo City

22·149 Posts
Default

Quote:
Originally Posted by bur View Post
Stargate38, I'm impressed and disappointed. ;) Is that the result of TF? But how can you get so quickly to 2^110, or is TF that fast on a single candidate?
Remember that all factors of Mersenne numbers are of the form 2kp+1, so larger exponents have fewer possible factors to check for a given bit range. A back-of-the-envelope calculation says it's actually significantly less than an equivalent GIMPS TF amount of work.
Happy5214 is offline   Reply With Quote
Old 2021-02-27, 01:23   #10
sweety439
 
Nov 2016

54038 Posts
Default

Quote:
Originally Posted by Happy5214 View Post
Remember that all factors of Mersenne numbers are of the form 2kp+1, so larger exponents have fewer possible factors to check for a given bit range. A back-of-the-envelope calculation says it's actually significantly less than an equivalent GIMPS TF amount of work.
In generally, all factors of Phi(n,b)/gcd(Phi(n,b),n) (b>=2) (where Phi is the cyclotomic polynomial, and gcd is greatest common divisor) are of the form kn+1
sweety439 is offline   Reply With Quote
Old 2021-02-27, 02:08   #11
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

3·43·73 Posts
Default

Quote:
Originally Posted by sweety439 View Post
In generally, all factors of Phi(n,b)/gcd(Phi(n,b),n) (b>=2) (where Phi is the cyclotomic polynomial, and gcd is greatest common divisor) are of the form kn+1
First of all, this is simply false*, and secondly what does it have to do with the subject of this thread!?
Only prime n are of interest for this thread, and for them gcd() is "1", and Phi() is 2^n-1.
So you typed 159 characters, that added 0 substance to what Happy already said.
___
* and in general, every statement that start with a guarding qualifier "generally,..." is good for social science arguments and is simply nonsense for math.
When you look at a statement, "Generally, <blah>" with a trained eye, you parse out the word "generally" and then skip the rest as irrelevant until next dot.
Batalov is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
x^y*y^x+-1 (Generalized HyperCulllen/Woodall) primes sweety439 And now for something completely different 8 2020-12-23 01:56
Cullen-Williams primes and Woodall-Williams primes sweety439 And now for something completely different 5 2020-10-28 00:36
Some new Generalized Cullen and Woodall primes Batalov And now for something completely different 15 2019-11-27 15:11
Super Cullen & Woodall primes Citrix And now for something completely different 1 2017-10-26 09:12
Mersenne Wiki: Improving the mersenne primes web site by FOSS methods optim PrimeNet 13 2004-07-09 13:51

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

Fri May 7 21:13:17 UTC 2021 up 29 days, 15:54, 1 user, load averages: 2.77, 2.76, 2.99

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, 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.