Find least number of primes required to sum up to a given integer less than 1000

Question

This is a programming challenge that I faced recently.

You are given a number less than 1000 you need to determine how many least number of primes are required that sum to given number.

Examples:

12: 2 (since 12=7+5)
14: 2  (since 14 = 7+7)

If it is not possible to split given number into sum of primes then return -1.

Here are few test cases:

88:2
117:3
374:2
363:3
11:1

Answer 1

In short: the maximum number of primes for a number is 3. Since there are only 168 prime numbers less than 1'000, we can exhaustively on the combination of two primes, or default on 3. By using some extra properties, we can find out easily the minimum number of elements, and even construct a collection of those numbers.

We can solve the problem if we assume we have access to a list of primes up to 1'000, there are 168 of those.

Given that the number is a prime number, then evidently the answer is 1.

For non-prime numbers, we will have to find different means to solve the problem.

Goldbach's conjecture [wiki] states that

Every even integer greater than 2 can be expressed as the sum of two primes.

This conjecture is not proven in general, but at least know to hold for all numbers up to 4×10¹⁸.

This thus means that for n = 2, the answer is 1, and for for an even n > 2, the answer is 2 (since there is only one even prime).

In case the number is odd, and non-prime, we know that the maximum number of prime numbers is 3. Indeed, since if we subtract 3 from that number, we get an even number, which can be composed out of 2 or three elements. Apparently this is known as Goldbach's marginal conjecture [wiki]:

Every integer greater than 5 can be written as the sum of three primes.

The only way we can improve that upperbound is by finding two prime numbers that sum up to the given number. This thus requires iterating over all the prime numbers (up to at most 1'000), and checking if there if n - p is a prime number as well. We can however, as @ AlexanderZhang says, just subtract 2, since that is the only even number that would result in an odd number, and thus is a candidate to be a prime.

So to sum up, there are basically the following cases:

1. for n < 2, there are no prime numbers, so that obviously fails;
2. for n a prime number, the answer is of course one, since we can simply use that number;
3. for even numbers greater than two, we can use Goldbach's conjecture, and thus return 2, we know that this is minimal, since except for 2, there are no even prime numbers;
4. for odd numbers greater than two, we know that if n-2 is prime, then the number is 2, since 2 is a prime number, and n-2 is a prime number, we know that there is no better solution, since n is not prime; and finally
5. for an odd number where n-2 is not prime, we know that n-3 is even and per Goldbach's conjecture, we can construct a sum of three prime numbers. We know that this is optimal, since with no other prime number than 2 the subtraction is even, and hence we can again use Goldbach's conjecture.

We thus can implement an algorithm like:

primes1000 = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509, 521, 523, 541, 547, 557, 563, 569, 571, 577, 587, 593, 599, 601, 607, 613, 617, 619, 631, 641, 643, 647, 653, 659, 661, 673, 677, 683, 691, 701, 709, 719, 727, 733, 739, 743, 751, 757, 761, 769, 773, 787, 797, 809, 811, 821, 823, 827, 829, 839, 853, 857, 859, 863, 877, 881, 883, 887, 907, 911, 919, 929, 937, 941, 947, 953, 967, 971, 977, 983, 991, 997}

def min_prime(n):
    if n < 2:
        return -1
    if n in primes1000:
        return 1
    # 2 and 3 are prime numbers prime number
    # so all values here are > 3
    if n % 2 == 0:
        return 2    # Goldbach's conjecture, so 2
    if n-2 in primes1000:
        return 2
    return 3  # fallback on 3

For example:

>>> min_prime(12)
2
>>> min_prime(14)
2
>>> min_prime(88)
2
>>> min_prime(117)
3
>>> min_prime(374)
2
>>> min_prime(363)
3
>>> min_prime(11)
1

Generating the primes

We can use the same approach to generate the primes, like:

def find_sum2(n):
    for p in primes1000:
        if n-p in primes1000:
            return (p, n-p)

def min_prime_tuple(n):
    if n < 2:
        return None
    if n in primes1000:
        return (n,)
    if n % 2 == 0:
        return find_sum2(n)
    if n-2 in primes1000:
        return (2, n-2)
    return (3, *find_sum2(n-3))

For example:

>>> min_prime_tuple(12)
(5, 7)
>>> min_prime_tuple(14)
(3, 11)
>>> min_prime_tuple(88)
(5, 83)
>>> min_prime_tuple(117)
(3, 5, 109)
>>> min_prime_tuple(374)
(7, 367)
>>> min_prime_tuple(363)
(3, 7, 353)
>>> min_prime_tuple(11)
(11,)

We can improve the above in terms of efficiency by cutting off the linear search from the moment the iterator is larger than n, but this will usually not make that much difference, since the number of prime numbers less than 1000 is quite small.

Performance

Since n has an upperbound of 1'000, there is no big-oh. Furthermore if n is unbounded, we do not know if the conjecture still holds.

If we assume that the conjecture holds, then generating the tuple is done in O(g×c) with g the time to generate all primes up to n, and c the time to check if a number is a prime.

If we benchmark the above not very efficiently implemented approach in Python, we achieve the following benchmark:

>>> timeit(lambda: list(map(min_prime_tuple, range(0,1000))), number=10_000)
4.081021320000218

This thus means that if we 10'000 times construct the tuples for all numbers up to 1'000, this is done in 4.08 seconds on an Intel(R) Core(TM) i7-7500U CPU @ 2.70GHz. This thus means that we can check the entire range in 408.1 μs, or a random number approximately in 0.408 μs.

Answer 2

This is just a variation of the classic knapsack problem.

In both the original knapsack problem and this one, we have a set of items which we can choose to take from. Each item has its cost/value which we are optimizing for, and it has a size which we are limited by. In the original knapsack problem, we want to maximize profit while keeping the weight below a set maximum. Here, we want to minimize the number of primes while the sum is exactly our given number.

We can change the definition of our DP array such that DP[i][j] is the minimum number of primes needed to sum to exactly j using only the first i primes or infinity if it isn't possible to sum to j using only the first i primes, and our recurrence relationship becomes DP[i][j] = min(DP[i - 1][j], DP[i][j - p[i]] + 1) where p[i] is the ith prime. DP[numPrimes][N] can then be computed by computing all values in the DP table or using memoization similar to the original knapsack problem.

As Willem Van Onsem pointed out, this problem is a special case in that every even number less than 4 * 10^18 can be expressed as the sum of two primes which allows for a faster solution with the complexity the same as the algorithm that you use to test for primes.