Por @Alvy — 21 de Junio de 2009

¿Cuál es el primer factorial que termina en mil ceros?

El factorial de un número natural es el producto de todos los números entre 1 y dicho número. Se escribe con el signo «!» Por ejemplo el factorial de 4 se calcula como 4! = 4 × 3 × 2 × 1 = 24.

Este breve problema lo encontré en Simplemente números, en cuyos comentarios está la solución oficial.

{Importante: puedes dejar pistas e ideas al respecto en los comentarios, pero recuerda esperar 24 horas antes de hablar abiertamente de la solución, para que los demás puedan disfrutar buscándola. Quien no quiera recibir ninguna ayuda ni pista para dar con la respuesta tal vez prefiera no leer los comentarios.}

Compartir en Flipboard  Compartir en Facebook  Tuitear

26 comentarios

#1 — franky

Este es mas facil que los que normalmente poneis

Pista: hay que fijarse en los factores que seguro que tendra ese numero, los factores de 10

#2 — Martín

Es todavía mas fácil que eso: con hacer un programa que calcule sucesivamente los factoriales y que pare cuando encuentre uno cuyos mil primeros dígitos (por la derecha) son ceros.

#3 — Pablo

Martín: Aún más fácil, mirar la respuesta.
En cuanto a tu programa, 1000 cifras es una precisión que pocos manejan. Y cuando te pregunte por el primer número cuyo factorial acaba en 1000000 ceros vas a divertirte cosa fina programando.

#4 — Héctor

Es bastante fácil, aunque hay que reconocer que si lo haces a lo loco (cuenta de la vieja) te puedes colar un poco porque parece demasiado fácil.

En realidad se puede hacer tanto con un programa que cuente los factores multiplicativos (no el factorial) o calculando una regresioón y sacando una ecuación ajustada. Y si no te quieres complicar, con la calculadora y yendo a tientas lo puedes obtener fácilmente.

#5 — Dye

En realidad lo unico que es necesario saber para resolver este problemilla es que 23 es el numero primo p mas pequeño tal que p! tiene p cifras :-P

#6 — josem1988

Buenas a todos,

A Martin: lo que comentas de hacer un programa que te calcule sucesivos factoriales y cuando llegue a uno con 1000 ceros que pare.....es una burrada. Ya sólo calcular factoriales relativamente grandes (100!, por ejemplo, ya es, aproximadamente, un 1 seguido de 158 ceros) con el ordenador es computacionalmente caro (el número de operaciones necesarias para calcular n! se hace enorme cuando n es grande), pero si además tienes que calcular una buena cantidad de factoriales grandes,...mueres.

Una buena manera de abordar el problema es como dice franky, fijarse en cuantos factores de 10 tendrá ese gigantesco número (de aproximadamente 12692 cifras).

#7 — Sequedad Íntima

No parece que lo hallais pensado mucho en poner a un ordenador a resolver esto. El numero más pequeño (no el factorial) que tiene mil ceros es un uno seguido de mil ceros. 10¹⁰⁰⁰ y en base binaria seria 2³³²², tendríais que usar un formato de numero muy largo para manejar esta cifra, pero seguramente sea más alta. Un formato con 3322 bits. Eso aparte de lo que podría tardar el ordenador en manejar esos datos.

Si se puede programar la solución, pero hay que ser más sutil. Si tengo tiempo la hago en java, se me acaba de ocurrir una idea.

#8 — josem1988

Sequedad íntima: dudo muchisimo que programes un algoritmo (bueno, programar si. Pero hacer funcionar es otra cosa...) como el que ha propuesto nuestro compañero Martín.

Ya nos contarás en que consiste la sutileza.

(Evidentemente se puede programar...solo tienes que ver como calcula Mathematica o Maple factoriales)

#9 — Sequedad Íntima

Te diré que tengo la solución y he tenido que hacer un pequeño programa para ayudarme. Como es tan pequeño lo pegaré cuando pueda dar la solución en los comentarios.

Si quereis pistas probad a usar las propiedades de los logaritmos.

#10 — franky

¿todos habeis empleado programas?

¿nadie conoce esa conocida herramienta para calcular el exponente de cierto factor primo en un factorial?

Es tan simple como usar la función parte entera y un poco de sentido comun

O mas facil, si lo trabajas como algo-parecido-a-un-fractal

Mi respuesta, en 24 horas

#11 — sabbut

