patternMinor
Find out the largest LCM of the partitions of n
Viewed 0 times
thelcmlargestpartitionsfindout
Problem
I want to find out an algorithm to find out the largest least common multiple (LCM) of the partitions of an integer $n$.
Example: $5 = 1 + 4$, $5 = 2 + 3$, since $\mathrm{LCM}(1,4) < \mathrm{LCM}(2,3) = 6$, the largest LCM of the partitions of $5$ is 6.
The definition of "partition" is the standard definition of it. In order to make the problem more clearly, I will take n = 10 as an example. The largest LCM if the partitions of 10 is 30, since 10 = 2 + 3 + 5.
More examples(Let g(n) be the answer that I want to get):
g(11) = 30
g(12) = 60
g(13) = 60
I want to find out an algorithm that can get the largest LCM in 1 second with the n less or equal to 250.
Example: $5 = 1 + 4$, $5 = 2 + 3$, since $\mathrm{LCM}(1,4) < \mathrm{LCM}(2,3) = 6$, the largest LCM of the partitions of $5$ is 6.
The definition of "partition" is the standard definition of it. In order to make the problem more clearly, I will take n = 10 as an example. The largest LCM if the partitions of 10 is 30, since 10 = 2 + 3 + 5.
More examples(Let g(n) be the answer that I want to get):
g(11) = 30
g(12) = 60
g(13) = 60
I want to find out an algorithm that can get the largest LCM in 1 second with the n less or equal to 250.
Solution
It seems that this a competition problem. Your best bet is to pre-calculate maximum values for all numbers(250 isn't very big) and store it into an array. That would be the best bet as this can give you timing near to zero.
Context
StackExchange Computer Science Q#13101, answer score: 4
Revisions (0)
No revisions yet.