Project Euler – Problem 6

Problem 6 is by far one of the easiest problems yet.

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.

Again, there are at – least two possible methods. One is our dear friend, Mr. Brute Force 🙂 The other is more mathematical.

Brute force description

There’s not much to be said about this one. Create loops to add the sum of numbers from 1 to 100, and another loop to add the squares of numbers from 1 to 100. Square the sum you get in the first loop, and then find it’s difference. It’s simple.

Mathematical Approach

To understand the mathematical approach, you must have knowledge of the two formulas given below:

It’s all high school maths. They are easy to prove as well, especially the first one.
Writing out functions for the above should not be a difficult task, whatever language you choose.

In my version, I’ve written them as Macros (using the # pre processor directive)

Comparison

For a single iteration, both methods take less than 0.001 s or 1 ms which means they can’t be measured. Over 1,000,000 iterations, the brute force method takes 0.723 s while the other approach still clocks in at a nifty 0.001 s.

Solution in C++

Advertisements
Leave a comment

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

%d bloggers like this: