¿Cuál es el mayor número que podemos obtener utilizando $n$ unos, suma, multiplicación y paréntesis?

Question

Digamos que tenemos $n$ de los mismos, es decir $1,1,\dots,1$ $n$ veces y se nos permite sumarlas, multiplicarlas e insertar paréntesis donde queramos.

¿Cuál es el mayor número que podemos obtener para un $n$ ? ¿Existe una forma cerrada o al menos una secuencia OEIS?

Para $n=5$ parece ser $(1+1)(1+1+1)=6$ , para $n=6$ parece ser $(1+1+1)(1+1+1)=9$ , para $n=9$ He encontrado $(1+1+1)(1+1+1)(1+1+1)=27$ para ser el mayor número.

Pero no veo la manera de encontrar una fórmula general. Supongo que tendría sentido empezar por el otro extremo: para cada número $N$ encontrar una factorización con la menor suma de factores o algo así.

Answer 1

Desde

1) no tiene sentido crear ningún término 1+1+1+... con más de 3 1s, ya que 1+1+1+1 es 'peor' que (1+1) por (1+1+1), y para más 1s será incluso 'mejor' multiplicar varios 1+1+.. Términos en lugar de tener uno largo, y con 4 1s 1+1+1+1 es tan bueno como (1+1) por (1+1),

y

2) dos términos 1+1+1 es mejor que tres términos 1+1,

su estrategia básica es conseguir el mayor número posible de términos 1+1+1. Así que:

Si n mod 3 = 0, lo mejor que puedes hacer es $3^{n/3}$

Si n mod 3 = 1, se obtienen dos términos 1+1, y en caso contrario 1+1+1, por lo que se obtiene $4*3^{(n-4)/3}$

Si n mod 3 = 2, se obtiene un término 1+1 además de los términos 1+1+1, por lo que $2*3^{(n-2)/3}$

Answer 2

No sé si esto podría ser una solución "aproximada" o algo así. Pero prueba lo siguiente.

Si la expresión final está formada por $x_1 \times ... \times x_k$ donde $x_1+...+x_k=n$ con $k<n$ Manteniendo n,k fijos, y suponiendo que el $x$ no necesitan ser enteros por el momento, el máximo es $(n/k)^k$ . Tomando la derivada wrt k y obteniendo $(n/k)^k ( \ln(n/k)-1)=0)$ para obtener el mejor $k$ que se trata de $n/e$ con el óptimo de que cada término sea aprox. $x \approx 2.7$ que puede ser tan bueno como $3$ en el caso de los enteros

Answer 3

Obviamente el problema se reduce a encontrar el máximo de $a_1 \cdot a_2 \cdot ... \cdot a_t$ cuando $a_1 + a_2 + ... + a_t = n$ . Ahora vamos a aumentar $a_1$ en uno y disminuye $a_2$ por uno. Entonces el valor de $a_1 \cdot a_2 \cdot ... \cdot a_t$ aumentará si $a_1 \ge a_2+2$ . Eventualmente esto lleva a concluir que para un "fijo" $t$ el máximo se producirá cuando $a$ son lo más parecido posible.

Ahora vamos a encontrar el óptimo $t$ . Como se ha concluido anteriormente se supone que $a_1 = \cdots = a_t = a$ . Entonces tenemos $a = \frac nt$ . Ahora $a_1 \cdot a_2 \cdot ... \cdot a_t = \left(\frac nt \right)^t$ . Esta función obtiene un máximo en $t=e$ por lo que el máximo se obtiene para $t = \frac ne$

Como todas las variables son enteras y como las funciones son continuas tenemos que el necesitamos elegir $t = \left\lfloor \frac ne \right\rfloor$ o $\left\lfloor \frac ne \right\rfloor + 1$ . En cada caso elegimos $a_i = \left\lfloor \frac nt \right\rfloor$ o $\left\lfloor \frac nt \right\rfloor + 1$ en consecuencia, s.t. la suma es $n$ . Esto reduce el problema a unos pocos casos, que pueden ser fácilmente comprobados.