Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

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

2 Answers 2

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.

share|improve this answer

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$

share|improve this answer
    
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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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