Finding the smallest value of the sum

Question

The multiplication of three natural numbers $a$, $b$ and $c$ equals $2016$. What is the smallest value of $a + b + c$?

I started by a prime factorization to find that $2016 = 2^5 \cdot 3^2 \cdot 7$. What should I do next?

Answer 1

The minimum for natural $a,b,c$ can't be lower than the minimum for real $a,b,c$, which is $3\sqrt[3]{2016}\approx37.8982$. Being also a natural number, it can't be lower than 38. Can 38 be reached? Looks like you already know that, thanks to a comment by lulu.

Answer 2

If we consider the fact that $7=2\cdot3\cdot\frac76$, then $2016=2^6\cdot3^3\cdot\frac76$, and it becomes easy to represent this number as a product of $\color\red3$ natural numbers which are as close to each other as possible:

• $a=2^{6/\color\red3}\cdot3^{3/\color\red3}=12$
• $b=2^{6/\color\red3}\cdot3^{3/\color\red3}=12$
• $c=2^{6/\color\red3}\cdot3^{3/\color\red3}\cdot\frac76=14$

Answer 3

Let $a_2,a_3,a_7$ denote the multiplicities of $2,3,7$ in the factorization of $a$.

You want to solve the following nonlinear integer programming problem:

$$\begin{cases}\min_\limits{a_2,a_3,a_7,b_2,b_3,b_7,c_2,c_3,c_7} 2^{a_2}3^{a_3}7^{a_7}+2^{b_2}3^{b_3}7^{b_7}+2^{c_2}3^{c_3}7^{c_7},\\ a_2,a_3,a_7,b_2,b_3,b_7,c_2,c_3,c_7\in\mathbb N_0,\\ a_2+b_2+c_2=5,\\a_3+b_3+c_3=2,\\a_7+b_7+c_7=1.\end{cases}$$

Similar linear problems are known to be NP-hard, so it is likely that there is not much better than exhaustive search for your question. (Though heuristics such as the one by @IvanNeretin can help. Most probably, Depth First Search would help too.)

There are $5$ ways to decompose $5$ so that $a_2\ge b_2\ge c_2$ (we are free to choose the order for the first decomposition), then $3$ ways to decompose $2$ and $3$ ways to decompose $1$, for a total of $45$ combinations.

