Posts

Showing posts from February 9, 2025

Factor any number by sieving every number around it.

The Lewis Sieve: Factorization by Default—A New Perspective on Primes and Composites For anyone who’s ever marveled at the elegance of the Sieve of Eratosthenes, there’s a new twist waiting to be discovered—a twist that not only finds the primes but also reveals the very building blocks of composite numbers. Welcome to the world of the Lewis Sieve . In this post, we’ll explore this innovative approach in depth. We’ll begin with a quick recap of the classical sieve, then introduce the concept behind the Lewis Sieve, and finally show how it unifies prime detection and factorization into one elegant process. Whether you’re a seasoned mathematician or simply passionate about number theory, prepare to see a familiar landscape with entirely new eyes. Revisiting a Classic: The Sieve of Eratosthenes Imagine you have a long chalkboard filled with numbers from 2 up to some large number N. The goal is to pick out the primes—the numbers that can only be divided evenly by 1 and themselves. The Siev...

The Lewis Sieve Thesis

Image
  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 Eratosthene...

The Lewis Sieve 2.0

Image
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 syste...

The Lewis Sieve: First Complicated Attempts... Now Defunct

Image
  The Lewis Sieve: Building Composites and Revealing Primes This method is now defunct.  I'm leaving it out as this is how I figured out how to do it.  Basically, I found the 10's position closest to the number and knew there was a 2 and a 5.  I used those positions to find the 3's and then just spread out in both directions...   while it works, it's hard to code and not easy to understand.  The news Lewis Sieve is just blitzing a list of mods through an area and factoring everything all at once with addition and subtraction.  It's great. Introduction The Lewis Sieve is a method for “sifting” through a range of numbers (our window) to automatically build all the composite numbers from known factors. Any number in the window that we do not “build” must be prime. Today, we will use the window from 500 to 540 and choose 520 as our base number. Why 520? It is composite. Its ending “20” immediately tells us it’s divisible by 2 and 5. These factor...