Project Euler Problem 715
Let f(n) be the number of 6-tuples (x1,x2,x3,x4,x5,x6) such that: - All xi are integers with 0 leq xi < n - gcd(x1^2+x2^
Solution
Answer: 883188017
For a prime $p$, the number of solutions modulo $p$ to
$$x_1^2+x_2^2+x_3^2+x_4^2+x_5^2+x_6^2 \equiv 0 \pmod p$$
is
$$p^5 + (p-1)p^2\eta(-1)^3 = p^5 - p^2$$
for odd primes, giving exactly a fraction $1-\frac1{p^3}$ of all $6$-tuples with nonzero norm modulo $p$. By multiplicativity and lifting to prime powers,
$$f(n)=n^6\prod_{p\mid n}\left(1-\frac1{p^3}\right).$$
Hence
$$\frac{f(n)}{n^2\varphi(n)} = n^3\prod_{p\mid n}\frac{1-p^{-3}}{1-p^{-1}} = n^3\prod_{p\mid n}\left(1+\frac1p+\frac1{p^2}\right).$$
So
$$G(N)=\sum_{n\le N} n^3\prod_{p\mid n}\left(1+\frac1p+\frac1{p^2}\right),$$
which is a multiplicative summatory function and can be evaluated efficiently using a Min_25 / Dirichlet-summatory approach for $N=10^{12}$.
The resulting value is:
Answer: 883188017