Para abordar este problema, primero observé que
Donde es el número de divisores (no necesariamente primos) de m . Si m es el entero más pequeño tal que ϕ ( m ) = n , entonces
( e 1 + 1 ) ( e 2 + 1 ) ⋯ ( e k + 1 ) = n
Ahora debemos elegir tal que ∏ i p e i i sea mínimo. Las opciones para p son triviales: son solo los números primos en orden ascendente.
Sin embargo, mi primer pensamiento para elegir fue incorrecto. Pensé que podría simplemente factorizar n , ordenar los factores en orden descendente y restar 1. La mayoría de las veces esto funciona bien, por ejemplo, el entero más pequeño con n = 15 divisores es:
15 = ( 4 + 1 ) ( 2 + 1 ) m = 2 4 3 2 = 144
Pero esto es incorrecto para :
16 = ( 1 + 1 ) ( 1 + 1 ) ( 1 + 1 ) ( 1 + 1 ) m = 2 1 3 1 5 1 7 1 = 210
Mientras que la respuesta correcta es:
m = 2 3 3 1 5 1 = 120
Entonces está claro que a veces necesitamos fusionar factores. En este caso porque . Pero no veo exactamente una estrategia de fusión limpia y directa. Por ejemplo, uno podría pensar que siempre debemos fusionarnos en el poder 2 , pero esto no es cierto:
No puedo pensar de inmediato en un ejemplo, pero mi instinto dice que algunos enfoques ambiciosos pueden fallar si fusionan primero los poderes equivocados.
¿Existe una estrategia óptima simple para fusionar estos poderes para obtener la respuesta correcta?
Sin embargo, la solución óptima es:
fuente
Respuestas:
Aquí hay una solución, basada en mis comentarios anteriores. No hago afirmaciones, esto es óptimo.
Y también tenemos la recurrencia:
Para ese fin, aquí hay un código de Python, que está de acuerdo con todos los números que proporcionó anteriormente. Tenga en cuenta que funciona con los logaritmos para mantener los números más pequeños: por lo tanto, el entero real que busca es
round(2**smallest(n))
.fuente
powerset
for factor_list in powerset(factors)
n
multiplicative_partitions(24)
[4, 3, 2]
[6, 2, 2]
fuente