mersenneforum.org  

Go Back   mersenneforum.org > Prime Search Projects > Riesel Prime Search

Reply
 
Thread Tools
Old 2020-12-11, 23:44   #221
pepi37
 
pepi37's Avatar
 
Dec 2011
After milion nines:)

5·281 Posts
Default

Quote:
Originally Posted by Batalov View Post
Good! Congratulations!
Thanks!
pepi37 is offline   Reply With Quote
Old 2020-12-12, 09:08   #222
carpetpool
 
carpetpool's Avatar
 
"Sam"
Nov 2016

2×163 Posts
Post

Quote:
Originally Posted by paulunderwood View Post
Congrats to a1call for this top5000 prime of a most unusual construction.

Very interesting, indeed.

The prime in question does not appear to be totally random?

I have actually constructed large random provable primes before (over 100,000 digits), but none of them were large enough size for Top5000 at the time.

This was a few years ago though and I had lost interest at some point.

I am also wondering how sieving was done. I've made general purpose programs and scripts for my searches in finding random primes, but they are far too slow at half a million digits compared to more advanced programs like srsieve and multisieve which won't support testing arbitrary numbers.

Also, PFGW appears to test some numbers faster than others, like Proth or Riesel numbers, so I could only imagine the extensive work done to find this prime.

These primes also might be of interest:

https://primes.utm.edu/primes/page.php?id=119933

https://primes.utm.edu/primes/page.php?id=119934

Edit: I did not see Paul's post was about a week ago, for some reason, this caught my attention...

Last fiddled with by carpetpool on 2020-12-12 at 09:13
carpetpool is offline   Reply With Quote
Old 2020-12-12, 12:21   #223
pepi37
 
pepi37's Avatar
 
Dec 2011
After milion nines:)

5×281 Posts
Default

And now it is official :)


92*10^1439761-1 is prime :)


pepi37 is offline   Reply With Quote
Old 2020-12-12, 20:39   #224
a1call
 
a1call's Avatar
 
"Rashid Naimi"
Oct 2015
Remote to Here/There

26·31 Posts
Default

@carpetpool
The prime has taken months of work for different iterations and I have modified the sieving over time.
As per faster PRP tests for some numbers than others of the same size, I believe it's a matter of proximity to repeated squaring which these iterations happen to be. The same behavior can be seen in Pari when calculating Mod (b,p)^(p-1) which is much faster if p is close to repeated squares which indicates that the routines have the intelligence to figure out the fastest way of calculating an Exponentiation.
As for the sieving, I use my own setup which means it is probably quite inefficient. However it has one thing going for it:
There is often the raised subject of how deep to sieve and I generally disagree with the replies.
IMHO one should sieve indefinitely and simultaneously as PRP testing. I basically take a range and let lose multiple threads at sieving it using both PRP-Test-threads and TF-sieving-threads. Any candidate in the queue that is knocked out by TF saves days of upcoming PRP tests.

I have a ryzen 9 PC dedicated to this sequence and run my routines in a virtual box which I can pause, snapshot and resume at any time.
I am currently looking for the next iteration but things have slowed down to a crawl. It appears that PRP tests are about 8 times slower than the last iteration.

ETA Good luck with your next Top-5k carpetpool.

Last fiddled with by a1call on 2020-12-12 at 21:30
a1call is offline   Reply With Quote
Old 2020-12-14, 07:05   #225
bur
 
Aug 2020

3516 Posts
Default

Quote:
IMHO one should sieve indefinitely and simultaneously as PRP testing. I basically take a range and let lose multiple threads at sieving it using both PRP-Test-threads and TF-sieving-threads. Any candidate in the queue that is knocked out by TF saves days of upcoming PRP tests.
If the same computer doing the sieving could eliminate candidates faster by using PRP, what's the advantage of sieving? Or vice versa.
bur is offline   Reply With Quote
Old 2020-12-14, 12:41   #226
a1call
 
a1call's Avatar
 
"Rashid Naimi"
Oct 2015
Remote to Here/There

198410 Posts
Default

Suppose you are testing 10000 candidates with 1M decimal digits each. And each PRP test takes 4 days and you have 10 threads available. Suppose you run PRP tests on 9 of them and trial factoring on the other. In the 1st 4 days anything divisible by small primes will be knocked out by TF. In the next 4 days candidates divisible by larger primes will be knocked out, next 4 days even larger.... Any candidates that are knocked out of the queue at anytime means you don't have to spend 4 days for a PRP test on them.

