Project Euler Problem 840
A partition of n is a set of positive integers for which the sum equals n.
Solution
Answer: 194396971
Let
$$F(x)=\sum_{n\ge0}G(n)x^n.$$
Since each part $m$ in a partition contributes a factor $D(m)$, we have the Euler product
$$F(x)=\prod_{m\ge1}\frac1{1-D(m)x^m}.$$
Also, from
$$D(p)=1,\qquad D(ab)=D(a)b+aD(b),$$
it follows that $D(n)$ is the arithmetic derivative:
$$D(n)=n\sum_{p^a\parallel n}\frac{a}{p}.$$
Taking logarithmic derivatives of $F(x)$,
$$\frac{F'(x)}{F(x)} =\sum_{k\ge1} c_k x^{k-1},$$
where
$$c_k=\sum_{d\mid k} d,D(d)^{k/d}.$$
Thus the coefficients satisfy
$$n,G(n)=\sum_{k=1}^n c_k,G(n-k), \qquad G(0)=1.$$
Using a CDQ divide-and-conquer convolution with NTT/CRT arithmetic modulo
$$999676999,$$
one obtains:
$$S(50000)=\sum_{n=1}^{50000}G(n)\equiv 194396971 \pmod{999676999}.$$
Answer: 194396971