Project Euler Problem 6: Sum of Square Difference06 Sep 2015
Let’s solve problem six in Project Euler in a programming language of your choice. Yes, that’s correct, you can choose!
If you have an academic interest in Project Euler, and you have not solved problem six, I suggest you do so before reading this post lest you deprive yourself of an opportunity to learn.
This is one of the easiest Project Euler problems.
Find the difference between the sum of the squares of the first one hundred natural numbers and the square of the sum.
Up to it is trivial, but we can use math to solve it up to massive numbers, like a thousand quinquagintaquadringentillion (that’s , or 1 followed by 2703 zeros), that could otherwise take years to solve even for a computer.
Sometimes the most obvious solution isn’t necessarily the best one.
This was my first try in Ruby.
For small numbers, this works well. But what if, instead of 100, you had to solve for a thousand quinquagintaquadringentillion? No one wants to create arrays with that many elements or loops with that many iterations.
A better solution
With the help of elementary math–specifically, mathematical induction–we can solve this problem up to any number.
This is the square of the sum up to .
And the sum of squares up to .
And the solution up to .
Using these formulas, we can solve this problem up to nonsensical numbers in microseconds. Here’s the solution in Ruby; it’s not terribly interesting.
I was curious, so I created benchmarks to illustrate the efficiency of four different techniques: Using map and reduce, enumerators, while loop, and induction. I tested the earlier three against , and the latter against a thousand quinquagintaquadringentillion, or .
It’s hardly surprising, but map/reduce, enumerator, and
while loop took 2.9, 1.6, and 1.2 seconds respectively. I imagine
while is faster because it deals only with primitive types and no data structures.
Using our equation took 10 microseconds for a ridiculously larger number, which is 10 millionth of a second. I ran these on my first gen MacBook Pro Retina.
Again, no surprises here, but I was curious.
On my computer, using map and reduce fills up the stack and throws an exception at , while using a loop solves up to in circa 3.5 seconds.
Swift didn’t fair much better.
You can find the sample code including benchmarks on Github.