Home — Project Euler (feed)

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