Step 1: Generate Sequence |A| for Symmetrical Range -N to N up to maximum multiple of A OR B in the given range using Base Prime Notation (BPN).
Generate the sequence |A| for the symmetrical range from -100 to 100, focusing on values of the form 6k ± 1.
| k Index | A (6k – 1) | Absolute Value |
|---|---|---|
| -16 | -97 | 97 |
| -15 | -91 | 91 |
| -14 | -85 | 85 |
| -13 | -79 | 79 |
| -12 | -73 | 73 |
| -11 | -67 | 67 |
| -10 | -61 | 61 |
| -9 | -55 | 55 |
| -8 | -49 | 49 |
| -7 | -43 | 43 |
| -6 | -37 | 37 |
| -5 | -31 | 31 |
| -4 | -25 | 25 |
| -3 | -19 | 19 |
| -2 | -13 | 13 |
| -1 | -7 | 7 |
| 0 | -1 | 1 |
| 1 | 5 | 5 |
| 2 | 11 | 11 |
| 3 | 17 | 17 |
| 4 | 23 | 23 |
| 5 | 29 | 29 |
| 6 | 35 | 35 |
| 7 | 41 | 41 |
| 8 | 47 | 47 |
| 9 | 53 | 53 |
| 10 | 59 | 59 |
| 11 | 65 | 65 |
| 12 | 71 | 71 |
| 13 | 77 | 77 |
| 14 | 83 | 83 |
| 15 | 89 | 89 |
| 16 | 95 | 95 |
This table lists the k-index values of A (6k – 1) for k from -16 to 16, and their absolute values.
Step 2: Order the absolute values which are the BPN index value candidates
Order the absolute values from 1 to N for the defined range. In this case, the range is from 1 to 100.
Absolute Value sequence: 1, 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.
These are the values we will work with to identify primes and generate composites within the range of 0 to 100. In this sequence, 1 has an index value of 0, 5 has an index value of 1, 7 has an index value of 2, and so forth.
We will not consider any other numbers within the range.
2 and 3 are givens as primes. No other multiples of 2 or 3 can ever be of the form A or B, and all primes greater than 3 are in 6k±1, so we won’t miss any primes focusing on these forms, and we won’t focus on the 2/3 of all numbers which are multiples of 2 and 3.
Further, by reducing our search to the absolute values of A OR B, we can search within just one of these forms, and in theory reduce the search space by half, so we are really only considering 1/6 of numbers in the given range.
Further, when using 6k±1 forms, and when determining composite factors, for example, the multiples of 5 which are contained in the range of 0-100; we do not need to consider the 20 different factors which we would otherwise need to cross out. We only need to consider the multiples of 5 which are also of the form |A| or |B|.
So this means with BPN, we only need to consider 6 candidates ({25, 35, 55, 65, 85, and 95}) as multiples of index 1 (which is 5), which is less than a third of the candidates we would need to eliminate in a Sieve of Eratosthenes in the same range.
The range from -100 to 100 contains 201 values (including 0), whereas the range from 0 to 100 contains 101 values. Therefore, working with the larger range initially seems counterintuitive. However, by working with only the form 6k – 1 in the range -100 to 100, we are essentially considering about 1/6th of the numbers in that range (since we’re skipping multiples of 2 and 3). This means we are searching through roughly 33 numbers.
If we were to work with both forms (6k – 1 and 6k + 1) in the range 0 to 100, we would be searching through about 1/3rd of the numbers in that range, which is approximately 33 numbers. While the range is doubled in -100 to 100, the reduction in the number of values we have to examine because we are only working with one form (6k – 1) does effectively reduce the search space. This is because the “savings” from only needing to consider one form outweighs the increase in the number of values due to the doubled range.
Step 3: Initialize Min-Heap for Composite Numbers
Initialize the heap with the squares of BPN index values less than or equal to √N to ensure composites remain within the range -N to N. For this example, N = 100.
Initial Heap: 1, 25, 49.
These correspond to the squares of the indices where the absolute values are 1, 5, and 7, respectively.
Step 4: Generate and Track Composite Numbers
Iterate through the sequence of |A| (6k – 1) from index 1 to the maximum index:
- 5 (Index 1):
- 5² = 25 ≤ 100.
- Maximum index j = floor((100 + 1) / (6 * 5)) = 3.
- New composites: 25, 35, 55, 65, 85, 95.
- 7 (Index 2):
- 7² = 49 ≤ 100.
- Maximum index j = floor((100 + 1) / (6 * 7)) = 2.
- New composites: 49, 77, 91.
- Continue this process for each subsequent index up to the maximum index.
Step 5: Infer Prime Numbers
After generating composites, numbers in the sequence |A| (6k – 1) that are not present in the heap are prime numbers.
Step 6: Create the Final Table
Based on the above steps, lets use a final table to illustrate the index, original A value, absolute value, whether it’s composite, and whether it’s prime.
| BPN Index | Original A Value | Absolute Value |A| | Composite? | Prime? |
|---|---|---|---|---|
| 0 | -1 | 1 | No | No |
| 1 | 5 | 5 | No | Yes |
| 2 | -7 | 7 | No | Yes |
| 3 | 11 | 11 | No | Yes |
| 4 | -13 | 13 | No | Yes |
| 5 | 17 | 17 | No | Yes |
| 6 | -19 | 19 | No | Yes |
| 7 | 23 | 23 | No | Yes |
| 8 | -25 | 25 | Yes (index 1 * 1) | No |
| 9 | 29 | 29 | No | Yes |
| 10 | -31 | 31 | No | Yes |
| 11 | 35 | 35 | Yes (index 1 * 2) | No |
| 12 | -37 | 37 | No | Yes |
| 13 | 41 | 41 | No | Yes |
| 14 | -43 | 43 | No | Yes |
| 15 | 47 | 47 | No | Yes |
| 16 | -49 | 49 | Yes (index 2 * 2) | No |
| 17 | 53 | 53 | No | Yes |
| 18 | -55 | 55 | Yes (index 1 * 3) | No |
| 19 | 59 | 59 | No | Yes |
| 20 | -61 | 61 | No | Yes |
| 21 | 65 | 65 | Yes (index 1 * 4) | No |
| 22 | -67 | 67 | No | Yes |
| 23 | 71 | 71 | No | Yes |
| 24 | -73 | 73 | No | Yes |
| 25 | 77 | 77 | Yes (index 2 * 3) | No |
| 26 | -79 | 79 | No | Yes |
| 27 | 83 | 83 | No | Yes |
| 28 | -85 | 85 | Yes (index 1 * 5) | No |
| 29 | 89 | 89 | No | Yes |
| 30 | -91 | 91 | Yes (index 2 * 4) | No |
| 31 | 95 | 95 | Yes (index 1 * 6) | No |
| 32 | -97 | 97 | No | Yes |