So the other night I was a bit bored and decided to do something to pass the time. I first came across Project Euler a while ago, but had never gone further than problem #1. Boredom is a great motivator and I went through problems #2 thru #9 last night and I decided to post my solutions in search of better ones. Feel free to comment with your suggestions.

Project Euler’s Problem #9 statement is —

A Pythagorean triplet is a set of three natural numbers, a<b<ca < b < c, for which:

a2+b2=c2. a^2 + b^2 = c^2.

For example, 32+42=9+16=25=523^2 + 4^2 = 9 + 16 = 25 = 5^2.

There exists exactly one Pythagorean triplet for which a+b+c=1000a + b + c = 1000.

Find the product abcabc.

Using c=1000−a−bc = 1000 - a - b removes one variable immediately. Substituting that into a2+b2=c2a^2 + b^2 = c^2 and solving for bb gives

b=1000(1000−2a)2(1000−a). b = \frac{1000(1000 - 2a)}{2(1000 - a)}.

That leaves only the possible values of a to search:

total = 1000

for a in range(1, total // 3):
    numerator = total * (total - 2 * a)
    denominator = 2 * (total - a)

    if numerator % denominator:
        continue

    b = numerator // denominator
    c = total - a - b
    if a < b < c:
        print(a * b * c)
        break

The divisibility check ensures that b is a natural number. The triplet is (200,375,425)(200, 375, 425), so the program prints 31875000 in linear time and constant space.