Somme des chiffres d’une factorielle

Lien vers le problème d’origine

Ce n’est pas une question de devoirs. Je pensais juste que quelqu’un pourrait connaître une vraie solution à ce problème.

Je participais à un concours de programmation en 2004 et il y avait ce problème:

Étant donné n, trouve la sum 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 numéros pour chaque ensemble de test.

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

Mais il y avait un gars qui a résolu ce problème avec environ 10 lignes de code et cela donnerait une réponse en un rien de temps. Je crois que c’était une sorte de programmation dynamic ou quelque chose de la théorie des nombres. Nous avions 16 ans à ce moment-là, donc ce ne devrait pas être une “science des fusées”.

Est-ce que quelqu’un sait quel type d’algorithme il pourrait utiliser?

EDIT : Je suis désolé si je n’ai pas clarifié la question. Comme l’a dit mquander, il devrait y avoir une solution intelligente, sans bug, avec juste du code Pascal, 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 sum des chiffres d’une factorielle. Nous pouvons également trouver combien de zéros sont à la fin du numéro. Pouvons-nous l’utiliser?

Ok, un autre problème du concours de programmation en Russie. Étant donné 1 <= N <= 2 000 000 000, sortie N! mod (N + 1). Est-ce en quelque sorte lié?

Je ne suis pas sûr de savoir qui fait toujours attention à ce sujet, mais ça va quand même.

Premièrement, dans la version liée à l’apparence officielle, il ne doit s’agir que de 1000 factorielles, et non de 10000 factorielles. 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 la façon dont vous devez travailler pour obtenir une solution suffisamment rapide.

Deuxièmement, pour les parameters réels du concours, la solution de Peter est saine, mais avec une touche supplémentaire, vous pouvez l’accélérer d’un facteur de 5 avec une architecture 32 bits. (Ou même un facteur de 6 si seulement 1000! Est souhaité.) À savoir, au lieu de travailler avec des chiffres individuels, implémentez la multiplication dans la base 100000. Puis, à la fin, additionnez les chiffres dans chaque super-chiffre. Je ne sais pas à quel point un ordinateur vous a été autorisé dans le concours, mais j’ai un 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 à la fin, mais cela économise seulement 7% du travail.

 #include  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 par un autre facteur important. Avec les méthodes modernes de multiplication des grands nombres, il ne faut pas du temps quadratique pour calculer n !. Au lieu de cela, vous pouvez le faire en O-tilde (n), où le tilde signifie que vous pouvez utiliser des facteurs logarithmiques. Il y a une simple accélération due à Karatsuba qui ne ramène pas la complexité du temps à cela, mais l'améliore encore et pourrait économiser un facteur de 4 ou plus. Pour l'utiliser, vous devez également diviser la factorielle en plages de taille égale. Vous faites un algorithme récursif prod (k, n) qui multiplie les nombres de k à n par la formule de pseudocode

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

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

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


Une partie de la question posée est une spéculation selon laquelle il existe un simple tour de théorie des nombres qui modifie 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 quand n + 1 est premier, et c'est un exercice vraiment facile de voir que c'est 2 quand n = 3 et sinon 0 quand n + 1 est composite. Il y a des variations de ceci aussi; par exemple n! est également très prévisible mod 2n + 1. Il existe également des liens entre congruences et sums de chiffres. La sum des chiffres de x mod 9 est aussi x mod 9, ce qui explique pourquoi la sum est 0 mod 9 lorsque x = n! pour n> = 6. La sum alternée des chiffres de x mod 11 est égale à x mod 11.

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

Ceci est A004152 dans l’ encyclopédie en ligne des séquences entières . Malheureusement, il n’a pas de conseils utiles sur la façon de le calculer efficacement – ses recettes d’érable et de mathematica adoptent une approche naïve.

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 de tester si N est premier.

Petit script python rapide disponible sur http://www.penjuinlabs.com/blog/?p=44 . C’est élégant mais toujours brutal.

 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 

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

L’astuce ci-dessous est de factoriser N! en factorisant tous les n <= N, puis calculer les puissances des facteurs.

Avoir un vecteur de compteurs; un compteur pour chaque nombre premier jusqu’à N; mettez-les à 0. Pour chaque n <= N, facteur n et augmentez les compteurs des facteurs premiers en conséquence (facteur judicieux: commencez par les petits nombres premiers, construisez les nombres premiers en factorisant, et rappelez-vous que division par 2 est un décalage). Soustraire le compteur de 5 du compteur de 2, et rendre 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'utilisions que de (très) petits nombres.

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

Dans l'ensemble, vous avez à propos des opérations N log (N) sur les petits nombres (facteurs premiers log N) et les opérations Log N Log (Log N) sur les grands nombres.

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

HTH

1 seconde? Pourquoi ne peux-tu pas calculer n! et additionnez les chiffres? Cela représente 10000 multiplications et pas plus de quelques dix mille ajouts, ce qui devrait prendre environ un milliardième de seconde.

Voyons voir. On sait que le calcul de n! car tout nombre raisonnablement élevé aboutira à un nombre avec beaucoup de zéros à la fin, qui ne consortingbuent pas à la sum. Que diriez-vous de supprimer les zéros en cours de route? Cela garderait le sizer du nombre un peu plus petit?

Hmm. Nan. Je viens de vérifier, et le débordement d’entier est toujours un gros problème, même alors …

Vous devez calculer le fatcorial.

1 * 2 * 3 * 4 * 5 = 120.

Si vous voulez seulement calculer la sum des chiffres, vous pouvez ignorer les zéros de fin.

Pour 6! vous pouvez faire 12 x 6 = 72 au lieu de 120 * 6

Pour 7! vous pouvez utiliser (72 * 7) MOD 10

MODIFIER.

J’ai écrit une réponse trop rapidement …

10 est le résultat de deux nombres premiers 2 et 5.

Chaque fois que vous avez ces 2 facteurs, vous pouvez les ignorer.

 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 

Le facteur 5 apparaît à 5, 10, 15 …
Ensuite, un zéro final apparaîtra après avoir multiplié par 5, 10, 15 …

Nous avons beaucoup de 2 et 3 … Nous allons déborder bientôt 🙁

Ensuite, vous avez toujours besoin d’une bibliothèque pour les grands nombres.

Je mérite d’être abaissé!

Même sans entiers de précision arbitraire, cela devrait être forcé. Dans l’énoncé de problème auquel vous vous êtes lié, le plus grand factoriel à calculer serait 1000 !. C’est un nombre d’environ 2500 chiffres. Alors faites ça:

  1. Allouer un tableau de 3000 octets, chaque octet représentant un chiffre dans la factorielle. Commencez avec une valeur de 1.
  2. Exécuter plusieurs fois la multiplication en classe sur le tableau afin de calculer la factorielle.
  3. Somme les chiffres.

Faire les multiplications répétées est la seule étape potentiellement lente, mais je suis certain que 1000 des multiplications pourraient être faites en une seconde, ce qui est le pire des cas. Sinon, vous pouvez calculer quelques valeurs “jalons” à l’avance et les coller dans votre programme.

Une optimisation potentielle: éliminez les zéros de fin du tableau lorsqu’ils apparaissent. Ils n’affecteront pas la réponse.

NOTE IMPORTANTE: Je prends une approche de programmation-compétition ici. Vous ne le feriez probablement jamais dans un travail professionnel.

une autre solution utilisant BigInteger

  static long q20(){ long sum = 0; Ssortingng factorial = factorial(new BigInteger("100")).toSsortingng(); for(int i=0;i