Primes under different moduli

[Robert'); DROP TABLE *;]

So I think it was this forum where I originally learned that all primes above 3 are of the form 6k+1 or 6k+5, meaning that if you want to search for primes, you can do so 3x as efficiently as searching evey single integer. However, I'm curious about whethere there is a value better than 6 to use that allows you to make the search space even smaller. (i.e. where even fewer than 1/3 of the possible remainders are possibly prime) What sort of properties make the resulting space small? Additionally, is it possible to prove what the most optimal value is?

[jaap]

So I think it was this forum where I originally learned that all primes above 3 are of the form 6k+1 or 6k+5, meaning that if you want to search for primes, you can do so 3x as efficiently as searching evey single integer. However, I'm curious about whethere there is a value better than 6 to use that allows you to make the search space even smaller. (i.e. where even fewer than 1/3 of the possible remainders are possibly prime) What sort of properties make the resulting space small? Additionally, is it possible to prove what the most optimal value is?

If you are familiar with the Sieve of Eratosthenes, then the 6k+-1 result follows directly from applying the first two passes of the sieve.

The first pass is crossing off all multiples of 2. This gives you that all primes above 2 are odd, i.e. of the form 2k+1.

The second pass is crossing off all multiples of 3. Since 2*3=6, there will result in a repeated pattern of length 6. We have the odd numbers 6k+1, 6k+3, 6k+5 from which the multiples of 3 are removed, leaving 6k+1 and 6k+5.

You can do a third pass by crossing off multiples of 5. This gives a repeated pattern of length 2*3*5=30. We have the numbers 6k+1, 6k+5, which can also be written in the form 30k+1, 30k+5, 30k+7, 30k+11, 30k+13, 30k+17, 30k+19, 30k+23, 30k+25, 30k+29. Two of these ten are multiples of 5, and so are eliminated, leaving 8 out of 30.

We started with all numbers (100%): 1
The first pass eliminated half: 1*(1-1/2) = 1/2
The second pass eliminated a further third: 1*(1-1/2)*(1-1/3) = 1/3
The third pass eliminated a further fifth: 1*(1-1/2)*(1-1/3)*(1-1/5) = 4/15

Beyond this it is hardly worth doing more passes because the amount you reduce the fraction by gets less and less, while the length of the pattern, the modulus, gets a lot bigger.

[Robert'); DROP TABLE *;]

The question originally occured to me in the process of trying to make a Sieve of Eratosthenes more memory-efficient, so that's a bit of a facepalm moment. I also knew that the list could get ridiculous quite quickly, but didn't particularly care since I was planning to have the computer do the actual arithmetic. However, I looked at using 2*3*5*7*11=2310 as the period, and discovered that this only decreased the size to ~1/8th, so I guess I have to agree its not very scaleable. (Although it might be useful to squeeze out the last drop of capacity on a fixed amount of memory.)

[Xanthir]

Yeah, each one decreases the number of candidates to check by 1/n, where n is the prime you're adding - adding 5 reduces by 1/5th, adding 7 reduces by 1/7th, etc.

I used the 2*3*5 wheel back when I was working with primes for Project Euler, but I didn't do any real tests to see if a larger wheel would be worthwhile. I suspect you could benefit from adding several more numbers.

[PM 2Ring]

Using mod 30 is nice because you can use one byte to hold the 8 potential primes in each block of 30 numbers (apart from the first block). I wrote a segmented sieve in C using this technique many years ago, when RAM and HD space was much smaller than it is today.