PREMIERE METHODE :
Cette méthode est bien appropriée pour un calcul "à la main".
Elle ne nécessite aucune opération compliquée.
Les explications sont longues, mais l'utilisation est rapide (exemple donné).
Séparons n! en produit de cinq termes: n!=P0.P1.P2.P5.Pr , avec :
P0 : produit des nombres terminés par 0.
P1 : produit des nombres terminés par 1.
P2 : produit des nombres terminés par 2.
P5 : produit des nombres terminés par 5.
Pr : produit des autres nombres (terminés par 3, 4, 6, 7, 8 ou 9).
Les nombres terminés par 1 n'affectant pas le résultat, nous ne nous occupons pas de P1.
Premièrement : Occupons nous de Pr :
On remplace Pr par le produit de ces nombres modulo 10. Ainsi Pr se met sous la forme :
( Pr mod 10)=3.4.6.7.8.9.3.4.6.7.8.9.3.4
etc.
[(3.4.6.7.8.9)mod(10)]=8.
De plus [(82)mod(10)]=4 ; [(83)mod(10)]=2 ; [(84)mod(10)]=6 ; [(85)mod(10)]=8 ; et cela se répète.
Donc pour trouver [(8k)mod(10)] il faut faire h=(k)mod(4) et u=[(8k)mod(10)]=6, 8, 4 ou 2 si h=0, 1, 2 ou 3 respectivement.
Le nombre de séquences complètes (3.4.6.7.8.9) est (n/10)=partie entière de ( n divisé par 10).
Il reste (ou non) une séquence incomplète s=(3.4
) dont on calcule v= (s) mod 10.
RESUMONS : k=n/10 ; h=(k)mod(4) ; u=6, 8, 4 ou 2 si h=0, 1, 2 ou 3 ; s=(séquence incomplète); v=(s)mod(10).
On trouve ainsi rapidement (Pr)mod(10)=(u.v.)mod(10).
EXEMPLE: n=357; k=n/10=35; h=3; u=2; s=(3.4.6.7); v=4; u.v=8; (Pr)mod(10)=8.
Deuxièmement : Occupons nous ensuite de P5 :
P5 n'existe pas si n<5.
P5=5.15.25.35.45.55.65 (10m-5) m=partie entière de (n+5)/10.
Divisons par 5m : P5/5m=1.3.5.7.9.11.13 (2m-1)
On élimine les nombres terminés par 1 et on sépare ceux terminés par 5 :
P5/5m=(3.7.9.13.17.19.23
)(5.15.25
)
Le nombre de séquences complètes (3.7.9) est k=(2m-1)/10.
(3.7.9) mod 10 = 9. Il faut donc trouver u=[(9k)mod(10)] qui vaut 1 si k est pair ou 9 si k est impair.
Il reste (ou non) une séquence incomplète s=3 ou 3.7 dont le modulo 10 vaut v= 3 ou 1 respectivement.
Donc le premier terme (3.7.9.13.17.19.23 ) donne (u.v) mod 10.
Le second terme (5.15.25
) sera traité de la même façon que P5 : Il est évidemment beaucoup moins long.
La répétition de ce procédé jusqu'à épuisement du second terme aboutit à P5/5M modulo 10.
M est le nombre total de divisions par 5 que l'on a effectuées. C'est donc la puissance maximum de 5
qui divise exactement n. La méthode pour trouver M directement est connue.
EXEMPLE. Poursuivons l'exemple précédent n=357
m=(357+5)/10=36. ( donc : P5/536=1.3.5.7.9.11.13 71)
k=(2m-1)/10=7. Comme k est impair, u=9
Il ne reste pas de séquence incomplète donc v=1 et (u.v) mod 10=9 (*).
Passons au second terme (5.15.25 65). On recommence avec m=(65+5)/10=7.
La division par 57 donne (1.3.5.7.9.11.13). Il ne reste plus qu'un seul facteur 5 une séquence entière
(3.7.9) et une incomplète (3), dont le modulo 10 est (9.3) mod 10 =7.
On multiplie ce résultat (7) du second terme par le résultat (9) obtenu pour le premier terme (*)
ci-dessus et on obtient (9.7) mod 10 = 3.
La puissance de 5 a été trouvée =36+7+1=44.
Donc le résultat final relatif à P5 est : (P5/544) mod 10 = 3.
Troisièmement : Occupons nous maintenant de P2 :
On procède comme précédemment, avec P2=2.12.22.32.42.52.62 (10m-8) , m=partie entière de (n+8)/10.
Divisons par 2m : P2/2m=1.6.11.16.21.36.41
(5m-4)
On élimine les nombres terminés par 1. Il reste: (6.16.26.36.46.56
).
Si on recommence les divisions par 2, on obtient (3.8.13.18.23.28
)
On sépare en un premier terme (3.13.23
) et un second (8.18.28
)
Le calcul de (3.13.23 (10j+3)) modulo 10 est rapide : ce sera 3, 9, 7 ou 1 selon que j mod 4 vaut 0, 1, 2 ou 3.
Pour le second terme (8.18.28
), on continue de la même façon.
Les divisions par 2 donnent (2, 9, 14, 19
) que l'on sépare à nouveau en nombres pairs et
impair (9, 19, 29,
(10i+9)) dont on calcule le modulo 10 = 9 ou 1 selon que i est impair ou pair.
La répétition de ce procédé jusqu'à épuisement du second terme aboutit à (P2/2K modulo 10).
N est le nombre total de divisions par 2 que l'on a effectuées. C'est donc la puissance maximum de 2
qui divise exactement n. La méthode pour trouver N directement est connue.
EXEMPLE. Poursuivons l'exemple précédent n=357
m=(357+8)/10=36.
P2/236=1.6.11.16.21.36.41 176
On élimine les nombres terminés par 1. Il reste: (6.16.26.36 176).
On divise par 218 : (3.8.13.18 88)=(3.13.23 83)(8.18.28 88)
j=9 ; j mod 4 = 1 donc (3.13.23 83) mod 10 = 9.
On divise (8.18.28 88) par 29 : (4.9.14.19 44)=(9.19.29.39)(4.14.24.34.44)
(9.19.29.39) mod 10 = 1.
On divise (4.14.24.34.44) par 25 : (2.7.12.17.22)=(7.17)(2.12.22)
(7.17) mod 10 = 9.
(2.12.22)=3.11.24
Récapitulons les résultats modulo 10: donc (9.1.3.11) mod 10 = 7
La puissance de 2 a été trouvée =36+18+9+5+4=72.
Le résultat final relatif à P2 est : (P2/272) mod 10 = 7.
Quatrièmement : Puissances de 2 et de 5 :
La puissance (M) de 5 est toujours plus grande ou égale à la puissance (N) de 2.
On élimine les zéro correspondants à (2.5)M et il reste 2(N-M).
Il faut maintenant calculer 2(N-M) modulo 10. Si N=M cela donne 1.
Dans les autres cas, on voit que (2(N-M) mod 10)= 2, 4, 8 ou 6 selon que (N-M) mod 4 = 1, 2, 3 ou 0.
Il ne reste plus qu'à multiplier les résultats modulo 10 obtenus dans les quatre étapes successives
pour obtenir le chiffre qui précède les zéros à la fin de n!.
EXEMPLE : Terminons l'exemple n=357.
On a trouvé N=72 et M=44. (N-M)=28. (N-M) mod 4 =0 donc (228 mod 10)=6.
Les résultats modulo 10 obtenus dans les 4 étapes successives donnent le résultat final:
(8.3.7.6) mod 10=8.
Résultat : 357 se termine par 8 suivi de 87 zéro.
SECONDE METHODE :
Cette méthode est d'un principe plus simple.
Par contre, étant basée sur une décomposition en facteurs premiers, elle serait fastidieuse pour un calcul "à la main".
Elle convient mieux que la méthode précédente pour une programmation sur ordinateur (je l'ai fait).
Mais une troisième méthode donnée ensuite (uniquement pour ordinateur) est encore plus simple à programmer.
Premièrement :
On sait décomposer n! en facteurs premiers.
La suite des nombres premiers est notée : P1=2, P2=3, P3=5, P4=7, P5=11,
etc.
Les puissances correspondantes sont notées q1, q2, q3,
etc. Ainsi n! est mis sous la forme :
Exemple : n=10 : 10! = 28.34.52.7 ; q1=8; q2=4; q3=2; q4=1; q5=q6= =0
Autre exemple : Trouver q3 pour n=357.
P3=5; Dans 357! il y a 357/5=71 nombres divisibles par 5;
357/25=14 nombres divisibles par 52 et 357/125=2 nombres divisibles par 53 ;
Au total on trouve q3=71+14+2=87.
On doit effectuer ce travail pour tous les nombres premiers inférieurs ou égal à n.
Pour n=357, on obtient q1=352, q2=176, q3=87, etc
Deuxièmement: occupons nous de q1 et q3 :
A chaque fois 5 est associée une fois 2, ce qui donne 10.
Donc q3 donne le nombre de zéro à droite de n!
Et il reste 2 à la puissance ( q1 - q3 ) dont on cherche la valeur modulo 10 (notée R2)
On a toujours q1 > q3 . Comme les puissances de 2 modulo 10 sont 2, 4, 8, 6, 2, 4, 8, 6, etc
,
il suffit de considérer k=(q1-q3) mod 4. Si k=1, 2, 3 ou 0 on a directement R2=2, 4, 8 ou 6 respectivement.
Exemple : pour n=357 on a q1=352 et q3=87 . k=(352-87) mod 4 = 3 donc R2=8.
Troisièmement : Occupons-nous des nombres premiers se terminant par 3,
c'est à dire P2=3, P6=13, P9=23, P14=43, etc.
Le produit de tous ces nombres à leurs puissances respectives q2, q6, q9, q14, etc.
calculé modulo 10 équivaut à 3 puissance (q2+q6+q9+q14+ ) mod 10 ( noté R3).
Comme les puissances de 3 modulo 10 sont 3, 9, 7, 1, 3, 9, 7, 1, etc
, il suffit de considérer
k=(q2+q6+q9+q14,
) mod 4. Si k=1, 2, 3 ou 0 on a directement R3=3, 9, 7 ou 1 respectivement.
Quatrièmement :
On procède de même pour les nombres premiers se terminant par 7,
c'est à dire P4=7, P7=17, P12=37,
etc.
De la même façon, il suffit de considérer k=(q4+q7+q12+
) mod 4. Si k=1, 2, 3 ou 0 on a directement
R7=7, 9, 3 ou 1 respectivement.
Cinquièmement :
On procède de même pour les nombres premiers se terminant par 9,
c'est à dire P8=19, P10=29, P17=59,
etc.
De la même façon, il suffit de considérer k=(q8+q10+q17+ ). On a R9=1 si k est pair et R9=9 si k est impair.
Finalement :
Les nombres premiers terminés par 1 ne jouent pas sur le résultat modulo 10.
Tous les autres nombres ont été considérés.
Le premier chiffre précédant les zéro à la droite de n! est égal à (R2.R3.R7.R9) mod 10.
TROISIEME METHODE (POUR ORDINATEUR) :
L'algorithme suivant donne le nombre (noté: k) de zéro à droite de n! et les chiffres qui précèdent ces zéro (noté: j). Le nombre de chiffres que l'on obtient (1 ou plus) est fixé par le paramètre L : Pour un chiffre L=10, pour deux chiffres L=100, pour trois L=1000, etc. . Il est limité par la capacité du logiciel de calcul utilisé (nombre de digits des integer) : il ne faut pas que (nombre de digits de n + nombre de zero de L) > (nombre de digits des integer). Le logiciel n'utilise pas d'opération sur de grands nombres.
label
1,2;
var i,j,k,h,L,n:integer;
begin
write('n= ? ');Readln(n);
L:=1000;j:=1;k:=0;h:=0;
for i:=1 to n do
begin
j:=j*i;
1:
if j mod 2 = 0 then begin
h:=h+1; j:=j div 2;
goto 1;
end;
2:
if j mod 5 = 0 then begin
k:=k+1;j:=j div 5;
goto 2;
end;
j:=j mod L;
end;
h:=h-k;
if h>0 then begin
for i:=1 to h do
begin
j:=2*j;j:=j mod L;
end;
end;
writeln('Nb.zero =',k,' chiffres precedants = ',j);
readln;
end.