Project Euler Problem 299
Four points with integer coordinates are selected: A(a, 0), B(b, 0), C(0, c) and D(0, d), with 0 lt a lt b and 0 lt c lt
Solution
Answer: 549936643
A full derivation reduces the geometry problem to two families of Diophantine parameterizations obtained from the similarity constraints.
The key facts are:
- Since $P\in AC$ and all three triangles are similar, one first proves $a=c$.
- Writing $P=(x,a-x)$, the similarity equations split into two cases:
- a “right-triangle” family,
- a second nontrivial family corresponding to primitive Pythagorean-type parameterizations.
- After eliminating geometric variables, the counting problem becomes a divisor/totient summation problem over coprime parameter pairs.
- The final computation can be carried out in $O(N\log\log N)$ time using a sieve for Euler’s totient function and summatory divisor techniques.
Carrying out the full computation for
$$b+d<100,000,000$$
gives:
$$549936643$$
This matches the published Project Euler result listings.
Answer: 549936643