Friday, October 08, 2010

Remembering Prime Numbers Fast; Dividing with Less Guessing

Edit: This is a shorthand form of the Sieve of Eratosthenes.

Way back in high school, I thought I was a genius. In my naivety, I thought I could solve the great prime number problem--that is, to find a pattern in prime numbers that predicts them without having to check via factoring.

At the time, I knew very little about proofs or logic or induction. I did, however, know how to write programs in QBasic, so I wrote a factoring program. Then I wrote a program that generated lists of prime numbers, and I let one run for two days, giving me a data set containing all prime numbers through the 2 millions.

I tried different approaches to analysis. I arranged and displayed the numbers in different ways. I never found the pattern. If I had, I'd be a millionaire right now, and that would be pretty cool.

I'm not a millionaire though; I'm studying for the GRE--the general GRE. Now, you may scoff at that, and perhaps you're worthy of that great privilege. I'm not. I scoffed at the SATs, and that bit me in the ass. I doubt I did more than an hour of studying for them. I did fine--it got me into college--but I'm sure I could have nailed them with some more practice.

Lesson learned, here I am. After four years of Physics, I'm drilling basic algebra. Why? When you're doing a Physics problem, you have hours to do algebra. You can space out and happily meander through mathematical meadows. You re-derive all the theorems of algebra that you'd forgotten because you don't want to memorize a few formulae. When you're doing a GRE problem, you have two minutes flat to determine unwavering truth. The mindset's different; it takes a little practice and memorization to adapt.

Every practice test I've taken has turned up at least one problem where prime numbers are involved. The first few are easy to recall: 2, 3, 5, 7, 11, 13, 17, and 19. Those appear so frequently that it's hard to forget them. But what about the others? What about numbers that are far larger--say, 153--but not too big to be on the GRE?

I remembered one of the optimistic results I had during my prime number function hunting days. I'll first write it in the form I remember it in, then explain that:
The left is the ten's column. The right contains entries from the ones columns that are, in fact, prime when combined with that tens column. So, the rows above say,
11, 13, 17, 19
23, 29
31, 37

If we keep this going through one hundred, it looks something like this,
This looks discouraging--there's all those holes in the pattern!

Let's take a look at the exceptions:
49 = 7 x 7
77 = 7 x 11
91 = 7 x 13

In fact, what I'd developed was a sieve. It's an incomplete one, but a sieve nevertheless. It seems to eliminate all numbers that have factors of 2, 3, or 5; these three factors make the sieve loop every 30 integers. I haven't proven it rigorously, though I can make a few hand-wavy arguments.

By inspection, it obviously eliminates anything with a factor of two or five. Anything that's a multiple of two is even; its first digit is an even number, and there are none of those caught by the sieve. There's a similar argument for five; any multiple of five's first digit is 0 or 5, and none of those are present.

As far as threes go, in the first row of the sieve, all multiples of three are even or divisible by five--12, 15, 18--leaving all four possible first digits. In the second row, the multiples of three are 21, 24, and 27, so only 3 and 9 remain to be prime. On the third row, multiples of three actually begin with three--33, 36, 39--so 3 and 9 are dropped, leaving 1 and 7.

How is this useful if there are exceptions? There's not that many of them--only three less than 100, only one, 91, that made me double-take. Looking at whether or not a sieve catches a particular number gives you a lot of information and can take a lot of the guess work out of division.

In fact, it comes in really handy when factoring. Factoring by random guesswork is tedious, but this can cut your guess time down dramatically.

Take, for example, 153. The sieve doesn't cut it out, and it's not divisible two or five, so it's obviously divisible three--the only other factor the sieve eliminates. 150/3 = 50, and 3/3 = 1, so its factors are 3 and 51. 51 is not blocked out by the sieve and not a multiple of 2 or 5, so it too is divisible by three. 51 = 30 + 21, so 51/3 = 30/3 + 21/3 = 17. So the factors of 153 are 3, 3, and 17.

Being able to factor speeds up any type of division. It eliminates a lot of the guess work, saving time. Saved time on the GRE effectively means a higher score because it leaves you more time to think.

That, and I really hate doing guess work. When I was in fifth grade, I remember being taught to "guess and check," and I thought it was the biggest waste of time. I still think that, because if I wanted to guess and check, I'd make a computer do it for me. Division, though, remains a guess and check problem, and on a test where I can't use a calculator, I'll take all the help I can get.


Anonymous LeeNguyen said...


Friday, October 08, 2010 10:28:00 PM  

Post a Comment

<< Home