Median of a Very Long List of Primes

This morning I read a short review of a new popular math book, the conceit of which will be obvious from the title:
The Unimaginable Mathematics of Borges’ Library of Babel

Using Amazon’s search feature, I got as far as reading the following passage, in which the author attempts to describe why it would be difficult to evaluate the expression “the median of the prime numbers less than 10100“:

By the famous prime number theorem – which we’ll outline in a moment – there are 1097 prime numbers smaller than 10100. This number may sound manageable, but 1097 is trillions of times larger than the number of subatomic particles in our universe. There simply isn’t any imaginable way to list and keep track of 1097 numbers, which precludes the possibility of finding the median

However, you don’t need to keep track of all the numbers to find their median. A simple algorithm will do the job.
Just look from prime numbers from both ends of the spectrum. Find one small prime number, then one big prime number, then one small prime number, etc, until the two paths either meet or cross. Then you’ve got the median. At any point, you only have to remember what number you’re building up from at the low end of the range, and what number you’re counting down from at the high end. Not only do you not need to remember the entire list of prime numbers, you don’t even need to remember how many prime numbers you’ve found.

To illustrate the method, find the median of all prime numbers less than 100:
Small Primes: 2 3 5 7 11 13 17 19 23 29 31 37 41
Big Primes: 97 89 83 79 73 71 67 61 59 53 47 41

Now that both lists have reached 41, you know that is the median. Even as I write this I don’t know how many primes there are between 1 and 100. And, although all the primes are listed on the lines I just wrote out, I don’t remember them off the top of my head.

It wouldn’t be fast to find the median prime when the top of the range becomes 10100. It gets increasingly harder to evaluate whether a number is prime when you start tacking on digits, and, as the author pointed out, there are a lot to go through. But storage space is no problem.


Tags: , , , ,

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: