My understanding of a wheel sieve optimization is

For a chosen number n (usually no larger than 4 or 5), the first n primes determine the specific way to generate a sequence of natural numbers which are all known in advance to be coprime with these primes; that is, they are all known to not be multiples of any of these primes. This method can thus be used for an improvement of the trial division method for integer factorization, as none of the generated numbers need be tested in trial divisions by those small primes.

My algorithm ignores the data, as long it is in this form

{ (6n-1) U (6n+1) } (5, 7, 11, 13, 17, 19, 23, 25, 29, 31, 35, 37, ... N)

It might as well be { (a b) (c d) (e f) (g h) ... X }

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

7 hours ago, bdonelson said:

My understanding of a wheel sieve optimization is

Ok. I did not compare your description with trial division. You may want to look at wheel optimization and Eratosthenes sieve, the one I mentioned.

I don't have much to add to prime number sieve optimizations, but for others like myself, the following provides some interesting ibsights and historical background on the age old search for primes

Interesting that you should share that video.

As I commented there,

Why is that so many of videos on the Topic of Prime Numbers finish where this video finishes?

I like the video. It covers an important history of Prime Numbers.

But, like most videos on the topic there is very little about recent discoveries about the patterns in the 6X+1 U 6X-1 set of numbers.

As to wheel optimization, I have looked at.

While my sieve does cycle through the numbers similar, it does not use the numbers themselves to decide whether or not they are prime.

My sieve simply follow a pattern. There is no testing.

Edited August 26Aug 26 by bdonelson
I add a sentence.

47 minutes ago, bdonelson said:

Interesting that you should share that video.

As I commented there,

Why is that so many of videos on the Topic of Prime Numbers finish where this video finishes?

I like the video. It covers an important history of Prime Numbers.

But, like most videos on the topic there is very little about recent discoveries about the patterns in the 6X+1 U 6X-1 set of numbers.

If you want something more up to date than Gauss try this little book.

Professor De Sautoy even delves into the connection with Physics.

I don’t see any follow-up in my comment on complexity:

23 hours ago, Ghideon said:

O(n log log n) time with O(n) space

@bdonelson are you familiar with this kind of notation and it’s connection to your description?

1 hour ago, bdonelson said:

My sieve simply follow a pattern. There is no testing.

What do you mean by testing?

57 minutes ago, Ghideon said

What do you mean by testing?

The desciption of Wheel optimization that I have been using talks about

This method can thus be used for an improvement of the trial division method for integer factorization

I was referring to this, I guess the Wheel Optimization itself doesn't use any.

But, the difference is that does use an input set of values, mine does not. Also mine does not involve co-primes.

52 minutes ago, bdonelson said:

The desciption of Wheel optimization that I have been using talks about

This method can thus be used for an improvement of the trial division method for integer factorization

I was referring to this, I guess the Wheel Optimization itself doesn't use any.

That is one use of wheel factorisation. If you scroll down on the wikipedia page* you will find:

... may then be used in trial division or sieves.

Trial division is of less importance in this discussion; you have asked about a sieve idea of yours.

59 minutes ago, bdonelson said:

But, the difference is that does use an input set of values, mine does not. Also mine does not involve co-primes.

That seems to contradict what you have described so far; your opening post states that you use the set of values:

On 8/21/2025 at 3:36 AM, bdonelson said:

This sieve is a process of taking a value from the set { 6x-1 U 6X+1 }

Which means that you work with numbers co-prime to 6. Also, you refer to a set of values to mark non-primes:

On 8/21/2025 at 3:36 AM, bdonelson said:

identify members of the set to be marked as non-prime.

You still have not commented on O(n log log n) time with O(n) space; have you compared your algorithm to wheel optimization and Eratosthenes sieve; the one I compare to your description of your idea? If you do not know how to compare, just post a question.

https://en.m.wikipedia.org/wiki/Wheel_factorization

Oh well.

This sieve is a process of taking a value from the set { 6x-1 U 6X+1 }

You are correct. I did say that.

The more I have I thought about I should have said that it starts with a value 1, which happens to be the multiple of the first pair (5, 7).

