Tetration Forum

Full Version: [number theory] sieving with a_i mod p_i
You're currently viewing a stripped down version of our content. View the full version with proper formatting.
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
(09/09/2014, 01:10 AM)tommy1729 Wrote: [ -> ]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".

However Im not sure what you computed.

There are 25 primes below 100.
Or 24 odd primes.

So i must be 24 or 25 depending on details in the definition.

But then you write

a_i
..
28..33

I do not know what that means ?

28,29,30,31,32,33 ?

Does that mean that for any of 28,29,... 33 as a fixed value of a_i we get the same result ?

Many interpretations are possible I think.

Im betting you are considering a fixed a_i and

0..27 1204 means that for any fixed a_i between 0 and 27 we get the same value : 1204.

Is my guess correct ?

Btw as for " intuition " I note that for prime twins we sieve
0 mod 2 0 mod 3 0 mod 5 ...
and
(3-2) mod 3 (5-2) mod 5 ...

Then for this variant , the intuition of " stable " at least for simple "patterns" in the a_i , leads to the conjecture of infinitude of the prime twins !

Note that in my OP - which appears confusing apparantly - the a_i are not neccessarily fixed.

So we could consider
1 mod 2 ,1 mod 3, 2 mod 5, 6 mod 7, 5 mod 11 etc

I assume fixed a_i are easier to study perhaps.

My question is thus more general.
I gave an example - between the brackets - of a fixed a_i ...
Probably that confused matters. ( sorry )

**
Probably this reminds some people of the " Lucky numbers ".
**

Hope this results in something constructive.

regards

tommy1729
(09/10/2014, 08:27 PM)tommy1729 Wrote: [ -> ]Thank you for your reply and intrest Jay !

However Im not sure what you computed.
(...)
But then you write

a_i
..
28..33

(...)

Does that mean that for any of 28,29,... 33 as a fixed value of a_i we get the same result ?

Many interpretations are possible I think.

Im betting you are considering a fixed a_i and

0..27 1204 means that for any fixed a_i between 0 and 27 we get the same value : 1204.

Is my guess correct ?

Exactly what I meant! For a fixed a_i of 0 (or 1, or 2, or 27, etc.), I found 1204 "primes" in the range of 101 to 10000 inclusive.

Quote:Note that in my OP - which appears confusing apparantly - the a_i are not neccessarily fixed.

So we could consider
1 mod 2 ,1 mod 3, 2 mod 5, 6 mod 7, 5 mod 11 etc

I assume fixed a_i are easier to study perhaps.
Well, my modular arithmetic is rusty, but it seems to me that {1 mod 2, 1 mod 3, 2 mod 5, 6 mod 7, 5 mod 11}, as a set, defines a unique number mod 2*3*5*7*11. Assuming my educated guess is right, you basically are fixing a_i, though not limited to the same range as initially defined. So I think it still makes sense to speak in terms of a fixed a_i, if perhaps we relax the restriction on the size of a_i (up to primorial(p_i)-1 or something like that).
{0 mod 2, 0 mod 3 , 0 mod 5 , ... 0 mod prime 't' } does not define a certain a mod b.

Rather it sieves out possibilities of a mod b.

Its like 0 mod 2 , 0 mod 3 , 0 mod 5 gives :

1,7,11,13,17,19,23,29 mod 30.

A similar thing happens with a_i mod p_i.

But maybe that is what you actually meant (to say).

regards

tommy1729
If we sieve an interval [a,b] with 0 mod 2 , 0 mod 3 , 0 mod 5 etc
we get close to the primes in that interval.

If we sieve an interval [a,b] with 5 mod 2, 5 mod 3, 0 mod 5, 5 mod 7 , 5 mod 11 etc , we get close to the primes in the interval [a-5,b-5].

Therefore it is not so surprising the results for fixed a_i are so similar.

This is also why I say fixed a_i are less intresting.

regards

tommy1729
(09/11/2014, 08:24 AM)tommy1729 Wrote: [ -> ]{0 mod 2, 0 mod 3 , 0 mod 5 , ... 0 mod prime 't' } does not define a certain a mod b.

Rather it sieves out possibilities of a mod b.

Its like 0 mod 2 , 0 mod 3 , 0 mod 5 gives :

1,7,11,13,17,19,23,29 mod 30.

A similar thing happens with a_i mod p_i.

But maybe that is what you actually meant (to say).

regards

tommy1729

Hmm, maybe we're talking about different things. I'm talking about an a_i that gives the respective remainders mod p_i, all at the same time, not individually. I agree that for sieving, we care about a single match, so we get back a set of sieved (or unsieved) numbers.

The only numbers that are 0 mod 2, 0 mod 3, 0 mod 5 (all at the same time, not individually) are the numbers that are 0 mod 30. The only numbers that are 1 mod 2, 2 mod 3, 1 mod 5 are the numbers that are 11 mod 30. So by giving me a set of a_i's to go with the p_i's, like a_i={1, 2, 1} and p_i={2, 3, 5}, I can give you back a new "a" to go with product(p_i): a=11 and primorial(5)=30.

In this sense, giving me a set of a_i's in the range 0 <= a_i < p_i is just equivalent to giving me a fixed a in the range 0 <= a < primorial(max(p_i))

In light of this, then yes, having unfixed a_i's is an interesting problem in its own right, as long as we can agree that it's just another way of looking at a fixed value of a.

Edit: So for example, sieving numbers against 1 mod 2, 2 mod 3, and 1 mod 5, is like sieving them against 11 mod 2, 11 mod 3, and 11 mod 5. Hopefully that made sense...End Edit

And I reserve the right to be wrong.
(09/11/2014, 08:00 PM)jaydfox Wrote: [ -> ]
(09/11/2014, 08:24 AM)tommy1729 Wrote: [ -> ]{0 mod 2, 0 mod 3 , 0 mod 5 , ... 0 mod prime 't' } does not define a certain a mod b.

Rather it sieves out possibilities of a mod b.

Its like 0 mod 2 , 0 mod 3 , 0 mod 5 gives :

1,7,11,13,17,19,23,29 mod 30.

A similar thing happens with a_i mod p_i.

But maybe that is what you actually meant (to say).

regards

tommy1729

Hmm, maybe we're talking about different things. I'm talking about an a_i that gives the respective remainders mod p_i, all at the same time, not individually. I agree that for sieving, we care about a single match, so we get back a set of sieved (or unsieved) numbers.

The only numbers that are 0 mod 2, 0 mod 3, 0 mod 5 (all at the same time, not individually) are the numbers that are 0 mod 30. The only numbers that are 1 mod 2, 2 mod 3, 1 mod 5 are the numbers that are 11 mod 30. So by giving me a set of a_i's to go with the p_i's, like a_i={1, 2, 1} and p_i={2, 3, 5}, I can give you back a new "a" to go with product(p_i): a=11 and primorial(5)=30.

In this sense, giving me a set of a_i's in the range 0 <= a_i < p_i is just equivalent to giving me a fixed a in the range 0 <= a < primorial(max(p_i))

In light of this, then yes, having unfixed a_i's is an interesting problem in its own right, as long as we can agree that it's just another way of looking at a fixed value of a.

Edit: So for example, sieving numbers against 1 mod 2, 2 mod 3, and 1 mod 5, is like sieving them against 11 mod 2, 11 mod 3, and 11 mod 5. Hopefully that made sense...End Edit

And I reserve the right to be wrong.

Unfortunately the primorial is a quickly growing function.

If the primorial is much larger than the interval we sieve , I wonder if that has practical use ?

Notice your table does not contain such large numbers.

regards

tommy1729