Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
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. –  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 1

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.