Theorem (using set B as an example): By testing numbers of the Set B form |6x + 7| for primality within the symmetrical segment -N ≤ x ≤ N, including their negative counterparts, we can accurately identify all prime numbers within the range 0 < p ≤ (6N + 7), including the missing values from set A.
Discussion (Human written): I’m continuing to look for efficient ways to identify primality using the symmetry of the prime number forms 6k±1 which all prime numbers greater than 2 and 3 exist. Specifically looking in the function 6x+7=n; which also corresponds to 6k+1=n; and which we call “B”. We are also specifically looking in the function 6y+5=n; which also corresponds to 6k-1=n; and which we call “A”.
Recall our basic approach:
Semiotic Prime Theorem (which I had ingloriously referred to as Hotchkiss Prime Theorem previously): Let A = {6x + 5 | x ∈ ℤ} be the set of all numbers of the form 6x + 5, and B = {6y + 7 | y ∈ ℤ} be the set of all numbers of the form 6y + 7. Let AA, AB, and BB represent the sets of products:
AA = {(6x + 5)(6y + 5) | x, y ∈ ℤ}
AB = {(6x + 5)(6y + 7) | x, y ∈ ℤ}
BB = {(6x + 7)(6y + 7) | x, y ∈ ℤ}
Then, any number that is an element of A or B but not an element of AA, AB, or BB is a prime number.
AB is always a composite number which we never need to check if we know it is of form AB it has an inherently composite form and will never be a prime number.
That means that when we are looking for prime numbers, we only need to look for numbers which are the form (A BUT NOT AA) AND (B BUT NOT BB).
If a number is not in AB (which we already know to be non-prime), then if it is (A BUT NOT AA) OR (B BUT NOT BB), then A OR B is a prime number.
In looking for efficient ways to leverage the “sign” of AA or BB to identify a non-prime number in number set A or set B; I’ve been looking at the expanded versions of these terms, recognizing that their Boolean properties must give them a “signature” to differentiate them from a “prime” form of A or B which can be expressed as A or B, but never be expressed as AA or BB:
AA=36xy+30x+30y+25
BB=36xy+42x+42y+49
However, this reductive approach was not bearing fruit and led to some mistaken attempts to determine primality which I embarrassingly shared 😀 . With that said, I have made some advancements in this concept to share which do further reduce the search space for primes using the Semiotic Sieve approach and leverage a similar concept to reduce the complexity of the forms we need to check for non primality in A and B using modular arithmetic.
Returning to the expanded forms of the non-prime forms of A AND B;
AA=36xy+30x+30y+25
BB=36xy+42x+42y+49
Consider that:
AA = {(6x + 5)(6y + 5) | x, y ∈ ℤ}
BB = {(6x + 7)(6y + 7) | x, y ∈ ℤ}
Then, we can condense:
AA = a*b = 6x+5 where a, b, and x are integers.
BB = a*b = 6y+7 where a, b, and y are integers.
Then, if a number is A=6x+5 OR B=6y+7; but is not also of the form AA=6x+5=ab OR BB=6y+7=ab; and A OR B is not divisible by 5; then A OR B is a prime number.
This overall significantly reduces the amount of candidates we need to search for as prime numbers further; and allows us to compute composite candidates for AA=6x+5=ab or BB=6y+7=ab using modular arithmetic;which is computationally elegant compared to factorization methods.
If a number is in list A OR B but not AA OR AB OR BB then it is a prime number.
Now, we can even further half the search space by finding ALL primes within just A OR B.
Firstly, the search space of Semiotic Sieve focuses on 6k±1 numbers. So right away, this is a significant reduction in the search space compared to Sieve of Eratosthenes (2/3 reduction in the starting number set).
Just focusing on the elegance of the theorem, and not implementing any other optimizations; we can optimize this even further, to just focus on 1/3 of the starting number set by looking at absolute values of function A (6x+5) and function B (6y+7). This is because the functions contain all the positive values of one function as negatives in the other function.
That is, A contains: …-19,-13,-7,-1,5,11,17,23…
and B contains: …-23,-17,-11,-5,1,7,13,19….
So, if A has all the values of B as negative values, and vice versa, we do not even need to consider candidate numbers of B AND BB when looking at A AND AA numbers. We can simply use the symmetrical properties of Semiotic Prime Theorem to infer the negative values of A AND AA as positive values of B AND BB and vice versa.
Therefore, we can find all the primes from 0 to N within a symmetrical segment around 0 for form (A BUT NOT AA) OR (B BUT NOT BB), simply by inferring the absolute negative values of A OR B in range −N≤x≤N.
Therefore, once we build a set of all the numbers A OR B in −N≤0≤N, which are not also AA OR BB then the absolute values of the returned integers will be the complete set of prime numbers in 0≤N for function A AND function B (which excluding 2 and 3 includes all prime numbers since all prime numbers greater than 3 are of the form 6k±1 as we established, and which we used to define A and B as sets/functions in the first place; however, we could not do this with A alone without B; and therefore it still takes 7 steps to create ALL the numbers).
(AI OUTPUT) Theorem (using set B as an example): By testing numbers of the Set B form |6x + 7| for primality within the symmetrical segment -N ≤ x ≤ N, including their negative counterparts, we can accurately identify all prime numbers within the range 0 < p ≤ (6N + 7), including the missing values from set A.
Proof Using Symmetry and Absolute Values of Set B:
- Foundation: Semiotic Prime Theorem:
- All primes greater than 3 can be expressed as either 6k + 1 or 6k +5.
- The Semiotic Prime Theorem states that a number of the form 6x + 5 (set A) or 6y + 7 (set B) is prime if and only if it cannot be expressed as a product of the forms AA, AB, or BB (as defined above).
- Focusing on Set B:
- We begin by generating numbers of the form B = 6x + 7 within the symmetrical segment –N ≤ x ≤ N. This range covers all potential primes of the form 6k + 7 within 0 < p ≤ (6N + 7).
- Ignore AB and remove all multiples of 5 other than 5 itself.
- Efficient Composite Identification:
- To identify composite numbers within set B, we use modular arithmetic to efficiently determine which numbers are of the form BB = (6x + 7)(6y + 7) = 6x + 7=ab, where a and b are integers greater than 1. This avoids the need for computationally expensive factorization.
- Prime Identification in Set B:
- Any number in set B that is not identified as composite (i.e., not of the form BB) must be prime, as it cannot be expressed as a product of two integers greater than 1 and it satisfies the conditions of the Semiotic Prime Theorem.
- Symmetry and Inferring Primes in Set B:
- The negative values of set A (6x + 5 where x is negative) correspond to the positive values of set B (6y + 7). This is due to the symmetry of the 6k ± 1 forms around zero.
- Therefore, by taking the absolute values of the negative primes we found in set B, we directly obtain positive primes of the form 6k – 1 (set A) within the range 0 < p ≤ (6N + 7).
- Completeness:
- By combining the primes we found in set B (and their inferred counterparts in set A), we have systematically checked all possible prime candidates within the desired range.
- The Semiotic Prime Theorem guarantees that any number satisfying the conditions within our method must be prime.
Conclusion:
This method, leveraging the Semiotic Prime Theorem, symmetry, and efficient composite identification through modular arithmetic, provides a complete and accurate way to find all prime numbers within a given range. It demonstrates the power of understanding the inherent structure of prime numbers to optimize sieving algorithms.
Thus, incorporating symmetry in the Semiotic Sieve reduces the search space by a factor of 6 compared to the original search space in the Sieve of Eratosthenes. This represents an 83.33% reduction in the number of candidates that need to be tested for primality prior to incorporating any other enhancements. If you have a half-bit to remember 2 and 3; this finds all prime numbers otherwise.
- Conceptual Search Space: In a theoretical sense, when we include negative values in our symmetrical segment (-N ≤ x ≤ N), we are conceptually considering twice as many numbers compared to just the positive range (0 ≤ x ≤ N). So, conceptually, the search space is not reduced.
- Computational Search Space: However, what matters more for practical efficiency is the number of computations we perform. Since we are leveraging symmetry and inferring the primality of numbers in set A from the results in set B, we are effectively only performing primality tests on numbers in set B.
- Negative Values vs. Larger Range: Storing negative values does not inherently take less memory than storing a larger range of positive values. Integers generally occupy the same amount of memory regardless of their sign.
- Optimization Potential: While the memory usage might be comparable, the key advantage of our symmetrical approach is that it allows for more efficient computation. We can exploit the symmetry to reduce the number of primality tests, which saves on processing time, even if the memory footprint is similar.
The most significant gain in efficiency comes from reducing the number of primality tests performed, not necessarily from reducing the memory footprint. The symmetrical approach allows us to halve the number of tests needed by inferring primes in set A from the results in set B.
By moving beyond this elegant implementation and incorporating tools like Sieve of Eratosthenes to mark composites of forms A and B within this approach, the speed of the Semiotic Sieve can be significantly improved further.