Cartesian Analysis
It's all about the square

The function y(x) = x2 + b * x  will generate all composites:

 

 

Let's look at the image rotated, zoomed in, and with the rows spread apart.... I find this a great way of visualising the complexity of the primes.... look at the complex way they line up... then get out of alignment, then line up again, all at different rates.... the mystery of the complexity of prime number distribution seems less mysterious when looking at it like this:

The top row is 4,6,8,10... etc. The second row is 9,12,15,18... etc. The third row is 16,20,24,28... etc

The function generates an inifnite number of discrete lines that defines all multiples of 2, all multiples of 3, all multiples of 4, etc... starting at the square of the positive integer... so for the first row starting at the top (all multiples of 2) it starts at 4... for the second row (all multiples of 3) it starts at 9... and so on.

Let's look at building an optimised prime number generating seive based on this visual insight.

The stock standard Sieve of Eratosthenes goes about knocking out primes for each multiple of that prime... so for 5 it will cross out 5, 10, 15, 20, 25... etc.  Looking at the results of y(x) = x2 + b * x  we can see that we don't need to cross out those under the square of the prime... we can start crossing out at 25.... 25,30,35,40,45 etc.

We can also see the redundancy of considering every second value of 3... because it will be even. This leaves only integers of the form 6n +/- 1 that could possibly be prime.

It also becomes obvious that we need only cross out every second multiple of the primes because they are the only odd multiples (e.g. for 7 we would be considering 49,56,63,70,77,84 etc...  only every second is odd)

We can go further with this process of identifying redundancy by analysing the points that actually contribute to excluding integers... i.e. ignoring them if they have already been crossed off. Ultimately the best pattern would be one that has a single point in each column of the integers that are composite... you can see in the above image that there is a lot of redundancy.... there are a lot of columns that have more than one mark.

The character * denotes that the pattern repeats... so if I write 4567*  I am implying 456745674567456745674567... continuing forever....

Prime Number

Repeating Pattern

Example

2 1*

4,6,8 etc.

3 2* 9,15,21 etc.
5 2 4* 25, 35, 55, 65 etc.
7

4 2 4 2 4 6 2 6  *

49,77,91,119,133,161,203,217,259,287 etc.

11

2 4 2 4 6 2 6 4 2 4 6 6 2 6 4 2 6 4 6 8 4 2 4 2 4 8 6 4 6 2 4 6 2 6 6 4 2 4 6 2 6 4 2 4 2 10 2 10 *

121,143,187,209.... you get the idea from the above examples where the repeating pattern is a bit shorter!
13

4 2 4 6 2 6 4 2 4 6 6 2 6 4 2 6 4 6 8 4 2 4 2 4 14 4 6 2 10 2 6 6 4 2 4 6 2 10 2 4 2 12 10 2 4 2 4 6 2 6 4 6 6 6 2 6 4 2 6 4 6 8 4 2 4 6 8 6 10 2 4 6 2 6 6 4 2 4 6 2 6 4 2 6 10 2 10 2 4 2 4 6 8 4 2 4 12 2 6 4 2 6 4 6 12 2 4 2 4 8 6 4 6 2 4 6 2 6 10 2 4 6 2 6 4 2 4 2 10 2 10 2 4 6 6 2 6 6 4 6 6 2 6 4 2 6 4 6 8 4 2 6 4 8 6 4 6 2 4 6 8 6 4 2 10 2 6 4 2 4 2 10 2 10 2 4 2 4 8 6 4 2 4 6 6 2 6 4 8 4 6 8 4 2 4 2 4 8 6 4 6 6 6 2 6 6 4 2 4 6 2 6 4 2 4 2 10 2 10 2 6 4 6 2 6 4 2 4 6 6 8 4 2 6 10 8 4 2 4 2 4 8 10 6 2 4 8 6 6 4 2 4 6 2 6 4 6 2 10 2 10 2 4 2 4 6 2 6 4 2 4 6 6 2 6 6 6 4 6 8 4 2 4 2 4 8 6 4 8 4 6 2 6 6 4 2 4 6 8 4 2 4 2 10 2 10 2 4 2 4 6 2 10 2 4 6 8 6 4 2 6 4 6 8 4 6 2 4 8 6 4 6 2 4 6 2 6 6 4 6 6 2 6 6 4 2 10 2 10 2 4 2 4 6 2 6 4 2 10 6 2 6 4 2 6 4 6 8 4 2 4 2 12 6 4 6 2 4 6 2 12 4 2 4 8 6 4 2 4 2 10 2 10 6 2 4 6 2 6 4 2 4 6 6 2 6 4 2 10 6 8 6 4 2 4 8 6 4 6 2 4 6 2 6 6 6 4 6 2 6 4 2 4 2 10 12 2 4 2 10 2 6 4 2 4 6 6 2 10 2 6 4 14 4 2 4 2 4 8 6 4 6 2 4 6 2 6 6 4 2 4 6 2 6 4 2 4 12 2 12  * 