Last fiddled with by a1call on 2020-12-14 at 13:03
a1call is offline   Reply With Quote
Old 2020-12-14, 16:07   #227
VBCurtis
 
VBCurtis's Avatar
 
"Curtis"
Feb 2005
Riverside, CA

4,673 Posts
Default

In no way did your explanation answer why sieving is better after the point where a prp test eliminates candidates faster than sieve does. If your sieve eliminates a candidate every 6 days, why do you think you're saving 4 days every time you find a factor?

When sieve is faster, sieve on all 10 threads. When prp is faster, prp on all 10 threads. You way may be convenient for you, but it's not an effort to be efficient.
VBCurtis is offline   Reply With Quote
Old 2020-12-14, 22:15   #228
a1call
 
a1call's Avatar
 
"Rashid Naimi"
Oct 2015
Remote to Here/There

26·31 Posts
Default

Suppose you have 2 available threads.
Suppose there are z candidates to test, none of which are prime.
Suppose each PRP-Test takes 4 days to complete.
Suppose running the 2 TF-threads for 4 days would sieve upto some prime x per thread.
Suppose y of the candidates have prime factors greater than x.
For the sake of the argument let's ignore the time it takes to run the TF-test on all the candidates.
the PRP tests alone will take 4y/2 days.
------
Now suppose you run 1 of the threads for trial-factoring indefinitely which means the candidates upstream the queue will be sieved deeper and deeper than x.
The other thread is used for PRP-tests
It will take you less than 4y days to PRP test all the candidates because some more of the candidates will be knocked out by TF.
How much less days is a factor of how large z is. The larger the z, the deeper the TF, the greater cutdown from 4y days.
Since there is no known upper bound for z, there is always a z value feasible where PRP tests will take less than 4y/2.

That's my 2 cents and that's how I run my setup, but you are welcome to disagree.
a1call is offline   Reply With Quote
Old 2020-12-14, 23:41   #229
a1call
 
a1call's Avatar
 
"Rashid Naimi"
Oct 2015
Remote to Here/There

26·31 Posts
Default

Couldn't add an ETA.
To make it clearer the 2 scenarios are a bit of apples and oranges comparison. The second scenario sieves less deep in the beginning and more deep towards the end. However its depth has no upper bound unlike the 1st scenario. I hope that makes sense.
a1call is offline   Reply With Quote
Old 2020-12-15, 01:10   #230
VBCurtis
 
VBCurtis's Avatar
 
"Curtis"
Feb 2005
Riverside, CA

124116 Posts
Default

We understand what you do, so "makes sense" is a pretty low bar. We disagree that it's faster.

Sieve on both threads until it takes longer than 4 days to find a factor. Then prp on both threads. Every candidate is optimally sieved this way, while in your way the first few tests are badly undersieved, and the last few are really badly oversieved.

If we both take a range and race on identical hardware, your way comes out slower. But, if you like the triumph of finding a factor, it's just fine to rank speed as not the first priority. Just don't claim it's better!
VBCurtis is offline   Reply With Quote
Old 2021-01-22, 02:17   #231
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

23·449 Posts
Default 321

Congrats to Rudi Tapper and PrimeGrid for the prime 3* 2^16819291 - 1 with 5,063,112 decimal digits and top5000 entrance rank of 21.

paulunderwood is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Mersenne Primes p which are in a set of twin primes is finite? carpetpool Miscellaneous Math 3 2017-08-10 13:47
Distribution of Mersenne primes before and after couples of primes found emily Math 34 2017-07-16 18:44
Conjecture about Mersenne primes and non-primes v2 Mickey1 Miscellaneous Math 1 2013-05-30 12:32
A conjecture about Mersenne primes and non-primes Unregistered Information & Answers 0 2011-01-31 15:41
possible primes (real primes & poss.prime products) troels munkner Miscellaneous Math 4 2006-06-02 08:35

All times are UTC. The time now is 22:59.

Sun Feb 28 22:59:51 UTC 2021 up 87 days, 19:11, 0 users, load averages: 2.39, 2.13, 1.85

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.