Ayuda con el problema 2 de la Ronda Final del 2001

Ayuda con el problema 2 de la Ronda Final del 2001

MindOverMatter 14 Nov 2009 19:50

Hola gente del foro!!
Estaba resolviendo algunos problemas viejos a modo de practica y me trabe en este.
Cito:

"Encontrar el menor entero positivo que tenga exactamente:
a) 400 divisores.
b) 1000 divisores."

Hacerlo con fuerza bruta se me hizo un poco complicado, puesto que no tengo limites entre los cuales buscar numeros (o son demasiado amplios).
Ademas, sospecho que debo estar perdiendome de alguna propiedad de cantidades de divisores que pueda implementar.
Algun consejo/sugerencia?
Gracias de antemano :)

Re: Ayuda con el problema 2 de la Ronda Final del 2001

pabloh 15 Nov 2009 20:36

Hola!

Bueno, primero, habría que ver cómo es tu solución por “fuerza bruta”. Por ejemplo, para contar la cantidad de divisores de un entero $N$ una solución es revisar todos los enteros de 1 a $N$. Eso no es eficiente. En el curso CyM98 de OmaNet las lecciones Los números primos y Divisor común mayor tienen información sobre cómo encontrar divisores y factores primos de varias formas, algunas de ellas razonablemente eficientes.

Segundo, límites entre los cuales buscar números. El límite inferior es 1, porque el enunciado dice “enteros positivos”. El límite superior no aparece, y eso es parte del problema, claro. Parte de tu trabajo es decidir cómo solucionar o esquivar esa cuestión. Una cota fácil para a) es $2^{399}$ (ejercicio: ¿por qué?), pero no sirve de mucho porque es demasiado grande. Yo digo que no hace falta poner un límite superior. Si no ves por qué ¡consultanos!

Tercero, puedes ser que haya alguna propiedad relacionada con cantidad de divisores que sea útil en este problema ;-) . Por ejemplo, hay una fórmula que si tenés la factorización en primos de $N$ (o sea, $N=p_1^{a_1} \cdot p_2^{a_2} \cdot p_3^{a_3} \cdot \ldots \cdot p_k^{a_k}$) te da la cantidad de divisores de $N$. Si no la conocés, podés (en orden de mejor a peor):

1. deducirla vos mismo (te puede resultar difícil, pero es excelente ejercicio¹),
2. preguntarnos acá mismo,
3. buscarla en algún libro, o
4. buscarla en internet :-P .

Por último, ¡no dudes en volver a preguntar hasta que te salga! (Hay más pistas. ;-) )

Footnotes

1. pista: empezá por $N=p_1$ con $p_1$ primo, luego $N=p_1^2$, luego $N=p_1^3$, luego $N=p_1^{a_1}$ y luego $N=p_1^{a_1} \cdot p_2^{a_2}$

Re: Ayuda con el problema 2 de la Ronda Final del 2001

MindOverMatter 17 Nov 2009 20:49

Muchas gracias por responder!
De hecho, conocía la fórmula que indica la cantidad de divisores de un numero a partir de los exponentes en sus factores primos, que sería (a1+1)*(a2+1)*…(an+1)…sin embargo, aunque la estaba implementando al problema (en la funcion para calcular cantidad de divisores); y obtenia el menor numero con 400 divisores en algo asi como 1:17 minutos, me inclinaba a pensar que podia implementar la formula de otra manera (ya que los numeros primos son los "bloques" que construyen a los demas numeros, porque no construir al numero a partir de estos en lugar de buscar un numero ya "construido"?). Además mi solucion iterativa no funcionaba para el de 1000 divisores, y sospechaba que era un numero bastante grande (al menos, para la velocidad de la funcion).
Sin embargo, y por mas que estaba seguro de que 2^399 era un numero de 400 divisores; y 2^999 un numero de 1000; como encontrar el menor?
Finalmente me di cuenta de que (y espero estar deduciendo correctamente) es un problema que se resuelve facilmente sin computadora.
Cuando descompuse a 400 en factores primos, me quedo:

400 = 2*2*2*2*5*5

Entonces, cuando descompuse al menor numero con 400 divisores positivos (encontrado iterativamente) en sus factores primos me dio:

6486480 = 2*2*2*2*3*3*3*3*5*7*11*13

Me di cuenta que al utilizar la formula con sus factores primos me daba:

2^4*3^4*5^1*7^1*11^1*13^1 => (4+1)*(4+1)*(1+1)*(1+1)*(1+1)*(1+1) => 5*5*2*2*2*2 = 400

Entonces probe con algunos numeros mas y me di cuenta de que el menor numero con X cantidad de divisores se puede construir descomponiendo a X en factores primos y ordenando esos factores (disminuidos en 1 unidad) como exponentes de numeros primos consecutivos, comenzando desde 2.
Así, el menor numero con 1000 divisores positivos seria:

1000 = 2*2*2*5*5*5;
cantidad_divisores(n) = 1000;
n = 2*2*2*2*3*3*3*3*5*5*5*5*7*11*13 = 810810000

Es esto correcto?
Si es asi, Muchas gracias por su ayuda! :)
saludos

Re: Ayuda con el problema 2 de la Ronda Final del 2001

pabloh 17 Nov 2009 21:27

Ok, entonces, si la descomposición de $N$ en primos es $N=p_1^{a_1} \cdot p_2^{a_2} \cdot p_3^{a_3} \cdot \ldots \cdot p_k^{a_k}$, tenemos que la cantidad de divisores de $N$ es $(a_1+1) \cdot (a_2+1) \cdot (a_3+1) \cdot \ldots \cdot (a_k+1)$. En particular, si $p$ es un primo, la cantidad de divisores de $p$ es 2, y de $p^a$ es $a+1$.

De ahí que si la cantidad de divisores de $N$ es 400 (o 1000), los exponentes de los factores primos, incrementados en 1, tienen que dividir a 400 (o 1000).

La parte difícil es justificar que el número que construiste es el mínimo posible. ¿Por qué no poner por ejemplo $2^9$ en lugar de $2^4 \cdot 13$? Hay unas cuantas posibilidades, y para que tu resolución sea correcta tenés que justificar cuidadosamente que no se te haya escapado analizar absolutamente ninguna de esas posibilidades, y que efectivamente es la menor de todas. Nada de poner “es obvio que lo más chico se logra con un 2 acá”. :-P

¿Cómo sería tu justificación? O tal vez prefieras hacer un programa que revisa menos casos. Por ejemplo, los factores primos de la solución van a ser los menores primos. Si no fuera así puedo reemplazar al primo por uno más chico (¡sin cambiar los exponentes!) y obtengo un número menor. (Se puede formalizar con letritas.) Esto puede servir para acelerar el programa, o para hacer un programa que construya el número.