Encontrar el menor valor de la suma

Question

La multiplicación de tres números naturales $a$ , $b$ y $c$ es igual a $2016$ . ¿Cuál es el valor más pequeño de $a + b + c$ ?

Empecé por una factorización de primos para encontrar que $2016 = 2^5 \cdot 3^2 \cdot 7$ . ¿Qué debo hacer ahora?

Answer 1

El mínimo para los naturales $a,b,c$ no puede ser inferior al mínimo para real $a,b,c$ que es $3\sqrt[3]{2016}\approx37.8982$ . Al ser también un número natural, no puede ser inferior a 38. ¿Se puede alcanzar el 38? Parece que ya lo sabes, gracias a un comentario de lulu .

Answer 2

Si consideramos el hecho de que $7=2\cdot3\cdot\frac76$ entonces $2016=2^6\cdot3^3\cdot\frac76$ y resulta fácil representar este número como un producto de $\color\red3$ los números naturales más próximos entre sí:

• $a=2^{6/\color\red3}\cdot3^{3/\color\red3}=12$
• $b=2^{6/\color\red3}\cdot3^{3/\color\red3}=12$
• $c=2^{6/\color\red3}\cdot3^{3/\color\red3}\cdot\frac76=14$

Answer 3

Dejemos que $a_2,a_3,a_7$ denotan las multiplicidades de $2,3,7$ en la factorización de $a$ .

Se quiere resolver el siguiente problema de programación entera no lineal:

$$\begin{cases}\min_\limits{a_2,a_3,a_7,b_2,b_3,b_7,c_2,c_3,c_7} 2^{a_2}3^{a_3}7^{a_7}+2^{b_2}3^{b_3}7^{b_7}+2^{c_2}3^{c_3}7^{c_7},\\ a_2,a_3,a_7,b_2,b_3,b_7,c_2,c_3,c_7\in\mathbb N_0,\\ a_2+b_2+c_2=5,\\a_3+b_3+c_3=2,\\a_7+b_7+c_7=1.\end{cases}$$

Se sabe que los problemas lineales similares son NP-duros, así que es probable que no haya nada mejor que la búsqueda exhaustiva para tu pregunta. (Aunque heurísticas como la de @IvanNeretin pueden ayudar. Lo más probable es que la búsqueda exhaustiva también ayude).

Hay $5$ formas de descomposición $5$ para que $a_2\ge b_2\ge c_2$ (somos libres de elegir el orden para la primera descomposición), entonces $3$ formas de descomposición $2$ y $3$ formas de descomposición $1$ para un total de $45$ combinaciones.

