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.

1 Comment

  1. Pingback: F# Weekly #2-#3, 2016 | Sergey Tihon's Blog

Leave a Reply

Your email address will not be published.