Step-by-Step Method to Identify Primes and Composites using BPN with Absolute Value

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 IndexA (6k – 1)Absolute Value
-16-9797
-15-9191
-14-8585
-13-7979
-12-7373
-11-6767
-10-6161
-9-5555
-8-4949
-7-4343
-6-3737
-5-3131
-4-2525
-3-1919
-2-1313
-1-77
0-11
155
21111
31717
42323
52929
63535
74141
84747
95353
105959
116565
127171
137777
148383
158989
169595

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 IndexOriginal A ValueAbsolute Value |A|Composite?Prime?
0-11NoNo
155NoYes
2-77NoYes
31111NoYes
4-1313NoYes
51717NoYes
6-1919NoYes
72323NoYes
8-2525Yes (index 1 * 1)No
92929NoYes
10-3131NoYes
113535Yes (index 1 * 2)No
12-3737NoYes
134141NoYes
14-4343NoYes
154747NoYes
16-4949Yes (index 2 * 2)No
175353NoYes
18-5555Yes (index 1 * 3)No
195959NoYes
20-6161NoYes
216565Yes (index 1 * 4)No
22-6767NoYes
237171NoYes
24-7373NoYes
257777Yes (index 2 * 3)No
26-7979NoYes
278383NoYes
28-8585Yes (index 1 * 5)No
298989NoYes
30-9191Yes (index 2 * 4)No
319595Yes (index 1 * 6)No
32-9797NoYes