Problem 9 Project euler solution with python

Special Pythagorean triplet

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

a² + b² = c²

For example, 3² + 4² = 9 + 16 = 25 = 5².
There exists exactly one Pythagorean triplet for which a + b + c = 1000.
Find the product abc.

This problem might seem easy to solve, but there is a hidden twist which one might miss.

Some of you might have used three for loops to create numbers a,b,c and then check sum of the three is equal to 1000 after which you might have checked the Pythagorean triplet condition given in the question. But you should not do this. One of the best way is to generate two numbers a,b and generate the third number with the condition c = a-b. This will reduce 1000's of extra iterations.
An another approach might be to stop the looping once you have found out the solution, because it is given in the question that there is only one such solution.
I have used the last approach(Stop after result is found) to solve the problem.

I have written three programs to solve this problem. The program is very simple and the algorithm has already been explained. Even though I have got a very fast solution I just wanted to try if I can write a program which will give me better result. I googled for the solution.

I found

1. Dickson's method
2. m, n formula (Search for Constructing Pythagorean Triples)

While I will show you both the programs I have written one by one, if you want to understand the programs I would like to ask you to visit the websites and spare just a few minutes to understand the formula. Then you are done.

Finally the program I have selected was the m,n formula method as the best solution because it had ~0.0005 seconds execution time.

 The first program just using the hint given in the question is as follows:

#http://radiusofcircle.blogspot.com

#Time module for calculating the 
#execution time
import time

#Time at the start of exection
start_time = time.time()

#Function to generate numbers
#with the help of hint given in question
def pythagorean_triplet():
 for a in xrange(1,1000):
  for b in xrange(1,1000):
   c = 1000-a-b
   if (a**2+b**2) == c**2:
    return a*b*c

#printing the result
print pythagorean_triplet()

#time at the end of execution
end_time = time.time()

#Printing the total_time
print end_time - start_time

Execution time for this program was around 0.0639238357544 seconds. I think this program can also be used because it is having very small execution time.

Using Dickson's method

The second program which I wrote to improve the above execution time using the Dickson's method is as follows:

#http://radiusofcircle.blogspot.com

#time module to calculate the time
import time

#time at the start of execution
start_time = time.time()

#function to find the pythagorean triplet
#Using Dickson formula
def pythagorean_triplet_dickson():
 for r in range(1,1000):
  for s in range(1,r):
   if ((r**2)/2)%s == 0:
    t = (r**2/2)/s
    if r+s+r+t+r+t+s == 1000:
     return (r+s)*(r+t)*(r+t+s)

#Printing the result
print pythagorean_triplet_dickson()

#time at the end of execution
end_time = time.time()

#Total time taken for execution
print end_time - start_time

This program had an execution time of around 0.00344491004944seconds, which is still better than the previous one.

Using m,n's formula

The following program written using m,n's formula is very easy to understand once you understand the concept behind it. It had a better execution time compared to Dickson's method.

The program is well commented so that it doesn't require any explanation if you have read the concept from the links.

You can download the program from Github Gist if you want.

Output

Answer: 31875000
Execution time:8.9168548584e-05s
output:

Project euler problem 9 output

Project Euler Problem 9 with solution

Summary

After solving this problem I have learned many things. They can be summarized as follows:

1. There are formulas to generate Pythagorean Triplets - Dickson method - m,n's formula etc.
2. If we have got a solution and want to stop looping it is better to use functions. StackOverflow - How to break out of multiple loops in Python 

I don't know if I have learnt anything more, but they have come to my mind and so I have written.

I haven't explained any of the programs because they are well commented and also they are just direct application of the formulas which we have learned from wiki and mathisfun. If you haven't understood anything or have a doubt then comment in the comment box below and I will be glad to help you.

Please don't hesitate to comment if I have made a typo or want me to improve anything in this post.

Please do share your code if it is better/different from any of the codes I have written above.

You can also contact me if you want to.

Thank you. Have a nice day😃.