Thursday, September 30, 2010
JSH: Puzzling counting prime numbers
Rather than give directly a mathematical find I've found it interesting to see if others can figure out something on their own, thus giving them an intellectual challenge. In this thread the challenge is to find a certain way to count prime numbers.
There are LOTS of resources available with a lot of mathematical literature on the subject, and all of the established literature is available for this challenge. Of course I also have the answer, which is not in established literature, for those who give up.
Challenge:
Find a prime counting function P that counts primes by first counting composites and subtracting that count and 1 from the total count to get primes, which only counts composites at each prime that have not already been counted.
That is, Legendre's method rather inefficiently counts ALL composites at each prime that have that prime as a factor, which is dumb!!! It's so dumb you end up just subtracting those back out which is a naive way to count, don't you think? Why, for instance, if you're counting composites divisible by 3, should you also count evens? Of if you're counting composites with 5 as a factor, count the ones with 3 and 2, and then just subtract them back out? It's WACKY!
Can you find a more efficient prime counting method than Legendre's which more smartly counts ONLY those composites at each prime that have not ALREADY been counted?
If you think the problem is too easy, great! Give the function in reply.
If you have no clue, here's a clue.
Hint: The requirements force a P(x,y) function, so you end up with a multi-dimensional prime counting function instead of a pi(x), single variable one.
Can anyone solve the puzzle on their own? If you get completely lost, of course, the answer is on my math blog. Given lots of places as I've explained, and explained and explained.
But if I can figure it out, can you?
There are LOTS of resources available with a lot of mathematical literature on the subject, and all of the established literature is available for this challenge. Of course I also have the answer, which is not in established literature, for those who give up.
Challenge:
Find a prime counting function P that counts primes by first counting composites and subtracting that count and 1 from the total count to get primes, which only counts composites at each prime that have not already been counted.
That is, Legendre's method rather inefficiently counts ALL composites at each prime that have that prime as a factor, which is dumb!!! It's so dumb you end up just subtracting those back out which is a naive way to count, don't you think? Why, for instance, if you're counting composites divisible by 3, should you also count evens? Of if you're counting composites with 5 as a factor, count the ones with 3 and 2, and then just subtract them back out? It's WACKY!
Can you find a more efficient prime counting method than Legendre's which more smartly counts ONLY those composites at each prime that have not ALREADY been counted?
If you think the problem is too easy, great! Give the function in reply.
If you have no clue, here's a clue.
Hint: The requirements force a P(x,y) function, so you end up with a multi-dimensional prime counting function instead of a pi(x), single variable one.
Can anyone solve the puzzle on their own? If you get completely lost, of course, the answer is on my math blog. Given lots of places as I've explained, and explained and explained.
But if I can figure it out, can you?
# posted by James Harris @ 10:08 
