Cartesian Analysis - Optimised Sieve Clarified

Some clarification of the composite gaps using an image:

In the above image the integers that contribute to identifying integers that are not prime are left marked in black. Those that are redundant because the integer has already been identified (by a black mark in a previous column) are marked in green.

If you removed all the green points and then squashed the image into a single line you would have a line with all the white gaps showing the prime numbers... with no duplication of black dots during the squashing up of the image.

In the first column (starting at the left, marking all multiples of 2 starting at 4) all contribute to identifying integers that are composites... so they are all left black.

In the second column, which marks all the multiples of 3 starting at 9, only every second one identifies an integer that was not already known to be composite... so only every second one is marked black.

The third column are all multiples of 4 (starting at 16)... and these are all green, because all even numbers were identified by the first column.

The fourth column are all multiples of 5 (starting at 25)... and here we see the pattern 2, 4, 2, 4... mark the first one (25) and then the second after that (35) and then the fourth after that (55)... etc. This is the 2, 4, 2, 4 repeating pattern referred to on the previous page (Cartesian Analysis).... hopefully this makes it a bit clearer.

The fifth column are all multiples of 6 (starting at 36).... and of course they are all green... all even numbers have already been marked as composite.

The sixth column (multiples of 7 starting at 49) reveals the pattern 4, 2, 4, 2, 4.... I didn't quite include enough to show that the pattern is not a simple 4, 2, 4, 2, 4, 2 pattern.... as described on the previous page the repeating pattern for 7 is actually  4, 2, 4, 2, 4, 6, 2, 6

However... when trying to bring in a definable pattern that contributes to removing redundancy (i.e. identifying the green dots) then using the pattern of 4, 2, 4, 2, 4  still works.... because the actual pattern 4, 2, 4, 2, 4, 6, 2, 6  can be describe with 4, 2, 4, 2, 4, (2 + 4), 2, (2 + 4)

What this means is that the simple rule of repeating 4, 2, 4, 2, 4, 2.... etc.  still works even though we're bringing in the redundancy of an 'extra' composite in the (2 + 4).... in other words the pattern still overlays the black points where they are needed, but there are two redundant points for each cycle of the repeating pattern 4, 2, 4, 2, 4, (2 + 4), 2, (2 + 4).... they land on a green point.

So the pattern is either 2,4,2,4... or 4,2,4,2... (see, for 5 it is 2,4,2,4... and then for 7 it is 4,2,4,2...)

Now, as I tried to explain on the previous page there is one more pattern to complete the picture of idenitifying a pattern which removes some of the redundant green points. This final pattern is that the repeating pattern of 2,4,2,4.... then 4,2,4,2... then 2,4,2,4.... only toggles when the difference between the prime and it's previous is not a multiple of 6.

This set of rules can be used to build a sieve that identifyies all composites (and hence all primes) with the removal of some redundancy of a basic sieve. The perfect set of rules would not have ANY redundancy... but this pattern I discovered includes more and more redundancy as the process goes higher up the number line. It always works (I think anyway... I have tested to 500 Million, which is all my C++ code could handle with the basic setup I slapped together).... but there will be more and more redundancy as you get further up the number line.

Copyright © 2007 - H Rudd