-   Riesel Prime Search (
-   -   Other Primes (

pepi37 2020-12-11 23:44

[QUOTE=Batalov;565974]Good! Congratulations![/QUOTE]

carpetpool 2020-12-12 09:08

[QUOTE=paulunderwood;564951]Congrats to a1call for [URL=""]this top5000 prime[/URL] 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:



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

pepi37 2020-12-12 12:21

And now it is official :)

[URL=""]92*10^1439761-1 is prime :)[/URL]


a1call 2020-12-12 20:39

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.:smile:

bur 2020-12-14 07:05

[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.[/QUOTE]If the same computer doing the sieving could eliminate candidates faster by using PRP, what's the advantage of sieving? Or vice versa.

a1call 2020-12-14 12:41

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 [U]anytime[/U] means you don't have to spend 4 days for a PRP test on them.

VBCurtis 2020-12-14 16:07

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.

a1call 2020-12-14 22:15

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.:smile:

a1call 2020-12-14 23:41

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.:smile:

VBCurtis 2020-12-15 01:10

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!

paulunderwood 2021-01-22 02:17

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


All times are UTC. The time now is 06:55.

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