The Problem

If p is the perimeter of a right angle triangle with integral length sides, {a,b,c}, there are exactly three solutions for p = 120.

{20,48,52}, {24,45,51}, {30,40,50}

For which value of p ≤ 1000, is the number of solutions maximised?

The Solution

So, the solution to this is fairly straightforward. The general plan of attack is to:

• Generate all the possible p values
• For each p, generate a and b values that fit within p
• With a and b we can compute c as p-(a+b)
• If a*a + b*b = c*c then we know we have a right triangle
• Count the number of right triangles we can make
• The p that is able to make the most right triangles is the answer.

Almost all of that is easy. The hard question is: how do you generate the a and b values?

You could simply say that a is 1..p-1 and b is 1..p-a. However, this generates a lot of combinations and, on the machine I originally used for this problem, it blew out the 1-minute time limit.

So we need better limits for a and b.

I am not a math guy, which limits my ability to solve some of these problems. So I consulted my friend Tony Jenkins who is a math guy who explained it to me like this:

We observe that c must always be greater than a or b, so we see that the maximum value of c in relation to p occurs when either a or b approaches 0.

Start with the Pythagorean Theorem. Let b=0. Then a*a = c*c which implies a=c. We already stated that c>a.

Now apply the definition of the perimiter. a+b+c = p, but we know that b = 0 so a + c = p.

Substitution: a = c, which implies 2*c = p.

Bring it all together: Divide by 2 and acknowledge the inequality to get:

c < 0.5 so we have our upper bound for c for a right triangle of perimiter p.

Now let's find the lower bound.

Observing our right triangle, we see that c min in relation to p occurs when a = b.

Back to the Pythagorean Theorem:

a*a + b*b = c*c

Substitution:

Let a = b. Then (2*a)*(2*a) = c*c

Solve for a:

a = c / sqrt 2

We know a + b + c = p. Substitute for a and we get:

2 * (c / sqrt 2)) + c = p => (2/sqrt 2 ) * c + c = p

Factor out c

c * (1 + (2/sqrt 2)) = p

Solve for c:

c = p/((1 + (2/sqrt 2)))

So after rationalizing the denominator:

c = (sqrt 2 – 1) * p (our lower bound for c, on a right triangle of perimeter p).

c is approximately 0.41 * p

So, for right triangles of hypoteneuse c, with perimeter p:

.41p <= c < .5p

Whew! Thanks, Tony!

In retrospect, I remember enough algebra and geometry to have figured this out on my own, but it helps to have an authoritative answer.

What this means for me, practically speaking, is that when generating my sequence of a,b I can cap them out at about 0.59 * p. I'll still be generating invalid combinations, but we can filter those out later. The point is to limit the combinations we generate as best we can from the get-go and only apply more complex filters if we have to. This makes things faster.

With that in mind, we can generate possible a,b values for p. We'll let a go all the way to the upper bound, and restrict b to the upper bound minus a.

let generateAB p =
    seq {
        for a in 1..(59*p/100) do
            for b in 1..(59*p/100 - a) -> (a,b)
    }

Now we'll generate right triangles that fit inside p:

let isRight a b c = a*a+b*b=c*c

let intsqrt i = int(sqrt(float i))

let generateTriangles p =
    generateAB p
    |> Seq.map (fun (a,b) -> (a,b,intsqrt(a*a+b*b)))
    |> Seq.filter (fun (a,b,c) -> a + b + c = p && isRight a b c)
    |> Seq.map (fun (a, b, c) -> [a; b; c] |> List.sort)
    |> Seq.distinct

The generateTriangles function starts by generating the possible a and b values.

Next, it computes c using the Pythagorean Theorem.

Next, it filters out any a,b,c that isn't a right triangle.

Finally, it converts the tuple to a List, sorts it, then filters out any duplicates.

Now we can get the answer:

#time
[3..1000]
|> List.map (fun p -> (p,generateTriangles p))
|> Seq.maxBy (fun (_,l) -> Seq.length l)
|> fst
#time

We start with the list of possible p values. We start at 3 because the problem definition specifies that the side lengths are integers. The smallest p is 3, i.e. when a and b and c are all 1.

We map the list of p to the right triangles that fit within it, find the p with the maximum number of right triangles, and that is our answer.

Other Posts in This Series