Project Euler – Problem 9

Problem 9 is sort of easy too! 🙂

The problem statement is as follows:

A Pythagorean triplet is a set of three natural numbers, a<b<c, for which,

a2 + b2 = c2

For example, 32 + 42 = 9 + 16 = 25 = 52.

There exists exactly one Pythagorean triplet for which a + b + c = 1000.
Find the product abc.

Knowing a little maths can take you a long way in this problem.

Mathematical Discussion

(skip this it bores you. The problem can still be solved without it)

Knowing this can cut your run time from 0.291 seconds to 0.001 seconds (as measured by the ctime library), which is basically 99.6% faster!

Basically, Pythagorean Triplets are an expression for possible integral values of the sides of a right angled triangle. Armed with this little nugget of knowledge, we can effectively reduce the iterations that we have to go through to find the required triplet.

General Algorithm

  1. We know that a + b + c = 1000.
  2. Therefore, m2 n2 + 2mn + m2 + n2 = 1000. So, 2m2 + 2mn = 1000.
  3. We now attempt to get the answer by applying brute force on the above expression, rather than plugging in all possible values of a, b and c.
  4. I believe that the brute force method merits no discussion. It has been included in the source, for comparison with the above method.

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: