Possible New Prime Number Sieve Idea

[bdonelson]

I have found what I think is a simple, possibly efficient, algorithm for a Prime Number Sieve.

This sieve is a process of taking a value from the set { 6x-1 U 6X+1 }, (5, 7, 11, 13, 17, 19, 23, 25, 29, 31, 35, 37 ... N ). Using that value as a starting point to move through the same of numbers, based a simple pattern that I have found, to mark / eliminate the non-primes. Repeating the process for all the primes.

The process using the multiple of 6, a pattern of the odd numbers, & an alternating switch to identify members of the set to be marked as non-prime.

The steps of this process are

Goto the starting value

Inside Loop
Add to the multiple the First Constant to the Starting Value and choose the Minus or Plus to set based on the alternating switch.
Add to the multiple the Second Constant to the Starting Value and choose the Minus or Plus set based on the alternating switch.
Repeat

The Outside Loop simply sets the First Constant and Second Constant.

I would like to hear comments about my idea. Is it as simple and efficient as I think it is?

[BigDumbDinosaur]

bdonelson wrote:

I have found what I think is a simple, possibly efficient, algorithm for a Prime Number Sieve...I would like to hear comments about my idea.  Is it as simple and efficient as I think it is?

It’s hard for me to make a judgment from what you are proposing.  Perhaps if you were to write some code illustrating the process it would be easier to form an opinion on simplicity and efficiency.

[BigEd]

Welcome, bdonelson!

