Express a number as a sum of consecutive primes (How many ways?)

Question

I found this problem on codeforces in an ACM archive.

---

Given a number $n$, find the number possible of ways of expressing that number as a sum of consecutive primes. Example :

Given $n = 41$:

$41 = 41 = 2 +5+3 +7 + 11 + 13 = 11 + 13 + 17$

As we can see, there are three ways of writing $41$ as a sum of consecutive primes, keeping in mind that since $41$ is a prime, a sum that consists of only $41$ is a valid sum as well.

Knowing that $n \leq 10000$, list the number of ways you can express the input numbers as sums of consecutive primes.

---

My effort regarding this problem consists of the following :

Given that the max $n $ is $10000 $, I populated a vector of primes using the sieve of eratosthenes (its size is precisely $1229$).

Following, I computed a vector of prefix sums, such that at index $p$ of that particular vector, we have the sum of all consecutive primes up to inclusively $p$ (non prime indexed entries are equal to $0$).

For example: $\text{prime_sums[2] = 2 }, \text{ prime_sums[3] =5 },\text{ prime_sums[5] = 10}$, etc.

Now, using this particular vector we could simply do traversals of the sum array for each of the input numbers and upon finding a way to write it as a sum (by comparing its value with that of each sum we encounter) , we would do multiple subtractions between elements of the sum array in order to find other possible ways to express our number as a sum of consecutive primes.

But this kills the speed of the program and feels really inelegant and awkward. Can you suggest alternative ways?

Answer 1

I assume that n is large, and that we only want the answer for one single n. In that case, we would avoid creating a sieve of all the primes up to n, if possible, because it would take O (n); I think we can do this faster.

Create a list of all primes p ≤ M, using a sieve, with a cleverly chosen M. This takes about O (M) and finds about $M / \ln M$ primes. Then we find all solutions involving primes up to M by adding up primes starting with p = 2 until the sum is ≥ n, recording a solution if the sum equals n, removing the first primes until the sum is < n, adding primes until the sum is ≥ n etc. This only takes O ($M / \ln M)$ which is less than O (M) for the sieve, so we can ignore it.

This part of the algorithm finishes when we would need to add a prime p > M to the list (which we don't have). At that point we know that the sum of the K largest primes ≤ M is less than s, for some K, and that we have found every possible way to write n as the sum of more than K primes. Now we have to find ways to write n as the sum of k ≤ K consecutive primes; in addition k is odd if n is odd, and k is even if n is even.

For every k, we do this by creating a sieve of primes around n / k; this sieve should be large enough to contain more than k primes. When we have the sieve, we find the first k/2 primes > n/k and k - k/2 primes ≤ n/k. If the sum is less than n then we add the next larger prime and remove the smallest one until the sum is ≥ n; if the sum is > n then we add the next smaller prime and remove the next larger one until the sum is ≤ n. If the sieve turns out to be to small we create a bigger one. If the sum is n, we have a solution.

Creating the sieve takes at least O ($(n/k)^{1/2} / \log n$) steps for trial divisions. Instead of creating the sieve around n/k, we could have made the original sieve larger, choosing M ≈ n / (k - 2) instead of M ≈ n / k, which would have cost about $n / k^2$ steps.

Both costs balance when $n / k^2 = (n/k)^{1/2} / \log n$ or $n^{1/2} = k^{3/2} / \log n$ or $n \log^2 n = k^3$ or $k = (n \log^2 n)^{1/3}$ or $M = n/k = (n \div \log n)^{2/3}$

The estimate for creating the small sieves may have been a bit generous; if we use this method with $M = n^{2/3}$ then it should run in $O (n^{2/3})$.

Answer 2

You say the number of primes less than 10000 is $n=1229 \sim 10^3$. Let the primes be stored in increasing order in the array $primes$. Let $map$ be a C++ map ( inserting in C++ map has complexity $O(\log{n})$ ). Then do the following

 for i = 1 to i = n
   sum = 0
   for j = i to j = n
     sum = sum + primes[j]
     map[sum] = map[sum] + 1

(After this when given an input number $num$ just report $map[num]$ )

Complexity for above code becomes $O(n^2log(n^2))$. $n$ being around $1000$ I guess it is fast enough. ( This is almost similar to your approach and will mostly pass the judge ).