¿Cuál es el mínimo posible LCM de $X$ de números naturales cuya suma es $N$?
Enfrenté un problema específico en mi módulo con $X=10$ y $N=45$ y me lo solucionó por semi-brute-force. ¿Cualquier ideas sobre cómo resolver el problema general?
Respuestas
¿Demasiados anuncios?
user8269
Puntos
46
Respuesta parece saltar mucho, ya que varía los parámetros. Tomemos $X=10$ y $40\le N\le50$. Escribe $a^b$ para "copias de $b$ $a$" obtener $$\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}$ $ prefiero el término "educación ensayo y error" para el término "semi-brute force", pero es su moneda de diez centavos.
runeh
Puntos
1304
Emigraron de comentario:
Entonces, ¿qué tipo de patrón de podemos esperar a ver?
Tome el simple caso de $X=2$. Si $N=2m$ $N=m+m$ es lo mejor que podemos hacer con LCM = $m$.
Si $N$ es extraño, por decir $N=(2m)+(1)$ tenemos una cota superior para el MCM de a $2m$ (que es apretado al $N=5,7$).
Sin embargo, cuando se $N=6r+3$ podemos ir a $(4r+2)+(2r+1)$, lo que da LCM $4r+2$. La respuesta dependerá de la menor factor primo $q$.
Si $N=qr$ uso de $(q−1)r+r$ con LCM $(q−1)r$.
La idea es dividir el número original en trozos que son "tan pequeño como sea posible", sin recoger extra factores primos para contribuir a la LCM.
Si $X=3$, en el caso especial es $N=3m$, que podemos dividir en $m+m+m$.
Si tenemos un factor de 2, pero no es un factor de 3, por lo que el $N=2m=a+b+c$ observamos que uno de $a,b,c$ debe ser, por lo que bien podemos tener todos ellos, ni siquiera y split $m$. Que nos reduce a considerar impar de factores primos mayor que 3.
$N=5m=2m+2m+m$, e $N=7m=3m+3m+m$ - (5,7 ser, respectivamente, el menor divisor primo de $N$) parece como si este patrón continúa, pero yo no lo he probado con ningún rigor.
Para continuar (de haber sido interrumpida a soplar un poco de globos):
Si $q$ es el menor factor primo de $N=qm$ $q\geq X$ aunque parece que la mejor estrategia puede ser dividida $q$ a $X$ piezas. Como $X$ se hace más grande, hay más casos especiales a considerar, con los números primos menores que $X$.
Tome $X=4$ -ahora $X$ no es primo, y que parece hacer una diferencia. Los siguientes casos especiales surgir:
$N=4m=m+m+m+m$
$N=2m=m+m$ y luego se divide $m$ como en el caso de $X=2$. $N=6m=2m+2m+m+m$ es un caso especial de esto.
$N=3m=?$ con la posibilidad de $N=9m=4m+2m+2m+m$
