Project Euler: Problem 9

Problem 9

Approach

We are looking for a Pythagorean triple such that sides $a + b + c = 1,000$.

One way to categorize Pythagorean triples is into primitives and non-primitives. A primitive triple has all three integers co-prime with each other.

E.g., (3, 4, 5) is primitive because the integers share no common factors except for 1.

(6, 8, 10) is not primitive because the integers have a common factor of 2.

Said another way, multiplying the integers of a primitive triple by a common factor $k$ will always result in a non-primitive triplet.

This is useful to know because we don't have perform an exhaustive search of all Pythagorean triples. We only need to search through the primitives. And if we find a primitive triplet whose integers sum to a factor of 1,000, then we can just multiply the primitive by said factor.

Example: Imagine we want to find the Pythagorean triple whose integers sum to 36. Since the (3, 4, 5) triplet sums to 12 (which goes into 36 three times), then we can just multiply the (3, 4, 5) triplet by 3.

And so the triplet whose integers sum to 36 is (9, 12, 15).

We can easily solve this problem by hand just by testing the most well known triplets:

$(3, 4, 5) \rarr 3 + 4 + 5 = 12; \quad \quad \quad 1,000\mod12 \neq 0$

$(5, 12, 13) \rarr 5 + 12 + 13 = 30; \quad 1,000\mod30 \neq 0$

$(8, 15, 17) \rarr 8 + 15 + 17 = 40; \quad 1,000\mod40 = 0$

40 goes into 1,000 25 times. Which means the triplet we are looking for is:

$(8, 15, 17) \cdot 25 \rarr (200, 375, 425); \quad 200 + 375 + 425 = 1,000$

And the product of those 3 numbers is:

$200 \cdot 375 \cdot 425 = 31,875,000$

Conclusion

A straightforward problem that doesn't require any coding.

Final answer

$31,875,000$