My first attempt at creating my own sieve was far more convoluted than I ever imagined. Initially, I designed the sieve to first locate the nearest number ending in 0, immediately deducing that 2 and 5 were factors and propagating them outward. Then I employed a trick that always revealed a factor of 3—and one of 7, 11, 13, 17, or 19—to further mark the numbers. After a while, I realized I was overcomplicating things. I streamlined the process, removing unnecessary steps, and now it’s simple and effective.

Introducing: The Lewis Sieve a new method of factorization that works on an entire list of numbers!

The Lewis Sieve

By Michael Lewis

Abstract

In this paper, we introduce and explore the Lewis Sieve, a novel arithmetic approach to factorization that eschews traditional division-heavy methods in favor of simple operations such as addition, subtraction, and modulo. By leveraging a carefully chosen window—typically defined by the square root of the target number—the Lewis Sieve systematically “sieves out” composite numbers, thereby revealing the primes through their natural periodicity. We detail the mathematical foundations of the method, provide a comprehensive step-by-step explanation, and discuss its efficiency and practical implications compared to classical methods such as the Sieve of Eratosthenes. Ultimately, the Lewis Sieve demonstrates both an elegant conceptual framework and promising performance in factorization tasks.

1. Introduction

Factorization has always been central to number theory, with its applications ranging from cryptography to computational mathematics. The classical Sieve of Eratosthenes is widely recognized for its simplicity and efficiency in generating primes up to a given limit. However, many modern applications demand even more efficient and conceptually transparent methods.

The Lewis Sieve introduces a paradigm shift by replacing heavy division routines with elementary arithmetic operations—namely, addition, subtraction, and modulo. This method takes advantage of the inherent periodic structure of multiples in the integers. Every composite number less than or equal to a target $n$ must have a prime factor no greater than $\sqrt{n}$ . By constructing a “window” based on this observation and precomputing primes up to the window’s limit, the Lewis Sieve efficiently marks composites, leaving unmarked the primes that are essential for various applications.

This paper provides a detailed, multi-faceted examination of the Lewis Sieve. We begin with the theoretical motivation behind the method, proceed with a step-by-step explanation of its implementation, and then analyze its efficiency relative to classical sieving techniques.

2. Theoretical Background and Motivation

2.1 Fundamental Observations

At the heart of the Lewis Sieve is a simple yet powerful observation: any composite number $m \leq n$ has at least one prime factor $p$ with $p \leq \sqrt{m}$ . This insight suggests that, to factor all numbers up to $n$ , it is sufficient to focus on primes up to $\sqrt{n}$ .

2.2 Defining the Window

The "window" in the Lewis Sieve is a segment of the number line, chosen to ensure that all small primes necessary for the factorization of composites up to $n$ are included. While one may opt for a window of size $2\sqrt{n}$ to add a margin of safety, this paper considers a window of size $\sqrt{n}$ for clarity and efficiency. Within this window, every composite number will be “hit” by at least one multiple of a prime $p$ that divides it, guaranteeing that the composites can be systematically identified.

2.3 Precomputing Primes

Before the sieving process begins, the method requires the precomputation of all primes up to $\sqrt{n}$ . By the Prime Number Theorem, the number of primes up to $x$ is approximately $\frac{x}{\ln x}$ . Thus, for $x = \sqrt{n}$ , the expected number of primes is roughly $\frac{2\sqrt{n}}{\ln n}$ , a relatively modest set that forms the backbone of the Lewis Sieve.

3. The Lewis Sieve Method

3.1 Overview

The Lewis Sieve avoids the conventional reliance on division by using addition, subtraction, and modulo operations to “sieve out” composite numbers. For each prime $p$ in our precomputed list, the method iterates through the window by stepping in increments of $p$ . This process exploits the regular periodicity of multiples: every $p$ th number is a multiple of $p$ .

3.2 Step-by-Step Procedure

3.2.1 Define the Window

Objective: Ensure that every composite number $m \leq n$ has at least one factor $p$ within the window.
Implementation: Set the window size to $\sqrt{n}$ . This means the sieve will consider numbers up to and including $\sqrt{n}$ , ensuring that every composite is examined through its smallest possible prime factor.

3.2.2 Precompute the Primes

Objective: Generate a complete list of primes up to $\sqrt{n}$ .
Implementation: Use a conventional method—such as the Sieve of Eratosthenes—to obtain all primes $p$ with $p \leq \sqrt{n}$ . Store these primes for rapid access during the sieving process.

