# Product of 3 integers is 72, find the 3 integers that give the smallest sum

Product of 3 integers a, b, c equals 72, where every factor is positive integer. Find the integers a, b, c with the smallest sum.

It's easy to get the factors of 72 manually and see that the 3 smallest factors that give the product as 72 will be the smallest sum.

I checked the factorization like this:

1-1-72: 74
1-2-36: 39
1-4-18: 25
1-8-9:  18
2-4-9:  15
3-4-6:  13


It seems like the smallest possible factors will give the smallest sum.

But there must be some trick to it or some kind of algorithm to find the smallest integers for any arbitrary product without laborious factoring.

Thanks for your help.

-
The factors must be close to each other. A heuristic: The AM-GM inequality gives us $(a+b+c)/3 \geq \sqrt[3]{abc}$ where equality holds when $a=b=c$ and the difference between the LHS and RHS increases when $a$, $b$ and $c$ are far apart from each other. –  user17762 Sep 26 '12 at 5:00
Yes @Marvis is right: And 3-4-6 are the closest number in this case. –  Sumit Bhowmick Sep 26 '12 at 6:15
One algorithm might be to find the factor of $72$ closest to $\sqrt[3]{72}$, which is $4$. Then find the factor of $72/4=18$ closest to $\sqrt[2]{18}$, which is $3$. That leaves $18/3=6$. I don't know if it is always optimal, but it should be close to optimal. –  Henry Sep 26 '12 at 7:40
@Graphth: Lagrange multipliers don't work when you need integer solutions. –  TonyK Nov 19 '12 at 15:34

## 1 Answer

You could try decomposing $72$ into its prime factors. This is:

$$72 = 2^3\times 3^2 = 2*2*2*3*3.$$

Then pick the smallest combination of factor, which is $2\times 2$, $2\times 3$ and $3$, so that $4\times 6\times 3 = 72$, and $4 + 6 + 3 = 13$.

Hope it helps.

-