Friday, March 17, 2006

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:

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


At 20 March, 2006 14:25, Anonymous Anonymous said...

Of course, the Mersenne formula does not result in primes for every prime number. But without a computer it was not possible for humans to calculate high enough to determine that.

At 20 March, 2006 15:39, Blogger Dr. Thursday said...

Well - for p=11, we have

so 2^11-1 = 2047
but 2047 = 23*89

Isn't the question still open as to whether that formula will EVENTUALLY give another prime or not: that is, is the set of Mersenne primes finite or not?

At 20 March, 2006 19:33, Blogger Dr. Thursday said...

I apologise for such a terse and perhaps tendentious response to my anonymous comment-writer, but I was away from my references, and found my memory incomplete as to exactly what Fr. Mersenne had claimed. Now I am back with my books, and have found some interesting things:

It indeed appears that Fr. Mersenne was aware that M-sub-p (defined to be 2-to-the-p minus one, where p is prime) gives primes only for certain cases:

"Mersenne asserted (1644) that the only p's for which M-sub-p is prime are:
p = 2, 3, 5, 7, 13, 17, 19, 31, 67, 127, 257." (quote from reference mentioned below; my emphasis. The point is that he "asserted" this - he said it was true, but he did not prove it.)

That is for a prime p less than or equal to 257. However!

In the 1880s it was found that this assertion was wrong, when M-sub-61 was found to be prime.

Also: in 1903, F. N. Cole proved that M-sub-67 is NOT prime. The story of how he presented his paper on this was very exciting, and I will post it another day (it is really quite good, and well worth the wait, it is almost Chestertonian, as I mentioned earlier!) Sometime later it was also shown that M-sub-257 is also NOT prime... and eventually Fr. Mersenne was shown to have made five mistakes: he included 67 and 257, and excluded 61, 89, and 107 - but it took 304 years to get the last results. (Good thing it wasn't a homework assignment!)

My information is taken from pages 503-5, volume one, of the very interesting The World of Mathematics.

Again I apologise for my somewhat misleading statement of what Fr. Mersenne had done, and also for sharpness of my previous posting. If there are further questions about this I will do what I can. After all, Number Theory is a wonderful field and can be fun as well as practical!

At 21 March, 2006 16:03, Anonymous Anonymous said...

Sorry my previous post wasn't entirely accurate. I was working from memory on the Mersenne primes, being clear only on the points that 1) Mersenne didn't exactly give a formula for finding primes, only a way to search where they might be, and 2) Mersenne wasn't able to actually prove his assertions up to 257. I did manage however, to prove another mathematical principle -- one should have the data absolutely clear before publishing.

At 30 March, 2006 13:16, Anonymous Anonymous said...

Well my head is spinning, but I love Chesterton so I've linked you to my site, thanks for the math brain freeze!


Post a Comment

<< Home