• 0 Vote(s) - 0 Average
• 1
• 2
• 3
• 4
• 5
 [number theory] sieving with a_i mod p_i tommy1729 Ultimate Fellow Posts: 1,493 Threads: 356 Joined: Feb 2009 09/09/2014, 01:10 AM 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 jaydfox Long Time Fellow Posts: 440 Threads: 31 Joined: Aug 2007 09/10/2014, 04:50 PM (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". ~ Jay Daniel Fox tommy1729 Ultimate Fellow Posts: 1,493 Threads: 356 Joined: Feb 2009 09/10/2014, 08:27 PM Thank you for your reply and intrest Jay ! 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 ? Thanks for the reply. 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 ". ** Thanks for your reply. Hope this results in something constructive. regards tommy1729 jaydfox Long Time Fellow Posts: 440 Threads: 31 Joined: Aug 2007 09/11/2014, 01:47 AM (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). ~ Jay Daniel Fox tommy1729 Ultimate Fellow Posts: 1,493 Threads: 356 Joined: Feb 2009 09/11/2014, 08:24 AM {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 tommy1729 Ultimate Fellow Posts: 1,493 Threads: 356 Joined: Feb 2009 09/11/2014, 11:40 AM (This post was last modified: 09/11/2014, 11:41 AM by 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 jaydfox Long Time Fellow Posts: 440 Threads: 31 Joined: Aug 2007 09/11/2014, 08:00 PM (This post was last modified: 09/11/2014, 08:02 PM by jaydfox.) (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. ~ Jay Daniel Fox tommy1729 Ultimate Fellow Posts: 1,493 Threads: 356 Joined: Feb 2009 09/12/2014, 07:28 AM (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 « Next Oldest | Next Newest »

 Possibly Related Threads... Thread Author Replies Views Last Post " x-theory " tommy1729 1 520 08/12/2021, 12:17 AM Last Post: tommy1729 Dynamical Systems and Number Theory Daniel 4 1,433 06/01/2021, 11:34 PM Last Post: JmsNxn Hyper operators in computability theory JmsNxn 5 9,827 02/15/2017, 10:07 PM Last Post: MphLee Cellular auto : rule 30 number ? tommy1729 0 2,699 08/03/2016, 08:31 PM Last Post: tommy1729 Set theory debate : cantor 1st / Virgil argument. tommy1729 1 4,027 12/08/2015, 11:14 PM Last Post: tommy1729 [2015] Spiderweb theory tommy1729 0 3,381 03/29/2015, 06:25 PM Last Post: tommy1729 " fake ring theory " tommy1729 0 3,554 06/11/2014, 11:29 PM Last Post: tommy1729 [Number Theory] pi(X,x,x+2)+pi(X,x,x+4) tommy1729 1 4,393 04/11/2014, 10:33 PM Last Post: tommy1729 the " average restart " of a number. tommy1729 0 2,890 03/26/2014, 01:02 AM Last Post: tommy1729 A conjecture about number theory and tetration tommy1729 0 3,421 10/23/2013, 09:28 PM Last Post: tommy1729

Users browsing this thread: 1 Guest(s)