¿Es posible hallar la suma de dígitos de $n!$ ( $n \in \mathbb{N} \text{ and } n \le100$ ) sin calcular realmente el factorial?

Question

¿Es posible hallar la suma de dígitos de $n!$ ( $n \in \mathbb{N} \text{ and } n \le100$ ) sin calcular realmente el factorial?

Me enfrenté a este problema en la prueba de aptitud cuantitativa que pide para encontrar la suma de los dígitos de $25!$ Me preguntaba si hay alguna método del lápiz de papel para deducir la suma contando el número de cada dígito en el factorial sin llegar a computarlo todo.

Answer 1

Por "sin calcularlo todo", voy a suponer que te refieres a "sin calcular el factorial de la forma tradicional, por fuerza bruta", es decir, "mostrar cualquier atajo posible".... ¡echemos un vistazo a 25! porque algunos de los métodos de papel y lápiz se aplicarán también a números superiores...

Primero vamos a escribir los factores de los números del 2 al 25: 2,3,2*2,5,2*3,7,2*2*2,3*3,2*5,11,2*2*3,13,2*7,3*5,2*2*2*2,17,2*3*3,19,2*2*5,3*7,2*11,23,2*2*2*3,5*5

Contando los factores, tenemos 22 2s, diez 3s, etc, es decir, ¡25! se puede escribir como: 2^22 * 3^10 * 5^6 * 7^3 * 11^2 * 13 * 17 * 19 * 23

Como dice joriki, podemos tirar dieces, así que vamos a tirar 6 de 5 y 6 de 2:

2^16 * 3^10 * 7^3 * 11^2 * 13 * 17 * 19 * 23

Podemos ponérnoslo aún más fácil factorizando algunos números con los que nos resulte más fácil trabajar sobre el papel. Por ejemplo, es fácil multiplicar por 1001, y 1001 es 7*11*13, así que separemos esos 3 factores:

2^16 * 3^10 * 7^2 * 11 * 17 * 19 * 23 * 1001

Del mismo modo, el 99 es fácil de trabajar, así que saquémoslo:

2^16 * 3^8 * 7^2 * 17 * 19 * 23 * 1001 * 99

Y el 98 es sólo un poco más difícil que el 99:

2^15 * 3^8 * 17 * 19 * 23 * 1001 * 99 * 98

Y, por último, 102 también está a sólo dos de 100:

2^14 * 3^7 * 19 * 23 * 1001 * 99 * 98 * 102

Ahora que lo pienso, 98 * 102 son 9.996, a sólo cuatro de los 10.000:

2^14 * 3^7 * 19 * 23 * 1001 * 99 * 9,996

Y multiplicar por 9 es más fácil que por 3, así que..:

2^14 * 3 * 9^3 * 19 * 23 * 1001 * 99 * 9,996

A estas alturas ya no nos quedan trucos, así que vamos a por ello. Hagamos ahora los grandes primos: 19 * 23 = 437.

Luego multiplica por 9 3 veces: 4370 - 437 = 3933 39330 - 3933 = 35397 353970 - 35397 = 318573

Y multiplica por 3 una vez:

318573 * 3 = 955719

Luego duplícalo 14 veces. (Espero no ser el único al que le resulta fácil duplicar números).

1911438 3822876 7645752 15291504 30583008 61166016 122332032 244664064 489328128 978656256 1957312512 3914625024 7829250048 15658500096

Los únicos factores que nos quedan son 1001, 99 y 9.996. Hagamos este último primero... es 10.000-4, así que doblaremos dos veces más:

31317000192 62634000384

Y luego resta:

156585000960000 - 62634000384 =156522366959616

Multiplica por 99:

15652236695961600 - 156522366959616 =15495714329001984

Y por último multiplica por 1001:

15495714329001984000 + 15495714329001984 =15511210043330985984

Por último, puedes sumar esos dígitos.

1+5+5+1+1+2+1+0+0+4+3+3+3+0+9+8+5+9+8+4=72

como menciona mt_, esperamos que el resultado sea divisible uniformemente por 9, por lo que 72 suena bastante plausible.

p.d. Nota para los operadores de stackexchange: la tendencia en esta cuestión parece ser la de publicar comentarios (no respuestas) a la pregunta original. Me encantaría hacerlo, pero como todavía tengo una reputación baja, no puedo publicar comentarios.