Detailed mathematical approach

Problem Summary

We consider all lists of strictly increasing primes whose sum is a target \(N\). These lists are sorted in lexicographic order, and the required list is the median list. When the number of lists is even, the last list is ignored first; equivalently, if there are \(M\) lists, the required one has one-based rank

$$r=\left\lfloor\frac{M+1}{2}\right\rfloor.$$

For \(N=20\), the four lists are \((2,5,13)\), \((2,7,11)\), \((3,17)\), and \((7,13)\). Since \(M=4\), the effective median rank is \(2\), giving \((2,7,11)\). The actual problem asks for \(N=2026\), and only the last nine digits of the product of the primes in the median list are needed.

Mathematical Approach

Prime lists are subsets with a canonical order

Because every list is strictly increasing, each valid list is exactly a subset of the primes not exceeding \(N\), written in increasing order, whose elements sum to \(N\). If

$$p_0 \lt p_1 \lt \cdots \lt p_{m-1}$$

are the primes at most \(N\), the problem is not to enumerate every subset, but to count enough subsets to jump directly to the median in lexicographic order.

The strict increase is important: after choosing \(p_i\), every later prime in the same list must come from \(p_{i+1},p_{i+2},\dots\). This creates a natural suffix dynamic program.

Counting completions from a suffix

Define

$$C(i,s)=\#\left\{A\subseteq\{p_i,p_{i+1},\dots,p_{m-1}\}:\sum_{p\in A}p=s\right\}.$$

The boundary condition is

$$C(m,0)=1,\qquad C(m,s)=0\quad(s\gt0).$$

For \(i\lt m\), either \(p_i\) is skipped or it is used. Therefore

$$C(i,s)=C(i+1,s)+ \begin{cases} C(i+1,s-p_i), & s\ge p_i,\\ 0, & s\lt p_i. \end{cases}$$

This is the subset-sum recurrence, but the table is used as a ranking oracle rather than just as a yes/no feasibility test. The total number of prime lists is \(M=C(0,N)\). These counts can be large, so the implementations use arbitrary-precision integers for the DP table.

Why suffix counts match lexicographic blocks

In lexicographic order, all lists whose first element is \(p_a\) appear before all lists whose first element is \(p_b\) whenever \(p_a\lt p_b\). If we try a candidate first prime \(p_i\), the number of lists beginning with that prime is exactly

$$C(i+1,N-p_i),$$

because the remaining entries must be chosen from strictly larger primes and must sum to \(N-p_i\). Thus each candidate first prime forms one contiguous lexicographic block.

The same idea applies after a prefix has already been fixed. If the current prefix ends at index \(i\), the next candidate \(p_j\) contributes a block of size

$$C(j+1,R-p_j).$$

This block size tells us whether the desired rank lies inside that block or after it.

Unranking the median list

Set \(r=\lfloor(M+1)/2\rfloor\). Start with remaining sum \(N\) and the first allowable prime index \(0\). Scan candidate primes in increasing order. For a candidate \(p_i\), compute

$$B_i=C(i+1,R-p_i).$$

If \(r>B_i\), the whole block beginning with \(p_i\) is before the median, so subtract it:

$$r\leftarrow r-B_i.$$

If \(r\le B_i\), the median list begins, or continues, with \(p_i\). Append \(p_i\), decrease the remaining sum by \(p_i\), and continue with candidates after \(i\). When the remaining sum becomes \(0\), the list has been reconstructed without enumerating all lists.

Worked example: \(N=20\)

The DP gives \(C(0,20)=4\), so \(r=\lfloor(4+1)/2\rfloor=2\). The first candidate \(2\) has

$$C(1,18)=2,$$

corresponding to \((2,5,13)\) and \((2,7,11)\). Since \(r=2\) lies inside this block, the first element is \(2\).

Now the remaining sum is \(18\). Candidate \(3\) has no valid completion, candidate \(5\) has one completion \((13)\), and candidate \(7\) has one completion \((11)\). After skipping the block for \(5\), the rank becomes \(1\), so \(7\) is selected. The final remaining sum is \(11\), forcing the last prime \(11\). Hence the median list is \((2,7,11)\).

How the Code Works

primes_up_to builds the prime list by a sieve. build_dp fills the suffix table \(C(i,s)\) from the last prime backward, using arbitrary-precision counts because the number of prime subsets can exceed fixed-width integer ranges.

kth_prime_list performs the lexicographic unranking. For each candidate prime it asks the DP table how many valid completions exist. Entire blocks are skipped by subtracting their sizes from the rank; the first block containing the rank determines the next prime in the answer.

median_prime_list converts the total count into the median rank \((M+1)//2\). Finally product_mod multiplies the selected primes modulo \(10^9\), which is enough because only the last nine digits are requested.

The checkpoint suite explicitly checks the \(N=20\) example and brute-forces every target from \(2\) through \(60\), verifying that the DP count, first rank, median rank, and last rank all match direct enumeration.

Complexity Analysis

Let \(m=\pi(N)\), the number of primes at most \(N\). The DP table has \((m+1)(N+1)\) entries and is filled in \(O(mN)\) arithmetic operations. The unranking pass scans primes at each selected position, bounded by \(O(mL)\), where \(L\) is the length of the median list; this is dominated by the DP for the given target.

The memory usage is \(O(mN)\) arbitrary-precision integers. For \(N=2026\), \(m=306\), so the table is small in practical terms.

Footnotes and References

1. Problem page: Project Euler 1005 - Median Prime List
2. Subset sum problem: Wikipedia - Subset sum problem
3. Dynamic programming: Wikipedia - Dynamic programming
4. Lexicographic order: Wikipedia - Lexicographic order
5. Sieve of Eratosthenes: Wikipedia - Sieve of Eratosthenes