6
$\begingroup$

What is the minimum possible LCM of $X$ natural numbers whose sum is $N$?

I faced a specific problem in my module with $X=10$ and $N=45$ and I solved it by semi-brute-force. Any ideas on how to solve the general problem?

  • 1
    It is not clear from the question if the numbers are distinct or not...2012-04-21
  • 2
    @pedja: Yes it is, if $X=10$ and $N=45$...2012-04-21
  • 0
    As a matter of interest, what answer did you get to your sample question?2012-04-21
  • 0
    @Mark Bennet: Since the total is $45$, at least one number is $\ge 5$. So the LCM cannot be less than $5$. But to get LCM $5$ each number can only be $5$ or $1$. We can check by trial and error that this is not possible. Hence, taking the next natural number $6$ we get $\{6,6,6,6,6,6,6,6,1,1\}$.2012-04-21
  • 1
    So what kind of pattern might we expect to see? Take the simple case $X=2$. If $N=2m$ then $N=m+m$ is the best we can do with LCM = $m$. If $N$ is odd, say $N=(2m)+(1)$ we get an upper bound for the LCM of $2m$ (which is tight when $N=5,7$). However when $N=6r+3$ we can go to $(4r+2)+(2r+1)$, which gives LCM $4r+2$. The answer will depend on the smallest factor $q$. If $N=qr$ then use $(q-1)r+r$ with LCM $(q-1)r$.2012-04-21
  • 0
    Last comment for $X=2$ doesn't quite work. e.g. for 45 it would suggest 3+42, but we can do 9+36. There is an inductive process which seems to work, which is in my head but not on paper, and which seems to work for $X=3$ too. The value of $X$ has a special status, which is what confused my logic above.2012-04-21
  • 1
    @Foool: You mean {6,6,6,6,6,6,6,1,1,1}.2012-04-21
  • 0
    @Angela, that can't quite be right, e.g., $X=5$, $N=7$, then $m=7$, $[7/4]=1$, but LCM 1 is not possible.2012-06-15
  • 1
    @Mark, $X=2$, $N=45$, 15 + 30 beats 9 + 36.2012-06-15
  • 0
    @GerryMyerson And 3 is less than 5. One day I will learn to count.2012-06-15
  • 0
    @Mark, I think you should put up your result for $X=2$ as an answer, together with whatever you have for $X=3$. It seems to be as good as anything anyone has found, and maybe it will stimulate something better, or maybe it will convince that there isn't anything better.2012-06-15
  • 0
    @GerryMyerson Have done, with some additions under pressure of a daughter's birthday party ...2012-06-15

2 Answers 2