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 10^{100}“:

By the famous prime number theorem – which we’ll outline in a moment – there are 10^{97} prime numbers smaller than 10^{100}. This number may sound manageable, but 10^{97} 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 10^{97} 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 10^{100}. 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.

### Like this:

Like Loading...

*Related*

Tags: algorithms, books, Borges, median, prime numbers

This entry was posted on December 21, 2008 at 8:38 am and is filed under math. You can follow any responses to this entry through the RSS 2.0 feed.
You can leave a response, or trackback from your own site.

## Leave a Reply