Project Euler – Problem 6

Sure has been a long time since I’ve done one of these, but I’ve been doing more front end development, and it makes it so my brain doesn’t get enough of a work out.

This is the sixth post in my Project Euler series (if series is the right word). The fifth problem is here.

I also decided that with Swift 2.0 in beta, I’d try this out in Swift instead of C/Objective-C.

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

1² + 2² + … + 10² = 385

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

(1 + 2 + … + 10)² = 55² = 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.

---

 

So let’s say we want to solve this problem in an efficient way. Obviously, we could do some brute force solving. We know the equations, they’re really simple and obvious. But If we’re trying to sum the squares of the first one hundred natural numbers, then the numbers get pretty big. Not too big to handle with a computer, but $latex 338,350$ is still pretty big. And if we wanted to do this problem for the first ten thousand natural numbers instead, then we’d be a little out of luck.

 

So to start off, we need simplified equations. We’ll do the first. If you head on over to this page, you can get an excellent explanation as to why the sum of squares comes out to be this equation

$latex \dfrac{n^3}{3} + \dfrac{n^2}{2} + \dfrac{n}{6}$

Next, we need an equation for the second. To use this, we will use the sum of natural numbers, and then square the equation. Once again, head over here for an explanation of how I got this equation for the sum of natural numbers.

$latex \dfrac{n^2}{2} + \dfrac{n}{2}$

Which, after spending a shamefully long amount of time doing and redoing algebra gives us this

$latex \dfrac{n^4}{4} + \dfrac{n^3}{2} + \dfrac{n^2}{4}$

---

Now that we have our two equations, we just need to subtract them from each other, which gives us this

$latex \dfrac{n^2}{4} + \dfrac{n}{6} – \dfrac{n^4}{4} – \dfrac{n^3}{6}$

Which, if we plug 10 in, we get $latex -2640$. Which brings me to a point of confusion with the problem description. It seems pretty straight forward

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.

But if we look at the phrasing, it says the difference between the SUM OF THE SQUARES and the SQUARE OF THE SUM. but the math shown is clearly the difference between the SQUARE OF THE SUM and the SUM OF THE SQUARES.

Given this, I believe that the answer should in fact be $latex -2640$ not $latex 2640$, because subtraction is not commutative.

Since we have such an awesome equation, doing it in code just seems overkill. But here goes