mersenneforum.org Largest Known PRP
 User Name Remember Me? Password
 Register FAQ Search Today's Posts Mark Forums Read

 2017-11-25, 22:36 #12 Batalov     "Serge" Mar 2008 Phi(4,2^7658614+1)/2 2×3×7×229 Posts If anyone was seriously interested in finding a PRP larger that the largest known prime, then consider this. There are no numbers that can be tested faster than Mersenne's (within a fraction of a % of a %, that is your "less iterations to run for the cofactor" which is negligible if you think for a minute). To be even remotely competitive with GIMPS in terms of size and plausibility, the candidates have to have three properties: (a) as fast to test as a Mersenne number. (b) as probable to find as a Mersenne number (that means sieved just as deep, that means factors are restricted) - this is a must. If your project can sieve to 36 bits and GIMPS to 72, then you already lost. (c) finally, the project has a compute throughput as large as GIMPS -- but for far less glory. Conditions (a+b) will mean that candidates have to be Mersenne cofactors, Wagstaff's, GFN cofactors or some cyclotomic cofactors (or straight with power not 3-smooth). Gaussian-Mersennes and Eisenstein-Mersennes (and their cofactors) are not contenders (they fail condition (a), though they do pass condition (b)) - failing condition (a) by a factor of 2 is as bad as failing condition (b) by a factor of 2 - in both cases in order to simply keeping up with GIMPS you have to have 2x more power. But then - why? You could just as well work with GIMPS even if you consider getting half of credit with GIMPS getting the other half.
2017-11-25, 23:37   #13
a1call

"Rashid Naimi"
Oct 2015
Remote to Here/There

87E16 Posts

Thank you very much for the detailed analysis Batalov, much appreciated.
On a somewhat related benchmark

Quote:
 The largest known Carmichael number of this form was found by H. Dubner in 1996 and has 1025 digits.

https://archive.lib.msu.edu/crcmath/...ath/c/c060.htm

Last fiddled with by a1call on 2017-11-25 at 23:38

2017-11-26, 14:35   #14
Dr Sardonicus

Feb 2017
Nowhere

24×3×107 Posts

Quote:
Originally Posted by a1call
Thank you very much for the detailed analysis Batalov, much appreciated.
On a somewhat related benchmark
Quote:
 The largest known Carmichael number of this form was found by H. Dubner in 1996 and has 1025 digits.

https://archive.lib.msu.edu/crcmath/...ath/c/c060.htm
Actually, this seems to be more than a bit garbled. The following 1996 post to the NMBRTHRY Listserv from Harvey Dubner himself, tells a different story. He found a couple of Carmichael numbers of the special "universal form"

U3 = PQR = (6M + 1)(12M+1)(18M + 1)

in which the prime factors P, Q, and R each have 1025 decimal digits. The post also refers to Carmichael numbers with "millions of digits."

Carmichael number record

 2017-11-26, 16:48 #15 Dr Sardonicus     Feb 2017 Nowhere 24·3·107 Posts A bit more digging turned up a 1998 post by Dubner with some larger examples of the form (6M + 1)(12M + 1)(18M + 1): 3-component Carmichael Numbers There was an error in a table, which was the subject of a Correction The smallest Carmichael number of this form, 7*13*19, is 1729, which is the smallest Carmichael number whose prime factors form a finite arithmetic progression, as well as being (as noted in the hardy-Ramanujan "taxicab number" anecdote) the smallest number that is the sum of two cubes in two different ways (10^3 + 9^3 and 1^3 + 12^3). Also, a 1996 paper with an algorithm for producing really large Carmichael numbers: A NEW ALGORITHM FOR CONSTRUCTING LARGE CARMICHAEL NUMBERS
 2017-11-26, 19:45 #16 a1call     "Rashid Naimi" Oct 2015 Remote to Here/There 2×1,087 Posts Thank you very much for the corrections and extra research DS. You are a very valuable member of this board.
 2017-11-26, 19:51 #17 a1call     "Rashid Naimi" Oct 2015 Remote to Here/There 2×1,087 Posts What is the largest PRP range that can be found using Fermat's Little Theorem (base 2) on Pari GP running on a custom pc with x GBs of memory? Another way of asking the same question is: What is the largest practical p for which 2^(p- 1) can be calculated? (Thank you in advance)^2 Last fiddled with by a1call on 2017-11-26 at 19:54
