5
$\begingroup$

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?

$\endgroup$
  • 1
    $\begingroup$ Hint: If for example 8,000 is supposed to be the sum of four consecutive primes, they must all be around 2,000. If it is the sum of three consecutive primes, they must be around 2,666. For speed, examine sums of many primes and sums of few primes separately. $\endgroup$ – gnasher729 Nov 9 '16 at 0:39
2
$\begingroup$

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})$.

$\endgroup$
  • $\begingroup$ Nice! Instead of using a sieve for the second part, we could just sequentially test each number larger than $n/k$ (and each number small than $n/k$) with a primality test until we find $k$ primes near $n/k$. If $n$ is very large, this should be more efficient. In particular I think it leads to a running time of something like $O(n^{1/3})$ for large $n$. I don't know if it'll be a win for the parameter values considered in the question, though. Does this sound right to you? $\endgroup$ – D.W. Nov 9 '16 at 23:05
  • $\begingroup$ A small sieve around n/k should be only very little slower than primality test by trial division. I have never found at what range asymptotically faster methods beat trial division. Anyway, if you can find these primes in O ((n/k)^(1/3)) that's obviously better than O ((n/k)^(1/2)), so the boundary M between both methods would become smaller. $\endgroup$ – gnasher729 Nov 10 '16 at 19:58
  • $\begingroup$ The Sherman Lehman algorithm can factor integers in O (n^(1/3)), I wonder if it can be used to find factors of integers in a small interval simultaneously in the same time. $\endgroup$ – gnasher729 Nov 10 '16 at 20:52
  • $\begingroup$ We want the number of ways for a list of numbers, not just for one $n$.. $\endgroup$ – user43389 Nov 11 '16 at 19:45
1
$\begingroup$

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 ).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.