mersenneforum.org  

Go Back   mersenneforum.org > Prime Search Projects > Wagstaff PRP Search

Reply
 
Thread Tools
Old 2013-09-08, 20:01   #1
ryanp
 
ryanp's Avatar
 
Jun 2012
Boulder, CO

2468 Posts
Default New Wagstaff PRP exponents

Hello,

I believe I have found the two largest known Wagstaff primes, after Tony Reix's discovery of (2^4031399+1)/3. Here they are:

Code:
(2^13347311 + 1)/3 is 3-PRP! (16355.1659s+0.0028s)
and:

Code:
(2^13372531 + 1)/3 is 3-PRP! (34165.4750s+0.0029s)
Each is a probable prime with about 4 million decimal digits.

Can anyone with some spare cycles help verify these using PFGW or other primality testing software?

Thanks!

-- Ryan
ryanp is offline   Reply With Quote
Old 2013-09-08, 20:37   #2
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(3,3^1118781+1)/3

2·3·5·7·43 Posts
Default

Congratulations!

You can:
* try the Vrba-Reix as implemented in LLR (you have to modify llr.ini)
* also run pfgw with -b5, -b7 (and another dozen bases).
* and run pfgw with -t, -tp and -tc.

I'll run a few of these for you, in parallel.
Batalov is offline   Reply With Quote
Old 2013-09-08, 21:16   #3
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

321510 Posts
Default

Wowee!
paulunderwood is offline   Reply With Quote
Old 2013-09-08, 21:18   #4
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

5·643 Posts
Default

What ranges did you search, Ryan?
paulunderwood is offline   Reply With Quote
Old 2013-09-08, 23:17   #5
diep
 
diep's Avatar
 
Sep 2006
The Netherlands

2·337 Posts
Default

Finding 2 close to each other, similar like how things work in Mersenne sometimes,

Maybe the odds for finding a Wagstaff in range [n;2n] which seemed a diverging sequence, so odds getting slowly a tad less each doubling of n, maybe maybe this is odds it's converging towards a near similar chance like one has to find a Mersenne.

Note that TF and P-1 rates of Wagstaff are considerable better than for Mersenne, so when i say 'converging towards' i still mean a considerable worse chance in range [n;2n], yet not as bad as the real small odds it seemed like considering the previous 2 were just under a million and something in the 4 million bits.

Moving towards the 4 million is factor 4+, then suddenly 2 at 13 million is factor 3, yet there is 2, where there is 2 there could be more.

So that's pretty good news, of course assuming both are PRP!
diep is offline   Reply With Quote
Old 2013-09-10, 00:20   #6
ATH
Einyen
 
ATH's Avatar
 
Dec 2003
Denmark

34×5×7 Posts
Default

Prime95 concur on the first one:

2^13347311+1/3 is a probable prime! We4: B33A699A,00000000
ATH is offline   Reply With Quote
Old 2013-09-10, 00:59   #7
philmoore
 
philmoore's Avatar
 
"Phil"
Sep 2002
Tracktown, U.S.A.

1,117 Posts
Default

A Hearty congratulations to the project! Thanks especially to Tony Reix, Paul Underwood, and Vincent Diepeveen for testing so many candidates over the years. I am surprised that it took until now for Five or Bust to lose its lock on the largest known probable prime (since January 2009), but apparently the Wagstaff search hit a fairly substantial gap.

If these were proven primes, they would come in at 11th and 12th largest known, just below the 39th Mersenne and just above the last discovery of Seventeen or Bust.

Quote:
Originally Posted by diep View Post
Note that TF and P-1 rates of Wagstaff are considerable better than for Mersenne
Do you have any statistics supporting this? I'm not saying it is wrong, just that I would expect the rates to be very similar.
philmoore is offline   Reply With Quote
Old 2013-09-10, 01:14   #8
diep
 
diep's Avatar
 
Sep 2006
The Netherlands

2·337 Posts
Default

Quote:
Originally Posted by philmoore View Post
A Hearty congratulations to the project! Thanks especially to Tony Reix, Paul Underwood, and Vincent Diepeveen for testing so many candidates over the years. I am surprised that it took until now for Five or Bust to lose its lock on the largest known probable prime (since January 2009), but apparently the Wagstaff search hit a fairly substantial gap.

If these were proven primes, they would come in at 11th and 12th largest known, just below the 39th Mersenne and just above the last discovery of Seventeen or Bust.