2017-11-26, 20:01   #18
CRGreathouse

Aug 2006

3·1,993 Posts

Quote:
 Originally Posted by a1call What is the largest PRP range that can be found using Fermat's Little Theorem (base 2) on Pari GP running on a custom pc with x GBs of memory?
Please don't use gp for this; it's not built for it and it will perform poorly. There are better tools like PFGW.

I love PARI/GP but this is like pounding nails with a Swiss Army knife.

2017-11-26, 21:17   #19
Batalov

"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

2×3×7×229 Posts

Quote:
 Originally Posted by a1call Another way of asking the same question is: What is the largest practical p for which 2^(p- 1) can be calculated?
Define practical.

You have a better chance to be struck by a lightning than finding a PRP with > 10M decimal digits. Do you feel particularly lucky?

You can run PRPs on the >100,000,000-digit Mersenne cofactors (candidates that had a factor or two found). In a few CPU years you will get the result.
Take 2^332200007-1 / 272240898059289853159 and run the PRP test. It is trivial:
Code:
# worktodo.txt
PRP=1,2,332200007,-1,"272240898059289853159"
If you do feel lucky, then one candidate should be enough. When done, take the next one.
You can take even larger cofactors.

 2017-11-26, 22:36 #20 a1call     "Rashid Naimi" Oct 2015 Remote to Here/There 87E16 Posts Point well taken. I wasn't considering the low probability of prime/PRP in the high ranges. But then again I am more interested in understanding the different mechanics of the concept rather actually attempting to find a large PRP. It's good to know the upper limits of what arbitrary-precision calculators can work at then consider the astronomically low possibility of finding a candidate.
2017-11-26, 22:41   #21
a1call

"Rashid Naimi"
Oct 2015
Remote to Here/There

2×1,087 Posts

Quote:
 Originally Posted by CRGreathouse Please don't use gp for this; it's not built for it and it will perform poorly. There are better tools like PFGW. I love PARI/GP but this is like pounding nails with a Swiss Army knife.
I like that reference

http://www.periodictable.com/Samples/026.55/s13.JPG

You know what they say:

You can't teach an old d d d distinguished gentleman new tricks.

PFGW, at the moment is nothing but an acronym to me.
I will have to research it.
Thank you.

2017-11-26, 23:33   #22
GP2

Sep 2003

50318 Posts

Quote:
 Originally Posted by Batalov Define practical. You have a better chance to be struck by a lightning than finding a PRP with > 10M decimal digits. Do you feel particularly lucky? You can run PRPs on the >100,000,000-digit Mersenne cofactors (candidates that had a factor or two found). In a few CPU years you will get the result. Take 2^332200007-1 / 272240898059289853159 and run the PRP test. It is trivial: Code: # worktodo.txt PRP=1,2,332200007,-1,"272240898059289853159" If you do feel lucky, then one candidate should be enough. When done, take the next one. You can take even larger cofactors.
Or just set WorkPreference=154 in prime.txt, and then mprime/Prime95 will automatically assign you 100-million digit PRP tests.

If you're feeling less ambitious, then use 150 for first-time PRP tests or 152 for world-record PRP tests. These two choices currently amount to the same thing, at least until the next Mersenne prime is found.

It goes without saying that you should be running the latest version, 29.4b5

Last fiddled with by GP2 on 2017-11-26 at 23:34

 Similar Threads Thread Thread Starter Forum Replies Last Post Uncwilly Data 38 2009-07-17 05:39 Unregistered Information & Answers 24 2008-12-13 08:13 amcfarlane Math 6 2004-12-26 23:15 heryu Miscellaneous Math 10 2004-09-08 11:15 wfgarnett3 Lounge 7 2002-11-25 06:34

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

Sun Dec 5 20:32:06 UTC 2021 up 135 days, 15:01, 1 user, load averages: 1.88, 1.59, 1.64