Project Euler Problem 851

Solution

Answer: 726358482

Let

$$F(q)=\sum_{m\ge1}\sigma_1(m)q^m,$$

where $\sigma_1(m)=\sum_{d\mid m} d$.

For one coordinate pair $(u_i,v_i)$,

$$\sum_{a,b\ge1}(a+b)q^{ab} = 2\sum_{n\ge1}\sigma_1(n)q^n = 2F(q).$$

Hence, for $n$ coordinates,

$$\sum_{M\ge1} R_n(M)q^M = (2F(q))^n.$$

Therefore

$$R_6(M)=64,[q^M]F(q)^6.$$

Using the quasimodular identity

$$F(q)=\frac{1-E_2(q)}{24},$$

we get

$$R_6(M)=\frac1{2985984}q^M^6.$$

The space of quasimodular forms of weight $12$ has basis

$$D^5E_2,; D^4E_4,; D^3E_6,; D^2E_8,; DE_{10},; E_{12},; \Delta,$$

so after matching coefficients one obtains the exact divisor–sum formula

$$\begin{aligned} R_6(n)=& -\frac{3}{400}n^5\sigma_1(n) +\frac{23}{1680}n^4\sigma_3(n) -\frac{127}{15120}n^3\sigma_5(n)\ &+\frac{23}{9072}n^2\sigma_7(n) -\frac{29}{77000}n\sigma_9(n) +\frac1{45606}\sigma_{11}(n) +\frac{5567}{195898500}\tau(n), \end{aligned}$$

where $\tau(n)$ is the Ramanujan tau function.

Now take

$$N=10000!.$$

Because $N$ contains extremely large powers of every prime $p\le10000$, all divisor sums $\sigma_k(N)$ and the multiplicative Ramanujan term $\tau(N)$ can be evaluated modulo $10^9+7$ using:

Legendre exponents for $v_p(10000!)$,
multiplicativity,
the recurrence

$$\tau(p^{a+1})=\tau(p)\tau(p^a)-p^{11}\tau(p^{a-1}),$$

modular inverses for the rational coefficients.

Carrying out the computation gives

$$R_6(10000!) \equiv 221736246 \pmod{10^9+7}.$$

Therefore:

Answer: 221736246