Calcul formel : Mode d'emploi - Exemples en Maple
Claude Gomez, Bruno Salvy, Paul Zimmermann
Masson, 1995
Chapitre IV, section 1.5, exercice 1, page 107.
Philippe.Dumas@inria.fr
http://algo.inria.fr/dumas/Maple/
|
|
La factorielle de est le produit des entiers de à . Dire que son écriture décimale comporte zéros en queue, c'est dire que la plus grande puissance de qui divise est . Comme est le produit des deux nombres premiers et le nombre que nous cherchons est donné par la formule
.
Dans cette formule est la valuation dyadique de l'entier , c'est-à-dire le plus grande puissance de qui divise . De même est la plus grande puissance de qui divise . Si est un nombre premier, nous devons donc calculer . Pour cela nous remarquons que les multiples de plus petits que sont en nombre égal à la partie entière de . Chacun d'eux apporte une unité dans le décompte qui va donner . Cependant les multiples de apportent chacun une unité supplémentaire et ils sont en nombre égal à la partie entière de . Continuant ainsi nous voyons que le nombre cherché est donné par la formule
.
La somme est finie car les termes sont nuls dès que surpasse . Il ne reste plus qu'à appliquer le raisonnement que nous avons suivi pour obtenir la procédure demandée.
> tailsize:=proc(n::posint)
local p,q,v;
for p in {2,5} do
v.p.n:=0;
q:=p;
while n>=q do
v.p.n:=v.p.n+iquo(n,q);
q:=p*q
od;
od;
min(v.2.n,v.5.n)
end:
Testons la sur des exemples simples.
> factorial(10);
> tailsize(10);
> factorial(100);
> tailsize(100);
> N:=factorial(100):
for i from 0 while irem(N,10,'N')=0 do od;
i;
Le calcul des intervient dans la méthode de Tchébycheff, qui est une approche élémentaire du théorème des nombres premiers [Blanchard69].