Project Euler #7 – Prime Mysteries of the Mind

By listing the first six prime numbers: 2, 3, 5, 7, 11, and 13, we can see that the 6th prime is 13.

What is the 10,001st prime number?

“Mathematicians have tried in vain to this day to discover some order in the sequence of prime numbers, and we have reason to believe that it is a mystery into which the mind will never penetrate.”

Leonard Euler, in G. Simmons, Calculus Gems, McGraw-Hill, New York, 1992

According to Wolfram Alpha, the 10,001st prime number is 104,743. Now (as always) we must ask,“what’s the point?”

To be fair, it’s all well and good that we have these fancy computers that we can just ask for the answer, but let’s dig deeper and get more background on what’s so hot about prime numbers. As the quote above from noted brainiac Leonard Euler indicates, prime numbers are a mystery wrapped in an enigma covered in secret sauce.

We’ve talked about prime numbers before and how they’re used to secure the Internet. But the ancient Greeks studied primes and they didn’t even have smartphones (at least, I don’t think so….nope, they didn’t). One thing to note about primes is that they are devilishly hard to predict. I mean, if I gave you a sequence of even numbers and asked you to determine what the next number in series would be, that would be a no-brainer. However, if I gave you a sequence of prime numbers, that would involve a lot more work. Factoring numbers (our main test for primality) is one of those problems that are known as NP (Non-Polynomial). In plain talk, there are no shortcuts to the answer. But what if we asked the question a different way?

That’s what a man named Eratosthenes did. Prime numbers were as weirdly fascinating to the ancient Greeks as they are to us and Eratosthenes was a noted mathematician of the day. Just to give you a sense of the man, he was also a music theorist, poet, astronomer, invented geography and in his spare time was the chief librarian of the greatest collection of ancient wisdom of his times, the Library at Alexandria, not to mention being the first person to calculate the circumference of the ENTIRE FREAKING PLANET.

Frankly, it’s all I can do to get through my daily Twitter feed before I feel the need for a lie down. But I digress.

Anyway, while his fellow mathematicians were mapping out primes the hard way, Eratosthenes asked the question, “How do we find the prime numbers in a given sequence of numbers?”. One day he had a revelation. He already knew how to find if a number was prime the hard way. But, he reasoned, any multiple of a prime is by definition not prime.
Here’s how it worked. Consider the first ten digits (1 is crossed off since it is neither prime or non-prime).

X 2 3 4 5 6 7 8 9 10

Our first prime is 2, so we cross off all multiples of 2.

X 2 3 X 5 X 7 X 9 X

3 is also a prime, so we cross off all multiples of 3.

X 2 3 X 5 7 X X X

We’ve finished the sequence and all we have left are the primes 2, 3, 5 and 7. We can do this for any sequence of numbers, filtering out the primes like grains of sand through a sieve. Hence the name for this technique, which has survived to this day – the Sieve of Eratosthenes. As a side benefit, this reduces the effort of finding primes to simple arithmetic, making it perfect for handing off to a machine. (In fact, one of the first programming problems they give students is to code up their version of the Sieve.)

One more thought about primes and this one’s a bit more relevant to the Project Euler problem above. If we map out the Nth primes for N in {1, 11, 101, 1001 and 10,001}, we get:

N

Gap

Nth Prime

Gap

1

n/a

2

n/a

11

10

31

29

101

90

547

516

1001

900

7,927

6,926

10001

9,000

104,743

96,816

If we look at the gaps we can see that, as the sequence numbers get bigger, the gaps between primes get bigger. It’s even more obvious when we graph out the first 100 primes:

This actually makes intuitive sense. Larger numbers have more possible factors so are less likely to be prime. (Give that a moment to sink in.) This is an illustration of what is known as the prime number theorem. Here’s the idea:

  • Pick a large positive integer. Call it N.

  • Pick a random integer between 1 and N. Call it R.

The probability of R being random are roughly 1/ln(N). (one divided by the natural logarithm of N). So the bigger N is, the smaller the odds of R being prime. In other words, as we see in our graph above, the gaps between prime numbers get bigger as our numbers get bigger. Like people, prime numbers are easier to understand when we look at them in groups.

“Some order begins to emerge from this chaos when the primes are considered not in their individuality but in the aggregate; one considers the social statistics of the primes and not the eccentricities of the individuals.”

P.J. Davis and R. Hersh, The Mathematical Experience, Chapter 5

 

Advertisements

Leave a Reply

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

WordPress.com Logo

You are commenting using your WordPress.com 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