bdonelson

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.

If I am not mistaken, all primes greater then 4 in the set { (6n-1) U (6n+1) }. 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 implement singly linked list using a class #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(); }

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.

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.

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".

Oh well.

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.

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.

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 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 }

Maybe it would be helpful, if I provided 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)

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.

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.

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.

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.

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

Ok, I will attempt to better describe my prediction of the interval non-primes. 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.

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?

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?

What I am think 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?

Actually, what I think that I have found is a pattern that does work, 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. Sorry I should have been clear about. The X is a varaible not times. Yes, you are right. How long would a sequence need to be not "smaller"?

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.

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?