# Project Euler — Problem 75 Solution

The prob­lem descrip­tion is here, and click here to see all my oth­er Euler solu­tions in F#.

I based my solu­tion on Euclid’s for­mu­la for gen­er­at­ing Pythagore­an triples.

And giv­en that max L is 1,500,000, the max­i­mum val­ue for m we need to con­sid­er 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 there­fore $m < \sqrt{\frac{L}{2}}$.

The above makes use of a recur­sive func­tion to cal­cu­late the GCD (based on Euclid­ean Algo­rithm):

For effi­cien­cy, we’ll cre­ate a cache to store the num­ber of ways L can be used to cre­ate inte­ger sided right-angle tri­an­gle. As we iter­ate through the m and n pairs we gen­er­at­ed above, we’ll take advan­tage of the fact that if $a^2 + b^2 = c^2$ then $ka^2 + kb^2 = kc^2$ must also be true and incre­ment mul­ti­ples of L by one.

Final­ly, to work out the answer:

This solu­tion runs for about 350ms on my machine.

The source code for this solu­tion is here.