Euleryx Problem 39 – Integer Right Triangles
My workflow (Not sure if I've broken anything but I seem to have lost both the spoiler tag and font size options again! Please scroll past the next section if you don't want to see the answer):
Workflow:
Answer: 840
Last Week's Favourite Solution:
Several solutions stood out last week, however the issue of downloading .yxdb files did make it challenging to decide a winner. That being said, based on the screenshots, @AkimasaKajitani was able to create a macro less , 7 tool solution (8 if you include the browse 😄). I’m intrigued on the power behind both the multirow and filter as I suspect they are doing the heavy lifting, but either way, @AkimasaKajitani was a clear winner on the tool golf front too! Please find their solution on page one of last week's post or click here.
Mathematical Theory:
A common theme among the Project Euler problems, is that while a single formula which leads directly to the answer may not exist, one can be derived which simplifies the bruit force effort. I particularly enjoyed this problem as it involved some formula manipulation, as well as bounding the variables where possible.
To begin with, we must introduce the formula we will use.
Firstly, as almost any mathematician would know, the moment a right angle triangle is mentioned, Pythagoras should pop into your head. This formula states that if you take the two shorter sides of a right angle triangle, square, then sum them, you will get the square value for the longest side. Lets call this equation one (1):
The next formula is simply the value of p, which is explained as follows: Equation two (2)
Rearranging equation two, to make c the subject we get (3):
Substitute (3) into (1) gives us:
Expand the brackets on the right hand side to get:
Cancel like terms:
Then rearrange to get all the bs on one side:
Take b out as a factor:
Finally, divide by (2p-2a):
Now this may not look like an answer yet, but there’s a couple of things to note. Firstly, we now have an equation with a, b and p, but no c. Meaning we have removed one of the variables so we no longer have to worry about it. Secondly, there are a couple of basic facts which we haven’t yet mentioned.
- We used Pythagoras’ theorem, and a key piece of information not yet explored is that a < b < c. As p = a + b + c, we can confidently say that a is less than a third of p, i.e a <p/3. Intuitively, what this formula is trying to say is that the SHORTEST, side on a triangle, can be no more than one third of the perimeter.
- The question states that p <=1000, so we only need to test 1000, values for p.
- We also know that only integer solutions count.
Combining all of this, if we test all values of p <= 1000, along with all a <p/3, by substituting them into the formula from above, we will find the value of b. From there all we need to do is figure out how many values of b are integers, per value of p, then choose the greatest.
Method:
1 List numbers from 1 to 1,000 (for p), then use a generate rows to generate the a values too, using the upper bound of p/3, as discussed above.
2 Use the formula derived above, to calculate the values of b, for the given scenarios of p and a values.
3 Filter to only the solutions where b is an integer.
4 Count the number of integer solutions per p value.
5 Sort then sample the single record with the greatest count to identify the answer.
6 Submit your answer to the Project Euler Website!
Summary:
Using a few facts around triangles, as well as Pythagoras theorem, we were able to remove one of the variables from this problem. By removing one of the variables, the potential candidates we needed to check was drastically reduced, turning this into a simple “bruit force” approach from this point forward.
Want to find out more, follow this link to our introduction post - Euleryx: Let The Games Begin.
