The Index Identity and Primality by Exclusion in the Generalized Index Generator (GIG) Sequence

1. The Unified GIG Sequence Definition and Structure

The Generalized Index Generator (GIG) sequence $X(k)$ is a deterministic sequence of integers, indexed by $k \in \mathbb{Z} \setminus \{0\}$, which contains all integers greater than 3 that are not divisible by 2 or 3. This set includes all prime numbers greater than 3.

1.1. GIG Term Definition and Scope

The sequence is defined by the unified absolute value function, which captures all numbers congruent to $\pm 1 \pmod{6}$:

The GIG sequence contains both primes $P_{GIG}$ and an infinite number of composite numbers $C_{GIG}$ (e.g., 25, 35, 49, etc.). The core challenge addressed is the efficient differentiation between the prime and composite terms based solely on their index $K$.

1.2. Indexing and Sequence Generation

The sign of the index $k$ determines the form of the resulting term $X(k)$ and its congruence modulo 6:

1.3. Ordinal Position and Index Mapping

The GIG sequence terms are ordered ascendingly by magnitude: $5, 7, 11, 13, 17, 19, \ldots$. The relationship between the ordinal position $i = 1, 2, 3, \ldots$ and the GIG index $k$ is given below.

2. Formal Derivation of the Index Identity

The GIG sequence is closed under multiplication: the product of any two GIG terms $X(n) \cdot X(m)$ yields another GIG term $X(K)$.

2.1. Algebraic Expansion of the Product

Let $n$ and $m$ be non-zero integers representing the indices of the factors. The product $P = X(n) \cdot X(m)$ always has the general algebraic expansion:

2.2. The Index Identity: Unified Proof

Proof: We solve for the index $K$ such that $X(K) = |6K - 1| = P$. The derivation is split into cases based on the congruence of the product $P$ modulo 6.

Case A: $P \equiv 1 \pmod{6}$ (Indices $n, m$ have the same sign)

When $n$ and $m$ have the same sign (e.g., $(+, +)$ or $(-, -)$), the product $P$ is congruent to $1 \pmod{6}$. The resulting term $X(K)$ must satisfy $X(K) = 6|K| + 1 = 6(-K) + 1$ (since $K$ must be negative). Substituting the general expansion for $P$:

Case B: $P \equiv 5 \pmod{6}$ (Indices $n, m$ have opposite signs)

When $n$ and $m$ have opposite signs, the product $P$ is congruent to $5 \pmod{6}$. The resulting term $X(K)$ must satisfy $X(K) = 6K - 1$ (since $K$ must be positive). Without loss of generality, let $n>0$ and $m<0$, so we write $m = -|m|$. The product $P$ is explicitly:

We solve for $K$ by equating $P = 6K - 1$:

Substituting the signed index $m = -|m|$ into the proposed identity $\mathbf{K = n + m - 6nm}$ gives $n + (-|m|) - 6n(-|m|) = n - |m| + 6n|m|$. Since the results match, the Index Identity is proven universally. $\square$

2.3. Completeness of the Index Mapping

The function $K(n, m)$ is sufficient to generate the full set of composite indices $C_{\mathbb{Z}}$. The table below confirms that the sign permutations of the factors $(n, m)$ correctly determine the sign and magnitude of $K$.

3. Primality Testing via Index Exclusion

3.1. GIG Factor Closure Lemma

Justification: A composite number $C \in C_{GIG}$ satisfies $C \equiv \pm 1 \pmod{6}$. The congruence $C \pmod{6} \equiv (P_1 \pmod{6}) \cdot (P_2 \pmod{6}) \equiv \pm 1 \pmod{6}$ necessitates that both factors $P_1$ and $P_2$ must also be congruent to $\pm 1 \pmod{6}$ (i.e., $P_1, P_2 \in GIG$).

3.2. GIG Primality Criterion

Proof: This is a direct consequence of Theorem 2.1 (The Index Identity) and Lemma 3.1 (GIG Factor Closure). If $X(K)$ is composite, it must factor into $X(n) \cdot X(m)$, guaranteeing $K$ is constructible. If $K$ is constructible, $X(K)$ is a product of two non-trivial factors, making it composite. $\square$

4. Composite Sequence Generation Algorithm and Complexity

4.1. Boundary Retrieval and Redundancy Reduction

The systematic search for composite indices $K$ requires defining a factor limit $N$, relative to the maximum absolute index magnitude under consideration, $|K|_{max}$:

