Home — Project Euler

Let’s consider the general case $a + b + c = s$, where $s$ can only be even. All the pythagorean triplets can be generated with the Euclid’s formula $a = k*(m^2 - n^2)$, $b = k*(2*m*n)$, $c = k*(m^2 + n^2)$. When substituting the above in $a + b + c = s$ we get $2*k*m*(n + m) = s$ and $k = \frac{s'}{m*(n+m)}$ with $s' = s/2$. The conditions for the Euclid formula are: $m > n$, $m - n$ odd and $m$ and $n$ coprime. So we just need to generate all the pairs $(m,n)$ which satisfy these conditions until we find one that evenly divides $s'$ at which point we calculate $k$. This can be done, starting with $m = 2$ and $n = 1$, by applying the following formulas at each iteration: $(2m - n, m)$, $(2m + n, m)$ and $(m + 2n, n)$ (see Generating all coprime pairs).

def euclid_formula(k, m, n):
    return k*(m**2 - n**2), k*(2*m*n), k*(m**2+n**2)
def coprimes():
    from collections import deque
    pairs = deque([(2, 1)])
    while True:
        (m, n) = pairs.popleft()
        yield m, n
        pairs.append((2*m - n, m))
        pairs.append((2*m + n, m))
        pairs.append((m + 2*n, n))

def k(s):
    s1 = s/2
    for (m, n) in coprimes():
        k, rem = divmod(s1, m*(n+m))
        if rem == 0:
            return euclid_formula(k, m, n)
        
a, b, c = k(1_000)
int(a*b*c)

31875000