Problem 249: Prime Subset Sums

Mathematical Foundation

Theorem 1 (Subset-sum counting via 0/1 knapsack DP). Let $p_1 < p_2 < \cdots < p_K$ be the primes less than $5000$ (where $K = 669$), and let $\sigma = \sum_{i=1}^{K} p_i = 1{,}548{,}136$. Define $dp[s]$ as the number of subsets of $\{p_1, \ldots, p_K\}$ that sum to exactly $s$, reduced modulo $M = 10^{16}$. Then the standard 0/1 knapsack recurrence correctly computes $dp[s]$ for all $0 \le s \le \sigma$.

Proof. We prove by induction on $j$ that after processing primes $p_1, \ldots, p_j$, $dp[s]$ equals (mod $M$) the number of subsets of $\{p_1, \ldots, p_j\}$ summing to $s$.

Base case ($j = 0$): $dp[0] = 1$ (empty subset), $dp[s] = 0$ for $s > 0$. Correct.

Inductive step: Assume the claim holds after $j - 1$ primes. When processing $p_j$, for $s$ from $\sigma$ down to $p_j$, we update $dp[s] \leftarrow dp[s] + dp[s - p_j]$. The reverse iteration ensures that the value $dp[s - p_j]$ used is from the $(j-1)$-th stage (before $p_j$ was available). Thus:

• $dp[s]$ after update $=$ (subsets of $\{p_1,\ldots,p_{j-1}\}$ summing to $s$) $+$ (subsets of $\{p_1,\ldots,p_{j-1}\}$ summing to $s - p_j$). The first term counts subsets not containing $p_j$; the second counts subsets containing $p_j$ (since adding $p_j$ to a subset summing to $s - p_j$ gives a subset summing to $s$). Together, these are exactly the subsets of $\{p_1,\ldots,p_j\}$ summing to $s$. $\square$

Lemma 1 (Prime sieve correctness). The Sieve of Eratosthenes correctly identifies all primes up to $N$ in $O(N \log \log N)$ time.

Proof. Classical result. Each composite $n \le N$ has a prime factor $p \le \sqrt{N}$, so it is marked during the sieve of $p$. No prime is ever marked. $\square$

Theorem 2 (Final summation). The answer is

Proof. Each subset with prime sum contributes exactly 1 to $dp[s]$ for exactly one prime $s$. Summing $dp[s]$ over prime $s$ counts each qualifying subset once. $\square$

Editorial

We collect primes below 5000. We then 0/1 Knapsack DP. Finally, sum over prime target sums. We use dynamic programming over the state space implied by the derivation, apply each admissible transition, and read the answer from the final table entry.

Pseudocode

Sieve primes up to sigma = 1,548,136
Collect primes below 5000
|primes_5000| = 669
0/1 Knapsack DP
Sum over prime target sums

Complexity Analysis

• Time: The DP performs $K \times \sigma = 669 \times 1{,}548{,}136 \approx 1.04 \times 10^9$ additions modulo $10^{16}$. The sieve takes $O(\sigma \log \log \sigma)$. The final summation is $O(\sigma)$. Total: $O(K \cdot \sigma)$.
• Space: $O(\sigma) = O(1{,}548{,}136)$ for the DP array and sieve, approximately 12 MB for 64-bit entries.

Answer

#include <bits/stdc++.h>
using namespace std;

int main() {
    const unsigned long long MOD = 10000000000000000ULL; // 10^16

    // Generate all primes below 5000
    const int LIMIT = 5000;
    vector<bool> sieve(LIMIT, true);
    sieve[0] = sieve[1] = false;
    for (int i = 2; i * i < LIMIT; i++)
        if (sieve[i])
            for (int j = i * i; j < LIMIT; j += i)
                sieve[j] = false;

    vector<int> primes;
    for (int i = 2; i < LIMIT; i++)
        if (sieve[i]) primes.push_back(i);

    long long S = 0;
    for (int p : primes) S += p;

    // Sieve up to S for final primality check
    vector<bool> is_prime(S + 1, true);
    is_prime[0] = is_prime[1] = false;
    for (long long i = 2; i * i <= S; i++)
        if (is_prime[i])
            for (long long j = i * i; j <= S; j += i)
                is_prime[j] = false;

    // DP: 0/1 knapsack
    vector<unsigned long long> dp(S + 1, 0);
    dp[0] = 1;

    for (int p : primes) {
        for (long long s = S; s >= p; s--) {
            dp[s] += dp[s - p];
            if (dp[s] >= MOD) dp[s] -= MOD;
        }
    }

    unsigned long long answer = 0;
    for (long long s = 2; s <= S; s++) {
        if (is_prime[s]) {
            answer += dp[s];
            if (answer >= MOD) answer -= MOD;
        }
    }

    cout << answer << endl;
    return 0;
}

def solve():
    """
    Problem 249: Prime Subset Sums
    Count subsets of primes below 5000 whose sum is prime, mod 10^16.
    """
    MOD = 10**16
    LIMIT = 5000

    # Sieve to get all primes below 5000
    is_prime_sieve = [True] * LIMIT
    is_prime_sieve[0] = is_prime_sieve[1] = False
    for i in range(2, int(LIMIT**0.5) + 1):
        if is_prime_sieve[i]:
            for j in range(i*i, LIMIT, i):
                is_prime_sieve[j] = False

    primes = [i for i in range(2, LIMIT) if is_prime_sieve[i]]
    S = sum(primes)

    # Sieve up to S
    is_prime = bytearray(S + 1)
    for i in range(2, S + 1):
        is_prime[i] = 1
    for i in range(2, int(S**0.5) + 1):
        if is_prime[i]:
            for j in range(i*i, S + 1, i):
                is_prime[j] = 0

    # DP (0/1 knapsack)
    dp = [0] * (S + 1)
    dp[0] = 1

    for p in primes:
        for s in range(S, p - 1, -1):
            dp[s] = (dp[s] + dp[s - p]) % MOD

    answer = 0
    for s in range(2, S + 1):
        if is_prime[s]:
            answer = (answer + dp[s]) % MOD

    print(answer)

solve()