¿Todos trabajáis con programas? Desde luego, a veces los informáticos lo complicáis tanto...

Para obtener un cero hace falta tanto un múltiplo de 2 como uno de 5. Como los de 2 son más comunes y ambos están distribuidos de forma uniforme entre los naturales, sin saltos ni nada raro, podemos reducir esto a buscar múltiplos de 5.

De esa manera, 5! es el primer factorial que acaba en un cero.
10! es el primer factorial que acaba en dos ceros.
15! es el primer factorial que acaba en tres ceros.
20! es el primer factorial que acaba en cuatro ceros.
25! es el primer factorial que acaba en seis ceros. Son seis y no sólo cinco porque 25 tiene dos factores 5, y cada uno aporta un cero al resultado final.

No voy a explayarme más para no dar la solución, pero esta es la manera de razonar, ¡y no hacen falta ordenadores ni cosas raras!

#12 — sabbut

De hecho, se puede emplear el mismo razonamiento para comprobar cuál es el primer fractal que acaba en un gúgol de ceros (es decir, un múltiplo de un gugolplex), aunque de forma mucho más trabajosa y empleando por supuesto un ordenador. En este caso, multiplicar 1 por 2 por 3 por 4 etcétera para hallar la respuesta sería directamente imposible.

Digo esto porque no hace falta escribir el número entero, sino que basta con hallar n tal que n! es el menor factorial que en base diez acaba en mil ceros.

#13 — Sequedad Íntima

Para sabut:

Yo empleé ese mismo razonamiento, lo único que por no pararme a contar cuantos ceros tiene cada múltiplo de 5 multiplicado con un múltiplo de 2 hice un programa.

1000 ceros me parecen muchos como para ponerme a contar. Y no soy informático, estudio teleco xD.

#14 — sabbut

Sequedad Íntima: Nah, si eso lo dije para provocar un poco, que he conocido a alguno que hasta para multiplicar por 10 usaba calculadora. Es en esos momentos cuando llego a entender la aversión que le tenía mi profesora de matemáticas del colegio a que los alumnos usáramos calculadora para hacer operaciones sencillas.

#15 — Sequedad Íntima

No si viendo la demostración de un tal Pablo Sussi en el enlace de donde lo sacaron me parece que hice un poco el tonto programando. Aunque también lo hice porque tenia ganas de programar xD.

#16 — el dva

Eso ya es bastante simple con un solo algoritmo, puedo poner el segundo y el tercero, mas faciles todavia, el primer numero solo toma 0.35 seg. en encontrarlo. con mi humilde pentium III., mas se demora en comprobar.

como no se puede dar la solucion, dare una pequeña gran pista:

1011 ceros finales en 4051!
1012 ceros finales en 4056!
1013 ceros finales en 4061!
1014 ceros finales en 4066!
1015 ceros finales en 4071!
1017 ceros finales en 4076!
1018 ceros finales en 4081!
1019 ceros finales en 4086!
1020 ceros finales en 4091!
1021 ceros finales en 4096!
1023 ceros finales en 4101!
1024 ceros finales en 4106!
1025 ceros finales en 4111!
1026 ceros finales en 4116!
1027 ceros finales en 4121!
1030 ceros finales en 4126!

#17 — franky

sabbut:

ese era exactamente mi razonamiento.

¿quien quiere fiarse de un monton de semiconductores teniendo una brillante maquinaria detrás de las gafas?

#18 — Baro

lo que haría yo sería decir que, siendo p un producto indeterminado e indeterminable de numeros naturales que no se expresan de la forma 2^n*5^m

solucion =
p*10^1000 =
p*5^1000*2^1000 =
p*2*5*5^999*2^999 =
p*2*3*4*5*5^999*2^997 =
p*2*3*4*5*6*5^999*2^996 =
p*6!*5^999*2^996 =
...

Y con paciencia, ir completando el factorial hasta "quedarme sin 5s ni 2s"

Pero no lo voy a hacer porque como estudiante de informatica que soy, lo que prima es la eficiencia y sobre todo, trabajar poco.

#19 — Ignacio

Aparte de poner la solución, os pongo la secuencia de los primeros números factoriales que terminan en 10^N.

N 1er factorial que termina en N ceros

0 5!

1 45!

2 405!

3 4005! --> Solución al problema actual

4 40010!

5 400005!

6 4000005!

7 40000010!

8 400000015!