Por fuerza bruta: $$ 38 =2^ 2 3^ 1 7^ 0 +2^ 2 3^ 1 7^ 0 +2^ 1 3^ 0 7^ 1 \\ 41 =2^ 3 3^ 0 7^ 0 +2^ 2 3^ 1 7^ 0 +2^ 0 3^ 1 7^ 1 \\ 43 =2^ 4 3^ 0 7^ 0 +2^ 1 3^ 1 7^ 0 +2^ 0 3^ 1 7^ 1 \\ 43 =2^ 3 3^ 1 7^ 0 +2^ 2 3^ 1 7^ 0 +2^ 0 3^ 0 7^ 1 \\ 44 =2^ 3 3^ 1 7^ 0 +2^ 1 3^ 0 7^ 1 +2^ 1 3^ 1 7^ 0 \\ 44 =2^ 3 3^ 1 7^ 0 +2^ 1 3^ 1 7^ 0 +2^ 1 3^ 0 7^ 1 \\ 46 =2^ 2 3^ 0 7^ 1 +2^ 2 3^ 1 7^ 0 +2^ 1 3^ 1 7^ 0 \\ 46 =2^ 2 3^ 1 7^ 0 +2^ 2 3^ 0 7^ 1 +2^ 1 3^ 1 7^ 0 \\ 49 =2^ 3 3^ 1 7^ 0 +2^ 2 3^ 0 7^ 0 +2^ 0 3^ 1 7^ 1 \\ 55 =2^ 3 3^ 1 7^ 0 +2^ 2 3^ 0 7^ 1 +2^ 0 3^ 1 7^ 0 \\ 56 =2^ 5 3^ 0 7^ 0 +2^ 0 3^ 1 7^ 1 +2^ 0 3^ 1 7^ 0 \\ 56 =2^ 5 3^ 0 7^ 0 +2^ 0 3^ 1 7^ 0 +2^ 0 3^ 1 7^ 1 \\ 56 =2^ 3 3^ 0 7^ 0 +2^ 1 3^ 1 7^ 1 +2^ 1 3^ 1 7^ 0 \\ 56 =2^ 3 3^ 0 7^ 0 +2^ 1 3^ 1 7^ 0 +2^ 1 3^ 1 7^ 1 \\ 58 =2^ 2 3^ 0 7^ 0 +2^ 2 3^ 1 7^ 0 +2^ 1 3^ 1 7^ 1 \\ 58 =2^ 2 3^ 1 7^ 0 +2^ 2 3^ 0 7^ 0 +2^ 1 3^ 1 7^ 1 \\ 61 =2^ 4 3^ 0 7^ 0 +2^ 1 3^ 1 7^ 1 +2^ 0 3^ 1 7^ 0 \\ 61 =2^ 4 3^ 1 7^ 0 +2^ 1 3^ 1 7^ 0 +2^ 0 3^ 0 7^ 1 \\ 65 =2^ 4 3^ 1 7^ 0 +2^ 1 3^ 0 7^ 1 +2^ 0 3^ 1 7^ 0 \\ 68 =2^ 3 3^ 0 7^ 1 +2^ 1 3^ 1 7^ 0 +2^ 1 3^ 1 7^ 0 \\ 68 =2^ 3 3^ 1 7^ 0 +2^ 1 3^ 0 7^ 0 +2^ 1 3^ 1 7^ 1 \\ 68 =2^ 3 3^ 1 7^ 0 +2^ 1 3^ 1 7^ 1 +2^ 1 3^ 0 7^ 0 \\ 71 =2^ 4 3^ 1 7^ 0 +2^ 1 3^ 0 7^ 0 +2^ 0 3^ 1 7^ 1 \\ 71 =2^ 3 3^ 0 7^ 1 +2^ 2 3^ 1 7^ 0 +2^ 0 3^ 1 7^ 0 \\ 91 =2^ 4 3^ 1 7^ 0 +2^ 1 3^ 1 7^ 1 +2^ 0 3^ 0 7^ 0 \\ 94 =2^ 2 3^ 0 7^ 0 +2^ 2 3^ 1 7^ 1 +2^ 1 3^ 1 7^ 0 \\ 94 =2^ 2 3^ 1 7^ 1 +2^ 2 3^ 0 7^ 0 +2^ 1 3^ 1 7^ 0 \\ 95 =2^ 3 3^ 0 7^ 0 +2^ 2 3^ 1 7^ 1 +2^ 0 3^ 1 7^ 0 \\ 98 =2^ 2 3^ 1 7^ 1 +2^ 2 3^ 1 7^ 0 +2^ 1 3^ 0 7^ 0 \\ 98 =2^ 2 3^ 1 7^ 0 +2^ 2 3^ 1 7^ 1 +2^ 1 3^ 0 7^ 0 \\ 106 =2^ 5 3^ 1 7^ 0 +2^ 0 3^ 0 7^ 1 +2^ 0 3^ 1 7^ 0 \\ 106 =2^ 5 3^ 1 7^ 0 +2^ 0 3^ 1 7^ 0 +2^ 0 3^ 0 7^ 1 \\ 109 =2^ 3 3^ 1 7^ 0 +2^ 2 3^ 1 7^ 1 +2^ 0 3^ 0 7^ 0 \\ 118 =2^ 5 3^ 1 7^ 0 +2^ 0 3^ 0 7^ 0 +2^ 0 3^ 1 7^ 1 \\ 118 =2^ 5 3^ 1 7^ 0 +2^ 0 3^ 1 7^ 1 +2^ 0 3^ 0 7^ 0 \\ 121 =2^ 4 3^ 0 7^ 1 +2^ 1 3^ 1 7^ 0 +2^ 0 3^ 1 7^ 0 \\ 175 =2^ 3 3^ 1 7^ 1 +2^ 2 3^ 0 7^ 0 +2^ 0 3^ 1 7^ 0 \\ 176 =2^ 3 3^ 1 7^ 1 +2^ 1 3^ 0 7^ 0 +2^ 1 3^ 1 7^ 0 \\ 176 =2^ 3 3^ 1 7^ 1 +2^ 1 3^ 1 7^ 0 +2^ 1 3^ 0 7^ 0 \\ 181 =2^ 3 3^ 1 7^ 1 +2^ 2 3^ 1 7^ 0 +2^ 0 3^ 0 7^ 0 \\ 230 =2^ 5 3^ 0 7^ 1 +2^ 0 3^ 1 7^ 0 +2^ 0 3^ 1 7^ 0 \\ 341 =2^ 4 3^ 1 7^ 1 +2^ 1 3^ 0 7^ 0 +2^ 0 3^ 1 7^ 0 \\ 343 =2^ 4 3^ 1 7^ 1 +2^ 1 3^ 1 7^ 0 +2^ 0 3^ 0 7^ 0 \\ 676 =2^ 5 3^ 1 7^ 1 +2^ 0 3^ 0 7^ 0 +2^ 0 3^ 1 7^ 0 \\ 676 =2^ 5 3^ 1 7^ 1 +2^ 0 3^ 1 7^ 0 +2^ 0 3^ 0 7^ 0 \\ $$