# Partition a set of factors so that the difference between products is minimized

I'm sure this problem must be well-known...

Given a collection $$S$$ of numbers, partition them into exactly two sub-collections, $$A$$ and $$B$$ (I mean, by definition $$B$$ is just $$S-A$$) such that the difference of products $$\Delta = \left|\left(\prod_{x\in B}x\right) - \left(\prod_{x\in A}x\right)\right|$$ is as small as possible.

If it helps, you can assume that all the members of $$S$$ are integers, and in fact you can assume that they are all prime! In my particular use-case, we're trying to split some big integer $$n$$ into its "squarest possible" pair of factors, and $$S$$ is simply a prime factorization of $$n$$ which we happen to have lying around.

What's the best way to do this? The brutish ways I have thought of are:

• Trial division (assuming everything is prime). Awful performance.
    int PS = productOf(S);
for (int PA = sqrt(PS); PA >= 1; --PA) {
if (PS % PA == 0) {
int PB = PS / PA;
return { factorsOf(PA), factorsOf(PB) };
}
}

• Search all the possible partitions. Would give better performance, I think, because $$\lvert S\rvert! \ll \prod{S}$$, but still "obviously" a dumb algorithm.
    int currentDiff = productOf(S);
intset currentA = {};
for (intset A in partitionsOf(S)) {
int PA = productOf(A);
int PB = productOf(S)/PA;
if (PB >= PA && PB-PA < currentDiff) {
currentA = A;
currentDiff = PB-PA;
}
}
return { currentA, S - currentA };


Is there any simple-ish algorithm to solve this problem without relying on brute exhaustive search?

I wonder if it would work to minimize the difference of sums $$\sum_{x\in B}{\log{x}} - \sum_{x\in A}{\log{x}}$$, and if that problem has a simpler known solution...

• A quick note regarding your final point on minimising the difference of logs: the problem can be reduced to 2-partition (en.wikipedia.org/wiki/Partition_problem) which is NP-complete, but has a pseudo-polynomial dynamic programming solution (efficient in practice). – integrator Oct 19 '20 at 16:19
• Here is relevant link to the problem you want to solve: cstheory.stackexchange.com/questions/16902/… – integrator Oct 19 '20 at 16:36
• FWIW, that problem seems like "split S so that $\prod{A} = \prod{B}$ exactly," and I don't (yet) understand how to adjust the solution to merely minimize the difference $\prod{B}-\prod{A}$. – Quuxplusone Oct 19 '20 at 17:12
• Are you looking for practical solutions or do you care about theoretical running time? If practical, what are the typical sizes of the sets and the numbers? – D.W. Oct 19 '20 at 18:22
• @D.W.: I'm looking for practical solutions IRL, but I'm also morbidly curious about impractical ones and would not downvote them. My inputs are the-prime-factorizations-of consecutive integers starting at $n=2$, so my set sizes are $\Omega(n)$ for whatever that's worth. :) Circa $n=10^9$, my "trial division" algorithm becomes noticeably "slow." I have not yet implemented the "search all partitions" algorithm because I decided I'd better ask for better algorithms before I spend the time to implement another one. – Quuxplusone Oct 19 '20 at 18:39