Skip to main content

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,
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.

 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

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😃.
Labels:

Popular posts from this blog

Making a quiz web app with python and flask

Edit : When you are creating a web app with h tml templates, then y ou will have to sa ve the html file in templates folder in the Current Wor ki ng Directory( CWD). If you save the file in the C W D directl y you will get a TemplateNotFound error. Thank you Udhay for pointing it out.   In this post we will create a quiz website using python . I will be using the flask framework . After reading this tutorial you will learn form submission , flask templates , python code in flask templates , shuffling the questions and options with the random module and few others.  Please note that this tutorial is not big as it seems to be. Some of the code has been rewritten to maintain consistency and also font size is somewhat big so that your eyes won't get stressed reading this tutorial. Also the content has not occupied the full width of the page. In this tutorial I am assuming that you are having a very basic understanding of the flask framework . Please refer the documentation
Read more

Problem 11 Project Euler Solution with python

Largest product in a grid In the 20×20 grid below, four numbers along a diagonal line have been marked in red. 08 02 22 97 38 15 00 40 00 75 04 05 07 78 52 12 50 77 91 08 49 49 99 40 17 81 18 57 60 87 17 40 98 43 69 48 04 56 62 00 81 49 31 73 55 79 14 29 93 71 40 67 53 88 30 03 49 13 36 65 52 70 95 23 04 60 11 42 69 24 68 56 01 32 56 71 37 02 36 91 22 31 16 71 51 67 63 89 41 92 36 54 22 40 40 28 66 33 13 80 24 47 32 60 99 03 45 02 44 75 33 53 78 36 84 20 35 17 12 50 32 98 81 28 64 23 67 10 26 38 40 67 59 54 70 66 18 38 64 70 67 26 20 68 02 62 12 20 95 63 94 39 63 08 40 91 66 49 94 21 24 55 58 05 66 73 99 26 97 17 78 78 96 83 14 88 34 89 63 72 21 36 23 09 75 00 76 44 20 45 35 14 00 61 33 97 34 31 33 95 78 17 53 28 22 75 31 67 15 94 03 80 04 62 16 14 09 53 56 92 16 39 05 42 96 35 31 47 55 58 88 24 00 17 54 24 36 29 85 57 86 56 00 48 35 71 89 07 05 44 44 37 44 60 21 58 51 54 17 58 19 80 81 68 05 94 47 69 28 73 92 13 86 52 17 77 04 89 55 40 04 52 08 83 97 35 99 16 07
Read more

Problem 60 Project Euler Solution with python

Prime pair sets The primes 3, 7, 109, and 673, are quite remarkable. By taking any two primes and concatenating them in any order the result will always be prime. For example, taking 7 and 109, both 7109 and 1097 are prime. The sum of these four primes, 792, represents the lowest sum for a set of four primes with this property. Find the lowest sum for a set of five primes for which any two primes concatenate to produce another prime. This problem is j u st a brute force problem. If you have come here because you don't know the limit upto which you will h ave to gener ate the prime numbers t hen go ahe ad and t r y with 10,000 . When I first start ed solving the problem I chose 1 million(beca use most of the problem s on project E uler have this limit ), but it took very long for the computer to fin d the solution. After searching on the internet then I found many people choosing 10, 000 so I have changed my in put f rom 1 million to 10000 and the output was f ast. He
Read more