El factorial de las mil y una noches.

Leyendo en Internet algunas cosas relacionadas con lo que se trata en la entrada anterior llegué a una de las "delicias digitales endiabladamente difíciles" (en palabras del autor). Se trata de una cuestión incluida en el capítulo 37 del libro La maravilla de los números, de Clifford A. Pickover. Así que desempolvo el libro, que lo tengo en mi estantería.

Incluyo aquí el fragmento al que me refiero:

"Desde la edad de trece años, cada 1001 días el doctor Googol lee Las mil y una noches, lo que significa que lee esa obra una vez cada 2,74 años. Con la excepción del Corán, ninguna otra obra literaria árabe se conoce mejor ni tiene más influencia en Occidente que Las mil y una noches. Esta colección de relatos está agrupada en derredor de uno central relativo a un sultán y a sus amantes. Después de descubrir que su esposa le había sido infiel, el sultán hace la promesa de tomar una nueva novia cada día y hacerla ejecutar al día siguiente.

Cuando Sahrazad fue elegida como su nueva esposa, cada atardecer ella le contaba un cuento al sultán, pero no lo terminaba, prometiendo hacerlo a la siguiente noche si sobrevivía. Esto continuó durante mil y una noches, hasta que el sultán quedó profundamente enamorado de Sahrazad y olvidó sus crueles planes de ejecución.

Una noche, después de haber leído Las mil y una noches, el doctor Googol empezó a preguntarse acerca de un número especial llamado el factorial de las mil y una noches. Este número está definido con el valor de x tal que x! tiene 1001 dígitos. Los factoriales crecen bastante rápidamente: 5!=120, 10!=3.682.800 y 15!=1.307.674.368.000. ¿Cuál es el factorial de las mil y una noches?"

Aprovechando lo que expliqué en la entrada anterior, lo que estamos buscando es el menor número x tal que x! tenga 1001 cifras, entonces, utilizando la expresión cifras de x! = [log(x!)] + 1 obtenemos:

1001 = [log(x!)]+1 que es equivalente a [log(x!)]=1000.

Como log(x!)=log(1)+log(2)+...+log(x) lo que podemos hacer es ir sumando los logaritmos decimales de los números naturales hasta que la parte entera del resultado sea 1000 (teniendo en cuenta que podríamos pasarnos de largo). O equivalentemente, hasta sumar el logaritmo decimal del número que haga que el resultado sea (por primera vez) mayor que 1000.

Con pequeñas modificaciones al programa de la entrada anterior construimos el siguiente código:

#include < stdlib.h >
#include < iostream >
#include < math.h >
main()
{
    double r=0;
    unsigned long int i=2, numero=1001;
    while(r < numero-1)
    {
        r+=log10(i);
        i++;
    }
    i--;  // quitamos el último incremento
    std::cout < < "El primer factorial cuyo resultado tiene por lo menos " < < numero < < " cifras es " < < i < < "!." < < std::endl;
    return 0;
}

La ejecución del programa anterior devuelve:

El primer factorial cuyo resultado tiene por lo menos 1001 cifras es 450!.

Podría ser que 450! tuviera más de 1001 cifras, dado que la condición que imponemos es que por lo menos tenga esa cantidad de cifras. Si ejecutamos el programa de la entrada anterior obtenemos:

El factorial de 450 tiene 1001 cifras.

O si alguien no se fía de mis dotes de programador, también puede preguntárselo a Wolfram Alpha :-)

Problema resuelto. Bueno, este en particular y el general de hallar el menor número x cuyo factorial tenga por lo menos n cifras (siempre que el tamaño de n no desborde la variable).

Curiosidad: Al igual que en la obra El prodigio de los números, Pickover dedica el libro al cuadrado mágico apocalíptico.

Clifford A. Pickover