By brute force: $$ 38 =2^ 2 3^ 1 7^ 0 +2^ 2 3^ 1 7^ 0 +2^ 1 3^ 0 7^ 1 \\ 41 =2^ 3 3^ 0 7^ 0 +2^ 2 3^ 1 7^ 0 +2^ 0 3^ 1 7^ 1 \\ 43 =2^ 4 3^ 0 7^ 0 +2^ 1 3^ 1 7^ 0 +2^ 0 3^ 1 7^ 1 \\ 43 =2^ 3 3^ 1 7^ 0 +2^ 2 3^ 1 7^ 0 +2^ 0 3^ 0 7^ 1 \\ 44 =2^ 3 3^ 1 7^ 0 +2^ 1 3^ 0 7^ 1 +2^ 1 3^ 1 7^ 0 \\ 44 =2^ 3 3^ 1 7^ 0 +2^ 1 3^ 1 7^ 0 +2^ 1 3^ 0 7^ 1 \\ 46 =2^ 2 3^ 0 7^ 1 +2^ 2 3^ 1 7^ 0 +2^ 1 3^ 1 7^ 0 \\ 46 =2^ 2 3^ 1 7^ 0 +2^ 2 3^ 0 7^ 1 +2^ 1 3^ 1 7^ 0 \\ 49 =2^ 3 3^ 1 7^ 0 +2^ 2 3^ 0 7^ 0 +2^ 0 3^ 1 7^ 1 \\ 55 =2^ 3 3^ 1 7^ 0 +2^ 2 3^ 0 7^ 1 +2^ 0 3^ 1 7^ 0 \\ 56 =2^ 5 3^ 0 7^ 0 +2^ 0 3^ 1 7^ 1 +2^ 0 3^ 1 7^ 0 \\ 56 =2^ 5 3^ 0 7^ 0 +2^ 0 3^ 1 7^ 0 +2^ 0 3^ 1 7^ 1 \\ 56 =2^ 3 3^ 0 7^ 0 +2^ 1 3^ 1 7^ 1 +2^ 1 3^ 1 7^ 0 \\ 56 =2^ 3 3^ 0 7^ 0 +2^ 1 3^ 1 7^ 0 +2^ 1 3^ 1 7^ 1 \\ 58 =2^ 2 3^ 0 7^ 0 +2^ 2 3^ 1 7^ 0 +2^ 1 3^ 1 7^ 1 \\ 58 =2^ 2 3^ 1 7^ 0 +2^ 2 3^ 0 7^ 0 +2^ 1 3^ 1 7^ 1 \\ 61 =2^ 4 3^ 0 7^ 0 +2^ 1 3^ 1 7^ 1 +2^ 0 3^ 1 7^ 0 \\ 61 =2^ 4 3^ 1 7^ 0 +2^ 1 3^ 1 7^ 0 +2^ 0 3^ 0 7^ 1 \\ 65 =2^ 4 3^ 1 7^ 0 +2^ 1 3^ 0 7^ 1 +2^ 0 3^ 1 7^ 0 \\ 68 =2^ 3 3^ 0 7^ 1 +2^ 1 3^ 1 7^ 0 +2^ 1 3^ 1 7^ 0 \\ 68 =2^ 3 3^ 1 7^ 0 +2^ 1 3^ 0 7^ 0 +2^ 1 3^ 1 7^ 1 \\ 68 =2^ 3 3^ 1 7^ 0 +2^ 1 3^ 1 7^ 1 +2^ 1 3^ 0 7^ 0 \\ 71 =2^ 4 3^ 1 7^ 0 +2^ 1 3^ 0 7^ 0 +2^ 0 3^ 1 7^ 1 \\ 71 =2^ 3 3^ 0 7^ 1 +2^ 2 3^ 1 7^ 0 +2^ 0 3^ 1 7^ 0 \\ 91 =2^ 4 3^ 1 7^ 0 +2^ 1 3^ 1 7^ 1 +2^ 0 3^ 0 7^ 0 \\ 94 =2^ 2 3^ 0 7^ 0 +2^ 2 3^ 1 7^ 1 +2^ 1 3^ 1 7^ 0 \\ 94 =2^ 2 3^ 1 7^ 1 +2^ 2 3^ 0 7^ 0 +2^ 1 3^ 1 7^ 0 \\ 95 =2^ 3 3^ 0 7^ 0 +2^ 2 3^ 1 7^ 1 +2^ 0 3^ 1 7^ 0 \\ 98 =2^ 2 3^ 1 7^ 1 +2^ 2 3^ 1 7^ 0 +2^ 1 3^ 0 7^ 0 \\ 98 =2^ 2 3^ 1 7^ 0 +2^ 2 3^ 1 7^ 1 +2^ 1 3^ 0 7^ 0 \\ 106 =2^ 5 3^ 1 7^ 0 +2^ 0 3^ 0 7^ 1 +2^ 0 3^ 1 7^ 0 \\ 106 =2^ 5 3^ 1 7^ 0 +2^ 0 3^ 1 7^ 0 +2^ 0 3^ 0 7^ 1 \\ 109 =2^ 3 3^ 1 7^ 0 +2^ 2 3^ 1 7^ 1 +2^ 0 3^ 0 7^ 0 \\ 118 =2^ 5 3^ 1 7^ 0 +2^ 0 3^ 0 7^ 0 +2^ 0 3^ 1 7^ 1 \\ 118 =2^ 5 3^ 1 7^ 0 +2^ 0 3^ 1 7^ 1 +2^ 0 3^ 0 7^ 0 \\ 121 =2^ 4 3^ 0 7^ 1 +2^ 1 3^ 1 7^ 0 +2^ 0 3^ 1 7^ 0 \\ 175 =2^ 3 3^ 1 7^ 1 +2^ 2 3^ 0 7^ 0 +2^ 0 3^ 1 7^ 0 \\ 176 =2^ 3 3^ 1 7^ 1 +2^ 1 3^ 0 7^ 0 +2^ 1 3^ 1 7^ 0 \\ 176 =2^ 3 3^ 1 7^ 1 +2^ 1 3^ 1 7^ 0 +2^ 1 3^ 0 7^ 0 \\ 181 =2^ 3 3^ 1 7^ 1 +2^ 2 3^ 1 7^ 0 +2^ 0 3^ 0 7^ 0 \\ 230 =2^ 5 3^ 0 7^ 1 +2^ 0 3^ 1 7^ 0 +2^ 0 3^ 1 7^ 0 \\ 341 =2^ 4 3^ 1 7^ 1 +2^ 1 3^ 0 7^ 0 +2^ 0 3^ 1 7^ 0 \\ 343 =2^ 4 3^ 1 7^ 1 +2^ 1 3^ 1 7^ 0 +2^ 0 3^ 0 7^ 0 \\ 676 =2^ 5 3^ 1 7^ 1 +2^ 0 3^ 0 7^ 0 +2^ 0 3^ 1 7^ 0 \\ 676 =2^ 5 3^ 1 7^ 1 +2^ 0 3^ 1 7^ 0 +2^ 0 3^ 0 7^ 0 \\ $$