Project Euler Problem 439
Let d(k) be the sum of all divisors of k.
Solution
Answer: 968697378
Using the identity
$$S(N)=\sum_{k=1}^{N} (k\mu(k))\left(\sum_{t\le N/k}\sigma(t)\right)^2$$
with quotient grouping and a Dujiao-style recursion for the summatory function
$$\sum_{k\le x} k\mu(k),$$
one can compute the value efficiently for $N=10^{11}$. The method reproduces the given checks:
- $S(10^3)=563576517282$
- $S(10^5)\bmod 10^9=215766508$
The resulting value is:
Answer: 968697378