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?

When x=1 you get 5 &7 both prime but for other numbers you get one only.

Easy if it's if it's 3 or 4, but more tricky if it's in the millions.

Also how do you get 2 and 3?

Actually, it not even 5 & 7.

Using the pattern I found you go through the subset { 6x-1 U 6X+1 }, (5, 7, 11, 13, 17, 19, 23, 25, 29, 31, 35, 37 ... N } eliminating the non-primes. There is no x=1. Its not an equation, but a process.

My process only deals with the numbers the subset.

41 minutes ago, bdonelson said:

Actually, it not even 5 & 7.

Using the pattern I found you go through the subset { 6x-1 U 6X+1 }, (5, 7, 11, 13, 17, 19, 23, 25, 29, 31, 35, 37 ... N } eliminating the non-primes. There is no x=1. Its not an equation, but a process.

My process only deals with the numbers the subset.

Ok perhaps I am not reading his correctly. What is "X" in "6x-1?"

9 hours ago, bdonelson said:

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

I understand what you are trying to do, but I see a difficulty.

I am not a number theory specialist, but as I understand prime number theory.

Yes all prime numbers greater than 3 can be expressed in the form 6n±1, where n is a positive integer.

However not all numbers of the form 6n±1 are prime.

So I see why you are looking for two loops.

But the problem, as I see it, is that the pattern of occurence of prime numbers is not regular.

This implies that the pattern of occurence of non primes is also non regular.

This also implies that you cannot therefore weed out non primes on a regular occurrence basis.

Your second loop would have to test each number as generated, and there is no known test for a prime.

Note there are some very long regular sequences in the smaller prime numbers.

7 hours ago, studiot said:

is that the pattern of occurence of prime numbers is not regular.

Actually, what I think that I have found is a pattern that does work,

7 hours ago, studiot said:

However not all numbers of the form 6n±1 are prime.

Yes, but all the non-primes or psuedo-primes of the set { 6n±1 } appear to be multiples of previous members of the set { 6n±1 } in a pattern that I am using. Each multiple has a pattern that I am using to mark the psuedo-primes.

11 hours ago, pinball1970 said:

Ok perhaps I am not reading his correctly. What is "X" in "6x-1?"

Sorry I should have been clear about.

The X is a varaible not times.

7 hours ago, studiot said:

Note there are some very long regular sequences in the smaller prime numbers.

Yes, you are right. How long would a sequence need to be not "smaller"?

50 minutes ago, bdonelson said:

es, you are right. How long would a sequence need to be not "smaller"?

I have no idea what you mean by smaller.

The clock here is unreliable but it says that you joined 18 hours ago.

New members are allowed 5 posts in their first 24 hours as a secuity measure.

Afte rthat posts are unlimited.

12 minutes ago, studiot said:

I have no idea what you mean by smaller.

What I am thinking of in that question is, how long of number sequence needs to be tested before it can be classified as possible more then just a long regular sequence?

Edited August 21Aug 21 by bdonelson
word correction

5 minutes ago, bdonelson said:

What I am thinking of in that question is, how long of number sequence needs to be tested before it can be classified as possible more then just a long regular sequence?

As noted this is not my area of Mathematics.

I seem to remember such questions were studied in Hardy's book in the subject, which used to be called 'Higher Arithmetic' (ie university arithmetic). Look for Davenport's book by that name.

But as far as I remember finding new primes no longer happens very often since the length of sequence is now so enormous that computers are definitely needed.

Edited August 21Aug 21 by studiot

Ok,

Maybe, I should read that.

But, the length of sequence is now so enormous is closer to what I am thinking about.

I have verified my pattern out to Primes equal to 100,000, and I can certainly test further.

I am wondering how far does the testing need to be done to be given "serious" consideration?

2 hours ago, studiot said:

As noted this is not my area of Mathematics.

I seem to remember such questions were studied in Hardy's book in the subject, which used to be called 'Higher Arithmetic' (ie university arithmetic). Look for Davenport's book by that name.

But as far as I remember finding new primes no longer happens very often since the length of sequence is now so enormous that computers are definitely needed.

I did say I am not up to date about this, but only 10⁵ ?

