Project Euler – Problem 75 Solution

The problem description is here, and click here to see all my other Euler solutions in F#.

 

I based my solution on Euclid’s formula for generating Pythagorean triples.

Prob75_01_wiki

And given that max L is 1,500,000, the maximum value for m we need to consider is \sqrt{\frac{L}{2}} . Because L = a + b + c and a^2 + b^2 = c^2 , we can deduce that c < \frac{L}{2} ; and since c = m^2 + n^2 we also have m < \sqrt{c} and therefore m < \sqrt{\frac{L}{2}} .

Prob75_01

The above makes use of a recursive function to calculate the GCD (based on Euclidean Algorithm):

Prob75_04

For efficiency, we’ll create a cache to store the number of ways L can be used to create integer sided right-angle triangle. As we iterate through the m and n pairs we generated above, we’ll take advantage of the fact that if a^2 + b^2 = c^2 then ka^2 + kb^2 = kc^2 must also be true and increment multiples of L by one.

Prob75_02

Finally, to work out the answer:

Prob75_03

This solution runs for about 350ms on my machine.

 

The source code for this solution is here.

Subscribe to my newsletter and get new contents delivered straight to your inbox :-)