3.2.3 Arithmetic Sieving of Composites

Objective: Mark all composites in the window using arithmetic operations rather than division.
Procedure:
- For each prime $p$ in the precomputed list, start at $p$ and repeatedly add $p$ to obtain the sequence: $p,\, 2p,\, 3p,\, 4p,\, \dots$
- At each step, use the modulo operation to confirm: $n \mod p = 0.$ This check confirms that the number is indeed a multiple of $p$ .
- Mark these numbers as composite in an appropriately sized boolean array or bit vector.
Rationale: Since each addition is a low-cost operation and modulo checks are extremely fast, this process efficiently “sieves out” the composites.

3.2.4 Propagation and Finalization

Objective: Propagate the composite markers throughout the window and extract the list of primes.
Procedure:
- As each prime $p$ propagates its multiples, update the composite marking.
- The number of steps required per prime $p$ is approximately $\frac{\sqrt{n}}{p}$ . The overall number of operations is then roughly: $\sqrt{n} \sum_{p \leq \sqrt{n}} \frac{1}{p}.$
- Given the asymptotic behavior of the sum $\sum_{p \leq x} \frac{1}{p} \approx \log\log x + M$ (with $M$ a constant), the total work is $O\left(\sqrt{n}\,\log\log n\right)$ .
Outcome: After propagation, the numbers that remain unmarked are primes. A final scan of the marking structure reveals these prime numbers, successfully completing the sieve.

4. Analysis and Practical Considerations

4.1 Efficiency Comparison

Arithmetic Operations:
The method requires roughly $O\left(\sqrt{n}\,\log\log n\right)$ operations, all of which are simple and execute rapidly on modern hardware.
Memory Footprint:
Only a boolean array of size $O(\sqrt{n})$ is needed, making the method memory efficient compared to full-range sieving approaches.
Constant Factors:
While traditional sieves may have similar asymptotic complexity, the Lewis Sieve benefits from the extremely low cost of addition and modulo operations versus division, yielding superior performance in practical scenarios.

4.2 Advantages and Limitations

Advantages:
- Simplicity: The method uses only elementary arithmetic operations, making it conceptually straightforward and easy to implement.
- Speed: The elimination of expensive division operations and the exploitation of arithmetic regularity can lead to performance gains.
- Clarity: By directly observing the periodicity of multiples, the method offers clear insights into the structure of composite numbers.
Limitations:
- Window Dependency: The efficiency of the method depends on an optimal choice of the window size. An improperly sized window may either miss necessary primes or introduce unnecessary overhead.
- Scalability: While effective for numbers within a certain range, further work is required to extend the method to extremely large values without significant modifications.

5. Conclusion

The Lewis Sieve represents a refreshing and innovative approach to factorization by harnessing the inherent rhythm of arithmetic operations. By defining a window of size $\sqrt{n}$ and precomputing the primes up to that limit, the method ensures that every composite number is “hit” by its smallest possible prime factor. Through a process of arithmetic sieving—stepping through the number line using addition and confirming with modulo checks—composites are efficiently marked, and primes are left unscathed.

This approach not only matches the theoretical efficiency of classical methods but also offers practical advantages in terms of speed and clarity. The simplicity of addition, subtraction, and modulo operations allows for a low-overhead implementation that can compete with, and in some cases surpass, traditional sieving methods.

Ultimately, the Lewis Sieve challenges us to rethink the way we approach factorization. By stripping the process down to its fundamental arithmetic elements, it exposes the elegant structure underlying the number system—a structure that, when properly harnessed, can reveal the secrets of primes in a manner both efficient and beautiful.

References and further readings may be added here to explore the topics of modular arithmetic, classical sieves, and modern factorization techniques in greater depth.

https://github.com/mikelewis1971/The-Lewis-Sieve

Below is the Python script that implements the Lewis Sieve. Think of it as the “practical appendix” to the paper, where we bring the theory into code. This script embodies the ideas discussed in the paper, from setting up a window and precomputing primes to marking composites via arithmetic operations and recursively propagating factors. Let’s break it down.

Overview

The script defines a class LewisSieveFullAnalysis which implements the Lewis Sieve. The algorithm works in several stages:

