Project Euler #9

project_euler_0009.md

def solve():
    for a in range(500):
        for b in range(a, 500):
            c = 1000 - a - b

            e1 = min(a, b, c)
            e3 = max(a, b, c)
            e2 = a + b + c - e1 - e3
            if e1 + e2 <= e3:
                continue

            if e1**2 + e2**2 == e3**2:
                return e1, e2, e3

e1, e2, e3 = solve()
print(e1, e2, e3, e1*e2*e3)

另解：Pythagorean triple

使用以下假設。維基

when a^2 + b^2 = c^2
then let
	a = m^2 - n^2
	b = 2mn
	c = m^2 + n^2
	m > n, m, n are positive integers.

a + b + c = 1000
m^2 - n^2 + 2mn + m^2 + n^2 = 1000
n = (500 - m^2) / m

Code

from math import sqrt

def solve():
    for m in range(1, int(sqrt(500))):
        n, r = divmod(500-m*m, m)
        if r is 0 and m > n:
            return (m*m - n*n), 2*m*n, (m*m + n*n)


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