#math trivia for #February18: #49 is the first composite that Eratosthenes sieves with a prime other than 2, 3 or 5. What’s the next one?
— Burt Kaliski Jr. (@modulomathy) February 18, 2012
The Sieve of Eratosthenes is an ancient algorithm for separating prime numbers from composites. Suppose we want to find all the primes between 1 and 20. The sieve starts with the full sequence of numbers
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 .
In the following, we’ll mark primes in italics and composites in bold. By convention, 1 is neither prime nor composite (it’s a unit), but for convenience, we’ll mark it as composite:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 .
The sieve follows a simple pattern:
- Let p be the smallest number that’s not yet marked.
- Mark p in italics; it must be a prime.
- Mark each unmarked multiple of p in bold; it must be composite.
- Repeat.
Let’s try this for a few primes. After the 1 is marked, the smallest unmarked number is 2. We’ll mark 2 prime then mark the remaining even numbers composite:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 .
The smallest unmarked number is now 3. We’ll mark 3 prime then mark the remaining multiples of 3 composite:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 .
The next prime is 5, and the other unmarked numbers in the sequence will also turn out to be prime.
The algorithm is called a “sieve” because it filters out composites, leaving only primes. Any composite by definition has at least one prime divisor smaller then itself. The simple steps above, repeated through the prime p, will have filtered out all the composites divisible by primes between 2 and p. The next unmarked number must therefore be a prime. And so the process continues.
Any composite that’s not sieved out by 2, 3, and 5 must be divisible by a prime p ≥ 7. The smallest composite with this property is 49. The next composite that’s not divisible by at least one of the first three primes — and the answer to the question — is the product of the next two primes: 77 = 7*11.
The next one is 91 = 7*13. So the impact of 2, 3 and 5 is quite extensive: With only two exceptions, every number up to 90 is either divisible by one of the first three primes, or a prime itself.
modulomathy.com 