Fundamental Concepts in Algebraic Set Theoretic Prime Operations
Case 1.) n=1k and n=xy
If an integer “n=1k” >1 cannot also be expressed as the product of two integers “n=xy”, where x and y are also greater than 1, then n is a prime number. This covers all prime numbers, including 2.
Case 2.) n=2k+1 and n=4xy+2y+2x+1
If an odd integer “n=2k+1” cannot also be expressed as the product of two odd numbers “n=(2x+1)(2y+1)=4xy+2y+2x+1”, where x and y are equal to or greater than 1, then n is a prime number. This covers all prime numbers greater than 2. This case eliminates all odd composites and thus identifies odd primes only.
Case 3.) n=|6k-1| and n=|36xy+6x-6y-1|
If an odd number “n=6k±1” cannot also be expressed as the product of two odd numbers of the form n=6k±1, “n=|(6x-1)(6y+1)|=|36xy+6x+6y-1|”, where x and y are positive or negative integers equal to or greater than |1|, then n is a prime number. This covers all prime numbers greater than 3.
The Case 3 approach works because for every z in 6k-1, there is a -z in 6k+1, and vice versa.
Composites in 6k±1 forms must be of the forms: (6x-1)(6y-1), (6x-1)(6y+1), and (6x+1)(6y+1). This is explicitly for a positive range of 0<q. However, taking in the fact that for every z in 6k-1 (e.g. …-7,-1,5,11,17..), there is a -z in 6k+1 (e.g. …-17,-11,-5,1,7…), and vice versa, we can work in an expanded range of -q<0<q with either form 6k+1 or 6k-1 and find all composites.
Since in range 0<q, all the composites in 6k-1 must be of the form n=(6x-1)(6y+1)=36xy+6x-6y-1 due to residue classes mod 6 (and the other forms must be within 6k+1), we know that all of the composites in 6k+1 ((6x-1)(6y-1) and (6x+1)(6y+1)) must have a negative twin of the form (6x-1)(6y+1) in 6k-1 in the negative range.
Thereby, inferring the absolute value of any number in sequence 6k+1 or 6k-1 in the negative range will give the corresponding value from the other sequence in the positive range.
When we consider the absolute values of negative range of 6k+1 or 6k-1 with the corresponding positive values from 0<q, then we can find all the primes in the form 6k+1 and 6k-1 combined by just considering one of the forms and absolute value relationships inferred from a symmetrical number range.
Generalized Theorem
A positive integer n is prime if and only if it satisfies one of the following conditions:
Case 1 (Fundamental Definition of Primes): n = 1·k for some positive integer k, and n cannot be expressed as x·y for any non-negative integers x, y > 1.
Case 2 (Odd Primes): n = 2k+1 for some non-negative integer k, and n cannot be expressed as (2x+1)(2y+1) = 4xy+2x+2y+1 for any non-negative integers x, y.
Case 3 (Primes of form ): n = |6k-1| for some integer k, and n cannot be expressed as |(6x-1)(6y+1)| = |36xy+6x-6y-1| for any non-zero integers x, y.
This theorem provides a hierarchical approach to characterizing prime numbers:
- The first case is the fundamental definition of primality that applies to all primes.
- The second case restricts to odd numbers (plus 2), narrowing the search space by eliminating even composites.
- The third case further restricts to numbers congruent to ±1 (mod 6), eliminating multiples of 2 and 3.
- The elegance of Case 3 lies in its use of absolute values and symmetry between 6k-1 and 6k+1 sequences, allowing us to capture all composite numbers in both sequences using a single formula. This provides a more efficient characterization of primes greater than 3.
Each successive case builds upon modular arithmetic properties to progressively refine an understanding of prime numbers and how efficiency of primality testing can be enhanced.
Review of Set-Based Prime Identification Theory
This set-based method for prime identification offers an alternative conceptual framework to traditional sieving methods.
Core Theory: The set method works by defining two explicitly generated sets and then excluding Set A from Set B:
In case 3, Set A: Contains all numbers of the form |6k-1| for integers k
In case 3, Set B: Contains all composite numbers expressible as |36xy+6x-6y-1| (products of |6x-1| and |6y+1|)
The set of primes greater than 3 is then defined as the set difference: P = A – B
Process: On-Demand Prime Generation
Series 1: Generating |6k-1| (or |6k+1|) Numbers:
Start generating numbers of the form |6k-1| (or |6k+1|) incrementally.
This series can continue indefinitely, as you’re not bound by a terminal limit.
You can stop this generation at any point, effectively defining your “terminal series 1 number.”
Series 2: Generating Composites |36xy + 6x – 6y – 1|:
Simultaneously, generate composite numbers using the formula |36xy + 6x – 6y – 1|.
Crucial Limiting Factor: To ensure you’ve captured all composites, you need to generate composites up to a limit that guarantees you’ve covered all possible factors.
Determining the Limit:
The smallest prime factor you’ll encounter in the |6k-1| form is 5.
The largest factor you need to consider is the square root of your “terminal series 1 number.”
Therefore, you need to generate composites using the formulas where:
- x and y vary such that (6x-1) and (6y+1) are factors within the range of 5 to the square root of your terminal series 1 number.
- Once all combinations of x and y have been used such that the factors that created them are less than or equal to the square root of the terminal series 1 number, then all composites have been created that are less than the terminal series 1 number.
Set Subtraction (P = Series 1 – Series 2):
- After stopping Series 1 and generating Series 2 up to the necessary limit, perform a set subtraction.
- The resulting set P will contain all prime numbers of the form |6k-1| that are less than your “terminal series 1 number.”
Visualization
A multiplication table is a good way to visualize how the sieve-like method works and how it can be used to check all possible ranges without missing any composites.
In any case, the table needs a number of rows equal to the number of integers of the considered number form which are less than the square root of the target number.
So, for Case 1, if you are considering how many primes are less than 100, you need 10 rows, because 10 is the square root of 100 and we are working in increments of 1. You would need 50 columns, because 100 divided by 2 is 50, and 2 is the smallest prime number considered in Case 1.
For Case 3, if you are considering how many primes are less than 100, you need 3 rows, because there are 3 numbers of the form |6k-1| less than 10 (the square root of 100). You would need 7 columns, because there are 7 numbers of the form |6k-1| less than 100 divided by 5; since 5 is the smallest prime factor produced by |6k-1| numbers.
In either case, if a number less than the target number (eg. 100) appears in Row 1 or Column 1 of the table, and does not appear in the body of the table, it is prime.
Parallels with Traditional Sieves
Both approaches share certain fundamental characteristics:
- Both ultimately identify primes by eliminating composites
- Both rely on the fact that all composites have prime factors
- Both exploit modular arithmetic properties (especially that primes > 3 are of form 6k±1)
Key Differences with Traditional Sieving Approaches
The set method differs from traditional sieves in several important ways:
- Generation vs. Elimination: Traditional sieves start with all numbers and iteratively remove multiples. The set method directly generates two sets using explicit formulas and compares them.
- Mathematical Formulation: Sieves use divisibility as the core operation. The set method uses closed-form expressions and set operations.
- Conceptual Approach: Sieves work “from the bottom up” by eliminating multiples of each prime found. The set method works by explicitly characterizing all composites of a certain form.
- Terminal Limit: The terminal “N” value needs to be input in a sieve before it is run. The set method can be arbitrarily run indefinitely without foreknowledge of the terminal limit.
- Implementation Focus: Sieves typically focus on efficient marking/elimination algorithms
The set method focuses on efficient generation of potentially very large sets.
Conclusion
This set-based approach offers a fresh perspective on prime identification, leveraging algebraic formulations rather than divisibility tests. While traditional sieves may be more familiar, this method provides both theoretical insights and potential advantages, especially when considering specific subsets of primes.
The key insight is that primality can be characterized as membership in a well-defined set that is directly constructible through algebraic expressions, rather than as the result of an elimination process.
This method qualifies as a prime number generator in the sense that:
- It produces exactly the set of all prime numbers (greater than 3, with simple extensions to include 2 and 3).
- It uses a deterministic method that will correctly identify any prime within its range.
- It can theoretically continually generate primes up to any arbitrary limit (given sufficient computational resources).
However, it differs from some other generators in that it’s not optimized for sequentially producing primes one at a time. Instead, it generates an entire set of primes within an arbitrarily terminating range by set-theoretic operations.