Initialization and Window Setup:
The sieve centers around a “base number” and creates a window around it—specifically, from (base - window_size) to (base + window_size), where the window size is chosen as twice the square root of the base number. This ensures that all small primes needed for factorization are present.
Precomputation of Primes:
Using sympy.primerange, the script generates all primes up to the window size. These primes form the building blocks that will later “sieve out” the composites.
Peeling Off Composites:
The method peel_off_primes iterates over every number in the window. For each number, it tests divisibility against the precomputed primes. When a number is divisible by any of these primes, those factors are recorded in the propagation_map.
Full Reduction:
In multiply_and_reduce, every number in the propagation map is “reduced” by repeatedly dividing it by its factors (as per the method fully_reduce). This mirrors our idea of “peeling off” layers of composites.
Identifying Missing Numbers:
The find_missing_numbers method identifies numbers in the window that were never marked during the initial trial division—these could be primes or composites that were not fully reached by the initial pass.
Recursive Propagation:
The method recursive_propagation takes any missing numbers and performs further trial division. If additional factors are found, they are propagated through the window. This recursive step ensures that the process continues until no new factors can be discovered.
Output:
Finally, run_sieve orchestrates the entire process and outputs the results in two pandas DataFrames: one detailing each number with its factors and reduced value, and one listing any “missing” numbers. It also provides a count of missing numbers that are not prime.

Detailed Walkthrough

Initialization (__init__):
- The constructor receives a base number and calculates a window size as int(math.sqrt(number)) * 2.
- It defines the lower and upper bounds of the window and initializes several data structures:
  - propagation_map: A dictionary to store numbers along with their factors.
  - reduced_map: A dictionary for storing the fully reduced form of each number.
  - missing_numbers: A list for numbers that initially get no factors.
  - processed_numbers: A set to keep track of numbers already processed in recursion.
- Finally, it precomputes a list of small primes using primerange.
Reduction (fully_reduce):
This function takes a number and a factor and repeatedly divides the number by that factor until it can no longer be divided evenly. It simulates “peeling off” the factor completely, analogous to stripping layers from a composite number.
Propagation (propagate_factors):
When factors are discovered for a number, this method “propagates” each factor to all multiples in the window. It updates propagation_map so that each multiple is tagged with the factor. This reflects the arithmetic stepping where, if a number is divisible by a prime $p$ , then every $p$ th number should also be marked.
Initial Factorization (peel_off_primes):
This method iterates over every number in the window. For each number, it tests divisibility by each prime in the precomputed list. If any factors are found, they are stored in the propagation_map. This is our first pass, using basic trial division with the small primes.
Multiplication and Reduction (multiply_and_reduce):
Once factors are recorded, this function processes each number by using the fully_reduce method with each of its factors. The result, stored in reduced_map, represents the number after all possible factors (from the propagation map) have been removed.
Finding Missing Numbers (find_missing_numbers):
This function determines which numbers in the window were never reached by any factor propagation (i.e., numbers that didn’t appear as keys in propagation_map). These “missing” numbers might be prime or composites that require further processing.
Recursive Propagation (recursive_propagation):
For each missing number, if it hasn’t been processed before, the function attempts to factor it using the precomputed primes. If new factors are found, they are propagated into the window, and the process repeats until no new factors are discovered. This recursive approach ensures that even stubborn composites are fully factored.
Final Output (run_sieve):
- The script runs all the above steps in sequence.
- It formats the results into a pandas DataFrame showing each number from the propagation map, its discovered factors, and its fully reduced number.
- It also creates a DataFrame for any missing numbers and prints out a count of those missing numbers that are not prime.
- This final output provides both a clear visualization of the factorization process and a summary of any numbers that might need further attention.

Conclusion

This script is the implementation of the Lewis Sieve described in the paper. It takes a theoretically motivated idea—using a window defined by the square root of the target number and relying on simple arithmetic to propagate factors—and turns it into a practical tool for factorization. By precomputing primes, marking composites through arithmetic progressions, and recursively refining the factorization, the Lewis Sieve efficiently reveals the structure of numbers.

The code demonstrates how theoretical insights from number theory can be implemented in an algorithm that is both elegant and efficient. As part of the paper, this script not only serves as a proof-of-concept but also as a practical tool that you can run, test, and modify to further explore the fascinating interplay between arithmetic operations and prime factorization.

Happy coding and happy factoring!

import pandas as pd
import math
from sympy import primerange,isprime  # Removed isprime and concurrent.futures

# Expand pandas output to see all rows/columns
pd.set_option('display.max_rows', None)
pd.set_option('display.max_columns', None)