Do you have any statistics supporting this? I'm not saying it is wrong, just that I would expect the rates to be very similar.
Jeff Gilchrist did do lately really a lot of work.

Interesting is to know what range was checked and what TF was done to find these 2 and whether a similar algorithm was used that was used to find some of the largest Mersennes past few years, prioritizing which exponent to use based upon factorisation of N+1 and N-1 of the exponent.

As for the TF and P-1, i tend to remember posts that Mersenne TF'ed roughly 50% and that P-1 removed roughly 7.5%. Please correct that if it's different.

For Wagstaff even a quick TF already removes 60% and with gpu's add another 10% and P-1 removes also 10%. The overlap of deeper TF and P-1 is not so large. So in total you look at a 70-75% that gets removed pretty easily with far less computational effort than has been done for Mersenne with respect to the P-1.

More accurate statistics will be there in some months hopefully with gpu factorisation stats.

It's been some years i datamined through Mersenne statistics there. Can't remember how shallow those were compared to what we're doing.

Note that Mersenne is a -1 formula and that Wagstaff is a +1 formula which should already explain a lot.

Mersenne give a reasonable steady number of primes in each given range just like 3 * 2^n - 1 also does.

Wagstaff so far was pretty much a gamble whether it would be converging or diverging or constant in odds to the next PRP.

I would guess blindfolded doing factorisation attempts other than P-1 to remove some composites from Wagstaffs list to be tested might be more succesful than for Mersenne.

In all cases and with respect to any statement the important emphasis is on the word "similar". Even if something factors 1% better i would not consider that similar.
diep is offline   Reply With Quote
Old 2013-09-10, 01:29   #9
Jeff Gilchrist
 
Jeff Gilchrist's Avatar
 
Jun 2003
Ottawa, Canada

7×167 Posts
Default

I just finished both exponents with LLR and they also show as PRP:

Code:
(2^13347311+1)/3 is Vrba-Reix PRP!  Time : 56958.781 sec.
(2^13372531+1)/3 is Vrba-Reix PRP!  Time : 57032.491 sec.
Good find.
Jeff Gilchrist is offline   Reply With Quote
Old 2013-09-10, 01:46   #10
ryanp
 
ryanp's Avatar
 
Jun 2012
Boulder, CO

2×83 Posts
Default

Quote:
Originally Posted by diep View Post
Jeff Gilchrist did do lately really a lot of work.

Interesting is to know what range was checked and what TF was done to find these 2 and whether a similar algorithm was used that was used to find some of the largest Mersennes past few years, prioritizing which exponent to use based upon factorisation of N+1 and N-1 of the exponent.
Yes, I am indebted to Jeff's prior work here as well. For my part, I started with the first 25,000 prime exponents from each of q=10e6, 11e6, 12e6 and 13e6. A large fraction of these were weeded out by a very basic program I wrote to do simple trial factoring up to d=1000, then many more by PFGW's own trial factoring. I'll have to do a bit of work to determine exactly how many exponents were fully tested by PFGW.
ryanp is offline   Reply With Quote
Old 2013-09-10, 02:25   #11
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(3,3^1118781+1)/3

2·3·5·7·43 Posts
Default

Note that for the pfgw trial factoring you would want to use something like this command line:
pfgw -f{13372607*2,1} -q(2^13372607+1)/3
(2^13372607+1)/3 has factors: 50253508240009

(this will only look for factors of form 2*p*k+1)
Compare the running time of the above to this:
pfgw -f -q(2^13372607+1)/3
____________________________________

P.S. The Vrba-Reix tests and some LLR and PFGW tests in a bunch of bases on the same two exponents are almost done here, too.
Batalov is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Searching for Wagstaff PRP T.Rex Wagstaff PRP Search 187 2020-02-23 15:10
Hot tuna! -- a p75 and a p79 by Sam Wagstaff! Batalov GMP-ECM 9 2012-08-24 10:26
Wagstaff Conjecture davieddy Miscellaneous Math 209 2011-01-23 23:50
Best settings to factor Wagstaff p = (2^n +1) / 1 diep GMP-ECM 10 2010-07-26 21:33
30th Wagstaff prime T.Rex Math 0 2007-09-04 07:10

All times are UTC. The time now is 20:44.

Thu Jun 4 20:44:16 UTC 2020 up 71 days, 18:17, 1 user, load averages: 1.50, 1.42, 1.47

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.