Help needed for doublecheck sieving!

[gd_barnes]

Originally Posted by Flatlander

At the risk of looking stupid(er), what about k = 25, 125, 625?

I'm the stupid one here.

I did miss one of these...125. But 25 and 625 have no algebraic factors because they are powers of 2 that are not divisible by 3. For those k's, n's that are divisible by 2 would have been sieved out with a trivial factor of 3.

Here's the rule for k=q^2 that will contain algebraic factors after normal sieving:

k=q^2 and q==(3 mod 6); i.e. q=3, 9, 15, etc. or k=9, 81, 225, etc.

There is no easy rule that I am aware of for k=q^3, k=q^5, k=q^7, k=q^11, etc. for all prime powers of q. The considerations for k=q^3 and k=q^5 for k<1000 are:

k=q^3:

k=27, n's divisible by 3 were removed.
k=125, missed.
k=343, all n divisible by 3 have trivial factors of 3,5,&13 and were sieved out. (Technically I was lucky here because I had not considered this one either.)
k=729, all n divisible by 3 have a trivial factor of 7 and were sieved out. (Since this is also a perfect square, all n divisible by 2 were removed.)

k=q^5:

k=243, n's divisible by 5 were removed.

Since we're testing by k-value, whomever reserves k=125 can remove all n's divisible by 3 from their sieved file. As a general rule, algebraic factors are < 5% of the file so it would only make a nominal difference.


Gary

[mdettweiler]

Okay, guys, files are now available for LLRing!

The Doublecheck Drive #1 thread is here.

Enjoy!

Note: I will unstick and lock this thread soon. All further discussion of this doublecheck effort can be done in the aforementioned thread.