The Lewis Sieve Thesis

 

---

The Lewis Sieve: A Natural Extension for Targeted Prime Detection and Instant Factorization

Abstract

The Sieve of Eratosthenes has long been celebrated as a simple and effective algorithm for generating primes. However, its classical implementation is limited by memory constraints when extended to very large ranges and provides no insight into the factorization of composites. In this paper, we introduce the Lewis Sieve—a natural extension of the Sieve of Eratosthenes that focuses on a targeted interval and, by propagating prime factor information during the elimination process, instantaneously factors composite numbers. We present the algorithm, formal definitions, and axiomatic proofs of correctness, and discuss the novelty and importance of this approach.

1. Introduction

Prime numbers are the building blocks of the natural numbers, and efficient algorithms for prime detection and factorization are central to number theory and its applications. The classical Sieve of Eratosthenes efficiently identifies primes by iteratively crossing off multiples, yet it requires vast storage when applied to large intervals and lacks any mechanism for recording the factorization process.

The Lewis Sieve addresses these limitations by combining two key innovations:

1. Targeted Segmentation: Instead of processing the entire number line, the sieve is applied to a carefully chosen interval. This focused approach circumvents the memory issues inherent in large-scale sieving.
2. Factor Propagation: As each composite is eliminated, the sieve records the smallest prime factor that caused its elimination. This “tagging” provides immediate factorization information and unifies the tasks of prime detection and factorization.

This paper argues that the Lewis Sieve is not a mere trick but a natural and significant evolution of the classical method, with wide-ranging implications for both theory and practice.

2. Preliminaries and Notation

Let $\mathbb{N}$ denote the natural numbers, and let $\mathbb{P} \subset \mathbb{N}$ denote the set of prime numbers. For any $n \geq 2$, we say that $n$ is prime if its only divisors are 1 and $n$ itself; otherwise, $n$ is composite.

Axiom 1 (Fundamental Theorem of Arithmetic):
Every integer $n \geq 2$ can be uniquely expressed as

$$n = p_1^{\alpha_1} p_2^{\alpha_2} \cdots p_k^{\alpha_k},$$

where $p_i \in \mathbb{P}$ and $\alpha_i \in \mathbb{N}$.

Definition 1 (Base Primes):
For a target number $N$, define the set of base primes as

$$P_{\text{base}}(N) = \{ p \in \mathbb{P} : p \leq \sqrt{N} \}.$$

3. Review of the Sieve of Eratosthenes

The classical Sieve of Eratosthenes works as follows for $n \in \mathbb{N}$:

1. Initialization:
   Create the set $S_0 = \{2, 3, \dots, n\}$.

2. Elimination:
   For each $p \in S_0$ with $p \leq \sqrt{n}$:

   • If $p$ is not eliminated, then for every integer $k \geq 2$ such that $p \cdot k \leq n$, remove $p \cdot k$ from $S_0$.

3. Output:
   The remaining numbers in $S_0$ are primes.

While effective for prime detection, this method does not capture any information regarding which prime factor eliminated a composite number.

4. The Lewis Sieve: Concept and Methodology

4.1. Conceptual Overview

The Lewis Sieve extends the classical sieve by adding a propagation mechanism. In addition to marking a number as composite, the sieve records a “tag” that indicates the smallest prime factor responsible for its elimination. Formally, define a tagging function:

$$\phi: \{ n \in [S,E] \mid n \text{ is composite} \} \to P_{\text{base}}(E)$$

so that for each composite $n$, $\phi(n)$ is the smallest prime $p$ (with $p \leq \sqrt{n}$) dividing $n$.

4.2. Targeted Segmentation

To address the practical limitations of storing and processing huge intervals, the Lewis Sieve operates on a specific target interval $[S, E]$. For example, rather than sieving from 2 to 48,000, one may focus on the interval $[48{,}000, 48{,}500]$. This segmentation greatly reduces memory requirements and allows the algorithm to focus its power where it is most needed.

5. Formal Algorithm Description

5.1. Precomputation of Base Primes

Given a target number $E$, compute the base primes:

1. Let $m = \lfloor \sqrt{E} \rfloor$.
2. Apply the Sieve of Eratosthenes to generate $$P_{\text{base}}(E) = \{ p \in \mathbb{P} : p \leq m \}.$$

5.2. Segmented Sieving with Propagation

Let $[S, E]$ be the target interval, and let $A(n)$ be a Boolean indicator for $n$ in the interval (initially, $A(n) = \text{true}$ for all $n$). Also, let $T(n)$ be a tag initialized as empty (denoted by $\varnothing$).

For each $p \in P_{\text{base}}(E)$:

