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

1

Answer seems to jump around a lot as you vary the parameters. Let's take $X=10$ and $40\le N\le50$. Writing $a^b$ for "$b$ copies of $a$" I get $$\matrix{N&a_i&{\rm LCM}\cr40&4^{10}&4\cr41&6^621^3&6\cr42&5^81^2&5\cr43&6^6321^2&6\cr44&6^62^4&6\cr45&6^71^3&6\cr46&5^91&5\cr47&6^72^21&6\cr48&6^72^3&6\cr49&6^732^2&6\cr50&5^{10}&5\cr}$$ I prefer the term "educated trial and error" to the term "semi-brute force", but it's your dime.

1

Migrated from comment:

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 prime factor $q$.

If $N=qr$ then use $(q−1)r+r$ with LCM $(q−1)r$.

The idea is to split the original number into pieces which are "as small as possible" without picking up extra prime factors to contribute to the LCM.

If $X=3$, the special case is $N=3m$, which we can split as $m+m+m$.

If we have a factor 2, but not a factor 3, so that $N=2m=a+b+c$ we note that one of $a,b,c$ must be even, so we may as well have them all even and split $m$. That reduces us to considering odd prime factors greater than 3.

$N=5m=2m+2m+m$, and $N=7m=3m+3m+m$ - (5,7 being respectively the smallest prime divisor of $N$) it looks as though this pattern persists, but I haven't tested it with any rigour.

To continue (having been interrupted to blow up some balloons):

If $q$ is the smallest prime factor of $N=qm$ and $q\geq X$ it looks as though the best strategy may be to split $q$ into $X$ pieces. As $X$ gets larger there are more special cases to consider, with primes smaller than $X$.

Take $X=4$ -now $X$ is not prime, and that seems to make a difference. The following special cases arise:

$N=4m=m+m+m+m$

$N=2m=m+m$ and then split $m$ as in the case of $X=2$. $N=6m=2m+2m+m+m$ is a special case of this.

$N=3m=?$ with the possibility $N=9m=4m+2m+2m+m$

  • 0
    It turns out that these comments about low values of $X$ and lowest prime factor $q$ of $n$ could be misleading. Take 187 = 11.17 and split it into 10 parts. If you split 11=9.1+2, lcm is 2.17=34. But you can do better by splitting 17 as 7.2+3.1, which gives 2.11=22. You can do the same with 77=7.11 into 6 parts. My next question is whether there is an example of this phenomenon for $X=5$.2012-06-16