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

 

Project Euler #6 – Hip to be Square

The sum of the squares of the first ten natural numbers is,

12 + 22 + … + 102 = 385

The square of the sum of the first ten natural numbers is,

(1 + 2 + … + 10)2 = 552 = 3025

Hence the difference between the sum of the squares of the first ten natural numbers and the square of the sum is 3025 – 385 = 2640.

Find the difference between the sum of the squares of the first one hundred natural numbers and the square of the sum.

I’m very well acquainted too with matters mathematical,

I understand equations, both the simple and quadratical,

About binomial theorem I’m teeming with a lot of news–

With many cheerful facts about the square of the hypotenuse.

Gilbert & Sullivan, “The Pirates of Penzance”

At first glance this seems to be just arithmetic which is kind of insulting. As we’ve discussed, arithmetic is only about getting to an answer and that’s the kind of boring stuff that is only fit for machine work. Clearly there must be something else going on here or I’m just going to be terribly annoyed. So let’s take a look at the math (which is much more interesting) behind sum of squares and then see if we can figure out a cunning way of getting our answer without all of that boring arithmetic. It turns out that there are at least two interesting things about the sum of squares.

The most interesting (to me, at least, dork that I am) has to do with storing cannonballs.

Let me explain.

Imagine you’re on vacation and you visit an historical site and you come across a cannon, complete with ammunition:

Photo courtesy of Hans Braxmeier (via Pixabay)

Pretty standard stuff, but what if you wanted to figure out how many cannonballs are in that pile? Better still, could you do it without actually counting any cannonballs? It turns out that you can. Note that the top of the pile has one cannonball, the layer underneath has four and so on. In other words, if we count the layers from the top down, our four layer pile here has:

12 + 22 +32 + 42 or 30 cannonballs (1 + 4 + 9 + 16). In other words, our pile of cannonballs can be expressed as a sum of squares. So we don’t need X-ray vision, we just count the number of layers in the pile and do a little arithmetic. Not bad! Note that this only works if the pile is in the shape of a square based pyramid, hence the name square pyramidal numbers for the number sequence. Of course, if there was an easy way to calculate the sum of squares than by doing all that boring arithmetic that would be better but we’ll talk more about that in a bit.

Okay, let’s look at an example that’s a bit more real world and not so much ‘Battle of Liechtenstein’. Sum of squares is more often used in statistics to analyze a set of data points. First let’s get the boring arithmetic over with so we can get on with our lives. Fortunately I recently learned about a programming language called Haskell that lets me do stuff like this pretty easily.

let x = sum(map (^2) [1..100]) (sum of squares of 1 to 100)
print x
338350
let y = foldl (+) 0 [1..100] (sum of 1 to 100)
print y
5050
[5050^2]
25502500 (square of the sum of 1 to 100)

When mathematician Carl Friedrich Gauss was eight years old (in 1785, by the way), his teacher asked the class to give the sum of the numbers 1 to 100. The idea was to keep the little buggers busy and quiet for at least a few minutes but Carl piped up almost immediately with the answer 5050. Not only did he do the sum in his head, he was able to prove his answer was correct.

Here’s how he did it (in his head, by the way):

Picture the numbers 1 to 100 in a line:

1 2 3 4 5 6 7 … 100

Now picture another row, with the same digits arranged in the opposite order:

100 … 7 6 5 4 3 2 1

Add the two rows together:

1 + 100 = 101, 2 + 99 = 101, 3 + 98 = 101 ...

Since there are 100 pairs of numbers, each adding up to 101, then the total sum is 101 x 100 or 10100. But the sum of the original sequence (which is what we wanted all along) is half of that or 5050. Sometimes you don’t need a computer if you look at the problem creatively enough.

So it turns out that the sum of the first n natural numbers (for any n) is:

Let’s apply that to our first 100 numbers and see if we really needed to write a computer program to sum 1 to 1000. Plugging 100 in for n we get (100(100 + 1))/2 or 5050.

So is there an easy way to get the sum of squares? It turns out that there is indeed:

Okay so the sum of the squares of 1 to 100 is 338,350 and the square of the sums is 25,502,500. The difference, therefore, is 25,164,150. At this point one could realistically ask, “So what?” (and who could blame you?)

It turns out that the sum of squares is an important technique in statistics for determining sample variance. That is to say, the amount that a set of data numbers varies from the average value. The bigger the variance, the more likely you’re going to have go back to the old drawing board and re-think your experiment. The traditional way to calculate variance is:

  • Find the average (mean) of the sample numbers.

  • Subtract each value from the mean and square the difference.

  • Add up all of the squared differences.

So if all of your data were perfect then the differences from the mean would be zero, which sums up to a total variance of zero. Such is the way of a perfect world. But the more your actual data points vary (see what I did there?), the bigger the difference from the mean and the bigger your variance.

That’s all well and good but where am I going with this? It turns out that there’s a shortcut way to get sample variance:

  • Sum up your sample data values and square the sum

  • Sum the squares of your sample data

  • Subtract the square of the sum from the sum of the squares

  • Divide by the number of data values

You don’t have to calculate the mean or the squares of the differences from the mean AND we’re back to our original technique of subtracting the square of sums from the sum of the squares. As your sample size gets bigger, this saves us a TON of work.

Thus endeth the lesson….