You needn't brute force the possible combinations. 1) if the number is odd, the lcm = ground(number/2) * (ground(number/ 2)+1)
2) if the number is even, and number/2 is still even . the lcm = (number/2-1)* (number/2+1) 3) if the number is even, and number/2 is odd. then lcm = (number/ 2-2)*(number/2+2) it can be proved as following: in situation 1), let ground(number/2) = a1*a2*...*an , let ax=multiply of random combination of a1,a2,...,an, then it is deducable that (ground(number/2) +1)%ax=1 so the lcm of ground(number/2) and (ground(number/2)+1) is ground(number/2) * (ground(number/2)+1). in situation 2), similar with situation 1), the only common divisor (number/2-1) and (number/2+1) have is 2. Since we've already know that number/2 is even, we can get the conclusion. similar deduction on situation 3). Regards and Thanks, James Fang On Dec 2, 7:35 pm, malicious code <[EMAIL PROTECTED]> wrote: > hi! > suppose i have a number, say.. '7' > i want to find the highest possible lcm of the set of numbers that add > upto 7 > that is.. in this case > 3+4 = 7 > lcm(3,4) = 12 > > how do i go about this? > i could always brute force the possible combinations(1,6)(2,5)... > (1,2,4)....(1,1,1,1,1,1,1) > this is clearly very inefficient > > what if i enumerate pairs of coprimes(2,3)(2,5) etc... > could this lead to a better solution? --~--~---------~--~----~------------~-------~--~----~ You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to [email protected] To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~----------~----~----~----~------~----~------~--~---
