Project Euler Problem 75 Solution: Singular Integer Right Triangles

Project Euler Problem 75 Statement

It turns out that 12 cm is the smallest length of wire that can be bent to form an integer sided right angle triangle in exactly one way, but there are many more examples.

12 cm: (3,4,5)
24 cm: (6,8,10)
30 cm: (5,12,13)
36 cm: (9,12,15)
40 cm: (8,15,17)
48 cm: (12,16,20)

In contrast, some lengths of wire, like 20 cm, cannot be bent to form an integer sided right angle triangle, and other lengths allow more than one solution to be found; for example, using 120 cm it is possible to form exactly three different integer sided right angle triangles.

120 cm: (30,40,50), (20,48,52), (24,45,51)

Given that $L$ is the length of the wire, for how many values of $L \le 1\,500\,000$ can exactly one integer sided right angle triangle be formed?

Solution

This is an overview for solving HackerRank's version of Project Euler Problem 75. The problem (basically) concerns counting how many integer perimeters $L$ (up to some limit) allow exactly one unique integer right triangle with sides $(a, b, c)$. A "unique" right triangle means that there is exactly one set of integer side lengths $(a, b, c)$ (with $a^2 + b^2 = c^2$) that sums to that particular perimeter $L = a + b + c$.

1. Generating Pythagorean Triples

A well-known parameterization of primitive Pythagorean triples uses two positive integers $m$ and $n$ (with $m > n$, $\gcd(m,n) = 1$, and not both odd). The sides of the primitive triple generated by $(m,n)$ are:

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

and the perimeter of this primitive triple is:

$$p_{\text{primitive}} = 2\,m\,(m + n).$$

The code loops over $m$ (from 2 to 1700) and $n$ (from $m-1$ down to 1, skipping only even/odd conflicts) to generate all primitive Pythagorean triples' perimeters $p_{\text{primitive}}$. It then considers multiples $k \times p_{\text{primitive}}$, because every multiple of a primitive perimeter is also the perimeter of a (non-primitive) right triangle. This process covers all right triangles with perimeter up to $L = 5{,}000{,}001$.

2. Tracking Perimeters with Exactly One Solution

The program uses two Python sets, c and b, to keep track of perimeters:

c: Records perimeters that have been seen at least once.
b: Records perimeters that appear more than once.

The key line is:

(b if (v := k*s) in c else c).add(v)

- If a new perimeter $v$ has not been seen before, it is added to c.
- If it has been seen (i.e., $v$ is in c), then that means $v$ is now appearing again, so we add it to b.

After the nested loops finish, any perimeter remaining solely in c (and not in b) is a perimeter that appeared exactly once – i.e., exactly one right-triangle solution. Thus, the expression (c - b) represents all the perimeters with exactly one solution.

3. Building a Cumulative Array

The code then constructs an array f of length $L$ (5,000,001). It marks f[v] = 1 for all $v$ in $c - b$. Then it performs a prefix sum:

for i in range(1, L):
    f[i] += f[i-1]

Hence, $f[i]$ stores the total count of perimeters $\le i$ that have exactly one right-triangle solution.

When the code reads an input $N$, it simply outputs f[min(N, L)], which is the cumulative count up to $N$. In other words:

"How many perimeters $\le N$ have exactly one integer right-triangle solution?"

HackerRank version

Solves all test cases for Hackerrank Project Euler Problem 75

HackerRank Project Euler 75: Given that $L$ is the length of the wire, for how many values of $L\le N$ where $12\le N\le 10^6$ can exactly one integer sided right angle triangle be formed?

Python Source Code

from math import gcd
L = 5_000_001
c, b = set(), set()

for m in range(2, 1700):
    for n in range(m-1, 0, -2):
        if gcd(m, n) == 1:
            s = 2*m*(m + n)
            for k in range(1, L//s + 1):
                (b if (v := k*s) in c else c).add(v)

f = [0] * L
for v in (c-b): f[v] = 1
for i in range(1, L): f[i]+= f[i-1]

for _ in range(int(input())):
    N = int(input())
    print(f[min(N,L)])

Last Word

Nothing to add at this time.