Saturday, October 02, 2010
JSH: Counting primes as a puzzle
I've realized that giving people something they can intellectually attack on their own is maybe preferable, when feasible, than just tossing a solution at them, so I'm trying to present what I think is a fascinating puzzle counting prime numbers, where maybe you need a little history to get going.
A guy named Legendre is credited with a simple approach to counting primes, as you use a negative, since composites are easy to count. Like up to 100, all the evens are 100/2, or 50 evens, while there are floor(100/3) = 33 numbers divisible by 3. (Say that three times fast!)
Rather than write floor() all the time, another more concise usage is[], so [100/3] = 33, and floor just means to chop off the remainder.
So to count primes you do the opposite! You count composites and subtract that count. So continuing on, 100/5 = 20—didn't need floor() there—and [100/7] = 14. Adding them up: 50 +33+20+14 = 117, which is greater than 100, so what's wrong?
Well, there are 33 numbers divisible by 3, but 3 itself is divisible by 3 so you're counting it, and also, there are evens divisible by 3, like 6, so you double-counted.
Legendre was a smart guy so he fixed both those problems, but he did it in a highly particular way. For 33, he now counted how many were even! So you have [33/] = 16, and subtracting gives 33-16 = 17, and subtract 1 for 3, so you have 16 odd composites divisible by 3, up to 100.
For 5 it's even worse!!! You subtract [20/3] and 20/2, but now you have another problem, as some of the numbers divisible by 3 are even! So you subtracted them twice!!! So Legendre added them back in with [20/6]. Yuck! You subtracted them out, and now you're adding them back! Way inefficient. Don't you feel silly now?
(The actual composites are 25, 35, 55, 65, 85 & 95.)
Can you find a better way at each prime so that for instance at 5, you'd only count 6 composites, without even bothering to count the evens and numbers divisible by 3 that are also divisible by 5?
Once you have your composite count you just subtract from the total, like for 100, there are 74 composites, and 1 itself, so you have 100 - 75 = 25 primes.
Legendre's idea is usually called Legendre's Method and you can get the full thing easily enough on the web. The task here is to improve on the basic idea in a particular way, which is to only count composites at each prime that have NOT already been counted!
Awesomely in this instance that simple requirement can lead to a complete mathematical function.
I can tell you that the answer I got is a multi-dimensional P(x,y) function that uses a partial difference equation.
If you don't know what a partial difference equation is, it's the discrete analog of a partial differential equation. That is, it's just a discrete partial differential equation.
Ok then, puzzle away. If you give up, just Google: my prime counting function
Yup. I'm serious!!! You do need the "my" on the front as well to get mine.
A guy named Legendre is credited with a simple approach to counting primes, as you use a negative, since composites are easy to count. Like up to 100, all the evens are 100/2, or 50 evens, while there are floor(100/3) = 33 numbers divisible by 3. (Say that three times fast!)
Rather than write floor() all the time, another more concise usage is[], so [100/3] = 33, and floor just means to chop off the remainder.
So to count primes you do the opposite! You count composites and subtract that count. So continuing on, 100/5 = 20—didn't need floor() there—and [100/7] = 14. Adding them up: 50 +33+20+14 = 117, which is greater than 100, so what's wrong?
Well, there are 33 numbers divisible by 3, but 3 itself is divisible by 3 so you're counting it, and also, there are evens divisible by 3, like 6, so you double-counted.
Legendre was a smart guy so he fixed both those problems, but he did it in a highly particular way. For 33, he now counted how many were even! So you have [33/] = 16, and subtracting gives 33-16 = 17, and subtract 1 for 3, so you have 16 odd composites divisible by 3, up to 100.
For 5 it's even worse!!! You subtract [20/3] and 20/2, but now you have another problem, as some of the numbers divisible by 3 are even! So you subtracted them twice!!! So Legendre added them back in with [20/6]. Yuck! You subtracted them out, and now you're adding them back! Way inefficient. Don't you feel silly now?
(The actual composites are 25, 35, 55, 65, 85 & 95.)
Can you find a better way at each prime so that for instance at 5, you'd only count 6 composites, without even bothering to count the evens and numbers divisible by 3 that are also divisible by 5?
Once you have your composite count you just subtract from the total, like for 100, there are 74 composites, and 1 itself, so you have 100 - 75 = 25 primes.
Legendre's idea is usually called Legendre's Method and you can get the full thing easily enough on the web. The task here is to improve on the basic idea in a particular way, which is to only count composites at each prime that have NOT already been counted!
Awesomely in this instance that simple requirement can lead to a complete mathematical function.
I can tell you that the answer I got is a multi-dimensional P(x,y) function that uses a partial difference equation.
If you don't know what a partial difference equation is, it's the discrete analog of a partial differential equation. That is, it's just a discrete partial differential equation.
Ok then, puzzle away. If you give up, just Google: my prime counting function
Yup. I'm serious!!! You do need the "my" on the front as well to get mine.
# posted by James Harris @ 10:37 
