Project Euler Problem 748
Upside Down is a modification of the famous Pythagorean equation: A solution (x,y,z) to this equation with x,y and z pos
Solution
Answer: 276402862
Starting from
$$\frac1{x^2}+\frac1{y^2}=\frac{13}{z^2},$$
multiply through by $x^2y^2z^2$:
$$z^2(x^2+y^2)=13x^2y^2.$$
A standard parametrization arises by writing
$$x=qr,\qquad y=pr,\qquad z=pq,$$
which transforms the equation into
$$p^2+q^2=13r^2.$$
Primitive solutions to $p^2+q^2=13r^2$ are generated via Gaussian integers:
$$p+iq=(3+2i)(m+in)^2,$$
with $\gcd(m,n)=1$ and opposite parity.
Expanding:
$$u=m^2-n^2,\qquad v=2mn,$$
gives
$$p=|3u-2v|,\qquad q=|3v+2u|,$$
and
$$r=m^2+n^2.$$
Then
$$x=qr,\qquad y=pr,\qquad z=pq.$$
Enumerating all primitive solutions with
$$x,y,z\le 10^{16},$$
summing $x+y+z$, and taking the final result modulo $10^9$, yields
$$S(10^{16}) \equiv 276402862 \pmod{10^9}.$$
The parametrization reproduces the sample values:
- $S(10^2)=124$
- $S(10^3)=1470$
- $S(10^5)=2340084$
matching the problem statement.
Answer: 276402862