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

Add/Embed SVG to Blogger website

In this post I will tell you my method(trick) of adding SVG images in a blogger website or blog. Before starting , the first thin g I am assu m ing is that you are aware of SVG if you are here. If not please see S calable V ec tor G raphics Recently when I tried to embed a SVG image for a post on pygal, I tried uploading the SVG file and blogger Image uploader came up with an error, because of which I had to find some other way.  SVG File upload Error in Blogger  I started sea rc hing Google " Embed SVG in Blogger " . I found blogorrhea , w h ich gave some i nformatio n on add ing SVG directly as a markup , which worked , but I faced another problem using this . Also th is guy has used lot of Javascript which was confusin g for me, being new to using SVG.   So I first t houg ht of learning on h ow to embed SVG in HTML and t his on e worked out. Actually we can embed SVG in HTML i n following ways: Using Object tag Using Iframe tag Using embed tag Us
Read more