 |
| Imagen generada con IA |
En una entrada anterior plantee el problema de encontrar el menor número con un número exacto de divisores.
Por ejemplo, el menor número con exactamente 1000 divisores es 810810000. Para ello desarrollé un programa en Python que recorría los naturales calculando sus divisores hasta encontrar uno que tuviera la cantidad deseada de divisores.
El programa funciona, pero utilizar una técnica de recorrido exhaustivo calculando los divisores de cada número no es un enfoque demasiado óptimo.
Vimos que el problema siempre tiene solución, en las condiciones planteadas. Para justificarlo me basé en propiedades de la factorización en números primos y planteé la pregunta de si era posible utilizar esto para abordar la programación desde otro enfoque.
Aunque pedí que si alguien se animaba a hacerlo lo compartiera, al final yo mismo me he animado a hacerlo y aquí está el código. Este enfoque es muchísimo más eficiente, pero para llegar hasta él hay que profundizar un poco en la parte matemática del problema.
Resumo el procedimiento con un ejemplo concreto: encontrar el menor número con exactamente 100 divisores (problema original del libro).
- Factorizamos el número de divisores deseado: 100 = 2^2 · 5^2
- Creamos una lista de mayor a menor con todos los factores primos repetidos tantas veces como diga el exponente: [5, 5, 2, 2]
- Elevamos los primeros 4 números primos (porque la lista anterior tiene 4 elementos) a los factores de la lista anterior menos una unidad: 2^(5-1), 3^(5-1), 5^(2-1), 7^(2-1)
- Multiplicamos los números resultantes en el paso anterior: 2^4 · 3^4 · 5 · 5 = 45360.
- El número obtenido es el menor con exactamente 100 divisores.
¿Por qué ordenamos la lista de los factores de mayor a menor? Porque como buscamos generar el menor número, nos interesa que los mayores exponentes estén en los números primos más pequeños.
¿Por qué separamos los factores primos de la factorización obtenida en el paso 1? Esta es la pregunta clave.
En la solución que da en su libro, Mariano Mataix calcula todas las combinaciones posibles con la factorización de 100:
100 = 2 · 2 · 5 · 5
100 = 2 · 5 · 10
100 = 2 · 2 · 25
100 = 2 · 50
100 = 4 · 5 · 5
100 = 4 · 25
100 = 5 · 20
100 = 10 · 10
Después calcula los primeros números primos elevados a dichas combinaciones (exponentes mayores primero) para determinar qué resultado de todos los posibles es el menor: 45360, 207360, 521654240, ... (todos ellos tendrán 100 divisores).
Para resolver el problema planteado es suficiente este enfoque, pero si pudiéramos determinar directamente qué combinación es la que produce el menor resultado sin necesidad de calcular todas las combinaciones nos ahorramos un buen trabajo, especialmente cuando los números son muy grandes.
Resulta que sí podemos saber qué combinación es la que produce el menor resultado. Siempre será la que separa los factores primos con exponente 1 (lo que hicimos en el paso 2). La justificación de esto me ha llevado algo de trabajo porque no veía que esto fuera así siempre, pero finalmente pude llegar a ella.
Podríamos resumir el objetivo de la siguiente manera. Si k1 y k2 son números primos consecutivos, p y q dos naturales mayores que 1, con p > q, ¿es cierta la siguiente desigualdad?
En un momento determinado de la justificación utilizo esto.
PD: sí, el editor de Blogger es muy malo. En algún momento configuraré que me deje escribir las fórmulas directamente en LaTeX.
No hay comentarios:
Publicar un comentario