Problem 39 – Perimeters of Right Triangles


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…


Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: