Hi Ola,

To say it first, DC sieve is not double cheching the sieve, it sieves for double check. But I guess, this sounds strange, so I'll try to start fromthe beginning.

I'm sure you know most of the things I'll write below, but I hope they will help with the explanation of DC sieve.

As you know, the seventeenorbust project is testing for numbers of the form --- k * 2^n +1 --- to find out primes for each of the k values. The project started with 17 k values and as primes for 5 k values have been found in 2002, we are left with 12 k values now.

There are mainly two different procedures used for the project, namely sieving and PRP testing.

Sieving, as it's name implies, looks at the remaining candidates and eliminates the ones that are divisible by a smaller prime number. The candidates that are divisible by a smaller prime obviously can not be primes themselves, so they are eliminated from the set of candidates that should be PRP tested.

On the other hand, PRP testing takes each candidate one by one, and tests if it is a prime or not.

Sieving can not find primes, but it is very useful, because it can eliminate candidates faster than a PRP test can eliminate (still much faster at the p values we are sieving right now). So, it helps the project proceed faster, by eliminating candidates before they are PRP tested. In a way, sieving cleans up the way for PRP testing.

Now, the Sieve and DC Sieve part:

Our main sieving sub-project started a couple of weeks before the main project started PRP testing for values where n in the k * 2^n +1 formula exceeds 3 million. The candidates the main sieving tries to eliminate starts from k * 2^3,000,000 +1 and ends at k * 2^20,000,000 +1, for each of the 12 remaining ks.

On the other hand, DC sieve aims to decrease the number of candidates from k * 2^1 + 1 up to k * 2^3,000,000 + 1, in case we need to double check them by PRP testing in the future.

Here comes the question, were they not been sieved in the first place when the main project was testing for n for values smaller than 3,000,000?

Yes, they were sieved, but not very deep. The trick is here: Just a couple of months ago, the sieve client was much more primitive than the one were are using right now. Thanks to the admirable efforts of Paul and Phil (and lately Mikael as well) it's far much better now.

To compare the situation, when our main project was PRP testing for numbers n smaller than 3,000,000, the sieve client could only test for one k value at a time, whereas it can test for all 12 k values at the same time. Also, it was much much slower (more than 30 times) than our client now.

Therefore, despite Louie's computing efforts, they could not be sieved deep enough. With the new client, the DC sieve is now trying to reduce the number of candidates for n smaller than 3,000,000, in case we need to double check their PRP testing in the future.

Then, the question comes to mind, will we ever need to double check for those numbers? I'm not sure when we should start that, but I'm sure it will be worth the effort when the time comes.

So, I hope this explanation helped you.

Please feel free to ask if you have further questions.

And others, please feel free to add your comments / corrections.

Regards,

Nuri