A few words about PWW #27

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 1 that is not yet crossed out, call it p.
  • Cross out every pth number after p, that is, all the multiples of p. These are not prime since they are multiples of p.

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 10 \times 10 sieve again:

Some questions for you to ponder:

  • Why can we always cross out multiples of each prime p 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 p 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 n = 29, one of my favorites. Click here for a larger version.

About Brent

Associate Professor of Computer Science at Hendrix College. Functional programmer, mathematician, teacher, pianist, follower of Jesus.
This entry was posted in pattern, pictures, posts without words, primes and tagged , , . Bookmark the permalink.

4 Responses to A few words about PWW #27

  1. 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$.

    • Brent says:

      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.

  2. Christophe BAL says:

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

    A lazzy man. 😉

Comments are closed.