Decomposing an integer number into up to N (not necessarily prime) numbers with minimal sum

Question

I am writing a program that processes data based on an integer factor. The process can either be done at once, or in multiple stages. For example, one stage with factor 500 could be replaced by three stages, the first one with factor 50, the second with factor 5, the third with factor 2. Because, 50*5*2 = 500. The reason for this is that the run-time complexity of the code is directly proportional to this integer.

It is best to order these sub-factors by size, largest first. Like in the example above: [50,5,2]. But, it is also best to make sure that the sum of these sub-factors is as small as possible. This means for example that [10,10,5] is better than [50,5,2], because the sum of the former is 25, while the sum of the latter is 57. This sum defines the run-time complexity, as mentioned above. The lower the number, the less work needs to be done, and the faster the code is.

It is of course possible that a factor simply cannot be decomposed into exactly the given number of sub-factors. One example is 25: Here, only [5,5] is possible. For this reason, I want something that decomposes an integer number into up to N numbers (N being a user specified parameter), with the constraint above about the sum of these numbers being as small as possible.

So far, I've had no luck finding anything that solves this. Does anybody know more?

Answer 1

The following algorithm gives an approximate solution, which is exact if $N=2$.

Let $a$ be the integer to be decomposed as a product of $N$ factors.

If $N=2$, let $d_1=\max\{k\in\Bbb N:k\text{ divides }a,k\le\sqrt a\} $ and $d_2=a/d_1$. Then $a=d_1\times d_2$ is the optimal solution. For instance, if $a=112476$, then $\sqrt a=335.374$, $d_1=309$, $d_2=364$ and $d_1+d_2=673$.

Suppose now that $N=3$. Choose $d_1=\max\{k\in\Bbb N:k\text{ divides }a,k\le a^{1/3}\}$ and apply the method for $N=2$ to $a/d_1$. As an example, take $a=112476$ again. Then $a^{1/3}=48.271$ and $d_1=42$; applying the method for $N=2$ to $a/d_1=2678$ we find $a/d_1=26\times103$, giving the decomposition $$ 112476=42\times26\times103,\quad42+26+103=171. $$ The actual minimum is given by $$ 112476=28\times39\times103,\quad28+39+103=170. $$ Not bad.

The process can be iterated to any value of $N$. Choose $d_1=\max\{k\in\Bbb N:k\text{ divides }a,k\le a^{1/N}\}$ and apply the method for $N-1$ to $a/d_1$.

For large $a$, the most time consuming part will be the computation of the divisors of $a$. However, not all of them are needed. Start from $\lfloor a^{1/N}\rfloor$ and go down by one until you find a divisor of $a$.

Answer 2

For every composite number $n=a\times b$ with $a,b>1$, you will have $n \ge a+b$. The only time that you have equality is $4=2\times 2=2+2$.

This means that it will always improve your runtime if you can split off another factor, so you basically you want to factorise your number into primes because those cannot be split any further.

If you do insist on limiting yourself to at most $N$ stages, then you may have to combine some primes of that prime factorisation to make fewer factors.

This can be very hard to do optimally if $N$ is low and you have many primes. In this case you would want to make the N stages around the same size, because that is when their sum is minimal. It then essentially becomes a cutting stock problem.

Actually you are multiplying numbers to make roughly equal sizes, whereas the cutting stock problem involves adding numbers to make equal sizes, but that is the same thing because you can take the logarithms first to convert multiplication to addition.

To give you an example of how tricky it can be, consider $3600$. This splits into 8 primes:
$2,2,2,2,3,3,5,5$
To reduce it to 7 or 6 factors you can combine the $2$s without changing the sum:
$3,3,4,4,5,5$
To get it down to 5 factors, you could combine the two smallest:
$4,4,5,5,9$
but it is better to keep the factors of $3$ separate and re-distribute the factors of $2$ instead:
$4,5,5,6,6$
To get this to 4 factors, you might think you should split the remaining $4$ and combine it with the $5$s like this:
$6,6,10,10$
but it is better to now combine the two factors of $3$:
$5,8,9,10$
The best arrangement into 3 factors is completely different, with the factors of $3$ separated again:
$15,15,16$
And for 2 factors you can do a completely even split:
$60,60$

The point this illustrates is that it is a hard problem, so if you don't need to limit the number of factors, then just go with the full factorisation.