Bonjour,
première étape :  cherchons le nombre de 0 à la fin de n!
Il faut chercher la multiplicité de 10 dans n!, cela revient donc à chercher la multiplicité de 2 et de 5, et de prendre la plus petite multiplicité.
On voit tout de suite que cela se ramène à chercher seulement la multiplicité de 5, mais on va d'abord chercher celle de 2, on verra plus tard que c'est utile.

notons [latex]m_2(n)[/latex] la multiplicité de 2 dans le nombre n.
[TeX]m_2(n!) = \sum \limits_{i=1}^nm_2(i)[/TeX]
On peut facilement démontrer par récurrence que [latex]m_2(n!) = 2\times m_2(\lfloor \log_2(n) \rfloor !) + 1 + m_2((n -\lfloor \log_2(n) \rfloor)!) [/latex]

Cela se démontre plutôt facilement par récurrence:
si [latex]n = 2^p[/latex], [latex]m_2(n) = n-1[/latex]
Pour trouver les n valeurs suivantes, il suffit d'ajouter 2^p aux n premières valeurs.
Cela ne change pas la multiplicité jusqu'à n-1 car elle est strictement inférieure à p, mais pour 2^p+1 = 2^p + 2^p, la multiplicité augmente de 1. La somme des multiplicité a donc été multipliée par 1.

Exemple:

Cherchons les multiplicités cumulées de jusqu'à 8 (juste pour les nombres pairs)
m2(2!) = 1
m2(4!) = 1 + 2 = 3
m2(6!) = 3+1 = 4
m2(8!) = 4+3 = 7 = 8-1
m2(10)  = m2(2 + 8) = m2(2)
donc m2(10!) = 7 + 1 = 8
m2(12) = m2(4+8) = m2(4)
donc m2(12!) = 8 + 2 = 10
...
m2(14!) = 11
m2(16) = m2(8 + 8) = m2(8) + 1
m2(16:) : 11 + 3 + 1 = 15
On a bien m2(16!) = 2*m2(8!) + 1

Le cas général se trouve alors facilement.

On obtient alors [latex]m_2(n!) = 2\times m_2(\lfloor \log_2(n) \rfloor!) + 1 + m_2((n -\lfloor \log_2(n) \rfloor)!) = 2^{\lfloor \log_2(n) \rfloor} - 1 + m_2((n -\lfloor \log_2(n) \rfloor)!)[/latex]
par résolution d'une suite aritmético-géométrique.

On reconnait ici une décomposition en base 2 de n, on obtient donc la formule miracle [latex]m_2(n!) = n - b(n)[/latex]
où b(n) est le nombre de 1 dans la décomposition en binaire. Ce terme apparait à cause du -1 dans la formule.

On peut aussi démontrer directement cette formule par récurrence, même si elle n'est pas intuitive à trouver.


Maintenant cherchons la multiplicité de 5.
Il suffit d'adapter un peu la formule, ce qui se démontre de la même manière. On trouve alors
[TeX]m_5(n!) = 5\times m_5(\lfloor \log_5(n) \rfloor!) + 1 + m_5((n -\lfloor \log_5(n) \rfloor)!) = \dfrac{5^{\lfloor \log_5(n) \rfloor} - 1}{4} + m_5((n -\lfloor \log_5(n) \rfloor)!)[/TeX]
On en déduit alors la formule miracle:
[latex]m_5(n!) = \dfrac{n - q(n)}{4} [/latex] où q(n) est la somme des digits quinternaires.

On en déduit donc que pour n = 1 000 000 000
m_5(n) = (1 000 000 000 - 8)/4 = 249999998
car 1 000 000 000 = 4022000000000(5) et que 4 + 2 + 2 = 8

Il y a donc 249999998 zéros à la fin de 1 000 000 000!

m2(n) = 1 000 000 000 - 13 = 999999987
car 1000 000 000 = 111011100110101100101000000000(2)
Il y a donc 999999987 - 249999998 = 749999989 2 qui ne sont pas impliqués dans la création d'un zéro.

deuxième étape : calcul informatique du résultat
On va d'abord se débarasser de tout les 2 et de tout les 5, et calculer les deux derniers chiffres modulo 100. Après, il faudra encore réintégrer tout les 2 en trop dans le calcul (toujours modulo 100)

