Project Euler Solution 75: Singular integer right triangles
In Project Euler Problem 75: Singular Integer Right Triangles we take a look at the Pythogorean theorem.
We have the theorem $a^2 + b^2 = c^2$. For a given circumference $L = a + b + c$ there may be zero, one or more ways to form a right triangle. We are asked to find the number of values of $L \leq 1\,500\,000$ for which there is exactly one particular way $(a, b, c)$ to make a triangle.
If we would naively try to go through all $a$, $b$ and $c$ we would not be able to finish in time. Here it helps to take a look into the Wikipedia article about Pythagorean triplets, which are exactly the numbers that we are looking for.
There is one particular way of enumerating them given there. One uses the integers $m > n > 0$, $k > 0$ and the prescription $a = k (m^2 - n^2)$, $b = 2 k m n$ and $c = k (m^2 + n^2)$. We can use those to enumerate these triplets. We just record the triplets according to their length. And then after having enumerated all with a length $L$ below the ceiling, we can see how many of the lengths only have one Pythagorean triplet associated with them.
def solution() -> None: ceiling = 1_500_000 solutions = collections.defaultdict(set) for m in range(2, int(math.sqrt(ceiling))): for n in range(1, m): a = m**2 - n**2 b = 2 * m * n c = m**2 + n**2 length = a + b + c if length > ceiling: break for k in itertools.count(1): if k * length > ceiling: break solutions[k * length].add((min(k * a, k * b), max(k * a, k * b), k * c)) return sum(len(elements) == 1 for elements in solutions.values())
This gives the correct answer in 3.7 s.
There are more clever enumeration schemes. We produce a bunch of them redundantly, we could likely improve this further by looking into other enumeration techniques.