Maximising lcm?

general
,
1

Given a number k you have to write it as a sum of numbers equal to k such that the lcm of the chosen numbers is maximum. eg. Given 12 write it as 5+4+3=12 because lcm(3,4,5) = 60.It can be verified that 60 is the best that can be done.

What would be the best strategy for solving this problem. My guess is that I should only be considering the cases where the number can be expressed as the sum of relatively prime numbers?

2 Likes
2

You can use dynamic programming,
for n around thousand it should work.The solution in O(n^2).(maybe you can better it).


    ans[1]=1      (the answer when n=1)
    for(i from 2  to n)
         initialize ans[i]=0
         for(j from 1 to i)
               ans[j]=max(lcm(ans[i-j],j),ans[j])