Largest Known PRP

[Batalov]

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.

[a1call]

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

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

[Dr Sardonicus]

Originally Posted by a1call

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

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

[Dr Sardonicus]

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

[a1call]

Thank you very much for the corrections and extra research DS.
You are a very valuable member of this board.

[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?
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

[CRGreathouse]

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.

[Batalov]

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:

# 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.

[a1call]

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.

[a1call]

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.

[GP2]

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:

# 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