Project Euler Problem 537

Solution

Answer: 779429131

Let

$$a_m = #{x\in \mathbb Z_{>0} : \pi(x)=m}.$$

Then $T(n,k)$ is exactly the number of ways to choose $k$ values whose prime-count totals sum to $n$, i.e.

$$T(n,k)=\sum_{\substack{m_1+\cdots+m_k=n\m_i\ge 0}} a_{m_1}a_{m_2}\cdots a_{m_k}.$$

This is a generating-function problem.

For $m\ge 1$, $\pi(x)=m$ exactly when

$$p_m \le x < p_{m+1},$$

where $p_m$ is the $m$-th prime. Hence

$$a_m = p_{m+1}-p_m$$

(the prime gap), and $a_0=1$ because only $x=1$ has $\pi(x)=0$.

Define

$$A(z)=\sum_{m\ge0} a_m z^m.$$

Then

$$T(n,k)=[z^n]A(z)^k.$$

Since we only need $n=20000$, we truncate all polynomials to degree $20000$. The modulus

$$1004535809$$

is a classic NTT prime ($479\cdot 2^{21}+1$), allowing fast polynomial multiplication via the Number Theoretic Transform.

Algorithm:

Compute primes up to $p_{20001}$.
Build coefficients

$$a_0=1,\qquad a_m=p_{m+1}-p_m.$$ 3. Compute $A(z)^{20000}$ modulo $z^{20001}$ using binary exponentiation and NTT convolution. 4. Read coefficient of $z^{20000}$.

Sanity checks:

$T(3,3)=19$ ✔️
$T(10,10)=869985$ ✔️
$T(1000,1000)\equiv 578270566\pmod{1004535809}$ ✔️

The computation yields:

Answer: 779429131