Resulta muy llamativa la irregularidad de las cifras menos significativas. ¿Alguna idea sobre cómo caracterizarlas en función de N?

#20 — Sequedad Íntima

Como prometí ayer aqui va la solución.

Lo básico es trabajar con logaritmos en vez de con números normales ya que estos son mucho más pequeños. Lo que queremos es un número que acabe en mil ceros, o lo que es lo mismo que su logaritmo en base 10 sea algo por 1000. Ese algo no nos importa, así que pasamos de él.

Una propiedad importante de los logaritmos es que Log (a*b)=Log (a+b). Dado que el número ese será Log(n·(n-1)·....·2·1)=Log n + Log (n-1) + .... Así que solo tenemos que sumar numeros pequeños.

De estos números solo nos interesan los que sean divisores de 10,100,1000,.... Cuyos logaritmos son 1,2,3,... Ese es el número de ceros que aportan. Si factorizamos: 10=2·5;100=2·2·5·5;100=2·2·2·5·5·5;... Es decir que nos interesan los múltiplos de 5, y estos aportarán tantos ceros como 5 contengan. Es decir 25·4=100;25=5·5. Como hay muchos más doses que cincos podemos emparejarlos sin más.

Así que ahora solo se trata de contar los múltiplos de 5 (ya que los de 10 también son múltiplos de 5), contar los ceros que aportan y sumar. P.Ej para 6 ceros: 5,10,15,20,25(Que aporta 2 ceros). 25! tiene 6 ceros.

Como no me apetecía ponerme a contar hice un programa en java. Os lo pego en el siguiente comentario que aquí no cabe. La solución es 4005!.

#21 — Sequedad Íntima

