I just finished Project Euler 39:
If p is the perimeter of a right angle triangle with integral length sides, {a, b, c} … For which value of p ≤ 1000, is the number of solutions maximised?
I'm pretty satisfied with my solution. I derive the formula for the hypotenuse as follows:
$$\begin{align} a + b + c &= p \tag{Def. perimeter}\\ b + c &= p - a \tag{2}\\ \\ a^2 + b^2 &= c^2 \tag{Pythagorean}\\ a^2 &= c^2 - b^2 \\ a^2 &= (c - b)(c + b) \\ a^2 &= (c - b)(p - a) \tag{from (2)} \\ \frac{a^2}{p - a} &= c - b \tag{7} \\ \\ (c - b) + (c + b) &= \frac{a^2}{p - a} + (p - a) \tag{from (7) and (2)}\\ 2c &= \frac{a^2}{p - a} + \frac{(p - a)^2}{p - a} \\ 2c &= \frac{a^2 + (p - a)^2}{p - a} \\ c &= \frac{a^2 + (p - a)^2}{2\ (p - a)} \end{align}$$
Any optimization would be appreciated.
from timeit import default_timer as timer
start = timer()
def find_pythagorean_triples(perimeter):
count = 0
for a in range(3, perimeter / 2 - 1): # triangle inequality
c = (a**2 + (perimeter - a)**2) / (2*(perimeter - a)) # derived formula
b = (c**2 - a**2)**0.5
if b.is_integer() and a + b + c == perimeter:
count += 1
return count
def find_most_solutions_upto(limit):
data = {"most": 0, "num": 0}
for p in range(limit/2, limit + 1): # scale upwards
if find_pythagorean_triples(p) > data['most']:
data['most'] = find_pythagorean_triples(p)
data['num'] = p
return data['num']
ans = find_most_solutions_upto(1000)
elapsed_time = (timer() - start) * 1000 # s --> ms
print "Found %d in %r ms." % (ans, elapsed_time)