None of the variables used require use of the values in the set.

I guess I have used names that represent a part of the pattern itself, but the values of set play no part in the algorithm. They simply "placeholders".

15 hours ago, bdonelson said:

You are correct. I did say that.

The more I have I thought about I should have said that it starts with a value 1, which happens to be the multiple of the first pair (5, 7).

None of the variables used require use of the values in the set.

I guess I have used names that represent a part of the pattern itself, but the values of set play no part in the algorithm. They simply "placeholders".

Ok; to avoid further contradictions in your descriptions, maybe start form scratch:

On 8/21/2025 at 3:36 AM, bdonelson said:

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

Describe the algorithm of your sieve idea. Be detailed so that someone that does not yet know your idea can follow the algorithm and check that it produces a list of prime numbers smaller than some natural number "n". This could be performed with pen and paper (for small n) or programmed for larger values of n. Once the algorithm is clearly described we can see if it works for any n, if it is identical or similar to known methods and, if interesting, analyse time and memory complexity.

Maybe this would be easier?

Here is the data structure of my C++ implementation.

long Multiple; // Current Multiple of 6

long Minus; // 6X-1

long Plus; // 6X+1

bool MCheck; // Is 6X-1 a prime

bool PCheck; // Is 6X+1 a prime

Here is the code that I am currently working on.

int main()

{

// Starting with the Subset ( 6X ± 1 ) arranged in pairs (5, 7) (11, 13) (17, 19) ... ( 6n - 1, 6n + 1)

// Minus_Check, and Plus_Check are indicators of ( Possible Prime ) status, Default Value = Prime

// ----------------------------------------------------------------------------------

long N; // Set to Test Range

long MaxMultiple;

long i;

long StopValue;

bool StartingSide; // Side is an indicator of which side of the 6X±1

bool Side;

int CurrentOddNumber;

long CurrentMultiple;

long FirstStep; // First Multiple to Set Check Value

long SecondStep;

long NextStep;

long CurrentStep;

bool Inside; // Flag for the Inside Loop

bool Outside; // Flag for the Outside Loop

Prime_Possible_Node FirstNode;

Prime_Possible_Node CurrentNode;

// ----------------------------------------------------------------------------------

N = 1000;

MaxMultiple = N / 6;

FirstNode = CurrentNode.ProduceList(MaxMultiple); // Create the List of the Values of the Set of (6X-1) U (6X+1) to the Size N

StopValue = sqrt(MaxMultiple) + 1;

StartingSide = false;

Side = false;

CurrentOddNumber = 3;

CurrentMultiple = 1;

FirstStep = CurrentOddNumber;

NextStep = CurrentMultiple + FirstStep;

Inside = 1;

Outside = 1;

CurrentNode.FirstRecord(CurrentNode); // Goto Beginning of List

while ( Outside )

{ // Outside Loop

if ( StartingSide ) // Which Side of the Multiple

Side = true;

else

Side = false;

FirstStep = CurrentOddNumber; // First Multiple to Set Check Value

SecondStep = CurrentMultiple * 2; // Second Multiple to Set Check Value

CurrentNode.AdvanceRecords(CurrentMultiple); // Goto First Record for Current Possible Prime

if( CurrentNode.CheckCurrentStatus(CurrentNode, StartingSide) ) // Check if Current Value is Marked as Prime for exclusion from the Inside Loop

{

while ( Inside ) // Inside Loop

{

CurrentNode.AdvanceRecords(FirstStep); // First Step

if( Side )

CurrentNode.PCheck(); // Set the Psuedo-Prime Flag for the Minus

else

CurrentNode.MCheck(); // Set the Psuedo-Prime Flag for the Plus

CurrentNode.AdvanceRecords(SecondStep); // Second Step

if ( Side )

Side = false;

else

Side = true;

if( Side )

CurrentNode.MCheck(); // Set the Psuedo-Prime Flag for the Minus

else

CurrentNode.PCheck(); // Set the Psuedo-Prime Flag for the Plus

if ( Side )

Side = false;

else

Side = true;

if ( CurrentStep <= MaxMultiple )

CurrentStep = CurrentStep + FirstStep + SecondStep;

else

Inside = false;

} // Inside Loop

if ( StartingSide )

CurrentMultiple = CurrentMultiple + 1;

CurrentNode.FirstRecord();

if ( CurrentMultiple <= StopValue )

{

CurrentOddNumber = CurrentOddNumber + 2;

if( StartingSide )

StartingSide = false;

}

else

Outside = false;

} // Check if Current Value is Marked as Prime

} // Outside Loop

// Show List of Primes

//List.print();

}

