1
$\begingroup$

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.

  • 4
    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.2012-09-26
  • 0
    Yes @Marvis is right: And 3-4-6 are the closest number in this case.2012-09-26
  • 0
    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.2012-09-26
  • 0
    @Graphth: Lagrange multipliers don't work when you need integer solutions.2012-11-19

1 Answers 1