1. Compute the first multiple of $p$ in the interval: $$m_p = \max(p^2, \lceil S/p \rceil \cdot p).$$
2. For $n = m_p, m_p+p, m_p+2p, \dots, E$:
   • Set $A(n) = \text{false}$ (marking $n$ as composite).
   • If $T(n) = \varnothing$, set $T(n) = p$.

At the end of the process:

• The numbers for which $A(n) = \text{true}$ are prime.
• For each composite $n$, $T(n)$ is its smallest prime factor.

5.3. Extraction of Factorization

For any composite $n \in [S,E]$:

• $T(n)$ gives the smallest prime factor.
• Compute $q = n / T(n)$ and, if necessary, apply the same process recursively on $q$ to obtain the complete prime factorization.

6. Proofs of Correctness

Theorem 1 (Soundness)

Statement:
If $A(n) = \text{true}$ for $n \in [S,E]$, then $n$ is prime. If $A(n) = \text{false}$, then $T(n)$ is defined and $T(n) \mid n$.

Proof:

• Suppose $A(n) = \text{true}$ and $n$ is composite. Then by the Fundamental Theorem of Arithmetic, there exists a prime $p \leq \sqrt{n}$ such that $p \mid n$. Since $p \in P_{\text{base}}(E)$ (as $n \leq E$), the algorithm would have processed $p$ and marked $n$ as composite, contradicting $A(n) = \text{true}$.
• Conversely, if $n$ is composite, there exists $p \in P_{\text{base}}(E)$ such that $p \mid n$. When processing $p$, the algorithm sets $A(n) = \text{false}$ and, if $T(n)$ was empty, assigns $T(n) = p$. Hence, $T(n)$ is defined and divides $n$. $\square$

Theorem 2 (Completeness)

Statement:
Every composite number $n \in [S,E]$ is marked (i.e., $A(n) = \text{false}$), and every prime $n \in [S,E]$ remains unmarked.

Proof:
Let $n \in [S,E]$.

• If $n$ is composite, then it has a prime factor $p$ with $p \leq \sqrt{n}$. Since $p \in P_{\text{base}}(E)$, the algorithm marks $n$ as composite.
• If $n$ is prime, no $p \in P_{\text{base}}(E)$ divides $n$, and hence $n$ remains unmarked. $\square$

7. Complexity Analysis

Assume the target interval $[S, E]$ has length $L = E - S + 1$.

• Precomputation of base primes up to $\sqrt{E}$ via the Sieve of Eratosthenes takes $$O(\sqrt{E} \log \log \sqrt{E})$$ time.
• For each base prime $p$, the marking of multiples in $[S, E]$ takes $O(L/p)$ time.

Thus, the total complexity is approximately

$$O\left(\sqrt{E} \log \log \sqrt{E} + L \sum_{p \leq \sqrt{E}} \frac{1}{p}\right),$$

and since

$$\sum_{p \leq X} \frac{1}{p} \sim \log \log X,$$

the propagation stage runs in roughly $O(L \log \log \sqrt{E})$ time.

8. Discussion

The Lewis Sieve is a natural extension of the Sieve of Eratosthenes. Its novelty lies not in altering the fundamental idea of crossing out multiples, but in focusing the sieve on a targeted interval and propagating factor information as composites are eliminated. This approach has several significant advantages:

• Memory Efficiency:
  By restricting the process to a specific range, the algorithm avoids the prohibitive memory requirements of sieving extremely large intervals.

• Instant Factorization:
  The built-in propagation mechanism immediately provides the smallest prime factor of every composite number, eliminating the need for separate, costly factorization routines.

• Unified Framework:
  The Lewis Sieve unifies prime detection and factorization into a single, elegant process. Rather than viewing these as two distinct steps, the sieve naturally integrates them, yielding richer information about the structure of numbers.

9. Conclusion

We have presented the Lewis Sieve as a significant, natural extension of the classical Sieve of Eratosthenes. By targeting a specific numerical interval and propagating prime factor information during the sieving process, the Lewis Sieve not only identifies primes but also instantaneously factors composite numbers. This dual functionality offers improved efficiency, especially for large ranges, and provides deeper insights into the structure of integers.

The Lewis Sieve is not a mere computational trick; it is a conceptually powerful method that enhances our classical tools. Its potential applications span cryptography, algorithm design, and theoretical number theory. As such, the Lewis Sieve invites further exploration and refinement, promising a new frontier in the efficient analysis of prime numbers and factorization.

---

References

1. Crandall, R., & Pomerance, C. (2005). Prime Numbers: A Computational Perspective. Springer.
2. Hardy, G. H., & Wright, E. M. (2008). An Introduction to the Theory of Numbers. Oxford University Press.
3. [Additional relevant references on sieving methods and factorization.]

---

Acknowledgments: This work builds on the classical methods of number theory and seeks to offer a fresh perspective on an age-old algorithm.