Yan Cui
I help clients go faster for less using serverless technologies.
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 $latex \sqrt{\frac{L}{2}} $. Because $latex L = a + b + c $ and $latex a^2 + b^2 = c^2 $, we can deduce that $latex c < \frac{L}{2} $; and since $latex c = m^2 + n^2 $ we also have $latex m < \sqrt{c} $ and therefore $latex 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 $latex a^2 + b^2 = c^2 $ then $latex 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.
Whenever you’re ready, here are 4 ways I can help you:
- If you want a one-stop shop to help you quickly level up your serverless skills, you should check out my Production-Ready Serverless workshop. Over 20 AWS Heroes & Community Builders have passed through this workshop, plus 1000+ students from the likes of AWS, LEGO, Booking, HBO and Siemens.
- If you want to learn how to test serverless applications without all the pain and hassle, you should check out my latest course, Testing Serverless Architectures.
- If you’re a manager or founder and want to help your team move faster and build better software, then check out my consulting services.
- If you just want to hang out, talk serverless, or ask for help, then you should join my FREE Community.
Pingback: F# Weekly #2-#3, 2016 | Sergey Tihon's Blog