Register to reply 
A new prime sieveby epsi00
Tags: primes sieve 
Share this thread: 
#1
Mar3111, 12:57 PM

P: 84

This sieve is similar to the Sieve of Eratosthenes but is very different in its implementation. Instead of considering all the numbers below N to find the primes, this sieve considers only N/3 since we know that 2/3 of the numbers up to N are multiples of 2 and 3.
No numerical experiment has been done to check the efficiency of this sieve because I cannot write code. 


#2
Apr1511, 09:13 AM

P: 84

How come no one has commented on this? Does it mean no one is interested in new ways to calculate the prime counting function Pi(N)?



#3
Apr1511, 01:19 PM

P: 205

This is very interesting to me. Unfortunately I’m a NuB when it comes to matrices. I do have a general understanding of your approach though. It reminds me of a mod 12 approach involving congruence of squares that I was working on. Do you have any suggestions for learning matrices?



#4
Apr1511, 02:13 PM

P: 84

A new prime sieve
Well you can learn about matrices by taking a course in linear algebra I guess at the undergrad level. But for the purpose of the sieve, you can think of a matrix as a table of multiplication. More importantly, if you were to implement the sieve above, you really do not need to set up the matrices because setting matrices will make the sieve very inefficient and increase the storage requirements dramatically. To calculate the "matrix" elements, you need far fewer multiplications than in theory. Simply because once you have the first element of a matrix, you can deduce the second from it and the third from the second etc...That is for the diagonal element ( 1st, 2nd, 3rd...) but I also gave a method to fill a column, say the 2nd column, simply by addition of a constant quantity once you have deduced the 2nd diagonal element. This can also be applied, with a slight change, to the nonsymmetric matrix.
And this is one of the point I made in the first post. That though we consider matrices to make the discussion simpler, we in fact do not need to really work with them. This sieve can calculate Pi(N) with very few multiplications and a lot more additions ( about one addition per composite number). if you want I can build one example and show how it is done. 


#5
Apr1511, 02:28 PM

P: 205




#6
Apr1511, 02:56 PM

P: 205

I would love an example!



#7
Apr1511, 03:00 PM

Emeritus
Sci Advisor
PF Gold
P: 16,091

Splitting a sieve into regions based on their residue modulo 6 (and throwing out the classes over 0, 2, 3, and 4) is a good optimization. You can go further and consider residues modulo 30 or 210 or more. I believe this is called a "wheel sieve". I believe this idea is used in the fastest algorithms for listing all primes less than some bound.
If you take a step back and rethink your algorithm, I think you will greatly simplify your approach. Just think about the actual computational problem (e.g. find all points that are 1 modulo 6 and also divisible by some prime p) independently of the way you thought to consider the problem. As for computing [itex]\pi(N)[/itex], there are much better algorithms than sieves. At the very least, a sieve  no matter how well optimized  has to do one unit of work for every prime. Mathworld's page on the function indicates there are known algorithms that take much, much less time. (At least, once N is sufficiently large) (30 = 2*3*5, 210 = 2*3*5*7) 


#8
Apr1811, 09:29 AM

P: 84




#9
Apr1811, 10:07 AM

P: 84

Let's take N=900 and see how to calculate the matrix elements for the matrix M=6ij + (i+j). Since M is symmetric, we only need to calculate about half the total number of elements ( the side below the diagonal but including the diagonal elements ). The first element is for (i=1, j=1) so M=6*1*1 + (1+1)=8. We know this element corresponds to 7*7=(6*1+1)(6*1+1)=49 since (491)/6=8. The maximum element is given by ME=900/6=150. We are now able to calculate the first column of the matrix simply by adding 7 to the previous element.
8 8+7=15 15+7=22 22+7=29 ... 141+7=148 Note that 7 is the first element of the arithmetic progression (6k+1). We see that element 148 is the last one needed since adding 7 to it will be greater than ME=150, the max element. To calculate the elements of the second column, we note that: 13*13=(7+6)*(7+6)=7*7 + 2*6*7 +6*6 and the in terms of indices (13*131)/6=(7*71)/6 +2*7 +6= 8+14+6=28. Please refer to the formula in the first post. Now we can calculate the 2nd column 28 28+13=41 41+13=54 54+13=67 ... 132+13=145 145 is the value of the last element of the second column. The third column can be calculated in the same way. The diagonal element is: 28+2*13+6=60. The third column looks like: 60 60+19=79 79+19=98 98+19=117 117+19=136 136 is the last element since adding 19 to it makes the result larger than ME=150. To calculate the fourth column, we first need to calculate the diagonal element. 60+2*19+6=104. The fourth column looks like: 104 104+25=129 we stop since 129+25 > ME. So we now have all the elements of the symmetric matrix M=6*ij+(i+j). These elements are simply the indices of the numbers ( composite ) in the arithmetic progression ap=(6k+1)=7,13,19,... They simply tell us that the 8th, 15th, 22nd ...elements of ap are composite numbers. Of course we still need to consider the other symmetric matrix M=6*ij (i+j) to get all the indices needed for ap=(6k+1). And finally, we also need to consider the non symmetric matrix M=6ij+(ij) to find the indices of the composite numbers in the arithmetic progression ap=(6k1). The procedure is the same ( with a slight change for the non symmetric matrix ). 


