Somme des chiffres d'une factorielle

Question

Lien vers le problème original

Ce n'est pas une question de devoir. J'ai juste pensé que quelqu'un pourrait connaître une vraie solution à ce problème.

J'ai participé à un concours de programmation en 2004, et il y avait ce problème :

Étant donné n, trouvez la somme des chiffres de n !. n peut être compris entre 0 et 10000. Limite de temps : 1 seconde. Je pense qu'il y avait jusqu'à 100 nombres pour chaque ensemble de test.

Ma solution était assez rapide, mais pas assez, alors je l'ai laissée tourner pendant un certain temps. Il a construit un tableau de valeurs précalculées que je pouvais utiliser dans mon code. C'était un hack, mais ça a marché.

Mais il y avait un type qui a résolu ce problème avec environ 10 lignes de code et qui donnait une réponse en un rien de temps. Je crois que c'était une sorte de programmation dynamique, ou quelque chose de la théorie des nombres. Nous avions 16 ans à l'époque, donc ça ne devait pas être une "science de la fusée".

Quelqu'un sait-il quel type d'algorithme il pourrait utiliser ?

EDIT : Je suis désolé si je n'ai pas rendu la question claire. Comme mquander l'a dit, il devrait y avoir une solution intelligente, sans bugnum, avec juste du code Pascal simple, quelques boucles, O(n 2 ) ou quelque chose comme ça. 1 seconde n'est plus une contrainte.

J'ai trouvé ici que si n > 5, alors 9 divise la somme des chiffres d'une factorielle. Nous pouvons aussi trouver combien de zéros il y a à la fin du nombre. Pouvons-nous l'utiliser ?

Ok, un autre problème du concours de programmation de Russie. Étant donné 1 <= N <= 2 000 000 000, on obtient N ! mod (N+1). Est-ce que ça a un rapport ?

Answer 1

Je ne sais pas qui prête encore attention à ce fil de discussion, mais je vais quand même le faire.

Tout d'abord, dans la version officielle en lien, la factorielle doit être de 1000 et non de 10000. De plus, lorsque ce problème a été réutilisé dans un autre concours de programmation, la limite de temps était de 3 secondes, et non d'une seconde. Cela fait une énorme différence dans l'effort que vous devez fournir pour obtenir une solution suffisamment rapide.