class LewisSieveFullAnalysis:
    def __init__(self, number):
        """Initialize with the base number and set up the sieve with recursive propagation."""
        self.base_number = number  # Starting point for factorization
        self.window_size = int(math.sqrt(number)) * 2  # Window size
        self.lower_bound = self.base_number - self.window_size
        self.upper_bound = self.base_number + self.window_size
        self.propagation_map = {}  # Stores numbers and their discovered factors
        self.reduced_map = {}  # Stores numbers after full reduction
        self.missing_numbers = []  # Numbers that never got any factors
        self.processed_numbers = set()  # Track numbers already processed in recursion
        # Precompute a list of small primes for trial division
        self.primes_to_test = list(primerange(2, self.window_size))

    def fully_reduce(self, num, factor):
        """Repeatedly divide num by factor until it no longer divides evenly."""
        while num % factor == 0 and num != factor:
            num //= factor
        return num

    def propagate_factors(self, number, factors):
        """
        For each factor, propagate it to every multiple in the window.
        This 'labels' numbers with the factors discovered.
        """
        for factor in factors:
            for num in range(number, self.upper_bound + 1, factor):
                if num not in self.propagation_map:
                    self.propagation_map[num] = set()
                self.propagation_map[num].add(str(factor))

    def peel_off_primes(self):
        """Single-threaded trial division over the entire window."""
        for num in range(self.lower_bound, self.upper_bound + 1):
            found_factors = set()
            for prime in self.primes_to_test:
                if num % prime == 0:
                    found_factors.add(prime)
            if found_factors:
                self.propagation_map[num] = found_factors

    def multiply_and_reduce(self):
        """Using the discovered factors, fully reduce each number in the propagation map."""
        for num, factors in self.propagation_map.items():
            reduced_num = num
            for factor in sorted(map(int, factors)):
                reduced_num = self.fully_reduce(reduced_num, factor)
            self.reduced_map[num] = reduced_num

    def find_missing_numbers(self):
        """Identify numbers in the window that never appeared in the propagation map."""
        found_numbers = set(self.propagation_map.keys())
        all_numbers_in_window = set(range(self.lower_bound, self.upper_bound + 1))
        self.missing_numbers = sorted(all_numbers_in_window - found_numbers)

    def recursive_propagation(self):
        """
        For each missing number, try to factor it using trial division.
        If factors are found, propagate them into the window.
        This recursive loop continues until no new factors are discovered.
        """
        new_factors = True
        while new_factors:
            new_factors = False
            # Update the list of missing numbers
            self.find_missing_numbers()
            for num in self.missing_numbers.copy():
                if num not in self.processed_numbers:
                    self.processed_numbers.add(num)
                    factors = []
                    n = num
                    for prime in self.primes_to_test:
                        if n % prime == 0:
                            while n % prime == 0:
                                factors.append(prime)
                                n //= prime
                        if n == 1:
                            break
                    if factors:
                        self.propagate_factors(num, factors)
                        new_factors = True

    def run_sieve(self):
        """Run the full sieve, then output the derived data and missing numbers."""
        # Step 1: Single-threaded factorization of the window
        self.peel_off_primes()

        # Step 2: Use the discovered factors to reduce numbers
        self.multiply_and_reduce()

        # Step 3: Identify numbers that were not hit initially
        self.find_missing_numbers()

        # Step 4: Recursively try to factor missing numbers and propagate any factors found
        self.recursive_propagation()

        # Format the derived propagation data
        formatted_data = []
        for idx, (num, factors) in enumerate(sorted(self.propagation_map.items())):
            factor_list = ", ".join(sorted(map(str, factors))) if factors else "N/A"
            reduced_value = self.reduced_map.get(num, num)
            formatted_data.append({
                "Index": idx + 1,
                "Original Number": num,
                "Factors": factor_list,
                "Reduced Number": reduced_value
            })

        # Build DataFrames for the output
        df_formatted = pd.DataFrame(formatted_data, columns=["Index", "Original Number", "Factors", "Reduced Number"])
        df_missing = pd.DataFrame({"Missing Numbers": self.missing_numbers})

        print("Formatted Lewis Sieve Output:")
        print(df_formatted)
        print("\nNumbers Not in Derived List (Missing Numbers):")
        print(self.missing_numbers)
        count = 0
        for x in self.missing_numbers:
            if isprime(x):
                count+=0
            else:
                count+=1
        print(f"Missing Number that are not Prime: {count}")


# Run the sieve on 3252 (you can change this value as needed)
sieve = LewisSieveFullAnalysis(20123)
sieve.run_sieve()

Search This Blog

Quantum Consepts - that can be wrong-but Usually ain't

The Lewis Sieve 2.0