sieve suggestion

[m0ti]

hi,

not an SB participant or anything and I'm pretty sure you've got much much better sieving in place than my simple suggestion.

In any case:

Looking at numbers modulo 6, we can quickly see that excluding 2 and 3, only numbers of the format 6i + 1 and 6i - 1 are candidates to be primes. As an aside, there should be many more primes with values of 6i - 1 than with 6i + 1 (because -1 * -1 = 1 (mod 6)).

Taking this further:

6i - 1 = k * 2^n + 1

k = 2j + 1

==> n is even, j mod 3 = 0
==> n is odd, j mod 3 = 2

6i + 1 = k * 2^n + 1

k = 2j + 1

==> n is even, j mod 3 = 2
==> n is odd, j mod 3 = 1

So since you're going by k (it's a constant over large searches for n unless I'm mistaken), you can eliminate many values to check based on the value of j and whether n is even or not.

Ex: if j mod 3 = 0, then the result must be of the form 6i - 1 and n must be even.

[Nuri]

Thanks for the suggestion.

If you are interested, you can find detailed discussion info on the client algortihm under the Sieve Client Thread (http://www.free-dc.org/forum/showthread.php?s=&threadid=2408).

And the discussion of the latest version of the client we're using starts with the post of Robert Gerbicz (http://www.free-dc.org/forum/showthread.php?s=&postid=29254#post29254), dated 06-08-2003.

[m0ti]

Explanation of the maths:

First a note on mod 6 math:

Arrange the numbers into rows as follows

1 7 13 19 ...
2 8 14 20 ...
3 9 15 21 ...
4 10 16 22 ...
5 11 17 23 ...
6 12 18 24 ...

As can quickly be seen excluding 2 and 3, all primes lie in the row (1, 7, 13...) and the row (5, 11, 17, ...). Removing the number 1 from the first row, we get that all primer numbers > 3 MUST have the format of 6i - 1 or 6i + 1. As can also be easily seen (6i - 1) * (6j -1) = (6k + 1) (i.e. -1 * -1 = 1 in mod 6), while (6i + 1) * (6j + 1) = (6k + 1) (i.e. 1 * 1 = 1 in mod 6). Thus, numbers of the format 6i - 1 are MUCH more likely to be primes than numbers in the format 6i + 1 (since these could potentially have factors from both 6i -1 and 6i + 1, while numbers of the format 6i - 1 will always have at least one factor of the format 6j - 1).

Important: 2^n mod 3 = 1 if n is even, 2^n mod 3 = 2 if n is odd
Proof: 2^0 = 1, 2^2 = 1, 2^(2p) = (2^2)^p = (1) ^ p = 1 (mod 3)
2^(2p + 1) = 2 * (2 ^ (2p)) = 2 * 1 = 2 (mod 3)

Let's solve:

6i - 1 = k * 2^n +1
6i = k * 2^n + 2
3i = k * 2^(n-1) + 1
3i = (2j + 1) * 2^(n-1) + 1
3i = j * 2^n + 2^(n-1) + 1

==> n is even: 0 = j * 1 + 2 + 1 (mod 3) ==> 0 = j mod 3
==> n is odd: 0 = j * 2 + 1 + 1 (mod 3) ==> -2 = j * 2 (mod 3) ==> 2 = j mod 3

alternatively:

6i + 1 = k * 2^n + 1
6i = k * 2^n
6i = (2j + 1) * 2^n
6i = 2j * 2^n + 2^n
3i = j * 2^n + 2^(n-1)

==> n is even: 0 = j * 1 + 2 (mod 3) ==> 1 = j mod 3
==> n is odd: 0 = j * 2 + 1 (mod 3) ==> 1 = j mod 3

Hmm, seems I made a mistake before (I had written in this case n is even: 2 = j mod 3, and n is odd 1 = j mod 3, but I found my mistake from before (had the last line written out as 3i = j * 2^n + 1), the above calculations are correct!).

For those who aren't sure about the maths consider the solved primes:

k = 44131 ==> j mod 3 = 0 ==> n is even (found n at 995972)
k = 46517 ==> j mod 3 = 2 ==> n is odd (found n at 698207)
k = 54767 ==> j mod 3 = 2 ==> n is odd (found n at 1337287)
k = 65567 ==> j mod 3 = 2 ==> n is odd (found n at 1013803)
k = 69109 ==> j mod 3 = 0 ==> n is even (found n at 1157446)

Furthermore, in terms of the forms (all of the above should be 6i - 1):

First off all of our n's are very large. Let's separate to two cases:
n is even: n = 2p ==> 2^n = (2^2) ^ p. 2^2 = 4 mod 6, 4 *4 = 4 mod 6 ==> 2^n = 4 mod 6 (for p > 0)
n is odd: n = 2p + 1 ==> 2 ^n = 2 * 2^(2p) = 8 mod 6 = 2 mod 6

Therefore the values for all of the primes (go ahead, check it out for yourself) mod 6 is 5 (so they do in fact have the format 6i - 1)!


Actually I guess it might have been a really good suggestion, looking at your project stats page:

k = 4847 ==> j mod 3 = 2 ==> n is odd, valid form: 6i - 1
k = 24736 ==> j mod 3 = 2 ==> n is odd, valid form: 6i - 1
k = 27653 ==> j mod 3 = 2 ==> n is odd, valid form: 6i - 1
k = 28432 ==> j mod 3 = 2 ==> n is odd, valid form: 6i - 1
k = 67607 ==> j mod 3 = 2 ==> n is odd, valid form: 6i - 1


k = 5359 ==> j mod 3 = 0 ==> n is even, valid form: 6i - 1
k = 19249 ==> j mod 3 = 0 ==> n is even, valid form: 6i - 1
k = 21181 ==> j mod 3 = 0 ==> n is even, valid form: 6i - 1
k = 22699 ==> j mod 3 = 0 ==> n is even, valid form: 6i - 1
k = 33661 ==> j mod 3 = 0 ==> n is even, valid form: 6i - 1
k = 55549 ==> j mod 3 = 0 ==> n is even, valid form: 6i - 1

k = 10223 ==> j mod 3 = 1 ==> n is even or odd, valid form: 6i + 1

First off we can see that for 11 out of the 12 values the valid form is 6i - 1. More importantly, for these 11 values we've managed to cut down on the number of values of n by half (either n is even, or n is odd).

In the final case we haven't gained any insight into n, but primes of this format are much rarer in any case.

Hope that this will give you a decent speed up (theoritically you should be able to run twice as fast over 11 of the remaining values).

[Joe O]

Originally posted by m0ti

k = 10223 ==> j mod 3 = 1 ==> n is even or odd, valid form: 6i + 1
you might want to recheck this


Hope that this will give you a decent speed up (theoritically you should be able to run twice as fast over 11 of the remaining values).
We have been doing this and more, since the first sieve program.

You should really read this thread (http://www.free-dc.org/forum/showthread.php?s=&threadid=2994) , especially the analyses by wblipp.

All our primes will be == 2 (mod 3) This was used from the beginning, to cut the work in half.
All our primes will be == 5 (mod 6).
All our primes will be == 2 (mod 5).
All our primes will be == 7 (mod 10).
All our primes will be == 2 (mod 15).
All our primes will be == 17 (mod 20).
All our primes will be == 17 (mod 24).
All our primes will be == 17 (mod 30).
All our primes will be == 17 (mod 60).
All our primes will be == 17 (mod 120).
All our primes will be == 17 (mod 240).

I'm doing this from memory, so I hope that it is right. We've also done quite an analysis on the possible n values for each k. I've attached a listing of all the possible n values == (mod 720) for each k in this thread about the sieve program. (http://www.free-dc.org/forum/showthread.php?s=&threadid=2408) I tried to attach it again, but the forum won't let me.

[Joe O]

m0ti,
Just thought I'd expound on k=10223.
For 10223*2^n+1 to not be trivially divisible by a small prime, n can only be congruent to one of the following possible values mod 720:
5
29
41
77
89
101
125
137
149
185
197
221
245
269
281
317
329
341
365
377
389
425
437
461
485
509
521
557
569
581
605
617
629
665
677
701
eg 10223*2^(5+m*720)+1 could be prime for some integer m. It will be composite for many m, and it may turn out to be composite for all m, but at least it is not trivially divisible by a small prime. You will note that all of these values are odd. You will also note that there are only 36 values out of the possible 360 odd values, so we only have to look at 1 /10 th of the possible values. This analysis has been carried out for all 12 k. This is one of two k values with 36 possible values congruent mod 720, there is a k value with only 8 possible values congruent mod 720.
By the way, as you pointed out, for a given k, all of the exponents are either all even (5359, 19249, 21181, 22699, 33661, 55459), or all odd (4847, 10223, 24737, 27653, 28433, 67607).

[m0ti]

I've actually expounded the idea quite a lot further, take a look here (http://rieselsieve.com/phpBB2/viewtopic.php?t=88) (well, they're solving for k * 2^n - 1, so just replace the -1 with +1 where appropriate).

Creating a large list of rules (i.e. wide range of values for X) shouldn't be that problematic at all. A program could run which given ranges for X would create approriate rules (this would be easily distributable). Then ranges of n could be sieved appropriately, hopefully without too much work (also fairly easily distributable).