I think perhaps your idea is the same as the wheel method:
https://en.wikipedia.org/wiki/Wheel_factorization
(if not, then please say so, and I'll think a little harder)

Funnily enough, I was just reading an old recreational maths book where there was a footnote

Quote:

One who invents anything in elementary mathematics is likely to find that “the ancients have stolen his ideas.”

Which is to say, there's still a thrill in discovering something, even if it's been discovered before.

[barnacle]

I'm unclear from your description whether this is a procedure for _finding_ primes, or for marking candidates to be tested for prime. It doesn't seem to have an output... maybe I'm not reading something correctly?

The 'rule' for all primes being a multiple of six, plus or minus one, is one I remember from school, but it certainly doesn't result in reverse for finding primes: in your example, 25 and 35 are not prime. Ohers later in the sequence: 49, 55, 57 and so on are also not prime.

(which this keyboard keeps spelling 'prome' for some reason. Perhaps my fingers need calibration?

Neil

[bdonelson]

Ok, I will be happy to.

Here is a more detailed psuedo code with two examples.

member = member of the set { (6n-1) U (6n+1) }

m = Multiple of member times 2 // 5 and 7 is 2, 11 and 13 is 4

odd = starting odd number

column = starting column number

x = m

switch column

Loop

x = x + odd

if (column =1)

then

{ 6x - 1 is not prime

column = 2 }

else

{ 6x + 1 is not prime

column = 1 }

x = x + m

if (column =1)

then

{ 6x - 1 is not prime

column = 2 }

else

{ 6x + 1 is not prime

column = 1 }

Loop

This used for every member of the set, incrementing odd by 2 for every member.

For example

m = (multiple of 5 is 1) times 2 = 2

odd = 3

column is 1

Switch Column

Add 1 to 3

Multiple 4 is the pair 23, 25

Based on Column the non-prime is 25

Switch Column

Add 4 + 2

Multiple 6 is the pair 35, 37

Based on Column the non-prime is 35

Switch Column

Add 6 to 3

Multiple 9 is the pair 53, 55

Based on Column the non-prime is 55

Switch Column

Add 9 + 2

Multiple 11 is the pair 65, 67

Based on Column the non-prime is 65

Switch Column

Add 11 to 3

Multiple 14 is the pair 83, 85

Based on Column the non-prime is 85

Switch Column

Add 14 + 2

Multiple 16 is the pair 95, 97

Based on Column the non-prime is 95

Switch Column

Second Example

m = (multiple of 7 is 1) times 2 = 2

odd = 5

and its column is 2

Switch Column

Add 1 to 5

Multiple 6 is the pair 35, 37

Based on Column the non-prime is 35

Switch Column

Add 6 + 2

Multiple 8 is the pair 47, 49

Based on Column the non-prime is 49

Switch Column

Add 8 to 5

Multiple 13 is the pair 77, 79

Based on Column the non-prime is 77

Switch Column

Add 13 + 2

Multiple 15 is the pair 89, 91

Based on Column the non-prime is 91

Switch Column

Add 15 to 5

Multiple 20 is the pair 119, 121

Based on Column the non-prime is 119

Switch Column

Add 20 + 2

Multiple 22 is the pair 131, 133

Based on Column the non-prime is 133

Switch Column

I believe that this pattern is consistent with every value of the set.

[BigEd]

Just to note, several forums have had new users sign up with the same username and offer the same initial post.

In the case of physicsforum the moderators closed the thread after a series of good-faith inquiries got unsatisfactory responses. The original poster declared that they had wasted their time, and the moderators declared that the original poster had wasted everyone else's time.

[bdonelson]

Yes, I am the same person.

If someone takes the time to review the questions and answers, I am hoping they can see my frustration.

I asked for opinions about

This is an algorithm of a prime sieve, and I am looking for ways to test its accuracy & efficiency. I am open to any suggestions.

I kept getting unrelated demands.

As a results, I made the statement about wasting time.

If they did not want to answer my question, why join the discussion?

Seems straightforward to me.

[bdonelson]

Maybe this will help illustrate my concept.

I have found that it appears that all the value of the set { (6n-1) U (6n+1) } (5, 7, 11, 13, 17, 19, 23, 25, 29, 31, 35, 37, ... N)

The pattern I found works like this

Following the pattern using 5 does not mark the numbers in bold because they multiples of but because they follow the pattern.

5 7

11 13

17 19

23 25

29 31

35 37

41 43

47 49

53 55

59 61

65 67

71 73

77 79

83 85

89 91

95 97

Following the pattern using 7 does not mark the numbers in bold because they multiples of but because they follow the same pattern.

5 7

11 13

17 19

23 25

29 31

35 37

41 43

47 49

53 55

59 61

65 67

71 73

77 79

83 85

89 91

95 97

Following the pattern using 11 does not mark the numbers in bold because they multiples of but because they follow the same pattern.

5 7

11 13

17 19

23 25

29 31

35 37

41 43

47 49

53 55

59 61

65 67

71 73

77 79

83 85

89 91

95 97

101 103

107 109

113 115

119 121

125 127

131 133

137 139

143 145

149 151

Following the pattern using 13 does not mark the numbers in bold because they multiples of but because they follow the same pattern.

5 7

11 13

17 19

23 25

29 31

35 37

41 43

47 49

53 55

59 61

65 67

71 73

77 79

83 85

89 91

95 97

101 103

107 109

113 115

119 121

125 127

131 133

137 139

143 145

149 151

155 157

161 163

167 169

The difference between the four examples is based on the multiple of 6 ( 5 & 7 is 1, 11 & 13 is 2 ) and the advancing odd number.

This means there is only an advancing so many values again and again.

Those are preset based on the same multiple and odd number for each run through the set { (6n-1) U (6n+1) } (5, 7, 11, 13, 17, 19, 23, 25, 29, 31, 35, 37, ... N)

I hope this makes it clearer.

[BigDumbDinosaur]

bdonelson wrote:

Maybe this will help illustrate my concept...

At the risk of being snarky, which I don’t intend to be, 6502.org is a website that is devoted to the MOS Technology 6502 family of processors and bus-compatible peripherals.  We like to keep the focus on homebrew or commercial computers powered by a 65(c)02 or 65C816, on methods of interfacing 6502 contraptions to other systems, oddball 6502 applications (such as implanted medical devices), along with algorithms, code, documentation and discussion that involves the 6502 family.  Many members have a specific range of interests related to the 6502 family, e.g., quite a few are Forth enthusiasts, some are hardware geeks, and still others have more generalized interests.

That considered, I think you may get a more receptive audience here if you post something that ties into the forum’s raison d'être.  A very generalized “do this and if this, do that” narrative tends to be less interesting than some example code that one can run through their favorite assembler, load onto their 6502 machine, and do some testing.  Even code written in a high-level language, e.g., C or BASIC, might spark interest.  Otherwise, I fear you will not drum up many responses to your original query.

[GARTHWILSON]

Yes, I'm hoping to find a key to figure this out, starting with the U in "{ (6n-1) U (6n+1) }" (which I looked up and what I found didn't really help), and then write a 65xx assembly-language routine, which I expect will interest several members here.

[bdonelson]

Quote:

At the risk of being snarky, which I don’t intend to be, 6502.org is a website that is devoted to the MOS Technology 6502 family of processors and bus-compatible peripherals.

I am sorry about that. I only posted here because I found similar discussions here.

I do have an interest in the MOS Technology 6502 family of processors.

I will come back when I have the time to discuss relevant topics.

[barnacle]

GARTHWILSON wrote:

starting with the U in "{ (6n-1) U (6n+1) }"

I read that as the set union operator: so the set of numbers that are either one higher or one lower than a multiple of six.

I _think_ I see where the OP is going, but I still don't follow the algortihm; it looks as if it's still the Sieve but without the initial removal of multiples of two and three.

Eratosthenes' Sieve is a way to find prime numbers in a set, optimised by dividing by already discovered primes up to the square root of the number being tested. I think this is doing the same.

Neil

edit: Aristophanes wrote 'The Frogs' with the immortal chorus 'coax, coax, coax'. Eratosthones filtered them from the swamp.

[BigEd]

bdonelson wrote:

I only posted here because I found similar discussions here.

I'm now pretty much certain that you've noticed that 4 in 6 numbers must be composite, and so when looking for primes you only need to consider 2 in 6 candidates. That's very much exactly the observation behind wheel factorisation: the development of any quick prime related program is almost always first to discard even numbers efficiently, and shortly after that many programs also discard (or skip) multiples of 3.

So, your observation is true, is interesting, and has some utility, but it isn't new.

We have indeed had previous discussions here, but I think always with some direct relevance to the 6502 or some 6502-based computer. A particularly good recent thread, with lots of commented and documented code, is by gfoot (George)
Fast prime sieve implementation

It is quite a technical and mathematical thread, which is as expected.

Edit: another relevant and fun thread is
A coding challenge: prime numbers

[bdonelson]

Yes, in some this similar to a wheel sieve.

Does a wheel use advance pattern like this does? ( 5 uses 2 & 3, 7 uses 2 & 5, 11 uses 4 & 7, 13 uses 4 & 9, and so on )

I believe the real difference lies in that

The core of the algorithm is Advance X “records”, Set the correct value to non-prime, Advance Y “records”, Set the correct value to non-prime, Repeat.

There is no calculation performed beyond what is need to advance to the next “record”.