ok..i just realised that i did overlook something ridiculously obvious.. thanks a lot!
On Dec 4, 7:41 pm, malicious code <[EMAIL PROTECTED]> wrote: > 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 algogeeks@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~----------~----~----~----~------~----~------~--~---
