minimize sum of primes with a lower bound on product

I can't quite figure out an algorithm for this:

Given some integer n, what subset of the primes (so no repeats) would yield the lowest possible sum if their product is at least n?

Example: 6 -> 2*3,

2308 -> 2*3*5*7*11,

14 -> 3*5

Does anybody know how I would do this?

This is part of a research project I'm doing on finite automata right now.

• Do you want the absolute optimum possible answer, or would you be OK with something that is close to optimum? How large will $n$ be (in practice)? Would you be OK with an algorithm that is $O((\log n)^3)$ time, or do you need something faster? – D.W. May 12 '17 at 1:35
• so for n=6 the solution is {2,3}, the prime factorization of n. For n=9 the factorization is not square free, but the factorization of n+1 is, and it is a solution. Can you provide a less trivial examples? – miracle173 May 12 '17 at 8:48

Your problem is: given $t$, find a set $S$ of primes whose sum is minimized, such that the product is at least $t$.

This is equivalent to: given $u$, find a set $S$ of primes whose sum is minimized, such that $\sum_{p \in S} \log p \ge u$. (Simply take $u=\log t$.) This is a knapsack problem, so it can be solved exactly using standard dynamic programming algorithms, or you can find good (but not necessarily optimal) solutions using standard approximation algorithms. I'll summarize a few options below, but the knapsack problem is well-studied, so you can probably adapt any of the standard methods to your setting.

Dynamic programming

There is a straightforward dynamic programming algorithm that solves your problem in $O((\log n)^3)$ time. We will construct an array $A[\cdot,\cdot]$ such that

$$A[s,q] = \max \{\prod_{p \in S} p : \sum_{p \in S} p = s \text{ and } p \le q \text{ for all } p \in S\},$$

i.e., $A[s,q]$ stores the largest possible product that is attainable from a set of primes that are all at most $q$ and that sum to $s$. You can fill in the contents of the array $A$ using a straightforward recursion:

$$A[s,q] = \max(A[s,q^*], q \times A[s-q,q^*]),$$

where $q^*$ is the previous prime before $q$. We'll fill in this array only for values $q$ that are prime. If we fill in the array in order of increasing $s$ and increasing $q$, each entry is known will be known before it is first used.

Finally, once we've filled in the $A$ array, we can find the smallest $s$ such that there exists a prime $q$ such that $A[s,q] \ge n$ by iterating over all the elements of the array.

How much of the array do we need to fill in? In particular, what's the largest value of $s$ and $q$ we need to fill in? Well, we can show that $s \le (\lg n)^2$ suffices. Also, we certainly have $q \le s$. Therefore, we only need to fill in $(\lg n)^3$ elements of $A$, and the algorithm has running time $O((\log n)^3)$.

I suspect that it can be done faster, and in particular, we can probably restrict to smaller values of $q$ (in particular, I suspect $q= O(\log s) = O(\log \log n)$ probably suffices)... but this gives a simple algorithm that is easy to show correct. Also, it is possible to find a tighter bound on the largest possible value of $s$, but that's not really necessary: if you fill in all of $A[1,\cdot]$, then $A[2,\cdot]$, then $A[3,\cdot]$, etc., and check each one to find the first that has an entry that is $\ge n$, this will enable the algorithm to terminate as soon as it finds the smallest attainable $s$.

Approximation algorithms

There are many possible approximation algorithms. A simple one is to use a greedy strategy: take the first $k$ primes, choosing $k$ as small as possible such that their product is at least $n$.

Why is this a greedy strategy? Well, we're trying to minimize $\sum_{p \in S} p$ subject to $\sum_{p \in S} \log p \ge n$. So, the greedy algorithm for that is to sort the primes in order of increasing value of $p/\log p$, and take the first $k$, for some $k$. But sorting the primes in increasing value of $p/\log p$ is equivalent to taking the primes in increasing order ($p=2,3,5,7,11,\dots$).

There are other standard ways to improve on this.

Another approach is to formulate this as an instance of integer linear programming and feed it to an ILP solver. We want to minimize $\sum_{p \in Q} p x_p$ subject to $\sum_{p \in Q} (\log p) x_p \ge n$, where $x_2,x_3,x_5,x_7,\dots$ are the unknowns and each is constrained to be zero or one, where $Q$ is the set of primes $\le \lg n$. That's an ILP instance, so you can give it to an ILP solver and let it grind away at it.

I'll suggest a very simple and very fast algorithm that I believe produces the correct result unless n is very large.

Step 1: If n = 1 the solution is {}. If n = 2 or n = 3 the solution is { n }. Otherwise, find the smallest prime p such that the product of the primes from 2 to p is ≥ n. Let S = the set of primes from 2 to p, let P = the product of the primes from 2 to p. If p < 2n then the result is S.

Otherwise, let r be the largest prime such that P / r ≥ n. Also, let q be the smallest prime > p, and let r' be the largest prime such that (P * q / p) / r' ≥ n. If r' - r > q - p then the result is S + { q } - { r', p }, otherwise the result is S - { r }.

The first n where this doesn't give the optimal solution is n = 2 * 3 * 5 * ... * 79 * 83 * 89 * 103 + 1 ≈ $2.622·10^{36}$.

Reasoning: We would want to use the smallest primes possible, because the ratio P / log p grows as p grows (with the exception of the primes 2 and 3). The exception is when we have a product that is quite a bit larger than n, and may get a product closer to n with a smaller sum.

If P < 2n, then we might replace p with a larger prime q and remove the prime 2 from the product. But q ≥ p + 2, so the sum of primes will not get smaller.

If P ≥ 2n, then removing the largest possible prime from the product will obviously make the product smaller. This does not give the optimal solution if for example P / 7 ≥ n but P / 11 < n, the next prime after p is q = p + 2, and replacing p with q in the product means that (P * q / p) / 11 ≥ n. In this case we increased the sum by 2 replacing q with p, and decreased it by 4 replace r with r'. But the algorithm will find this case.

This does not detect the case where replacing p with the next prime after q would improve the sum. Let q be the smallest prime > p, and q' the smallest prime > q. We know that q' ≥ p + 6 because p, p+2 and p+4 cannot all three be prime. So we might not find the optimal solution if the prime after r is r+8.

This is the case for the first time when r = 89 and the next prime is 97 = p + 8. If p = 101, then q = 103 and q' = 107 = p + 6. So take n = 2 * 3 * 5 * ... * 79 * 83 * 89 * 103 + 1: We need all the primes up to p = 101 to have a product P ≥ n. We can leave out r = 89 from that product, but not 97 because the remaining product is much smaller than n. If we exchange 103 for 101, we still cannot remove 97 because the product would be n-1. But we can exchange 107 for 101 and remove 97 instead of 89 from the product, getting a sum that is smaller by 2. So the optimal solution here is { 2, 3, ..., 83, 89, 107 } where the algorithm will return { 2, 3, ..., 83, 97, 101 }.