Skip to main content

Problem 39 Project Euler Solution with python

Integer right triangles

If p is the perimeter of a right angle triangle with integral length sides, {a,b,c}, there are exactly three solutions for p = 120.
 {20,48,52}, {24,45,51}, {30,40,50}
For which value of p ≤ 1000, is the number of solutions maximised?


Again an easy problem, it just took me a few minutes to write the first draft of the code which worked in less than a second. I still modified it and made it to work under 0.1 second.

Algorithm is very simple, we will use Pythagorean Theorem to generate the side lengths of the right angle triangle. If you don't know about Pythagorean Theorem, then the best places to learn about it are:
Wikipedia - Pythagorean Theorem
Pythagoras Theorem - Mathisfun
Pythagorean Theorem - University of Georgia
Pythagorean Theorem - Worlfram Math

 Anyways I will give you the formula that Pythagorean Theorem states:
c2 = a2+b2
where
c - Length of Hypotenuse
a,b length of two other sides
Pythagorean triangle
Pythagorean Triangle - Image from Wikipedia
From the above equation we can say that the maximum value that a can take is 1000 and also the same in the case of b, but we can reduce it further. After I have written a program with the limits extending upto 1000, it took less than 1 second for the program execution. But I was not satisfied and wanted to reduce the code(i.e. to reduce the limit of iterations).

 I got an answer from ProjectEuler forum where Augustingianni from Argentina on Saturday 4 August 2007 posted the following:

 We know that the value of c can be written as √a2+b2. So the perimeter of can be written as
  p = a + b + c
⇒p = a + b + √a2+b2
Now if we will consider b = 0 then
⇒p = a + 0 + a
⇒p = 2a
So 2a ≤ 1000
a ≤ 500
and similarly the proof follows for b also.

 Unfortunately I am not able to tag this post to attribute this guy.

 We also know that the values of c generated from the above can also be a real numbers, but the question asks us to generate only integer values also called as Pythagorean Triples. So we will check if the value of c is integer and then add it to the perimeter list for further counting if it is an integer.

 After all the iterations are over, i.e after we have generated all the values of c for a<500 then we will count the number of instances of the given element in the list and finally we will print the most repeated perimeter.

Program 

Again this time I have tried to maintain PEP8 standards. I have checked my code with pep8 module and it gave me a green signal.

As you can see I have used Counter from collections module which I have seen from Stack overflow

Have a look at the Stack answer and you will understand the whole code after for loops.

As always you can download the source code from Github Gist pep39.py

Output 


Summary

First time I wrote the code, I used 1000 instead of 500 which took less than 1 second. But I was not satisfied and wanted a more faster optimized solution. So I went on to check the forums and found a very great answer and thus the time of execution was reduced. This was a good problem, which again challenged your mathematical skills. Using the collections module made my job still easy, I want to thank the Stack community for this. And of course without python this would not have been possible. 

 Anyways as always if you have any doubt or didn't understand anything then you can comment in the comment box below and I will be glad to help you.

 Please do comment in the comment box if you have found a typo, or have a different program or have a better program or have a suggestion. I will be very happy to view each of them.

 You can also contact me.

 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