(le modulo 100 permet de ne jamais avoir de dépassement de mémoire puisque les nombres de chaque calcul n'auront que deux chiffres chacun, et les calculs des modulos 100 ne sont jamais problématique non plus niveau mémoire.)

Après, 1 000 000 000 d'itération est assez long à  exécuter, je vais d'abord voir s'il n'y a pas moyen d'améliorer ça en regroupant les nombres par catégories.

J'ai une méthode pour m'en tirer, j'ai lancé un programme, mais il faut encore quelques minutes de calcul pour que j'obtienne le résultat. Comme ça on pourra comparer avec ta méthode manuelle

Si on écrit (10^9)!=k.2^a.5^b, alors :
* a vaut (10^9) moins le nombre de 1 dans l'écriture binaire de 10^9, soit (10^9-13) = 999 999 987.
* b vaut [(10^9) moins la somme des chiffres de 10^9 écrit en base 5]/4, soit (10^9-8)/4 = 249 999 998.

Après, j'ai écrit un programme pour calculer les deux derniers chiffres de k : au lieu de calculer 1*2*3*4*5*6..., on commence par supprimer dans chacun de ces entiers les facteurs 2 et 5, c'est-à-dire qu'on calcule 1*1*3*1*1*3*7*1*9*1*11*3*13..., et on fait ce calcul modulo 100, c'est-à-dire qu'il suffit de conserver les deux derniers chiffres du produit au cours du calcul. Par exemple, 1*1*3*1*1*3*7*1 donne 63, et quand on multiplie par 9, ça donne 567, donc on garde 67. Puis 67*11 donne 37, etc.

Il ne restera qu'à multiplier le nombre obtenu au bout d'un milliard de calculs par 2^(a-b), le calcul se faisant là aussi modulo 100.

@ Ebichu : c'est le résultat que j'ai trouvé.

Comme je l'ai dit à Caduk, le bon tri des nombres est essentiel pour la méthode manuelle. Ce qui me frappe, c'est que Caduk et toi avez géré les facteurs pairs séparément. Ce faisant, vous passez à coté de quelques propriétés remarquables....

@ Vasimolo : Compenser chaque 5 par un 2 n'est pas la voie que j'ai choisie.

Salut Caduk.

Je laisse encore du temps s'écouler, la question est en cours sur 2 autres sites.

Comme je l'ai déja dit à Vasimolo, je n'ai pas cherché à compenser les 5 par des 2. Cela dit, cette piste n'est pas forcément une impasse.

Ce n'est pas compliqué du tout, il faut juste prendre le problème par le bon bout.

En calcul générique, 100 petites multiplications.
Et pour application du nombre 1 000 000 000 !, 1 seule multiplication.

N'as tu pas oublié 9 et 21 dans ta liste ?
Comme ça, tu risques de passer à coté de l'essentiel....

OK Enigmatus.
Je note que le calcul a été fait sans les 2 et les 5, puis avec la différence.

Bon, je donne ma solution, une parmi d'autres.

Bonne lecture, j'espère que ce sera compréhensible.

_____________________________________________________________


On établit au préalable la valeur modulo 100 des factorielles de 1 à 100, en excluant les nombres multiples de 5 ( pour éviter les 0 ).

1: 1........21: 96....41: 16.....61: 36.....81: 56 
2: 2........22: 12....42: 72.....62: 32.....82: 92
3: 6........23: 76....43: 96.....63: 16.....83: 36
4: 24......24: 24....44: 24.....64: 24.....84: 24
6: 44......26: 24....46: 04.....66: 84.....86: 64
7: 08......27: 48....47: 88.....67: 28.....87: 68
8: 64......28: 44....48: 24.....68: 04.....88: 84
9: 76......29: 76....49: 76.....69: 76.....89: 76
11: 36....31: 56....51: 76.....71: 96.....91: 16
12: 32....32: 92....52: 52.....72: 12.....92: 72
13: 16....33: 36....53: 56.....73: 76.....93: 96
14: 24....34: 24....54: 24.....74: 24.....94: 24
16: 84....36: 64....56: 44.....76: 24.....96: 04
17: 28....37: 68....57: 08.....77: 48.....97: 88
18: 04....38: 84....58: 64.....78: 44.....98: 24
19: 76....39: 76....59: 76.....79: 76.....99: 76


On remarque que pour 99! (et tous ceux qui se terminent par 9) on obtient la valeur 76 qui est élément neutre pour la multiplication des nombres multiples de 4.
A savoir 76 * 4a = 4a modulo 100. Ce qui se prouve facilement :
76 * 4a = 4a + 100 k   
76 * a = a + 25 k et comme 76 = 1 mod 25
a = a modulo 25.

Cette propriété est bien utile pour notre problème, puisque comme 76 * 76 = 76 [100] = élément neutre, pour trouver le résultat des 2 derniers chiffres de n !
sans les multiples de 5, il suffit de regarder dans le tableau le nombre correspondant aux 2 derniers chiffres de n, c'est à dire la dernière centaine.

Bien entendu, le travail n'est pas fini, puisque les multiples de 5 qu'on a mis de coté engendrent une nouvelle factorielle ( 1*2*3....sous entendu fois 5, fois 5,...) dont on peut
déterminer à nouveau facilement la valeur des 2 derniers chiffres. Et on aura sans doute encore une autre factorielle des multiples de 5 extraite de cette dernière qu'il
faudra traiter. Etc...Le résultat final R de toutes les factorielles hors multiples de 5 est :
résultat 1ere factorielle * résultat 2ème factorielle * résultat 3ème factorielle*..... modulo 100.

Reste à traiter les facteurs 5. 
On note que multiplier par 5, c'est multiplier par 10 et diviser par 2. Mais si R = 04 par exemple, comment choisir, en divisant par 2, entre 2 et 52 ?
La réponse est simple : il faut toujours choisir le nombre divisible par 4, car évidemment que la factorielle sans les 0 est divisible par 4. Dans notre exemple, il faut donc
prendre 52. Ceci nous amène à établir un second tableau, celui des puissances de 2 modulo 100, avec uniquement les multiples de 4 :

04.08.16.32.64.28.56.12.24.48.96.92.84.68.36.72.44.88.76.52, la dernière valeur se rebouclant sur la 1ère de la liste.   

On note donc que s'il faut multiplier 20 fois par 5, ce qui revient à diviser 20 fois par 2, on revient au nombre initial. Donc, on a besoin de connaître C, le nombre de 5 modulo 20.
Une fois qu'on le connait, il ne reste plus qu'à remonter le tableau C fois à partir de la valeur R pour obtenir ce que l'on cherche.

Application pour 10^9 !

Divisions...........................Valeur de la....................nombre de 5
successives......................factorielle........................modulo 20
par 5   

10^9..................................1 (76)
2*10^8...............................1.........................................0
4*10^7...............................1.........................................0
8*10^6...............................1.........................................0
16*10^5.............................1.........................................0
32*10^4.............................1.........................................0
64*10^3.............................1.........................................0
128*10^2...........................1.........................................0
2560.................................1.........................................0
512..................................32........................................12
102...................................2........................................2
20.....................................1........................................0
4......................................24.......................................4

R = 32 * 2 * 24 = 32 * 48 = 36
C = 18 = -2
Le résultat se trouve 2 rangs après 36 dans le tableau 2 : 44.

Une explication que j'espère claire :

@Vasimolo #18 : Explications très claires

J'ai programmé ton algorithme, le résultat est instantané.

#!/usr/bin/env python3
'''
Quels sont les 2 derniers chiffres non nuls de 1 000 000 000 ! (factorielle 1 milliard) ?
'''
import sys
N=int(sys.argv[1])

puissances_12=(76,12,44,28,36,32,84,8,96,52,24,88,56,72,64,68,16,92,4,48)
#---------------------------------------------------
def mul2(n1,n2): return (n1*n2)%100
#---------------------------------------------------
def facto_2chiffres(n):
   ns5=n//5; fac=1
   for k in range(ns5*5+1,n+1): fac=mul2(fac,k)
   if ns5>0:
      fac=mul2(fac,puissances_12[ns5%20])
      fac=mul2(fac,facto_2chiffres(ns5))
   return fac
#---------------------------------------------------
print("N=%d factorielle=%s"%(N,facto_2chiffres(N)))

Très belle solution, bravo à ceux qui ont trouvé!

Ca me rappelle
http://www.prise2tete.fr/forum/viewtopi … 87#p185659

Le calcul est de complexité logarithmique (même de tête on peut sortir au moins le dernier chiffre pour 10^9!)