Suma de las cifras del factorial de 100

En una conocida página de retos de programación, aparecía este reto.

“Suma las cifras del factorial de 100”

Recordemos que el factorial de 100 (en notación matemática expresado como 100!) es el resultado de multiplicar todos los números del 100 al 1. Este es un número muuuuy grande. Segun wolframalpha el factorial de 100 es:

93326215443944152681699238856266700490715968264381621468592963895217599993229915608941463976156518286253697920827223758251185210916864000000000000000000000000

El máximo número positivo que se puede almacenar en un entero de 64 bits (el tamaño de palabra de cualquier ordenador hoy en día) es el 9223372036854775807 , un número que, aunque respetable, no llega ni de lejos al orden de magnitud de 100!

Afortunadamente este reto se puede hacer en python (version 2.7) en una única línea de código. Vamos a ello.

Primero necesitamos los números del 1 al 100 para multiplicarlos. Para ello usamos range (o xrange). Abrimos una consola python y escribimos:

>>> range(1, 101)

Aparecerá el resultado:

>>> range(1, 101)
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90, 91, 92, 93, 94, 95, 96, 97, 98, 99, 100]

Esto devuelve una lista con los números del 1 al 100. Ahora tendríamos que multiplicarlos todos para hallar el factorial. Podemos usar reduce para ello:

>>> reduce(lambda x,y:x*y, range(1, 100))
933262154439441526816992388562667004907159682643816214685929638952175999932299156089414639761565182862536979208272237582511852109168640000000000000000000000L

Que parece coincidir con el resultado de wolframalpha :P

reduce aplica una función al conjunto de los elementos de una lista aplicado de 2 en 2. En este caso la función (que aparece como lambda x,y:x*y en el código) realiza una multiplicación de los 2 elementos que se le pasan.

Ahora hay que sumar esas cifras, para ello hay que separarlas y sumarlas. Para separarlas, podemos pasarlas a cadena:

>>> str(reduce(lambda x,y:x*y, range(1, 100)))
'933262154439441526816992388562667004907159682643816214685929638952175999932299156089414639761565182862536979208272237582511852109168640000000000000000000000'

y luego pasar a entero cada carácter de la misma. Para ello usamos lo que se llama list-comprehension.

>>> [int(x) for x in str(reduce(lambda x,y:x*y, range(1, 100)))]
[9, 3, 3, 2, 6, 2, 1, 5, 4, 4, 3, 9, 4, 4, 1, 5, 2, 6, 8, 1, 6, 9, 9, 2, 3, 8, 8, 5, 6, 2, 6, 6, 7, 0, 0, 4, 9, 0, 7, 1, 5, 9, 6, 8, 2, 6, 4, 3, 8, 1, 6, 2, 1, 4, 6, 8, 5, 9, 2, 9, 6, 3, 8, 9, 5, 2, 1, 7, 5, 9, 9, 9, 9, 3, 2, 2, 9, 9, 1, 5, 6, 0, 8, 9, 4, 1, 4, 6, 3, 9, 7, 6, 1, 5, 6, 5, 1, 8, 2, 8, 6, 2, 5, 3, 6, 9, 7, 9, 2, 0, 8, 2, 7, 2, 2, 3, 7, 5, 8, 2, 5, 1, 1, 8, 5, 2, 1, 0, 9, 1, 6, 8, 6, 4, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]

Solo queda sumar la lista de enteros:

>>> sum([int(x) for x in str(reduce(lambda x,y:x*y, range(1, 100)))])
648

Y ya está. 648 es el resultado que esperábamos !!!

PD: En python 3, reduce dejó de ser un nombre global para pasar a habitar en functools por lo que debería importarse este módulo primero y dejaría de ser una única línea (bueno si, se podría hacer en una línea pero quedaría más confuso y fuera de lo que se quiere mostrar).