[number theory] sieving with a_i mod p_i

[jaydfox]

Consider all the primes between 1 and 100.
Call them p_i.

If we want to count the primes between 100 and 10000 then we sieve that interval with 0 mod p_i.

But what happens if say we sieve 7 mod p_i ?
( 7 mod 2 => 1 mod 2 , 7 mod 3 => 1 mod 3 , 7 mod 5 => 2 mod 5 , 7 mod 7 => 0 mod 7 , 7 mod 11 , ... )

In general what happens if we sieve a_i mod p_i with 0 < a_i < p_i ?


How do we choose the a_i such that we sieve as many numbers as possible ?
Or how do we choose the a_i such that there are as many numbers left as possible ?

regards

tommy1729

It took me a couple minutes to really figure out what you were even asking here. Once I did, I threw together some tests in Excel. I was expecting it to be very erratic, but counter-intuitively, it's really stable. I haven't had a chance to validate these numbers or write some gp code, so these numbers are very preliminary, but...

Taking primes between 2 and 97 ("100"), and sieving the numbers from 101 to 10000, I get:

Code:

a_i     Count("Primes")
0..27   1204
28..33  1203
34..51  1202
52..59  1201
60..69  1200
70..71  1199
72..77  1198
78..93  1197
94..96  1196

I suppose the numbers might be more stable if I had sieved from 98 to 97^2? Or perhaps from 98 to 101^2-1? Anyway, this single data point suggests that low numbers, close to 0, maximize the number of "primes".