06.03.08

Project Euler: Problem 9

Posted in python tagged , , at 1:08 pm by redochre

Problem 9:

A Pythagorean triplet is a set of three natural numbers, a < b < c, for which,
a2 + b2 = c2

For example, 32 + 42 = 9 + 16 = 25 = 52.

There exists exactly one Pythagorean triplet for which a + b + c = 1000.
Find the product abc.

A solution:
First, the math part. We have two equations in three unknowns. Eliminating c gives 2000a+2000b-2ab=1000000. Then, solving for a gives a = (500000-1000b)/(1000-b). Now we can loop through values for b, looking for one that will give us a natural number result for a.

limit = 1000  # gotta stop somewhere
for i in range(1,limit):
    if (500000 - 1000*i)%(1000-i) == 0: # ie, will make a natural number
        b = i
        a = (500000 - 1000*b)/(1000 - b)
        c = 1000 - a - b
        print "a = %d, b = %d, c = %d" %(a, b, c)
        print "product is %d" %(a*b*c)
        break
    if i == limit-1: print "solution not found, try a higher limit"