Deuxièmement, pour les paramètres réels du concours, la solution de Peter est bonne, mais avec une astuce supplémentaire, vous pouvez l'accélérer d'un facteur 5 avec une architecture 32 bits. (Au lieu de travailler avec des chiffres individuels, implémentez la multiplication en base 100000. Puis, à la fin, faites le total des chiffres de chaque superchiffre. Je ne sais pas si vous aviez droit à un bon ordinateur pour le concours, mais j'ai un ordinateur de bureau à la maison qui est à peu près aussi vieux que le concours. L'exemple de code suivant prend 16 millisecondes pour 1000 ! et 2,15 secondes pour 10000 ! Le code ignore également les 0 de queue lorsqu'ils apparaissent, mais cela n'économise que 7% du travail.

#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); }

Troisièmement, il existe un moyen étonnant et assez simple d'accélérer le calcul d'un autre facteur appréciable. Avec les méthodes modernes de multiplication des grands nombres, le calcul de n ! ne prend pas un temps quadratique. Au contraire, vous pouvez le faire en O-tilde(n) temps, où le tilde signifie que vous pouvez ajouter des facteurs logarithmiques. Il existe une accélération simple en raison de Karatsuba qui ne ramène pas la complexité temporelle à ce niveau, mais l'améliore tout de même et pourrait permettre d'économiser un autre facteur de 4 ou plus. Pour l'utiliser, vous devez également diviser la factorielle elle-même en plages de taille égale. Vous créez un algorithme récursif prod(k,n) qui multiplie les nombres de k à n par la formule pseudo-code suivante

prod(k,n) = prod(k,floor((k+n)/2))*prod(floor((k+n)/2)+1,n)

Puis vous utilisez Karatsuba pour faire la grande multiplication qui en résulte.

L'algorithme de multiplication de Schonhage-Strassen basé sur la transformée de Fourier est encore meilleur que celui de Karatsuba. Il se trouve que ces deux algorithmes font partie des bibliothèques modernes de grands nombres. Le calcul rapide d'énormes factorielles pourrait être important pour certaines applications de mathématiques pures. Je pense que Schonhage-Strassen est un peu excessif pour un concours de programmation. Karatsuba est vraiment simple et vous pourriez l'imaginer dans une solution A+ au problème.

---

Une partie de la question posée est une spéculation selon laquelle il existe une simple astuce de théorie des nombres qui change complètement le problème du concours. Par exemple, si la question était de déterminer n ! mod n+1, alors le théorème de Wilson dit que la réponse est -1 lorsque n+1 est premier, et c'est un exercice très facile de voir que c'est 2 lorsque n=3 et sinon 0 lorsque n+1 est composite. Il existe également des variations de ce principe ; par exemple, n ! est également très prévisible mod 2n+1. Il existe également des liens entre les congruences et les sommes de chiffres. La somme des chiffres de x mod 9 est également x mod 9, ce qui explique pourquoi la somme est 0 mod 9 lorsque x = n ! pour n >= 6. La somme alternée des chiffres de x mod 11 est égale à x mod 11.

Le problème est que si vous voulez la somme des chiffres d'un grand nombre, non modulo quoi que ce soit, les astuces de la théorie des nombres s'épuisent assez rapidement. L'addition des chiffres d'un nombre ne s'accorde pas bien avec l'addition et la multiplication avec des reports. Il est souvent difficile de promettre que les mathématiques n'existent pas pour un algorithme rapide, mais dans ce cas, je ne pense pas qu'il existe de formule connue. Par exemple, je parie que personne ne connaît la somme des chiffres d'une factorielle googol, même si ce n'est qu'un nombre d'environ 100 chiffres.

Answer 2

C'est A004152 dans le Encyclopédie en ligne des séquences de nombres entiers . Malheureusement, il ne contient pas de conseils utiles sur la manière de le calculer efficacement - ses recettes maple et mathematica adoptent une approche naïve.

Answer 3

J'attaquerais le deuxième problème, pour calculer N ! mod (N+1), en utilisant Le théorème de Wilson . Cela réduit le problème à tester si N est premier.

Answer 4

Petit, rapide script en python trouvé chez http://www.penjuinlabs.com/blog/?p=44 . C'est élégant mais ça reste de la force brute.

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

Answer 5

Supposons que vous ayez de grands nombres (c'est le moindre de vos problèmes, en supposant que N soit vraiment grand, et non 10000), et continuons à partir de là.

L'astuce ci-dessous consiste à factoriser N ! en factorisant tous les n<=N, puis à calculer les puissances des facteurs.

Ayez un vecteur de compteurs ; un compteur pour chaque nombre premier jusqu'à N ; mettez-les à 0. Pour chaque n<= N, factorisez n et augmentez les compteurs des facteurs premiers en conséquence (factorisez intelligemment : commencez par les petits nombres premiers, construisez les nombres premiers pendant la factorisation, et rappelez-vous que la division par 2 est un décalage). Soustrayez le compteur de 5 du compteur de 2, et mettez le compteur de 5 à zéro (personne ne se soucie des facteurs de 10 ici).

calculer tous les nombres premiers jusqu'à N, exécuter la boucle suivante

for (j = 0; j< last_prime; ++j) {
  count[j] = 0;
  for (i = N/ primes[j]; i; i /= primes[j])
    count[j] += i; 
}

Notez que dans le bloc précédent, nous n'avons utilisé que des (très) petits nombres.

Pour chaque facteur premier P, vous devez calculer P à la puissance du compteur approprié, ce qui prend un temps log(compteur) en utilisant la quadrature itérative ; vous devez maintenant multiplier toutes ces puissances de nombres premiers.

En tout, vous avez environ N log(N) opérations sur les petits nombres (log N facteurs premiers), et Log N Log(Log N) opérations sur les grands nombres.

et après l'amélioration de l'édition, seulement N opérations sur les petits nombres.

HTH