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?
{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
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.
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
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😃.
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 - Image from Wikipedia |
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😃.