# 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.

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}}$.

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

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.

Finally, to work out the answer:

This solution runs for about 350ms on my machine.

The source code for this solution is here.

Enjoy what you’re reading? Subscribe to my newsletter and get more content on AWS and serverless technologies delivered straight to your inbox.

Yan Cui

I’m an AWS Serverless Hero and the author of Production-Ready Serverless. I have run production workload at scale in AWS for nearly 10 years and I have been an architect or principal engineer with a variety of industries ranging from banking, e-commerce, sports streaming to mobile gaming. I currently work as an independent consultant focused on AWS and serverless.