4
$\begingroup$

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.

Improve this question
$\endgroup$
4
  • 3
    $\begingroup$ You only want two numbers $x$ and $y$ that add up to $n$, not all partitions? What did you try (I assume you tried the obvious)? What running time did you achieve? Do you want to improve the running time? $\endgroup$
    – Pål GD
    Jul 6, 2013 at 11:47
  • 2
    $\begingroup$ Expanding on Pål's comment, for input 10 is the answer 3*7 or 2*3*5? If you use the standard definition of "partition", the answer should be 2*3*5. $\endgroup$
    – Peter Shor
    Jul 6, 2013 at 17:24
  • $\begingroup$ @PeterShor: Yes, the definition of "partition" is its standard definition and the answer when n = 10 is 2*3*5 = 30. $\endgroup$
    – Jiabin He
    Jul 7, 2013 at 7:31
  • $\begingroup$ @PålGD: You can divide n into more than two positive numbers. For example, 10 = 2 + 3 + 5, and the largest LCM of the partitions of 10 is 30. $\endgroup$
    – Jiabin He
    Jul 7, 2013 at 7:36

2 Answers 2

Reset to default
4
$\begingroup$

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.

Improve this answer
$\endgroup$
3
  • 1
    $\begingroup$ This isn't a very good competition problem if you can precompute all the values. And how do you precompute the optimum value? There are around $2.3 \cdot 10^{14}$ partitions of 250. $\endgroup$
    – Peter Shor
    Jul 7, 2013 at 18:01
  • $\begingroup$ Let me revise my previous comment ... maybe the hard part in this competition problem is actually computing this array the first time. In this case, it might be a reasonable competition problem. $\endgroup$
    – Peter Shor
    Jul 15, 2013 at 12:01
  • $\begingroup$ @PeterShor I didn't realize that I missed replying to your comment. I have no idea how to solve the problem itself. I answered this question based on the general SE philosophy that real questions should be asked. As it was probably a competition problem not a real problem so instead of spending time to devise or find an algorithm I placed the real work on the OP. If he were able to find even an inefficient algorithm his purpose would be fulfilled but only if he did some work himself to find an algorithm. That is the value I was trying to add to this Question by answering it. $\endgroup$
    – Aseem Bansal
    Jul 15, 2013 at 12:51
-1
$\begingroup$

For partitioning into two numbers the product is maximized when the two variables are closest to one another: $$g(n) \equiv \mathrm{max} \{ xy : x + y = n\} = \left\{ \begin{array}{clll} \frac{n}{2}\cdot \frac{n}{2} &=& \frac{n^2}{4} & \text{even} \\ \frac{ n-1}{2 }\cdot \frac{ n+1}{2 } &=& \frac{ n^2-1}{4 }& \text{odd} \end{array}\right. $$ This is called convexity.

Since we are looking for LCM and not product, call that result $f(n)$.

In the even case, we should be careful that $\mathrm{LCM}(n,n) = n$ so we need to find the next best one: $$\left(\frac{n}{2} -1 \right)\cdot \left(\frac{n}{2} +1\right)= \frac{n^2}{4}-1$$ Two consecutive numbers will have an LCM of at most 2.

In the odd case, two consecutive numbers will be relatively prime.

  • f(9) = 4*5 = 20
  • f(8) = 3*5 = 15
  • f(10) = 3*7 = 21

Here's a draft answer:

$$f(n) \equiv \mathrm{max} \{ xy : x + y = n\} = \left\{ \begin{array}{cr} \frac{n^2}{4}-1 & 0 \mod 4 \\ \frac{n^2}{4}-4 & 2 \mod 4 \\ \frac{ n^2-1}{4 }& 1,3 \mod 4 \end{array}\right. $$

Because the integers are discrete, and the irregularities of the LCM, you have to make all sorts of corrections.

  • for small $n$ this is certainly wrong
  • the answer seems to depend on the factors of $\frac{n}{2}$ for even values of $n$

You may not want to follow this logic to several variables - and there may be a slicker totally different way. At least we can see some of the continuity of the numbers you are generating.

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ This doesn't work for the problem as stated, since it focuses only on breaking $n$ down into a sum of two numbers, and for some values of $n$ you need to consider it as the sum of multiple smaller numbers (e.g., $n=10$). $\endgroup$
    – D.W. ♦
    Jul 7, 2013 at 22:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.