problem-009.py

"""
Question:
Pythagoream truplet is a set of natural nos, a < b < c, for which a^2 + b^2 = c ^2
There exists only one triplet for which a + b + c = 1000
Find product abc
"""
import time

a, b, c = 2, 3, 5
N = 1000

def isPythagoreanTriplet(a,b,c):
    hyp = max(a,b,c)
    smallest = min(a,b,c)
    other = (a+b+c) - (hyp + smallest)
    if hyp**2 == smallest**2 + other**2:
        return True
    return False

def findTriplet():
    for i in range(a, 1000):
        for j in range(b, 1000):
            for k in range(c, 1000):
                if i + j + k == 1000 and isPythagoreanTriplet(i,j,k):
                    ans = i * j * k
                    return ans, i, j, k

t0 = time.perf_counter(), time.process_time()
ans, a, b, c = findTriplet()
t1 = time.perf_counter(), time.process_time()
print(ans)
print("triplet: ",a,b,c)
print("Brute force with minor optimizations")
print(f"Real time: {t1[0]-t0[0]:.5f} seconds")
print(f"CPU time: {t1[1]-t0[1]:.5f} seconds")
print("----------")


# Idea2: Euler's Formula & Primitive Pythagorean Triplets
"""
Note that for all pythagorean triplets, a,b,c are pairwise coprime. 
Primitive Pythagorean Triplets: if gcd(a,b,c) = 1 i.e in other words, gcd(a,b) = 1 since a,b,c are already pairwise coprime.
eg. (2,3,5), (5,12,13) etc
Euler's Formula: 
All primitive triplets can be generated using following:
a = m^2 - n^2
b = 2mn
c = m^2 + n^2
with m > n > 0
The triplet generated by Euler's formula will be primitive if and only if, gcd(a,b) = 1

From any Pythagorean triplet you get a primitive one by dividing out the greatest
common divisor, so every Pythagorean triplet has a unique representation
a = (m^2 − n^2) * d
b = 2mnd
c = (m^2 + n^2) * d
with m > n > 0, gcd(m, n) = 1 and exactly one of m, n even & d is the greatest common divisor of a, b and c.

Coming to the problem,we can say (a+b+c = s given): 
a + b + c = 2 * m * (m+n) * d
s = 2 * m * (m+n) * d
s = 2 * m * k * d with m < k < 2m & gcd(m, k) = 1

"""
import math
s = 1000

def primitivePrimesAlgo():
    """
    s = 2 m k d
    lets find factors of s/2 - m & k are unknowns
    """
    s2 = s // 2
    lim = math.ceil(math.sqrt(s2))
    for m in range(2, lim+1):
        sm = s2 // m
        # m can be even, m is ensured to be odd, since gcd(k,m) has to be 1
        k = m+2 if m%2 else m+1
        while k < 2*m and k <= sm:
            if sm % k == 0 and math.gcd(k,m) == 1:
                d = s2 // (k*m)
                n = k - m
                a = d * (m*m - n*n)
                b = 2*d*m*n
                c = d*(m*m+n*n)
                return a,b,c
            k += 2

t0 = time.perf_counter(), time.process_time()
a,b,c = primitivePrimesAlgo()   
t1 = time.perf_counter(), time.process_time()
print(f"Real time: {t1[0] - t0[0]:.5f} seconds")
print(f"CPU time: {t1[1] - t0[1]:.5f} seconds")
print(a*b*c)