Solution

Answer: 161667

The key to this problem is the structure of all integer right triangles.

A Pythagorean triple $(a,b,c)$ satisfies

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

and its perimeter is

$$L=a+b+c.$$

We need to count how many $L \le 1{,}500{,}000$ correspond to exactly one integer right triangle.

Mathematical analysis

Every primitive Pythagorean triple can be generated uniquely by Euclid’s formula:

$$a=m^2-n^2,\qquad b=2mn,\qquad c=m^2+n^2$$

where

$m>n>0$,
$\gcd(m,n)=1$,
one of $m,n$ is even and the other odd.

Then the perimeter is

$$L=a+b+c.$$

Substitute:

$$L=(m^2-n^2)+(2mn)+(m^2+n^2)$$

which simplifies to

$$L=2m(m+n).$$

Every non-primitive triple is just a multiple:

$$(k a,; k b,; k c)$$

with perimeter

$$kL.$$

So the strategy is:

Generate every primitive perimeter

$$p=2m(m+n)\le1{,}500{,}000.$$ 2. For every multiple $kp$, increment a counter. 3. Count how many perimeters were hit exactly once.

Bounds on $m$

Since

$$2m(m+n)\le N$$

and $n\ge1$,

$$2m(m+1)\le N.$$

Thus approximately

$$m \lesssim \sqrt{N/2}.$$

For $N=1{,}500{,}000$,

$$m \lesssim 866.$$

So brute force over valid $(m,n)$ pairs is very feasible.

Python implementation

from math import gcd

LIMIT = 1_500_000

# counts[L] = number of different right triangles with perimeter L
counts = [0] * (LIMIT + 1)

m = 2

# Generate primitive triples using Euclid's formula
while 2 * m * (m + 1) <= LIMIT:

    for n in range(1, m):

        # Primitive triple conditions:
        # 1. m and n coprime
        # 2. opposite parity
        if ((m - n) % 2 == 1) and gcd(m, n) == 1:

            primitive_perimeter = 2 * m * (m + n)

            # Add all multiples of this primitive perimeter
            for p in range(primitive_perimeter, LIMIT + 1, primitive_perimeter):
                counts[p] += 1

    m += 1

# Count perimeters with exactly one representation
answer = sum(1 for x in counts if x == 1)

print(answer)

Code walkthrough

1. Create the counter array

counts = [0] * (LIMIT + 1)

counts[L] will store how many distinct integer right triangles have perimeter $L$.

2. Generate primitive triples

while 2 * m * (m + 1) <= LIMIT:

This guarantees even the smallest perimeter for this $m$ fits inside the limit.

3. Loop over $n$

for n in range(1, m):

Euclid’s formula requires $m>n$.

4. Check primitive conditions

if ((m - n) % 2 == 1) and gcd(m, n) == 1:

These ensure the triple is primitive.

opposite parity,
coprime.

5. Compute perimeter

primitive_perimeter = 2 * m * (m + n)

Derived directly from Euclid’s formula.

6. Mark all multiples

for p in range(primitive_perimeter, LIMIT + 1, primitive_perimeter):
    counts[p] += 1

Every multiple of a primitive triple is also a valid triple.

7. Count unique perimeters

answer = sum(1 for x in counts if x == 1)

We only want perimeters with exactly one representation.

Small-example verification

The problem statement gives:

$12 \to (3,4,5)$
$24 \to (6,8,10)$
$30 \to (5,12,13)$

Each has exactly one triangle.

For $120$:

$(30,40,50)$
$(20,48,52)$
$(24,45,51)$

so counts[120] == 3.

The algorithm reproduces all of these correctly.

Final verification

The search space is small enough that the algorithm runs quickly.

Complexity is roughly harmonic:

$$O(N \log N)$$

style behavior from stepping through multiples.

Every integer right triangle is generated exactly once from a unique primitive source plus scaling factor.

This is the standard efficient solution for this Euler problem.

Answer: 161667

Project Euler Problem 75