## Notes on Lookup – Eratosthenes and Other Sieves

The best known sieve in mathematics is the sieve of Eratosthenes, used for finding a collection of prime numbers.  In an earlier post I described a version of that sieve that finds all divisors (and not just whether a number is prime, though it finds primes also.)

There are many kinds of sieves, and we’ll see one later in this post.  The essential characteristic of a sieve, from where I look, is that it reverses direction.  Instead of doing a tricky determination for a single number, like finding out if a number is prime, we do a larger number of easy, systematic, steps, and collect the results in a look-up table.  The results we get not only tell us if the specific number we cared about is prime, but also gives us all the smaller primes.  If we want multiple primes, this look-up approach is quite efficient.  Look-up tables have many uses beyond sieves, but in this post we’ll stick to sieves.

Let’s introduce a new term, “final odd”, and give it a particular meaning.  We’ll say that the “final odd” of 20 is 5.  How you get the final odd is to cut the number in half repeatedly, until you get to an odd number.  If the number is odd to start with, you don’t need to do anything.   Sounds simple enough, right?  If we start with 48, you would proceed to cut it in half repeatedly, getting 24, 12, 6 and finally 3.  If this thing we’ve called “final odd” is something you needed a lot, it might make sense to make a look-up table. Let’s assume we’ve been working on this look-up table, and have gotten this far:

$\begin{matrix} 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 \\ 1 & 1 & 3 & 1 & 5 & 3 & 7 & \text{?} \end{matrix}$

and we now need to fill in the entry for 8 and onward. We know how to calculate the final odd for 8: the sequence we calculate is 8, 4, 2, and 1. But everything after the first step of calculating 4 is a repetition of what we already did to find the final odd of 4, and the result of all that work is already in the table.  As you can see, this will apply generally: with the look-up table, you never need to do more than one step of cutting the number in half.

$finalOdd[n] = \begin{cases}n & \text{if n is odd} \\ finalOdd[n/2] & \text{if n is even} \end{cases}$

But we can improve on this even more, and make it into a real sieve. For this, we determine upfront the size of the table we are going to fill in.   We’re only showing a table with 8 entries, but you can easily extend this to be longer.

$\begin{matrix} 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 \\ \text{?} & & & & & & & \end{matrix}$

We find the first unmarked entry, and then do a sweep based on that. Here, the first unmarked entry is 1, and we can fill in its entry. We can now repeatedly double the number, and give it the same entry. This gives

$\begin{matrix} 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 \\ 1 & 1 & & 1 & & & & 1 \end{matrix}$

We repeat this process for what’s now the first unmarked entry, the third entry.

$\begin{matrix} 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 \\ 1 & 1 & 3 & 1 & & 3 & & 1 \end{matrix}$

The last two sweeps are easy, and complete the table:

$\begin{matrix} 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 \\ 1 & 1 & 3 & 1 & 5 & 3 & 7 & 1 \end{matrix}$

Note that we ended up with the same lookup table as before, but without having to do any divison.  We didn’t even have to do multiplication, just doubling, which we could do by adding a number to itself.  Also note that in this case, we didn’t particularly make use of the values in the table while building the table.  The only use we had for the values when we were building the table is to find the first entry in the table that hadn’t been filled in yet.  Some sieves depend both on the values previously stored in the table and on finding unmarked entries.  We’ll see an example of that in a post soon.