In problem 39 we’re supposed to look at right triangles with integral sides and perimeter no bigger than 100. Specifically, among such perimeters, which has the most representing right triangles?

The given bound seemed small enough that I figure brute force was a good place to start. Loop through lengths for the legs, calculate what the hypotenuse would be, keep track of solutions you find, organized by perimeter, and see who wins. The first (correct) program I wrote ran in 5 seconds. With 5 minutes tweaking the code without much thought, I had the runtime down to half a second. 1000 really isn’t a difficult bound (fwiw though, 10000 takes nearly a minute on my computer). Here’s my code:

def solve(bound): solns = [0 for n in range(0,bound+1)] # storage ret = 0 # the winning perimeter for smleg in xrange(1,bound//2 + 1): # the larger leg will still be shorter than the hypotenuse for lgleg in xrange(smleg+1, (bound-smleg)//2 + 1): hyp = int((smleg**2 + lgleg**2)**.5) peri = smleg + lgleg + hyp if peri <= bound and smleg**2 + lgleg**2 == hyp**2: solns[peri] += 1 if solns[peri] > solns[ret]: ret = peri return ret

I have a hard time letting such ugly code go, but I’m pretty sure I’m supposed to be spending my time doing other things anyway, so perhaps I should… move on to problem 40 🙂 Nearing a level-up on Project Euler…