Project Euler Problem 650

Project Euler Problem 650

Solution

Answer: 538319652

Let

$$B(n)=\prod_{k=0}^{n}\binom{n}{k}$$

and

$$D(n)=\sum_{d\mid B(n)} d$$

with

$$S(n)=\sum_{k=1}^{n} D(k).$$

We need $S(20000)\bmod 1,000,000,007$.

Key mathematical idea

Using factorials:

$$\binom{n}{k}=\frac{n!}{k!(n-k)!}$$

so

$$B(n) = \prod_{k=0}^{n}\binom{n}{k} = \frac{(n!)^{n+1}} {\left(\prod_{k=0}^{n}k!\right)^2}.$$

For a prime $p$, let $v_p(m)$ denote the exponent of $p$ in $m$. Then

$$v_p(B(n)) = (n+1)v_p(n!) - 2\sum_{k=1}^{n} v_p(k!).$$

A more computationally useful form comes from expanding the factorial valuations:

$$v_p(B(n)) = \sum_{i=1}^{n}(2i-n-1),v_p(i).$$

If

$$B(n)=\prod_p p^{e_p(n)},$$

then the divisor sum is multiplicative:

$$D(n) = \prod_p \left( 1+p+\cdots+p^{e_p(n)} \right) = \prod_p \frac{p^{e_p(n)+1}-1}{p-1}.$$

The efficient algorithm maintains the prime exponents incrementally for all $n\le 20000$, updating the valuation state instead of recomputing factorizations from scratch.

Verification against given values

The implementation reproduces the supplied checks:

• $S(5)=5736$
• $S(100)\bmod 1,000,000,007 = 332792866$

and then computes $S(20000)$.

Answer: 538319652