In this article, we’ll be exploring Project Euler problem 6. I’ll provide some ideas and hints, but it’ll be up to you to create a program or design an algorithm that obtains the answer. Good luck!

Also, if you get stumped, stick around on my blog for my next article in which I’ll provide a full walkthrough.

This article is part of the Project Euler series.

Project Euler Problem 6

The sum of the squares of the first ten natural numbers is,
1^2 + 2^2 + ... + 10^2 = 385

The square of the sum of the first ten natural numbers is,
(1+2+ ... +10)^2=55^2=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.

The first thing that comes to my mind when I see this problem is brute-forcing it to find the answer – that is just calculating the sums in a loop of some kind, and calculating the difference. While this approach is a valid approach, there is a better way of doing this that will scale way better!

The arithmetic approach

There is actually a formula to find the sum of n natural numbers. It is expressed below:

S_{n}=\frac{n(n+1)}{2}

Try it yourself. This provides the first part of our problem – finding the sum of natural numbers.

Now, we need a way to find the sum of squares of natural numbers. Luckily, a formula for this exists as well. Isn’t math amazing?

S^2_{n}=\frac{n(n+1)(2n+1)}{6}

Now, using these two formulas combined, you should be able to easily write simple code to obtain the answer. The best part: it’ll run in O(1). (The execution time is constant as a function of N, meaning that no matter the size of the input, the algorithm will scale constantly.)