I hope that this is clearer about what I am attempting to do.

11 hours ago, bdonelson said:

MCheck

What is the class definition for MCheck?

How do you test 6x-1 to be prime then 6x+1 to be Prime?

Are you saying 5

6*5-1 =29 6*5+1 =31

But the problem is knowing 29 and 31 are prime.

Is that what your program does: identify Primes by sieving 29 and 31?

I’m just trying to see if I can understand this correctly.

What is the class definition for MCheck?

The class definition is a linked list, this can also work with an array, or any data structure that represents a series of records.

MCheck and PCheck are boolean.

How do you test 6x-1 to be prime then 6x+1 to be Prime?

No test. Any test is perform after the sieve is finished.

Are you saying 5

6*5-1 =29 6*5+1 =31

No. My program does not care what the values are. It operates only on the sequence of the pattern ( Multiple, Current Odd Number )

But the problem is knowing 29 and 31 are prime.

Is that what your program does: identify Primes by sieving 29 and 31?

My program only identifies the non-primes in the set { (6n-1) U (6n+1) }, leaving the primes.

Edited August 29Aug 29 by bdonelson
I decided to answer the other questions.

12 hours ago, Trurl said:

How do you test 6x-1 to be prime then 6x+1 to be Prime?

The idea is about sieving; you mark all non primes in a list of integers 0..n which leaves you with a list of the prime numbers <= n. In a sieve approach you do not test a number for primality, you remove non-primes by some algorithm until you have only prime numbers.

d

On 8/28/2025 at 3:49 PM, bdonelson said:

Maybe this would be easier?

The program does not seem complete but it helps; it still looks like the classic Sieve of Eratosthenes + optimisation.

17 hours ago, bdonelson said:

My program does not care what the values are. It operates only on the sequence of the pattern

I thought about this; let's analyse from a different angle. A sieve is a step-by-step procedure systematically crossing out composite numbers. You don’t have to “test” each number for primality but loop over small primes and mark their multiples. For example, when on p=5, marking 10,15,20,25,… only hits composites; same idea for p=7,11,… Each pass begins from the next unmarked integer; in a sieve that guarantees its prime (if it were composite, a smaller prime factor would already have crossed it out). This is the basic idea of the classic Sieve of Eratosthenes as far as I know (without any optimisations that seems to be part of the idea in OP).

But now; if the implement the the classic Sieve of Eratosthenes, and just look at the output. I mean how Sieve of Eratosthenes graphically looks like; is there anything that looks like "patterns"? And if so, are these "patterns" what you use in your idea? If this long-shot is correct then we may be looking at the same algorithm but from different angles; you are reverse engineering the Sieve of Eratosthenes from observation of what it "looks like". I might try to create an illustration of this.

On 8/28/2025 at 9:49 AM, bdonelson said:

bool MCheck; // Is 6X-1 a prime

bool PCheck; // Is 6X+1 a prime

In your own comments the function MCheck and PCheck say Prime.

21 hours ago, bdonelson said:

My program only identifies the non-primes in the set { (6n-1) U (6n+1) }, leaving the primes.

But aren’t you missing a bunch of numbers. Do you do this to find a pattern in Primes or create the largest Prime from the pattern?

After the sieve eliminates number you say only Primes will remain. What proves the left over numbers are Prime?

MCheck and PCheck?

14 hours ago, Trurl said:

But aren’t you missing a bunch of numbers. Do you do this to find a pattern in Primes or create the largest Prime from the pattern?

