A Pythagorean triplet is a set of three natural numbers, a < b < c, for which, a^2 + b^2 = c^2 For example, 3^2 + 4^2 = 9 + 16 = 25 = 5^2. There exists exactly one Pythagorean triplet for which a + b + c = 1000. Find the product abc.
I think I can figure out a way to brute force it, but it's not pretty. Well, there are only so many numbers for a+b+c=1000. 1+1+998, but 1 ^ 2 + 1 ^ 2 != 998 ^ 2.
No, maybe that won't work? Shoot, this is the first PE problem where it wasn't obvious how to brute force it. Oh wait, there's the additional constraint that a < b < c. Maybe that's helpful? Ok so start with 1 < 2 < ? That's 1 ^ 2 + 2 ^ 2 = 5. I can check that 5 isn't a square number (I hope). IF the sum isn't a square I increment b (nested loop?). If it is square, I check for a+b+c=1000. Once I hit a square number as c that causes a+b+c < 1000 then I know I need to start over with incrementing a to 2 and starting b at 3. Then repeat.
That's the way to brute force it... maybe.
No comments:
Post a Comment