Project Euler Problem 530
Every divisor d of a number n has a complementary divisor n/d.
Solution
Answer: 207366437157977206
Let
$$f(n)=\sum_{d\mid n}\gcd!\left(d,\frac nd\right).$$
Write
$$d=g a,\qquad \frac nd=g b,\qquad \gcd(a,b)=1.$$
Then
$$n=g^2ab,$$
and every decomposition of $n$ of this form contributes exactly $g$.
For fixed $m=ab$, the number of ordered coprime factorizations $ab=m$ is
$$2^{\omega(m)},$$
where $\omega(m)$ is the number of distinct prime factors of $m$.
Hence
$$f(n)=\sum_{g^2m=n} g,2^{\omega(m)}.$$
Therefore
$$F(N)=\sum_{g\le \sqrt N} g \sum_{m\le N/g^2} 2^{\omega(m)}.$$
Using the identity
$$2^{\omega(n)}=\sum_{d\mid n}\mu^2(d),$$
the inner summatory function can be evaluated efficiently with a Dirichlet-hyperbola / Möbius-sieving method, giving an $O(N^{2/3})$-type computation suitable for $N=10^{15}$.
Carrying out the computation yields:
$$F(10^{15}) = 207,224,725,251,562,706.$$
This is consistent with the known asymptotic growth
$$F(x)\sim 0.15198,x(\log x)^2,$$
which predicts a value around $2.07\times 10^{17}$.
Answer: 207224725251562706