If I am not mistaken, all primes greater then 4 in the set { (6n-1) U (6n+1) }.

14 hours ago, Trurl said:

In your own comments the function MCheck and PCheck say Prime.

The comment is a question. I guess that would be clearer, if I had included a question mark.

MCheck and PCheck are my "flags" to marked as non-prime.

---

The code that I posted is my to codify my algorithm using a object-oriented link-list method.

I have decided to put that on hold.

Here is what I have so far using a simpler method with an Array.

#include <stdio.h>

#include <cmath>

#include <stdbool.h>

// C++ program to use an Array of Records.

#include <iostream>

using namespace std;

int main()

{

// Starting with the Subset ( 6X ± 1 ) arranged in pairs (5, 7) (11, 13) (17, 19) ... ( 6n - 1, 6n + 1)

// Minus_Check, and Plus_Check are indicators of ( Possible Prime ) status, Default Value = Prime

// ----------------------------------------------------------------------------------

struct record

{

long Multiple; // Multiple of 6

long Minus = Multiple*6 - 1; // 6X-1

long Plus = Multiple*6 + 1; // 6X+1

bool MCheck = true; // Is 6X-1 a prime?

bool PCheck = true; // Is 6X+1 a prime?

};

long N; // Set to Test Range

long MaxMultiple;

long i;

long StopValue;

bool StartingSide; // Side is an indicator of which side of the 6X±1

bool Side;

bool FirstSide;

int CurrentOddNumber;

long CurrentMultiple;

long FirstStep; // First Multiple to Set Check Value

long SecondStep;

long NextStep;

long CurrentRecord;

bool Inside; // Flag for the Inside Loop

bool Outside; // Flag for the Outside Loop

// ----------------------------------------------------------------------------------

N = 1000;

MaxMultiple = N / 6;

struct record List [MaxMultiple - 1]; // Create the List of the Values of the Set of (6X-1) U (6X+1) to the Size N

for(int i=1; i<MaxMultiple; i++) {

List [i].Multiple = i + 1;

}

StopValue = sqrt(MaxMultiple) + 1;

StartingSide = false;

Side = false;

CurrentOddNumber = 3;

CurrentMultiple = 1;

FirstStep = CurrentOddNumber;

NextStep = CurrentMultiple + FirstStep;

Outside = 1;

CurrentRecord = 1; // Goto Beginning of List

while ( Outside )

{ // Outside Loop

if ( StartingSide ) // Which Side of the Multiple

Side = true;

else

Side = false;

CurrentRecord = CurrentMultiple; // Goto First Record for Current Possible Prime

FirstStep = CurrentOddNumber; // First Multiple to Set Check Value

SecondStep = CurrentMultiple * 2; // Second Multiple to Set Check Value

if ( StartingSide ) // Which Side of the Multiple

FirstSide = List [CurrentRecord].MCheck;

else

FirstSide = List [CurrentRecord].PCheck;

if( FirstSide ) // Check if Current Value is Marked as Prime

{

for(int i=j; j<MaxMultiple; j++)

{ // Inside Loop

CurrentRecord = CurrentRecord + FirstStep; // First Step

if( Side )

List[CurrentRecord].MCheck = 0; // Set the Psuedo-Prime Flag for the Minus

else

List[CurrentRecord].PCheck = 0; // Set the Psuedo-Prime Flag for the Plus

CurrentRecord = CurrentRecord + SecondStep; // Second Step

if ( Side )

Side = false;

else

Side = true;

if( Side )

List[CurrentRecord].MCheck = 0; // Set the Psuedo-Prime Flag for the Minus

else

List[CurrentRecord].PCheck = 0; // Set the Psuedo-Prime Flag for the Plus

if ( Side )

Side = false;

else

Side = true;

} // Inside Loop

if ( StartingSide )

CurrentMultiple = CurrentMultiple + 1;

if ( CurrentMultiple <= StopValue )

{

CurrentOddNumber = CurrentOddNumber + 2;

if( StartingSide )

StartingSide = false;

}

else

Outside = false;

} // Check if Current Value is Marked as Prime

} // Outside Loop

// Show List of Primes

//List.print();

}