The largest known prime has over 40,000 decimal digits.

2^136,279,841 − 1

https://en.wikipedia.org/wiki/Mersenne_prime

Actually, I was asking the last question because of the size of Prime Numbers.

I am hoping that someone can the question of how large should I make my test cases, before attempting to find the computer resources necessary to test those large values?

I can test higher then 100,000. It's just how effort should I make too justify the next step?

6 hours ago, bdonelson said:

Actually, I was asking the last question because of the size of Prime Numbers.

I am hoping that someone can the question of how large should I make my test cases, before attempting to find the computer resources necessary to test those large values?

I can test higher then 100,000. It's just how effort should I make too justify the next step?

Since you haven't fully addressed my first reply, that is come up with a reasoned prediction of the interval of non primes, your only method of proof is the method of exhaustion.

This method is of course impossible for an infinite sequence, unlike the proof of the four colour theorem which was only difficult.

Ok, I will attempt to better describe my prediction of the interval non-primes.

On 8/20/2025 at 9:36 PM, bdonelson said:

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 have no formula or equation. Maybe that is the result of my own lack of understanding of mathematics.

What I do have is the above process that uses a pattern based on the Multiple of 6 and every odd number. This pattern appears to hold for every member of the set { (6n -1) U (6n+1) }

My test appears to eliminated every non-prime below 100,000.

Is there any other currently known pattern of prime numbers does even this?

I finally found an article, after a year searching, that comes close to describing the structure I have based my pattern on.

https://www.scirp.org/journal/paperinformation?paperid=74345

I wish that I had read this back then.

52 minutes ago, bdonelson said:

What I do have is the above process that uses a pattern based on the Multiple of 6 and every odd number.

Can you explain the pattern? I do not follow how it works.

In other words, assume I have a fair amount of computing power available; what should I implement in software to beat able to test your idea up to some large number N. I know how to program but I do not have a clear specification of your new prime number sieve idea.

Can you explain the pattern? I do not follow how it works.

Ok, I will be happy to.

Using the structure described in the mention journal, the pattern is as follows.

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 79

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.

Sorry, typo the Second example non-prime is 77

One thing I will add is that the complete algorithm does stop at members >= sqrt ( N)

Also, it does not perform the run through the set for values already marked as non-primes, only updates the starting values.

Thanks for the answer. It appears equivalent to a 6-wheel optimization of the Sieve of Eratosthenes rather than a new sieve. Unfortunately the current description is too vague to be further analysed.

Ok, I can see how it could a 6-wheel optimization.

But, it is my understanding that all other functional sieves use some form of division / factorization to test to see if a value is a prime.

Is any other one that uses a set pattern to simply mark the primes?

As I understand the concept, wheel optimizations still leave non-primes.

33 minutes ago, bdonelson said:

But, it is my understanding that all other functional sieves use some form of division / factorization to test to see if a value is a prime.

Sieve of Eratosthenes, the one I mentioned above, use additions. No division or multiplication is needed.

(Note: just as @studiot I am not a number theory specialist. I have some limited knowledge and interest in primes mainly due to it's use in cryptography)

Ok, I agree the Sieve of Eratosthenes does addition to find the multiples, and does not test the values left.

But, I guess purpose in posting my question is simplicity and efficiency.

I agree that it is slightly more complicate then the Sieve of Eratosthenes, but I believe that it can be more effective then the currently available sieve options.

25 minutes ago, bdonelson said:

I agree that it is slightly more complicate then the Sieve of Eratosthenes, but I believe that it can be more effective then the currently available sieve options.

Unfortunately I don't understand the description of your method so I can't comment on its complexity.

Fair enough.

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

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)

I hope this makes it clearer.

Maybe it would be helpful, if I provided more two examples.

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)

Edited August 25Aug 25 by bdonelson
I forgot a word.

Thanks for the update. What you describe still looks like 6-wheel optimization of the Sieve of Eratosthenes, nothing different. That reduces constants by skipping multiples of 2 and 3 but doesn’t change the asymptotics; the standard sieve runs in O(n log log n) time with O(n) space* and your description doesn’t indicate an improvement beyond that.

*) unsegmented