hi! i did not know that!! thanks for replying.. it is not necessary that you have to spilt the number into 2 numbers only... for example for '6' the nos. are (1,2,3), which give lcm as 6. and i am not sure if it is possible to form and solve subproblems.(i might be wrong)
but then, that was very valuable info.. i could not have guessed it myself. if i am over looking something obvious please let me know.. thanks!! On Dec 3, 8:41 pm, James Fang <[EMAIL PROTECTED]> wrote: > 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 -~----------~----~----~----~------~----~------~--~---