I'll give you a guess... it starts with 169,221,247....

Let me clarify the patterns... when I say 2 4* is the repeating pattern for 5 I mean that the multiples of 5 starting at 25 (5 squared) that contribute to identifying composites that had not already been identified are 25 + (2 x 5) and then 25 + (2 x 5) + (4 x 5)    and this repeats (hence the 2 4*)... so the next one is 25 + (2 x 5) + (4 x 5)  + (2 x 5)  and then 25 + (2 x 5) + (4 x 5)  + (2 x 5) + (4 x 5) 

You can see the pattern is already getting pretty long for 13. So why the repeating patterns? Well, it's all about where the integers are lining up... if we are only using 2 and 3 we can quickly work out that the common factor for these two is 6... 2 and 3 both divide into 6, so when you are working with two lines that are stepping by 2 and 3 they will line up every 6th integer. I have written 2* as a repeating pattern for then number 3 in the above table... remember, the number 2 in the repeating pattern 2* is the number of  steps of 3 that we take before repeating.... and 2  multiplied by 3 is 6. The example becomes clearer when looking at 5. 5 is the third line we are looking at, so the pattern will repeat when multiples of 2, 3 and 5 all line up... this is every 30 integers... we can work this out by going  2 x 3 x 5 = 30. And, look at the repeating pattern for 5... it's 2 4*, which is every 6... and 6 x 5 = 30. So the repeating pattern is well accounted for, and you can see why I didn't show the pattern for 17 .... the pattern repeats every 2 x 3 x 5 x 7 x 11 x 13 = 30,030

The repeating pattern comes after the next prime cycle has started... (except for 2,3... they line up at 6, which is before the next prime, 7). For example, for 17 we determined that all the primes up to 17 will line up in cycles of 30,030 integers. But by the time we get to 30,030 many many other prime cycles are taking effect... 23, 27,29.... all the way up to something like 173.

There is a cycle in the repeating patterns though:

 Prime Number  

Start of repeating pattern 

 7

  4 2 4 2 4 6 2 6...

11

  2 4 2 4 6 2 6...

13

4 2 4 6 2 6...

17

2 4 6 2 6...

See how the first number of the previous pattern is removed, and the pattern is passed to the next prime. The pattern is more complex than this, but there is a pattern there.

The repeating pattern that defines composites at the offset from the square of the prime also defines the gaps between primes starting from the prime up to the square of the prime. For example, the repeating pattern for 7 is 4 2 4 2 4 6 2 6*, so we can say that 7 + 4 = 11 is prime, 11 + 2 = 13 is prime, 13 + 4 = 17 is prime, 17 + 2 = 19 is prime, 19 + 4 = 23 is prime, 23 + 6 = 29 is prime, 29 + 2 = 31 is prime, 31 + 6 = 37 is prime, then back to the start of the repeating pattern.... 37 + 4 = 41 is prime, 41 + 2 = 43 is prime, 43 + 4 = 47 is prime, 47 + 2 = 49 not prime... this is the square of the prime who's repeating pattern we are looking at so it's not that suprising that the road ends here.... well, it doesn't quite end there.

Conversely,  we can say that the gaps between primes will define the composite offsets from the square of a prime.... again, up to the square of the prime. For example, lets use 13 this time.... the primes from 13 up to 169 (132) are:

13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101,103,107,109,113,127,131,137,139,149,151,157,163,167

The gaps between these are:

4,2,4,6,2,6,4,2,4,6,6,2,6,4,2,6,4,6,8,4,2,4,2,4,14,4,6,2,10,2,6,6,4

Which matches exactly the start of the long repeating pattern in table that shows the complete repeating pattern for 13 at the top of this page.

Now... the interesting part that allows us to make a more efficient prime seive is that the repeating patterns are of the form 2,4,2,4,2,4... or 4,2,4,2,4,2. Yes, there are some 6's and 8's and later on much higher integers.... but, the underlying reducable pattern is always 2,4,2,4,2,4... then 4,2,4,2,4,2.  This means that we have a way of skipping integers that we want to mark as composites.

For each prime after 2 we cross out every 2nd, then every 4th... alternating between the order that we do that, so for 5 we cross out every 2nd then every 4th... then for 7 we cross out every 4th then every 2nd. We are starting to cross out redundant integers... like a 6 here and there... but the 6 is made up of a 4 and a 2... then the pattern lines back up again... it works every time. However, we only alternate if the difference between the two consecutive primes in not a multiple of 6.... that's the interesting piece of the puzzle.... I though the pattern fell apart until I discovered this peice of the puzzle. I have implemented this algortihm and run it over the first 500 Million integers (yes, I know.. that's not THAT many in the world of numbers) and it works nicely... not sure how much faster it makes it (if at all. I have not tested yet), but the logic seems to hold up.

Copyright © 2007 - H Rudd