Redundancy Reduction: The search space is halved by imposing the ordering constraint $|n| \ge |m|$, exploiting the symmetry of the Index Identity, $K(n,m) = K(m,n)$.

4.2. Computational Complexity and Practical Bottlenecks

Time Complexity: Since the factor search is proportional to $N^2$, where $N \sim \sqrt{|K|_{max}}$, the time complexity of generating the composite index set up to $|K|_{max}$ is linear:

Space Complexity Bottleneck: The requirement to store all composite indices up to $|K|_{max}$ for exclusion results in an unmanageable space complexity for large limits: $\mathbf{S(|K|_{max}) = O(|K|_{max})}$.

4.3. The Segmented GIG Index Sieve

To address the space complexity bottleneck, the Segmented GIG Index Sieve is employed. This technique constrains the primality test to a segment $[K_{start}, K_{end}]$ of indices at a time.

• Segmentation: The full range is divided into segments of size $S$.
• Factor Bound $N$: The factor loop utilizes the full $N$ bound (based on the highest limit of the overall range) to ensure all necessary factors for marking composites within the current segment are included.
• Memory Utilization: A temporary Boolean array of size $S$ is used to mark composite indices $K$ that fall within the current segment. The memory consumption is effectively reduced to $\mathbf{O(S)}$, independent of the overall limit $|K|_{max}$.

5. Pseudocode Implementation

5.1. Core Identity Functions

These functions define the mapping between the index and the GIG term, and the Index Identity used to generate composite indices.

FUNCTION GIG_TERM(k: Integer) -> Integer
    // Calculates the GIG sequence term X(k) = |6k - 1|
    RETURN ABS(6 * k - 1)
END FUNCTION

FUNCTION COMPOSITE_INDEX_K(n: Integer, m: Integer) -> Integer
    // Index Identity: K = n + m - 6nm
    // 'n' and 'm' are the indices of the two GIG factors.
    RETURN n + m - 6 * n * m
END FUNCTION

5.2. Segmented GIG Index Sieve Logic

This procedure implements the Index Identity for efficient generation of composite indices within a fixed range, embodying the Segmented Sieve strategy.

FUNCTION GENERATE_COMPOSITE_INDICES_IN_RANGE(K_start: Integer, K_end: Integer) -> Set<Integer>
    // Determines the optimal search depth N based on the range limit
    K_max_abs = MAX(ABS(K_start), ABS(K_end))
    N = FLOOR(SQRT(K_max_abs / 6)) + 5 // Factor limit for the largest possible factor index
    
    UNIQUE_K = New Set()
    
    // Iterate factors i and j up to the maximum required bound N
    FOR i FROM 1 TO N DO
        // Redundancy Reduction: Enforce |n| >= |m| by checking j <= i
        FOR j FROM 1 TO i DO
            
            // Test all four sign permutations to cover all GIG product types
            PERMUTATIONS = [(i, j), (-i, -j), (i, -j), (-i, j)]
            
            FOR EACH (n, m) IN PERMUTATIONS DO
                // Calculate the composite index K using the Index Identity
                K = COMPOSITE_INDEX_K(n, m)
                
                // Check if the calculated index K falls within the current segment
                IF K_start <= K AND K <= K_end THEN
                    UNIQUE_K.ADD(K)
                END IF
            END FOR
            
        END FOR
    END FOR
    
    // The resulting set contains all indices K whose corresponding term X(K) is composite.
    RETURN UNIQUE_K.SORTED()
END FUNCTION

6. Implications for Number Theory and Algorithm Design

The Index Identity and the resulting exclusion method offer significant theoretical and practical advancements.

6.1. Theoretical Significance

The identity $\mathbf{K = n + m - 6nm}$ provides a closed-form, polynomial definition of the structure of all composite numbers greater than 3. This fundamentally changes the framework for primality analysis, shifting the focus from the chaotic distribution of prime numbers to the ordered, deterministic generation of composite numbers via a simple quadratic function of two integer variables. This structured approach provides a new algebraic tool for addressing problems related to prime distribution.

6.2. Algorithmic Significance

Time Complexity: The $\mathbf{O(|K|_{max})}$ time complexity, combined with the redundancy reduction optimization, establishes this as an exceptionally fast deterministic sieve method, relying primarily on high-speed integer arithmetic.

Space Efficiency: The Segmented GIG Index Sieve (Section 4.3) successfully removes the $\mathbf{O(|K|_{max})}$ space constraint, transforming the method from a theoretical construct into a practical, memory-efficient algorithm for large-scale primality testing and sequence generation.