Wednesday, May 09, 2007

Just how many prime ribs or prime numbers are there.

Just how many numbers are prime? Something on inspired me to got to the Prime pages to figure it out. Experimentalist that I am, I just went and grabbed a list of the first thousand primes and then some points along the way to the first 15 million to see what I could see. I divided the number of primes by the prime number I had reached to get the fraction of numbers below that number that are prime. Plotting this yields a suspiciously smooth decreasing curve if you use a log x-axis, which is necessary because we have numbers from 2 to 275 million.

Since we don't have a straight line yet the next plot is of the inverse of the fraction of prime numbers. Bingo! We have a straight line. A quick check of wikipedia (Distribution of Prime Numbers. Know your search terms!) reveals that I have just empirically rediscovered the Prime Number Theorem. Typical engineer.

That theorem defines pi(n) as the number of numbers that are prime below n. The fraction of numbers that are prime that I was trying to figure out is pi(n)/n.

pi(n) ~ n/ln (n)

pi(n)/n ~ 1/ ln(n)

My plot is the inverse of the fraction on a log which gives me my straight line ln(n). The chance of a randomly selected number being prime is 1/ ln(n).

No comments: