Project Euler Problem 39

Solution

Answer: 840

We seek the perimeter $p \le 1000$ that yields the largest number of integer right-triangle solutions $(a,b,c)$ satisfying

$$a^2+b^2=c^2,\qquad a+b+c=p$$

where $a,b,c$ are positive integers.

1. Mathematical analysis

A right triangle with integer side lengths is a Pythagorean triple:

$$a^2+b^2=c^2$$

We want to count how many triples exist for each perimeter $p\le 1000$.

Since order does not matter, assume:

$$a \le b < c$$

Then:

$$a+b+c=p$$

Substitute:

$$c = p-a-b$$

into the Pythagorean equation:

$$a^2+b^2=(p-a-b)^2$$

Expanding:

$$a^2+b^2 = p^2+a^2+b^2-2pa-2pb+2ab$$

Cancel $a^2+b^2$:

$$0=p^2-2p(a+b)+2ab$$

Rearrange:

$$2ab = 2p(a+b)-p^2$$

For a fixed perimeter $p$, we can efficiently enumerate integer values of $a,b$ and check whether

$$c=\sqrt{a^2+b^2}$$

is integral and whether

$$a+b+c=p.$$

Search bounds

Since $a \le b < c$,

$$a < \frac{p}{3}$$

and

$$b < \frac{p-a}{2}$$

which significantly reduces the search space.

Example: $p=120$

The problem states three solutions:

$$(20,48,52)$$

$$(24,45,51)$$

$$(30,40,50)$$

Indeed:

$20^2+48^2=52^2$
$24^2+45^2=51^2$
$30^2+40^2=50^2$

So $p=120$ has exactly 3 solutions.

2. Python implementation

def count_solutions(p):
    """
    Count the number of integer right-triangle solutions
    with perimeter p.
    """
    count = 0

    # Ensure a <= b < c
    for a in range(1, p // 3 + 1):
        for b in range(a, (p - a) // 2 + 1):
            c = p - a - b

            # Check Pythagorean condition
            if a * a + b * b == c * c:
                count += 1

    return count

max_count = 0
best_p = 0

# Test every perimeter up to 1000
for p in range(1, 1001):
    solutions = count_solutions(p)

    if solutions > max_count:
        max_count = solutions
        best_p = p

print(best_p)

3. Code walkthrough

`count_solutions(p)`

This function counts valid right triangles for perimeter p.

for a in range(1, p // 3 + 1):

Since $a<b<c$, the smallest side cannot exceed $p/3$.

for b in range(a, (p - a) // 2 + 1):

We enforce $a \le b$, and because $c>b$,

$$b < \frac{p-a}{2}$$

Then:

c = p - a - b

Since perimeter is fixed.

We test:

if a * a + b * b == c * c:

which verifies the triangle is right-angled.

Confirming the example $p=120$

Running:

count_solutions(120)

returns:

matching the problem statement exactly.

4. Final verification

The maximizing perimeter should:

be even, since almost all Pythagorean triple perimeters are even;
have many factor combinations (high divisibility);
plausibly be a multiple of several primitive triples.

Executing the search gives:

$$p = 840$$

which has 8 distinct integer right-triangle solutions, the maximum for $p \le 1000$.

Answer: 840