Other Primes

[bur]

Originally Posted by a1call

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.

I only saw this now, sorry. Sounds convincing at first, but why not use 2 out of 10 threads, or 7 or all?

Fundamentally you have two methods to remove a candidate for good, TF or PRP. If one is faster on average, you have the highest average throughput when using that method exclusively. I don't see how it can be different.

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.

After 5 days verifying it was finally added to the list.

[a1call]

Originally Posted by bur

Fundamentally you have two methods to remove a candidate for good, TF or PRP. If one is faster on average, you have the highest average throughput when using that method exclusively. I don't see how it can be different.

By that logic there would be no justification to use more than one method, either TF or PRP-Testing on any given range. But that's not the case now, is it?
Both methods are used in practice to weed out candidates they are better at sieving. TF for candidates with smaller factors and PRP-Testing for the rest, even though one would have to be faster on acreage on the whole set than the other.

[VBCurtis]

Originally Posted by a1call

By that logic there would be no justification to use more than one method, either TF or PRP-Testing on any given range. But that's not the case now, is it?
Both methods are used in practice to weed out candidates they are better at sieving. TF for candidates with smaller factors and PRP-Testing for the rest, even though one would have to be faster on acreage on the whole set than the other.

No, you are fully misunderstanding what he said.

If TF is faster, use it exclusively. At some point in your TF efforts, TF is no longer faster, and PRP becomes faster. At that crossover point, use PRP exclusively.

This is clearly the most efficient path, yet you wave your hands and use all sorts of words to make yourself feel better that it's not true.

[LaurV]

Originally Posted by a1call

By that logic there would be no justification to use more than one method, either TF or PRP-Testing on any given range.

That's a fallacy. It would be true if the speed of each method would be constant as you go deeper, but it is not. The TF speed decreases exponentially, it halves with every bitlevel. The speed of PRP decreases slower with the size of the exponent (range, size of the FFT). In a certain point they will cross. As VBCurtis says.

By "speed of TF" we mean how fast you can eliminate an exponent, by finding a factor. TF programs seem "much faster", they do many tests in the wallclock time taken by a PRP test, but to find a factor, you need to do many assignments (roughly, equal to the bitlevel, i.e. if you look for 70 bits factors, you will need to test about 70 exponents, to find a factor). If your hardware can test 70 exponents to 70 bits faster than it takes for the same hardware to do a PRP for an exponent of the same size (plus or minus a little change, considering the certification process, error rates, vanity of having a factor as opposite of having a PRP residue, whatever rows your boat), then YOU SHOULD CERTAINLY DO ONLY TF to 70 bits.

This is how GIMPS works since its inception, if we make abstraction of the people who only run TF because they want more credit, or they like to have found factors, or (I would say "selfish") people who only run LL/PRP because they want the glory of finding a prime and take George's money. Most users here will try to help the project most, by optimizing their rate of getting rid of exponents, at front wave, either doing TF or PRP. Of course, the options will wary in time, according with the exponent size at the front level and the bitlevel that has to be trial-factored, you can do PRP today because the bitlevels are very deep here, and TF next month if your exponent gets higher and the bitlevel is lower or stays the same, but once the exponent and bitlevel is given, and assuming you know your hardware, you should optimally chose ONE of them, and DO THAT ONE ONLY.

[paulunderwood]

Congrats to Serge Batalov for the smallest known 1 million digit prime:

10^999999 + 308267*10^292000 + 1

Can this be limbo-ed?

[JeppeSN]

Originally Posted by paulunderwood

Congrats to Serge Batalov for the smallest known 1 million digit prime:

10^999999 + 308267*10^292000 + 1

Can this be limbo-ed?

This beats an idea of simply doing 10^999999 + k*10^(333333-m) ± 1 with m very small. Such a prime would be simpler to test than Serge Batalov's, but not quite as close to 10^999999. /JeppeSN

[sweety439]

Originally Posted by paulunderwood

Congrats to Serge Batalov for the smallest known 1 million digit prime:

10^999999 + 308267*10^292000 + 1

Can this be limbo-ed?

The smallest known 1 million digit prime is 10^999999+593499

[paulunderwood]

Originally Posted by sweety439

The smallest known 1 million digit prime is 10^999999+593499

That may be the smallest PRP. No proof of primality, unless you have a new theorem

[paulunderwood]

We had a nice email from Jeff Gilchrist this morning saying one of his computers had reported:

2^13380298-27 is base 3-Fermat PRP! (4027872 decimal digits)  Time : 9677.550 sec.
2^13380298-27 is Fermat, Lucas and Frobenius PRP! (P = 5, Q = 5, D = 5)  Time : 75222.576 sec.

We would like to thank rouge for his sieve and Jean and George for their software.



It is official now

[Batalov]

A new Generalized Cullen number - 4'143'644 decimal digits.

[pepi37]

Originally Posted by Batalov

A new Generalized Cullen number - 4'143'644 decimal digits.