El uso de la función divisor es meramente anecdótico. Simplifica un poco las fórmulas, pero no hay que saber nada sobe ella más que un hecho elemental:
Si tienes un número \( n = q_1^{e_1}\cdots q_r^{e_r} \), donde los \( q_i \) son primos distintos, entonces su número de divisores es \( d(n)=(e_1+1)\cdots (e_r+1) \).
Esto se debe a que un divisor tiene que ser de la forma \( q_1^{k_1}\cdots q_r^{k_r} \), donde cada exponente tiene que ser \( 0\leq k_i\leq e_i \), luego tienes \( e_i+1 \) posibilidades para cada exponente y \( (e_1+1)\cdots (e_r+1) \) posibilidades en total.
No entiendo tu argumento de fuerza bruta. La fuerza bruta pura sería razonar así:
Si un número \( n \) tiene \( 16 \) divisores, entonces los exponentes de sus factores primos cumplen \( (e_1+1)\cdots (e_r+1)=16 \), luego cada \( e_i \) es de la forma \( 2^i-1 \). Esto nos deja cinco posibilidades:
- \( p\cdot q\cdot r\cdot s \)
- \( p^3\cdot q\cdot r \)
- \( p^3\cdot q^3 \)
- \( p^7\cdot q \)
- \( p^{15} \)
donde las bases tienen que ser primos distintos dos a dos. Para que el número sea el menor posible, las bases tienen que ser los menores primos posibles. Por ejemplo, el caso 1 nos da el número \( 2\cdot 3\cdot 5\cdot 7 = 210 \).
En el caso 2 el menor número se obtendrá con el exponente \( 3 \) en el menor primo: \( 2^3\cdot 3\cdot 5 = 120 \).
En el caso 3 sólo hay una posibilidad: \( 2^3\cdot 3^3=216 \) y los casos restantes son mayores que \( 2^7 \), luego no nos sirven, y concluimos que el mínimo es \( 120 \).
Si no quieres fuerza bruta, hay un teorema debido a M.E. Grost (
The Smallest Number with a Given Number of Divisors, The American Mathematical Monthly 75, 725-729), que permite calcular de forma relativamente fácil el menor número con \( q^n \) divisores, donde \( q \) es primo.
Consiste en calcular los números \( G(i, l) = p_i^{(q-1)q^{l-1}} \), donde \( p_i \) es el primo \( i \)-ésimo, \( i, l\geq 1 \) y ordenarlos. Por ejemplo, para \( q=2 \) son
\( \begin{array}{r|rrrr}
&1&2&3&4\\
\hline
2&2&4&8&16\\
3&3&9&27&81\\
5&25&\cdots\\
7&7&49&\cdots\\
11&11&\cdots\\
\end{array} \)
Ordenados son:
\( 2, 3, 4, 5, 7, 8, 9, 11,13, 16, 17, 19, 23, 25, 27, 29, \ldots \)
Si quieres prolongar la sucesión para los valores menores que 100, sólo tienes que enumerar los primos e ir intercalando los números que ves en la tabla. Para valores mayores que 100 hay que prolongar las filas de la tabla.
Lo que dice el teorema de Grost es que el mínimo número con \( q^n \) divisores es el producto de los \( n \) primeros números de esta lista.
En el caso de \( 16 = 2^4 \) es \( 2\cdot 3\cdot 4\cdot 5 = 120 \).
Igualmente, el menor número con \( 2^{16}=65\,536 \) divisores es
\( 2\cdot 3\cdot 4\cdot 5\cdot 7\cdot 8\cdot 9\cdot 11\cdot 13\cdot 16\cdot 17\cdot 19\cdot 23\cdot 25\cdot 27\cdot 29=20\,123\,333\,822\,592\,000 \).
La prueba es elemental. Ahora no tengo tiempo, pero si te interesa la puedo poner.
