A Prime Example

The other day something a young friend posted something on his site, The Map Guy. Actually he was posting something about Egypt or Alexandria or something, and mentioned Eratosthenes.

Eratosthenes was an ancient Greek scholar, who did some amazing things, but one thing in particular leaped out in my memory, so I posted a long comment about it. Since then I decided I had some more to say about the matter, so I will take the liberty of reproducing most of that comment, and augmenting it with some more interesting items.

First, I must point out something very funny about our favourite Uncle Gilbert. Most people think that because he was a writer, he only did "literary" things, which if you are from England you must say "lit'ry" things, and then quickly sip some tea. I am not from England. Ahem. But you see our Uncle Gilbert was interested in everything, which means he even talked about...


(shh, come close to the screen and be quiet so I can whisper it!)

... math.

Yes, I mean mathematics, like 2+2, and x over y, and that sort of thing - and of course he immediately related it to much larger and more dramatic topics, like martyrdom, and belief in the Trinity. You are surprised? You should not be. If you won't beliege me, a lowly computer scientist, then believe Mr. Chesterton. Here's what he said:

[People have] the common idea that mathematics is a dull subject, whereas the testimony of all those who have any dealings with it shows that it is one of the most thrilling and tantalising and enchanting subjects in the world. It is abstract, but so, to all appearance, is theology. Men have hurled themselves on the spears of their enemies rather than admit that the second person of the Trinity was not co-eternal with the first. Men have been burned by inches rather than allow that the charge to Peter was to be understood as a charge to him as an individual rather than to him as a representative of the Apostles. Of such questions as these it is perfectly reasonable for anyone to say that, in his opinion, they are preposterous and fanatical questions. And what men have before now done for the abstractions of theology I have little doubt that they would, if necessary, do for the abstractions of mathematics. If human history and human variety teach us anything at all, it is supremely probable that there are men who would be stabbed in battle or burnt at the stake rather than admit that three angles of a triangle could be together greater than two right angles.
[GKC, Lunacy and Letters 58-59, emphasis added]

At first, when you read the particular topic that I posted over on the Map Guy's blogg, you may also think it dull. But I will show you that it is actually kind of fun, and also then I will tell you the thrilling part, which is what I forgot to post in my comment, because I was playing hookey then, and waiting for some dull thing to finish while I was at work. Now I am playing hookey from some other things I ought to be doing, and so I have decided to write about something thrilling, just for a little while. OK. So first, I will give you the comment, which is a nice fun project, with a little more detail, and then go on to the thrilling part.

[The following is from my comment...]

In computer science, we learned about a thing called the "Sieve of Eratosthenes" - it is a way of finding prime numbers. A prime number does not have any divisors except for itself and one. (13 is prime, 12 is not prime, because 2 goes into 12.)

The "Sieve" is easy to do, and even kids can find prime numbers with it - and what's even more fun, you do NOT have to learn how to divide in order to use it!!!

I will tell you how to do it, so you do not have to go looking around. Take a blank page, and write the numbers, starting at one - go as high as you have room to write. To be tidy, you might just write them in ten columns. Let's say you go from one (at the top) to one hundred at the bottom. Then, sit back and enjoy the nice table of integers! (ah.)

OK, now when you are ready to do the sieve: get a new color pencil (it's not really necessary, but helps make for a nice design). Now, make a circle around your TWO, and then go through the table, putting a slash ("/") through every SECOND number - so you slash four, six, eight... etc until you come to the end of the table.

Now, go back to the top, and circle THREE, and slash every THIRD number (yes, you slashed SIX again - well, six is two times three, remember?) and so on down the table.

Now, back to the top, and circle FIVE, and slash every FIFTH number. ...

Now, back to the top, and circle - what? and then slash - what?

Now you see what happens? You keep going until there is nothing left to do.

The numbers with circles are prime. You can check, there ought to be 25 circles between 1 and 100 (check - one is neither circled nor slashed!) All the others are crossed off.

Hurray! No dividing, no sticky fingers, no crying, no crumbs for the dog to lick up. Lots of ancient math fun for the whole family.

[end of excerpt from my comment]

Now for a couple of thrilling parts.

First, there are ways of saving some work for yourself. Once you do this for numbers from 1 to 100, you will quickly see that you do NOT have to write any numbers which end in any of the following digits:

zero
two
four
five
six
eight

because ALL of them will be crossed off (except, of course, for the very first row, which has two and five circled!) So the only columns you really need are those ending in one, three, seven and nine, but then of course you have to remember to skip the missing columns as you count.

Second, there are lots of very interesting things about prime numbers. Primes are one of the very important topics in the branch of mathematics called "number theory". One of the very important workers in this area was a French mathematician by the name of Marin Mersenne. There are a special kind of prime number called "Mersenne primes" which he studied. They are numbers which are prime, and have the form
2^p-1
where p is a prime number. But the really interesting part about Mersenne, who lived from 1588 to 1648 and talked with people like Descartes and Galileo is this - he was a CATHOLIC PRIEST. He also did work in physics and astronomy.

Now for another thrilling thing. When I was doing my doctorate in computer science we had a funny little saying. It's sometimes just as important to find funny things to say as it is to find interesting things to study - and it's even better when the two are connected. This time they were connected. Here is the funny thing, which we made up because we listened to another student talk about how he was studying a new way of working on numbers to see if they are prime. We said:

Spies like big prime numbers.

That's because one of the ways in which one can encrypt messages - that means, turn into a SECRET CODE!!! - is to use a really big prime number. It is complicated, and spies and government agents or even credit card companies like secret things which allow information to be hidden in a code - so of course they like big prime numbers.

But there are other things one can use prime numbers for which are not so secret. One of them is also a lot of fun to talk about. It is called "hashing" and it is a way of storing information in a computer. But that will take some time to explain, so I will have to talk about that another day.