Pregunta :
Dado algún número natural, podemos, por supuesto, dividirlo en varias sumas de otros naturales (por ejemplo $7 = 6 + 1 = 1 + 4 + 2 = \ldots$ )
Más concretamente, para $n \in \mathbb{N}$ podemos encontrar una secuencia de distribución (o partición ) $s_0,\ldots,s_u \in \mathbb{N}$ con
$$\sum_{i=0}^{u}s_i = n$$
Ahora, ¿cómo puedo encontrar la partición $s$ para el que el mínimo común múltiplo global de todos los elementos es máximo. O formulado de otro modo, el producto máximo de factores primos distintos de todos los elementos.
Ejemplo:
$$ 7 \mapsto (3, 4); \Pi_{lcm} = 12 $$ $$ 7 \mapsto (1, 2, 4); \Pi_{lcm} = 4$$ $$ \ldots $$
En este caso, la primera solución es la deseada.
Antecedentes:
El fondo de mi pregunta es: ¿Cómo puedo dividir una secuencia/cadena en subsecuencias contiguas que, al repetirse y con cremallera , producirá la secuencia resultante más larga posible.
Para el ejemplo anterior, podría dividir una cadena de longitud $7$ de la siguiente manera:
7: abcdefg 7: abcdefg
I II
1: aaaa 3: abcabcabcabc
2: bcbc 4: defgdefgdefg
4: defg Por supuesto, utilizando la segunda distribución, la secuencia resultante tiene un periodo mucho mayor.
Así que:
¿Qué algoritmo/enfoque puedo utilizar para resolver este problema y maximizar el producto? ¿Se trata de un problema conocido y qué complejidad tendría el cálculo de la solución? No es NP, espero.
Edición: Solución parcial
Como señaló @KennyTM en los comentarios, Función de Landau $g$ describe el LCM máximo, es decir $g(7) = 12$ .
Así que esto se convierte en realidad: ¿Cómo producir realmente la partición? ¿El conocimiento de $g(x)$ ayuda aquí, ¿tal vez para una solución de programación dinámica?
