¡Encuentra la suma de los dígitos del número 100!

Question

Estoy trabajando en un problema del Proyecto Euler http://projecteuler.net/problem=20 .

$n!$ significa $n(n - 1)\dots...3.2. 1.$

Por ejemplo, $10!$ $=$ $10$ $9$ $...$ $3$ $2$ $1$ $=$ $3628800$ y la suma de los dígitos del número $10!$ es $3 + 6 + 2 + 8 + 8 + 0 + 0$ $=$ $27$ .

Encuentra la suma de los dígitos del número $100!$

El quid del problema es que, el número es demasiado grande para los tipos de datos nativos.

Podría simplemente usar python / ruby o algún lenguaje que tenga tipos int grandes nativos, pero muchos de estos problemas tienen pequeños trucos inteligentes.

Mi primer pensamiento fue simplemente mod 10 la respuesta una y otra vez, pero comprobando wolframalpha.com me muestra que sólo recortaría $24$ dígitos de la $158.$

Mi segunda idea es hacer una pequeña implementación de BCD capaz de sumar y multiplicar.

Así que he investigado un poco, no puedo encontrar ninguna manera de hacer la función gamma hormiga más fácil que el factorial ...

Me he encontrado con cosas como Aproximación de Stirling pero parece que calcular eso requeriría más trabajo de lo que vale hacer funciones superdimensionadas.

Así que mi pregunta, supongo: ¿se puede digerir este problema de manera que se resuelva utilizando sólo números arbitrariamente pequeños?

Answer 1

Tiene que haber una forma mejor.

$100!$ es el producto de sólo 100 números pequeños, cada uno de los cuales tiene una factorización prima fácil de encontrar. Por el Teorema Fundamental de la Aritmética (y la conmutatividad), la factorización prima de $100!$ se puede encontrar "agrupando" los primos similares de cada una de las factorizaciones primarias de sus factores. Por ejemplo, $8! = 2^3 \cdot 7 \cdot 2 \cdot 3 \cdot 5 \cdot 2^2 \cdot 3 \cdot 2 = 2^7 \cdot 3^2 \cdot 5 \cdot 7$ .

Cada uno de los factores primos puede expandirse como potencias de 10, por ejemplo $a\times 10^2 + b \times 10 + c$ .

A partir de ahí, debería ser más o menos sencillo distribuir sobre potencias de 10 para encontrar cada dígito individual. Suma, y listo.

Voy a ver si puedo MATLAB un ejemplo ... pero aquí es un ejemplo para $8!$ :

$$\begin{align*} 8! &= 2^7 \cdot 3^2 \cdot 5 \cdot 7\\ &= (1\times 10^2 + 2\times 10 + 8) \cdot 9 \cdot (3\times 10 + 5) \\ &= (9 \times 10^2 + 18 \times 10 + 72) \cdot (3\times 10 + 5) \\ &= ((9+1) \times 10^2 + (8+7)\times 10 + 2) \cdot (3\times 10 + 5) \\ &= (1 \times 10^3 + 1\times 10^2 + 5\times 10 + 2) \cdot (3 \times 10 + 5) \\ &= 3 \times 10^4 + 3\times 10^3 + 15 \times 10^2 + 6 \times 10 + \ldots \\ &\ldots 5\times 10^3 + 5\times 10^2 + 25\times 10 + 10). \end{align*}$$

El último paso fue la distribución de 35 sobre los términos anteriores. Ahora, agrupa las potencias iguales sumando. Cada vez que obtengas un múltiplo de 2 dígitos de una potencia de 10, desplazamos su dígito a la siguiente potencia mayor de 10.

$$\begin{align*} 8! &= 3\times 10^4 + 9 \times 10^3 + 12\times 10^2 + 12\times 10 \\ &= 3\times 10^4 + 9 \times 10^3 + 13\times 10^2 + 2\times 10 \\ &= 3\times 10^4 + 10 \times 10^3 + 3\times 10^2 + 2\times 10 \\ &= 4\times 10^4 + 3\times 10^2 + 2\times 10 \\ &= 40320. \end{align*} $$

Ahora, aquí es donde se pone realmente genial.

La multiplicación de polinomios puede considerarse como una convolución de vectores, que es lo mismo que la Producto Cauchy . El número 40320 es básicamente un polinomio en potencias de 10. Imagina momentáneamente que el 10 no es un número, sino un símbolo como $x$ . Entonces,

$$40320 = 4 (10)^4 + 0 (10)^3 + 3 (10)^2 + 2 (10)^1 + 0 (10)^0.$$

Podemos escribirlo en forma vectorial como $[ 4\ 0\ 3\ 2\ 0 ]$ .

Si queremos entonces multiplicarlo por algo más, digamos $10 \cdot 9 = 9 (10)^1$ para calcular $10!$ , entonces encontramos la convolución discreta/producto de Cauchy de los dos vectores. Lo dejaré a tu criterio, dado que se ha señalado que algunas personas no ven con buenos ojos las soluciones demasiado completas a los problemas de PE.

---

Los comentarios a este post son dignos de mención. Sí, esto es exactamente una implementación de una biblioteca BigInt. Sí, esto es exactamente el algoritmo de multiplicación.

En mi opinión, sin embargo, el propósito de PE no es entrenar a la gente a encontrar bibliotecas para hacer su trabajo; es descubrir la matemática subyacente. Con suerte, las relaciones que he mencionado entre los productos de Cauchy, las convoluciones discretas y el algoritmo de multiplicación son interesantes, más interesantes que encontrar un lenguaje con soporte para BigInt.

Answer 2

Creo que una forma de sumar todos los dígitos de la centena es sumar los números pares y luego todos los números Impares. Yo probé esto y realmente me funcionó. O otra forma es seguir sumando el número con el que se empezó (pequeño) y luego tomar una tabla con todos los números del 1 al 100 y marcarla cuando se haya alcanzado el número o cuando se haya llegado a este número. Ejemplo: 1,2,4,8,16,32,64. ¡Gracias y deseo realmente que esto te ayude! Firmando, Srivacthi Nadar.

Answer 3

Curiosamente, si se continúa sumando los dígitos para cualquier factorial entero mayor o igual a 6, de manera que se termine con un solo dígito, la respuesta será siempre ser 9.

La razón es que cualquier número divisible por 9, cuando se escribe en decimal, tiene la propiedad de que su suma de dígitos (cuando se repite hasta tener un solo dígito) es siempre 9.... y cualquier factorial de cualquier entero >= 6 incluye 3*6 en el cálculo, que es 18, que es divisible por 9.

Toma la solución de 27 que alcanzaste, da 2+7 = 9

Y la respuesta de Emily de 40320, da 4 + 3 + 2 = 9

Answer 4

Sugerencia: Una gran fruta madura es que toneladas de esos dígitos van a ser un enorme bloque de $0$ 's en la parte delantera.

Utiliza este hecho para mantener la magnitud de tu respuesta bajo control mientras calculas.