Project Euler Problem 9 Solution

Question:

To find the pythagoras triplet a, b, c such that a^2 + b^2 = c^2 and a + b + c = 1000


Idea:

as, a + b + c = 1000 and a ^2 + b^2 = c^2, hence a < b < c

s = a + b + c

hence,

a < s/3  because a < b < c
(in worst case, a = b = c = s/3 )

b < s/2 because b > a i.e. b > s/3 and b < c
(in worst case a =1, b ~ c hence, b = c = s/2)


CODE:

-----------------------------------
#!/usr/bin/python

import math


a = b = c = 0
s = 1000
f = False

a = 1
while ( a < s/3 ):
        b = a
        while ( b < (s / 2)):
                c = s - a - b
                if ( a * a + b * b == c * c):
                        f = True
                        break
                b = b + 1

        if f:
                break

        a = a + 1


print a, b, c , (a * b * c)

-----------------------------------------------------