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?
$\begingroup$
$\endgroup$
12
-
1$\begingroup$ It is not clear from the question if the numbers are distinct or not... $\endgroup$– PedjaCommented Apr 21, 2012 at 6:53
-
2$\begingroup$ @pedja: Yes it is, if $X=10$ and $N=45$... $\endgroup$– TonyKCommented Apr 21, 2012 at 7:05
-
1$\begingroup$ 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$. $\endgroup$– Mark BennetCommented Apr 21, 2012 at 7:40
-
1$\begingroup$ @Foool: You mean {6,6,6,6,6,6,6,1,1,1}. $\endgroup$– TonyKCommented Apr 21, 2012 at 10:15
-
1$\begingroup$ @Mark, $X=2$, $N=45$, 15 + 30 beats 9 + 36. $\endgroup$– Gerry MyersonCommented Jun 15, 2012 at 12:31
|
Show 7 more comments
2 Answers
$\begingroup$
$\endgroup$
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.
answered Jun 13, 2012 at 4:59
$\begingroup$
$\endgroup$
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$
answered Jun 15, 2012 at 15:20
-
$\begingroup$ 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$. $\endgroup$ Commented Jun 16, 2012 at 5:58