algorithm - propiedades - Suma de dígitos de un factorial
video de factoriales (10)
¡Atacaría el segundo problema para calcular N! mod (N + 1), usando el teorema de Wilson . Eso reduce el problema para probar si N es primo.
No es una pregunta de tarea. Solo pensé que alguien podría conocer una solución real a este problema.
Estaba en un concurso de programación en 2004, y estaba este problema:
Dado n, encuentre la suma de dígitos de n !. n puede ser de 0 a 10000. Límite de tiempo: 1 segundo. Creo que hubo hasta 100 números para cada conjunto de prueba.
Mi solución fue bastante rápida pero no lo suficientemente rápida, así que dejé que funcionara por un tiempo. Construyó una matriz de valores precalculados que podría usar en mi código. Fue un truco, pero funcionó.
Pero había un chico, que resolvió este problema con alrededor de 10 líneas de código y le daría una respuesta en poco tiempo. Creo que fue algún tipo de programación dinámica, o algo de teoría de números. Teníamos 16 años en ese momento, así que no debería ser una "ciencia de cohetes".
¿Alguien sabe qué tipo de algoritmo podría usar?
EDITAR : Lo siento si no hice la pregunta clara. Como dijo mquander, debería haber una solución inteligente, sin bugnum, con un código simple de Pascal, un par de bucles, O (n 2 ) o algo así. 1 segundo ya no es una restricción.
Encontré here que si n> 5, entonces 9 divide la suma de dígitos de un factorial. También podemos encontrar cuántos ceros hay al final del número. ¿Podemos usar eso?
Ok, otro problema del concurso de programación de Rusia. Dado 1 <= N <= 2 000 000 000, salida N! mod (N + 1). ¿Está eso de alguna manera relacionado?
¿1 segundo? ¿Por qué no puedes simplemente calcular n? y sumar los dígitos? Eso es 10000 multiplicaciones y no más de unas diez mil adiciones, lo que debería tomar aproximadamente una décima de segundo.
Esto es A004152 en la enciclopedia en línea de secuencias A004152 . Desafortunadamente, no tiene ningún consejo útil sobre cómo calcularlo de manera eficiente: sus recetas de arce y matemática tienen un enfoque ingenuo.
Incluso sin números enteros de precisión arbitraria, esto debería ser de fuerza bruta. En la declaración del problema al que se vinculó, el factorial más grande que tendría que calcularse sería 1000. Este es un número con aproximadamente 2500 dígitos. Así que haz esto:
- Asigne una matriz de 3000 bytes, con cada byte representando un dígito en el factorial. Comience con un valor de 1.
- Ejecute la multiplicación de la escuela primaria en la matriz repetidamente, para calcular el factorial.
- Suma los dígitos.
Hacer las multiplicaciones repetidas es el único paso potencialmente lento, pero estoy seguro de que 1000 de las multiplicaciones se pueden hacer en un segundo, que es el peor de los casos. De lo contrario, podría calcular algunos valores de "hitos" por adelantado y simplemente pegarlos en su programa.
Una optimización potencial: elimine los ceros finales de la matriz cuando aparezcan. No afectarán la respuesta.
NOTA OBVIOSA: Estoy tomando un enfoque de competencia de programación aquí. Probablemente nunca harías esto en un trabajo profesional.
No estoy seguro de quién sigue prestando atención a este hilo, pero aquí va de todos modos.
Primero, en la versión vinculada de aspecto oficial, solo tiene que ser 1000 factorial, no 10000 factorial. Además, cuando este problema se reutilizó en otro concurso de programación, el límite de tiempo fue de 3 segundos, no de 1 segundo. Esto hace una gran diferencia en lo difícil que es trabajar para obtener una solución lo suficientemente rápida.
En segundo lugar, para los parámetros reales del concurso, la solución de Peter es sólida, pero con un giro adicional puedes acelerarla en un factor de 5 con una arquitectura de 32 bits. (O incluso un factor de 6 si solo se desea 1000). A saber, en lugar de trabajar con dígitos individuales, implementar la multiplicación en la base 100000. Luego, al final, sumar los dígitos dentro de cada superdígito. No sé qué tan buena computadora se te permitió en el concurso, pero tengo un escritorio en casa que es más o menos tan viejo como el concurso. El siguiente código de muestra demora 16 milisegundos por 1000! y 2.15 segundos por 10000! El código también ignora los 0 finales a medida que aparecen, pero eso solo ahorra aproximadamente el 7% del trabajo.
#include <stdio.h>
int main() {
unsigned int dig[10000], first=0, last=0, carry, n, x, sum=0;
dig[0] = 1;
for(n=2; n <= 9999; n++) {
carry = 0;
for(x=first; x <= last; x++) {
carry = dig[x]*n + carry;
dig[x] = carry%100000;
if(x == first && !(carry%100000)) first++;
carry /= 100000; }
if(carry) dig[++last] = carry; }
for(x=first; x <= last; x++)
sum += dig[x]%10 + (dig[x]/10)%10 + (dig[x]/100)%10 + (dig[x]/1000)%10
+ (dig[x]/10000)%10;
printf("Sum: %d/n",sum); }
En tercer lugar, existe una manera increíble y bastante simple de acelerar el cálculo por otro factor considerable. Con los métodos modernos para multiplicar números grandes, no se requiere tiempo cuadrático para calcular n !. En cambio, puedes hacerlo en tiempo O-tilde (n), donde la tilde significa que puedes arrojar factores logarítmicos. Hay una aceleración simple debido a Karatsuba que no reduce la complejidad del tiempo a eso, pero aún lo mejora y podría ahorrar otro factor de 4 más o menos. Para usarlo, también necesita dividir el factorial en rangos de igual tamaño. Se crea un algoritmo recursivo prod (k, n) que multiplica los números de k a n por la fórmula del pseudocódigo
prod(k,n) = prod(k,floor((k+n)/2))*prod(floor((k+n)/2)+1,n)
Luego usas Karatsuba para hacer la gran multiplicación que resulta.
Incluso mejor que Karatsuba es el algoritmo de multiplicación Schonhage-Strassen basado en transformada de Fourier. Da la casualidad que ambos algoritmos forman parte de las bibliotecas modernas de grandes números. Computar grandes factoriales rápidamente podría ser importante para ciertas aplicaciones de matemáticas puras. Creo que Schonhage-Strassen es excesivo para un concurso de programación. Karatsuba es realmente simple y podrías imaginarlo en una solución A + al problema.
Parte de la pregunta planteada es la especulación de que existe un truco simple de teoría de números que cambia por completo el problema del concurso. Por ejemplo, si la pregunta fuera para determinar n! mod n + 1, luego el teorema de Wilson dice que la respuesta es -1 cuando n + 1 es primo, y es un ejercicio realmente fácil ver que es 2 cuando n = 3 y por lo demás 0 cuando n + 1 es compuesto. Hay variaciones de esto también; por ejemplo n! también es altamente predecible mod 2n + 1. También hay algunas conexiones entre congruencias y sumas de dígitos. La suma de los dígitos de x mod 9 también es x mod 9, por lo que la suma es 0 mod 9 cuando x = n! para n> = 6. La suma alternante de los dígitos de x mod 11 es igual a x mod 11.
El problema es que si quieres la suma de los dígitos de un número grande, no de módulo, los trucos de la teoría de números se agotan bastante rápido. Agregar los dígitos de un número no combina bien con la suma y la multiplicación con acarreos. A menudo es difícil prometer que las matemáticas no existen para un algoritmo rápido, pero en este caso no creo que haya ninguna fórmula conocida. Por ejemplo, apuesto a que nadie sabe la suma de los dígitos de un factorial de googol, a pesar de que es solo un número con aproximadamente 100 dígitos.
Script Python pequeño y rápido encontrado en http://www.penjuinlabs.com/blog/?p=44 . Es elegante pero sigue siendo fuerza bruta.
import sys
for arg in sys.argv[1:]:
print reduce( lambda x,y: int(x)+int(y),
str( reduce( lambda x, y: x*y, range(1,int(arg)))))
$ time python sumoffactorialdigits.py 432 951 5436 606 14 9520
3798
9639
74484
5742
27
141651
real 0m1.252s
user 0m1.108s
sys 0m0.062s
Supongamos que tiene grandes números (este es el menor de sus problemas, suponiendo que N es realmente grande, y no 10000), y continuemos desde allí.
El truco a continuación es factorizar N! factorizando todo n <= N, y luego calcule los poderes de los factores.
Tener un vector de contadores; un contador para cada número primo hasta N; establézcalos en 0. Para cada n <= N, factor ny aumente los contadores de factores primarios en consecuencia (factor de manera inteligente: comience con los números primos pequeños, construya los números primos mientras factoriza, y recuerde que la división por 2 es cambio). Reste el contador de 5 del contador de 2 y haga el contador de 5 cero (a nadie le importan los factores de 10 aquí).
calcule todo el número primo hasta N, ejecute el siguiente ciclo
for (j = 0; j< last_prime; ++j) {
count[j] = 0;
for (i = N/ primes[j]; i; i /= primes[j])
count[j] += i;
}
Tenga en cuenta que en el bloque anterior solo usamos números (muy) pequeños.
Para cada factor primo P tiene que calcular P a la potencia del contador apropiado, que toma el tiempo de registro (contador) usando cuadratura iterativa; ahora tienes que multiplicar todos estos poderes de los números primos.
En general, tiene aproximadamente N log (N) operaciones en números pequeños (log N factores primos), y Log N Log (Log N) operaciones en números grandes.
y después de la mejora en la edición, solo N operaciones en números pequeños.
HTH
Tienes que calcular el fatcorial.
1 * 2 * 3 * 4 * 5 = 120.
Si solo desea calcular la suma de dígitos, puede ignorar los ceros finales.
Para 6! puedes hacer 12 x 6 = 72 en lugar de 120 * 6
¡Para 7! puedes usar (72 * 7) MOD 10
EDITAR.
Escribí una respuesta demasiado rápido ...
10 es el resultado de dos números primos 2 y 5.
Cada vez que tenga estos 2 factores, puede ignorarlos.
1 * 2 * 3 * 4 * 5 * 6 * 7 * 8 * 9 * 10 * 11 * 12 * 13 * 14 * 15...
1 2 3 2 5 2 7 2 3 2 11 2 13 2 3
2 3 2 3 5 2 7 5
2 3
El factor 5 aparece en 5, 10, 15 ...
Entonces aparecerá un cero final después de multiplicar por 5, 10, 15 ...
Tenemos muchos 2s y 3s ... Desbordaremos pronto :-(
Entonces, todavía necesitas una biblioteca para grandes números.
¡Merezco ser votado!
Veamos. Sabemos que el cálculo de n! para cualquier número razonablemente grande eventualmente conducirá a un número con muchos ceros finales, que no contribuyen a la suma. ¿Qué hay de cortar los ceros en el camino? ¿Eso mantendría el tamaño del número un poco más pequeño?
Hmm. Nop. Acabo de comprobar, y el desbordamiento de enteros sigue siendo un gran problema incluso entonces ...
otra solución usando BigInteger
static long q20(){
long sum = 0;
String factorial = factorial(new BigInteger("100")).toString();
for(int i=0;i<factorial.length();i++){
sum += Long.parseLong(factorial.charAt(i)+"");
}
return sum;
}
static BigInteger factorial(BigInteger n){
BigInteger one = new BigInteger("1");
if(n.equals(one)) return one;
return n.multiply(factorial(n.subtract(one)));
}