public class facto {

public static void main(String[]args){

int nceros=1000;

if(args.length==1)

nceros=Integer.parseInt(args[0]);

int cont10=0;

int cont=5;

while(cont10

#22 — sabbut

Parece que se puede proceder así en pseudocódigo:

Sea n tal que se quiere saber en cuántos ceros acaba n!

Sea x=4*10^n /* ésta es la aproximación inicial */

Sea k=10^n

Mientras x > 0, {

x -> parte_entera(x/5)

k -> k - x /* se entiende el nuevo valor que toma x */

}

La solución sería 4*10^n+5*k

Por ejemplo, para n=4

x=40000

k=10000

iteración 1: x=8000, k=2000

iteración 2: x=1600, k=400

iteración 3: x=320, k=80

iteración 4: x=64, k=16

iteración 5: x=12, k=4

iteración 6: x=2, k=2

iteración 7: x=0, k=2

con lo que (4*10^4+5*2)! = 40010! acaba en 10000 ceros.

Falta ver que se cumple siempre esto, pero vamos, a mí me sale:

0 5!

1 45!

2 405!

3 4005!

4 40010!

5 400005!

6 40...005! (oculto sólo ceros, un cero más en cada columna respecto de la anterior)

7 40...010!

8 40...015!

9 40...015!

10 40...015!

11 40...015!

12 40...010!

13 40...015!

14 40...020!

15 40...025!

16 40...025!

17 40...025!

18 40...020!

19 40...015!

20 40...025!

21 40...030!

22 40...035!

Parece que tienen que ver los restos que quedan de las sucesivas divisiones entre 5, si la suma de esos restos es 4k, entonces el factorial buscado es de la forma 4*10^n+5k. De todas formas, no he podido demostrar esto de forma rigurosa ni encontrar un contraejemplo, así que esto queda en el aire.

#23 — visent

Me he perdido con vuestras explicaciones, pero me han parecido de lo más interesantes.

Saludos.

#24 — Tkn

Perdonad mi escritura: no soy "bloguero" ni siquiera comentarista habitual.

Un par de precisiones:

#6, el cálculo del factorial no es computacionalmente costoso: es lineal.

#7: Java tiene una clase, BigInteger, que permite manejar números... (déjadme que mire)... arbitrariamente grandes. Y es relativamente rápido. Factorial de 4005 lo ha calculado (mediante un programa: la clase sólo tiene, suma, resta, etc.) 37662573 nanosegundos.

Saludos. Estos problemas son muy estimulantes.

#25 — curro

Creo que se puede resolver con una ecuación simple, de primer grado y un poquito de lógica. A ver... sea x el número que buscamos. Cada múltiplo de 5 aporta un cero, como hay x/5 múltiplos de 5 si ordenamos los números desde 1 hasta x, tendremos que estos aportan x/5 ceros. Cada múltiplo de 25 aporta otro cero, tendremos ahora x/25...

Así llegamos a x/5 + x/25 + x/125+ x/625 + x/3125= 1000. ¿Que por qué me he parado en 3125?... Pues muy sencillo, porque si incluyo la siguiente potencia de 5 (15625), al hallar la solución me sale un número que al dividirlo por 15625 es menor que uno...

Soluciono y el resultado es algo superior a 4001, como ha de ser múltiplo de 5 y superior a 4001, el resultado es 4005.

¿Acerté?

#26 — cards

curro, tu solución es correcta pero:

x/5 + x/25 + x/125+ x/625 +...

No son divisiones normales, es decir, son divisiones ENTERAS (sin decimales), entonces si es correcto.

Por ejemplo, con 125! sale bien porque es múltiplo de cinco, pero probando con 124! mira lo que pasa:

124/5 + 124/25 = 29.76 incorrecto

Pero con división entera (represado, por ejemplo, como //) sucede esto:

124//5 + 124//25 = 24+4=28 resultado correcto

(incluso podría poner mas factores, total, la división entera dará cero)

124! tiene 28 ceros en verdad y no los 29~30 que salen dividiendo normal.

(ojo, no es el primero que tiene 28 ceros, el primero es el 120, simplemente he usado el 124 para mostrar el error que acarrean los decimales).

Es lógico pensar en divisiones enteras, ja que estamos "contando" ceros (y arrastrar los decimales y sumarlos hacen aparecer "nuevos" ceros, causando el resultado incorrecto)

Pues bien, comprobando 4005!:

4005/5 + 4005/25 + 4005/125 + 4005/625 + 4005/3125 = 1000.93 error

De echo, a partir del 4002 sale que tiene 1000 y algo de ceros. Cosa totalmente falsa.

Pero con división entera:

4005//5 + 4005//25 + 4005//125 + 4005//625 + 4005//3125 = 801+160+32+6+1 = 1000 zeros

Con 4004 da 999 ceros, tambien correcto. Por lo tanto, confirmo que 4005 es el primero con 1000 zeros

Como las divisones normales no son las adecuadas, resolverlo mediante una equacion no es del todo exacto

Por ejemplo, el 1r numero con 28 ceros es el 120, pero...

x/5+x/25=28 aislando sale: x=116.66666

Pero ahora biene tu "trampa" (ojo, que funciona perfectamente) que es "redondarlo" hasta el siguiente multiplo de 5, en este caso 120, el resultado correcto.

Técnicamente la ecuacion dice que el numero 116.6666 tiene 28 ceros, cuando el 116 o el 117 tienen 27 (tambien el 115,118 y 119).

Error causado por las divisiones normales, y compensado con el redondeo.

Una equacion con divisones enteras seria lo correcto, pero imposible de resolver.

Asi que tu solucion funciona perfectamente ^^

Bueno, ya acabo, solo queria hacer un pequeño inciso tu su solución.

Asi que, si se quiere saber cuantos ceros tiene CUALQUIER NUMERO de manera correcta, se tienen que usar divisiones enteras.

Si se quiere saber el 1r numero con X ceros, se puede usar el metodo de curro.

Pero ojo! como no se sabe el resultado, hasta que factor tenemos que añadir?

Pues, no se sabe. Se tiene que iterar. Por ejemplo, se divide hasta el factor 3125, si el resultado es menor, sobran factores (los mas grandes). Si el resultado es mayor, se tiene que añadir factores.

Se tienen que ir añadiendo o quitando factores hasta encontrar los necesarios.

Como en este caso el numero era el 4005, se tiene que añadir hasta el 3125 (el siguiente seria 15625, pero como ya es mayor que el numero que se busca, pues no se pone).

Otra manera (y la que utilizado yo) es crearse una pequeña hoja de calculo con unos cuantos factores (he utilizado 10) y que haga las divisionese ENTERAS las sume.

Vas cambiando el numero hasta encontrar el que te de 100 (en 10 segundos lo he obtenido).

Asi te ahorras hacer equaciones añadiendo y quitando factores, ya que en la oja de calculo puedes poner tantos como quieras que no van a a fectar al resultado, ya que si son mas grandes que el numero, su divison entera dará cero y no afectaran al computo de ceros.

En cambio en la equacion salen numero deciamales que afectaran al resultado.

Ostiaaaaa, me he pasado XD