¿Cuál es el menor número con exactamente 100 divisores?
Una vez resuelto con Python podemos aprovechar para generalizar el problema al siguiente:
¿Cuál es el menor número con exactamente m divisores?
He subido a mi repositorio de matematica-recreativa en GitHub una solución utilizando la librería sympy, que calcula los divisores de un número dado (también se puede implementar dicha función fácilmente).
 |
| Imagen extraída de joguiba.com |
La pregunta es ¿siempre existirá dicho número? Es decir, dado cualquier número natural positivo m, ¿podemos encontrar un natural con exactamente m divisores?
La respuesta es que sí. Si tenemos la factorización en números primos de un número, podemos calcular sus divisores como el producto de los exponentes aumentados en una unidad.
Por ejemplo, el número 18 factoriza de la siguiente manera 18 = 2^1 · 3^2. Si aumentamos los exponentes en una unidad y los multiplicamos obtenemos (1+1) · (2+1) = 2 · 3 = 6. Por lo que el número 18 tiene 6 divisores.
Div(18) = {1, 2, 3, 6, 9, 18}
Por tanto, a la pregunta de si siempre existirá dicho número con exactamente m divisores debemos contestar que sí porque una cota superior siempre será 2^(m-1), que por lo anterior sabemos que tiene m divisores.
¿Podríamos utilizar esto para abordar la programación de la solución desde otro enfoque? ¿Será más rápido, más lento o dependerá del caso?
Si alguien se anima a implementar las dos formas (calculando divisores o utilizando los exponentes de la factorización) para comparar casos que nos cuente sus resultados en los comentarios.
No hay comentarios:
Publicar un comentario