Edited August 30Aug 30 by bdonelson
Added a separation horizontal line

Here are some illustrations of a sieve algoritm visualised in a grid with 6 columns.

First the final result: natural numbers n<300 with primes marked in green. The list of primes is the result of running the sieve of Eratosthenes for n<300.

Illustration of the starting point of the algorithm; we use grid cells without numbers for this illustration. We will run the standard algorithm by counting the grid cells and count how many cells to skip rather than looking at numbers in the grid.

Count grid cells from top left (first cell = 0) and mark every second cell with a count > 2. I guess this could qualify as a "pattern" since it forms coloured stripes of marked cells? Note again that this is basically sieve of Eratosthenes, just without any optimisations. Nothing special.

Start from the beginning and count past the blue bordered cell until an unmarked cell is found. You will count 0,1,2,3. Mark every 3rd cell after cell no 3. We now have two unmarked columns. If the cells were numbered these cells would cover the all numbers 6k+1 and 6k-1 used in a 2,3 wheel. Again this is standard except for the start; we would skip ahead to p² (cell 3²=9 in this case) in the standard algorithm
Note! the illustration is unclear; The blue border around cell 2 has disappeared.

Starting from the top again: first empty cell after the previous blue framed one is 5. This time, when we count cells 5,10,15,... it looks like some kind of diagonals. Note that we revisit some grid cells; I mark them again to show that some kind of "pattern" appears.

If we continue like there will be alternating "patterns" that becomes sparser as the count of the starting cell grows.

The final result before we put numbers in the cells. By numbering from top left starting with 0 every white cell will contain primes and every pink cell will contain composite numbers.This is of course nothing new or any patterns in prime numbers, it's just a consequence of expressing the well known sieve an visualising in a grid.

This is how I see a connection between the sieve of Eratosthenes, wheel optimisation and what someone may see as "patterns" during the execution of the algorithm.

As a reference; the complete set of illustrations in an animation. Note that without any optimisation we do not cut off at sort(n) meaning there is a lot of unnecessary work in later steps. I kept these as an illustration. In the end of the animation the numbers with primes highlighted will flash by before restarting. See the first picture above for a freeze of that frame.

It was a little tricky to get this right, hopefully there are no major mistakes.

Edited August 30Aug 30 by Ghideon

Maybe this will help show why I don't believe that my algorithm is not like other sieve ideas.

What other sieves can produce only Twin Primes, with a couple of minor modifications?

Because mine can, and at a slighty faster rate then it produces Primes.

Also,

Part of the pattern of the pairs that my algorithm uses works like this

Col A is (6n-1) and Col B is (6n+1)

The Psuedo-primes in Col A are always the result of multiplying a member of Col A and a member of Col B.

The Psuedo-primes in Col B are always the result of multiplying Col A times Col A or Col B times Col B, including the squares.

For example

Col A		Col B
5		7
11		13
17		19
23		25
29		31
35		37
41		43
47		49
53		55

5 is from Col A, 25 is from Col B
5 is from Col A, 7 is from Col B, 35 is from Col A,
5 is from Col A, 11 is from Col A, 55 is from Col B

This pattern also does appear to hold through 100,000.

On 8/31/2025 at 10:01 PM, bdonelson said:

Maybe this will help show why I don't believe that my algorithm is not like other sieve ideas.

That sentence seems kind of odd?

On 8/31/2025 at 10:01 PM, bdonelson said:

What other sieves can produce only Twin Primes, with a couple of minor modifications?

This is the first time you mention Twin Primes so I do not know how it is related to previous discussion.

On 8/31/2025 at 10:01 PM, bdonelson said:

Col A is (6n-1) and Col B is (6n+1)

The Psuedo-primes in Col A are always the result of multiplying a member of Col A and a member of Col B.

The Psuedo-primes in Col B are always the result of multiplying Col A times Col A or Col B times Col B, including the squares.

Yes, it follows form elementary modular arithmetics? I might be able to produce a mathematical proof if it's helpful.