#10
Apr1911, 09:18 AM

P: 84

Let's take N=900 again and see how to calculate the matrix elements for the matrix M=6ij  (i+j). Since M is symmetric, we only need to calculate about half the total number of elements ( the side below the diagonal but including the diagonal elements ). The first element is for (i=1, j=1) so M=6*1*1  (1+1)=4. We know this element corresponds to 5*5=(6*11)(6*11)=25 since (251)/6=4. The maximum element is given by ME=900/6=150. We are now able to calculate the first column of the matrix simply by adding 5 to the previous element.
4 4+5=9 9+5=14 14+5=19 …. 144+5=149 Note that 5 is the first element of the arithmetic progression (6k1). We see that element 149 is the last one needed since adding 5 to it will be greater than ME=150, the max element. To calculate the elements of the second column, we note that: 11*11=(5+6)*(5+6)=5*5 + 2*6*5 +6*6 and in terms of indices (11*111)/6=(5*51)/6 +2*5 +6= 4+10+6=20. Please refer to the formula in the first post. Now we can calculate the elements of the 2nd column, starting with its diagonal element. 20 20+11=31 31+11=42 42+11=53 …. 130+11=141 141 is the value of the last element of the second column. The third column can be calculated in the same way. The diagonal element is: 20+2*11+6=48. The third column looks like: 48 48+17=65 65+17=82 82+17=99 … 133+17=150 150 is the last element since adding 17 to it makes the result larger than ME=150. To calculate the fourth column, we first need to calculate the diagonal element. 48+2*17+6=88. The fourth column looks like: 88 88+23=111 111+23=134 we stop since 134+23 > ME=150 The fifth column has only one element, the diagonal one and its value is 140. So we now have all the elements of the symmetric matrix M=6*ij(i+j). These elements are simply the indices of the numbers ( composite ) in the arithmetic progression ap=(6k+1)=7,13,19,... simply because the product (6i1)*(6j1) is an element of the ap=(6k+1) and not an element of ap=(6k1). They simply tell us that the 4th, 9th, 14th ...elements of ap=(6k+1) are composite numbers. The indices of the composite numbers in the arithmetic progression ap=(6k1) will be given by the non symmetric matrix M=6*ij + (ij) and will be given in another post. 


#11
Apr2711, 11:59 PM

P: 166

Removing the multiples of 2 and 3 is the first to steps of the normal sieve.



#12
Apr2811, 07:02 AM

P: 84




#13
Apr3011, 10:06 PM

P: 12

Similarly, you can reduce the quantity of numbers to check by another 20% by incorporating 5 into your algorithm thusly: { 30k+1, 30k+3, 30k+7, 30k+11, 30k+13, 30k+17, 30k+19, 30k+23, 30k+29 } You are basically preloading some filtering into the design of your algorithm and this can continue to any arbitrary level. Obviously, you will get into diminishing returns if you are doing these computations manually, so {6k1, 6k+1} seems like a good stopping point. But if you are doing these computationally, there's no reason to not expand your algorithm to whatever size is optimal for your computer configuration. 


#14
May111, 07:47 AM

P: 84

Thanks for the suggestion Baric
Hopefully one of the bright kids on this forum will write the code and experiment with it to see how far it can be pushed and which representation provides the most efficient sieve. 2*3 or (6k+/ 1) ======>done 2*3*5 or ( 30k+1,3,...)====> to be done 2*3*5*7 or ( 210k+1,...) ====> to be done ... 


#15
May111, 09:59 AM

P: 12

A sieve stopping at 2 gives you a 50% reduction and a sieve size of 1 (the minimum anyway). At 3, you get a 67% reduction and a sieve size of 2. (1*2) At 5, you get a 73% reduction and a sieve size of 8. (1*2*4) At 7, you get a 77% reduction and a sieve size of 48. (1*2*4*6) At 11,you get a 79% reduction and a sieve size of 480. (1*2*4*6*10) At 13, you get an 81% reduction and a sieve size of 5760. (1*2*4*6*10*12) While that may seem like a huge sieve, an additional 8% reduction (going from 79% to 81%) can be quite significant over a large range of numbers and justify the initial sieve setup. I have no idea what computational algorithms are used to apply the sieve to large numbers, but I'm guess that they would gladly make a 5K for 8% tradeoff :) 


#16
May111, 10:07 AM

P: 12

Then when you've factored the primes up to 2310, you can easily switch to the sieve {2,3,5,7,11}. This way, your sieve will automatically become more efficient as you progress through the primes, up to your computer's memory capacity to maintain the sieve. 


#17
May111, 11:42 AM

P: 84

I agree with you but since I can't write code, I won't be able to test all the issues you raised.



#18
May211, 09:04 AM

P: 12

aww, man.. that's the easy part! :) 


Register to reply 
Related Discussions  
Twin Prime Sieve  Linear & Abstract Algebra  2  
Goldbach’s Conjecture and the 2Way Sieve  General Math  6  
An algorithm based on Eratosthenes Sieve  Programming & Computer Science  6  
Sieve of Eratosthenes  Programming in VB  Computing & Technology  14 