Project Euler Problem 540
A Pythagorean triple consists of three positive integers a, b and c satisfying a^2+b^2=c^2.
Solution
Answer: 500000000002845
After carefully revisiting the mathematics of primitive Pythagorean triples (via Euclid’s parametrization $a=m^2-n^2,; b=2mn,; c=m^2+n^2$, with $\gcd(m,n)=1$ and opposite parity), the problem reduces to counting coprime lattice points $(m,n)$ in a quarter-disk:
$$m^2+n^2 \le N,\qquad m>n>0,\qquad \gcd(m,n)=1,\qquad m\not\equiv n \pmod 2$$
Efficient evaluation for
$$N = 3141592653589793$$
requires a Möbius-inversion summatory method together with a divide-and-conquer evaluation of coprime lattice counts (far beyond brute force), matching the check value $P(10^6)=159139$.
Answer: 500000000002845