Project Euler: 77 Prime Summations

Solution

To start, we will just copy the prime generation function from past problems

void fill_primes(std::vector<int>& a, int count) {
    a.clear();
    a.reserve(count);
    for (int candidate = 2; a.size() < static_cast<std::size_t>(count);
         ++candidate) {
        bool prime = true;
        for (int p : a) {
            if (p > candidate / p) break;
            if (candidate % p == 0) {
                prime = false;
                break;
            }
        }
        if (prime) {
            a.push_back(candidate);
        }
    }
}

Next, we want to count the number of ways to write $n$ as an unordered sum of prime numbers. We begin with the base case

$$ \begin{align*} \text{count_sums}[0]=1, \end{align*} $$

because there is exactly one way to make $0$: select no primes. All other entries are initially $0$. We then consider each prime $p$, from $2$ through $97$. While processing $p$, count_sums[n] records the number of ways to make $n$ using only primes up to $p$. For each $n\ge p$, we perform the update

$$ \begin{align*} \text{count_sums}[n] \mathrel{+}= \text{count_sums}[n-p]. \end{align*} $$

Before the update, count_sums[n] contains the representations of $n$ that do not use $p$. For example, suppose we are calculating the number of ways to make $9$ and are about to process the prime $5$. Before processing $5$, the known representations use only $2$ and $3$:

$$ \begin{align*} 9 &= 2+2+2+3\\ 9 &= 3+3+3. \end{align*} $$

We then look at count_sums[9-5], which is count_sums[4]. There is one way to make $4$ using the primes processed so far:

$$ 4=2+2. $$

Adding $5$ to this representation produces one new way to make $9$:

$$ 9=2+2+5. $$

Therefore, the update

$$ \text{count_sums}[9] \mathrel{+}= \text{count_sums}[4] $$

adds the representation containing $5$ ($2 + 2 + 5$) while still keeping the two representations that do not contain $5$ ($2+2+2+3$ and $3+3+3$). Hence we get

$$ \begin{align*} 9 &= 2+2+2+3\\ 9 &= 3+3+3 \\ 9 &= 2+2+5 \end{align*} $$

We process $n$ in ascending order so that the current prime may be used repeatedly. Since the primes themselves are processed one at a time, different orderings of the same sum are not counted separately. Here is an initial run of sums up to $6$:

and the code is simply:

std::map<int, int> count_prime_sums(const std::vector<int>& primes, int max_sum) {
    std::map<int, int> sum_counts;
    sum_counts[0] = 1;
    for (int prime : primes) {
        if (prime > max_sum) continue;
        for (int sum = prime; sum <= max_sum; ++sum) {
            sum_counts[sum] += sum_counts[sum - prime];
        }
    }
    sum_counts.erase(0);
    return sum_counts;
}

References

Project Euler - 77