The images in my last post were particular realizations of the famous *Sieve of Eratosthenes*. The basic idea of the sieve is to repeatedly do the following:

- Circle the next number bigger than that is not yet crossed out, call it .
- Cross out every th number after , that is, all the multiples of . These are not prime since they are multiples of .

This is an efficient way to find all the primes up to a given limit. Note that it doesn’t require doing any division or factoring, just adding. Here’s the image of the sieve again:

Some questions for you to ponder:

- Why can we always cross out multiples of each prime using parallel straight lines?
- When will the lines be vertical? When will they be diagonal?
- Is there only one way to cross out multiples of each with straight lines, or could we have chosen different lines?
- Why are the primes on the top row circled, while the rest of the primes are in boxes? What’s the difference?

And just for fun here’s the sieve diagram for , one of my favorites. Click here for a larger version.

Really fun! I now see that I could have taken my comment on the previous post a bit further: all lines go down-left if $n – 1$ is a multiple of $p$, which you already do, except for $2$.

I do wonder how you choose which line to draw: I thought it would be to draw the line through the closest (in distance) next multiple of $p$, but then the line for $p = 17$ in the drawing for $n = 29$ would have gone through $102$ instead of $51$.

My code only looks for slopes which are integers or reciprocals of integers (or vertical).

In more detail, think of the slope of a line as given in the form (dr, dc), that is, the offset in terms of rows and columns from one crossed out number to the next. Then I only consider (1, -n mod p) and (-n^{-1} mod p, 1) and pick whichever one has the smaller absolute value for the non-unit dimension. There are certainly other ways it could be done — I like your idea of picking the closest.

Hello. Can you give the code used to do the plot ?

A lazzy man. 😉

Sure, the code is available here: https://hub.darcs.net/byorgey/mathlesstraveled/browse/2019-10-sieve/Sieve.hs It ended up being a lot more complicated to code than I thought it would be.