Thread for posting tiny primes

[3.14159]

@Cmd: Please, post something of substance.

Also; Karsten: I managed to do more work in 30 minutes, than I did with the script in 1 hour.

[3.14159]

Up to n = 625, which means, I covered every prime under about 1880 digits.

Oops. 1962 digits*

[3.14159]

Covered every prime below 2000 digits. Excellent.

Also; in terms of sieving for k * 2⁵⁹⁴⁸⁰⁰ + 1; I've sieved to about 23.64 trillion so far.

15:54:47 36131 k's remaining. p=23631242467579 divides k=1138351

Should I continue further?

[CRGreathouse]

Originally Posted by 3.14159

Should I continue further?

How long does it take you to sieve out additional candidates? How long does each test take? How far in your list do you expect to go?

[3.14159]

Originally Posted by Charles

How long does it take you to sieve out additional candidates? How long does each test take? How far in your list do you expect to go?

1. The average time for elimination is now between 1.5 and 2.5 minutes.
2. Each test takes 13.5 to 14 minutes.
3. I'm just a few away from reaching a sieve efficiency of 28. I'm at about 27.5 to 27.7.

So far, I have saved 4-6 days of testing over a conventional limit.

[CRGreathouse]

I would do more sieving, then, until it's 5-7 minutes between eliminations.

[mdettweiler]

Originally Posted by 3.14159

So far, I have saved 4-6 days of testing over a conventional limit.

Where are you getting this "conventional limit"? Usually, the standard procedure for a straight-up prime search (that is, not a conjecture search where a k is no longer searched after a prime is found) is to sieve until the removal rate is equal to the time it takes to do a PRP test about 80% through the range.

[CRGreathouse]

Originally Posted by mdettweiler

Where are you getting this "conventional limit"? Usually, the standard procedure for a straight-up prime search (that is, not a conjecture search where a k is no longer searched after a prime is found) is to sieve until the removal rate is equal to the time it takes to do a PRP test about 80% through the range.

Right. I used removal rate @ 100% of expected depth (rather than in the whole range, since I supposed you were looking for only one k) = time for PRP test.

[mdettweiler]

Originally Posted by CRGreathouse

Right. (I was using 100%, not 80%, though, in my above suggestion.)

But...13.5 to 14 minutes != 5 to 7 minutes.

Originally Posted by 3.14159

2. Each test takes 13.5 to 14 minutes.

Originally Posted by CRGreathouse

I would do more sieving, then, until it's 5-7 minutes between eliminations.

[CRGreathouse]

Originally Posted by mdettweiler

But...13.5 to 14 minutes != 5 to 7 minutes.

36131 primes remain at sieve efficiency 28 at size 2^594800, so the expected number of primes is 36131 * 28/(594800 * log 2) = 2.45.... Assuming (as mentioned above) that Pi wants to find exactly one prime, one prime should be removed from the first 1/2.45-th of the range in the same amount of time as a PrP test. Assuming (reasonably) that the sieve removes candidates at roughly the same rate throughout the range, that means that the sieving should continue until it takes 1/2.45 times as long as a PrP test. If a PrP test takes 14 minutes, then sieving should take about 14/2.45 = 5.7... minutes.

This procedure should roughly minimize the time needed to find the first prime in the range. To minimize the time needed to test the entire range (if you plan to continue past the first prime), you should sieve until the removal time is equal to the average time for a PrP test, as mdettweiler seems to suggest.

[mdettweiler]

Originally Posted by CRGreathouse

36131 primes remain at sieve efficiency 28 at size 2^594800, so the expected number of primes is 36131 * 28/(594800 * log 2) = 2.45.... Assuming (as mentioned above) that Pi wants to find exactly one prime, one prime should be removed from the first 1/2.45-th of the range in the same amount of time as a PrP test. Assuming (reasonably) that the sieve removes candidates at roughly the same rate throughout the range, that means that the sieving should continue until it takes 1/2.45 times as long as a PrP test. If a PrP test takes 14 minutes, then sieving should take about 14/2.45 = 5.7... minutes.

This procedure should roughly minimize the time needed to find the first prime in the range. To minimize the time needed to test the entire range (if you plan to continue past the first prime), you should sieve until the removal time is equal to the average time for a PrP test, as mdettweiler seems to suggest.

Ah, right--I forgot that Pi is only testing until he finds a prime. Pi, you may want to consider going ahead and testing the whole range--it's most efficient that way, since no sieving is wasted. And since the range is well enough ahead of the 5000th place that you should be able to test it all before it becomes too small, you may just get lucky and pull out more primes than statistically expected for the range.