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

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?

-
It is not clear from the question if the numbers are distinct or not... –  pedja Apr 21 '12 at 6:53
@pedja: Yes it is, if $X=10$ and $N=45$... –  TonyK Apr 21 '12 at 7:05
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$. –  Mark Bennet Apr 21 '12 at 7:40
@Foool: You mean {6,6,6,6,6,6,6,1,1,1}. –  TonyK Apr 21 '12 at 10:15
@Mark, $X=2$, $N=45$, 15 + 30 beats 9 + 36. –  Gerry Myerson Jun 15 '12 at 12:31

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.

-

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$

-
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$. –  Mark Bennet Jun 16 '12 at 5:58