We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
Not a so easy problem.
I found 10560 triples for x under 10^12 but it takes 47s to my python program to find them which is quick enough to pass the first 7 test cases but not the last one.
So I generate all pythagorean triples with hypotenuse = a in ascending order then for each combinations of pythagorean triples with same a, I test all the 3 left constraints (c>e, (c+d)%2 = 0 and c²-e² = b²).
I have not much idea how to improve that. Can we skip some pythagorean triplets? Can we have some constraint on d and e to avoid to test twice with them reversed?
Project Euler #142: Perfect Square Collection
You are viewing a single comment's thread. Return to all comments →
Not a so easy problem. I found 10560 triples for x under 10^12 but it takes 47s to my python program to find them which is quick enough to pass the first 7 test cases but not the last one.
My program is based on pythagorean triples :
So I generate all pythagorean triples with hypotenuse = a in ascending order then for each combinations of pythagorean triples with same a, I test all the 3 left constraints (c>e, (c+d)%2 = 0 and c²-e² = b²).
I have not much idea how to improve that. Can we skip some pythagorean triplets? Can we have some constraint on d and e to avoid to test twice with them reversed?
I found some other way to solve that but did not implement it yet : https://sites.google.com/site/tpiezas/0020. What did you implemented?