Inscription / Connexion Nouveau Sujet
Factorielle 100!
Y-t-il une astuce ou méthode pr savoir le dernier chiffre non null de 100! ?
Merci
Bonjour,
Je te conseille de commencer par diviser par 10 tous les multiples de 10.
Ensuite, idem en regroupant certains nombres dont le produit est un multiple de 10.
Lorsque la liste est épurée, on peut ne s'intéresser qu'au chiffre des unités de ceux qui restent.
Par exemple, 13 et 17 deviennent 3 et 7. Leur produit se termine donc par 1. Ils n'ont donc pas d'incidence sur le dernier chiffre non nul du résultat.
Je te laisse continuer ?
Voici une méthode générale qui fonctionne pour trouver les k derniers chiffres de n! avant les zéros à la fin:
on se définit une factorielle modifiée: f(m) est le produit des entiers de 1 à m sauf ceux qui sont multiples de 5. Par exemple, f(30)=1*2*3*4 *6*7*8*9 *11*12*13*14 *16*17*18*19 *21*22*23*23 *26*27*28*29.
Les entiers qui manquent sont 5*10*15*20*25*30, si on divise ce produit par 5^7 (7 est la valuation 5-adique de 30!, c'est -à-dire le nombre de facteurs 5 dans 30!), il reste 1*2*3*4*6 qui se trouve être f(6). Donc on peut écrire l'égalité suivante:
où f(0)=1 par définition. Et en général, pour n! on a la formule:
où d est la valuation 5-adique de n! et [r] est la partie entière de r.
Mais pour éliminer les zéros à la fin, il faut diviser les 2 côtés par 10^d donc il faut ajouter une division par 2^d aux deux côtés.
Ensuite, si on veut les k derniers chiffres non nuls, il faut faire ces calculs modulo 10^k. Mais en fait on va faire les calculs modulo 5^k car dans ce cas la fonction f() a des propriétés qui permettent de simplifier les calculs. Donc la formule finale est un système de 2 congruences comme ceci:
Les propriétés de f qui permettent de simplifier les calculs sont:
Comme exemple: on veut les k=3 derniers chiffres avant les zéros finaux de (10^6)!:
la valuation 5-adique de 10^6 est 249 998, et on fait les calculs modulo 125
Le système de congruences est:
x = f(10^6) f(200 000) f(40 000) f(8 000) f(1600) f(320) f(64) f(12) f(2) f(0) 2^(-249 998) mod 125
x = 0 mod 8
On commence par utiliser la propriété 1 pour simplifier le plus possible:
f(10^6) = (-1)^200000 f(10^6 mod 125) mod 125 = 1 * f(0) = 1 mod 125
et de la même façon, f(200000)=f(40000)=f(8000)=1 mod 125
f(1600)=(-1)^12 f(1600 mod 125) = f(100) mod 125
f(320) = (-1)^2 f(320 mod 125) = f(70) mod 125
Donc en fait on doit calculer x=f(2) f(12) f(64) f(70) f(100) 2^(-249 998) mod 125
f(2)=2 mod 125
f(12)=32 mod 125 (on doit les calculer au long ces deux-là).
f(64)=f(50)*51*52*53*54*56...*63*64 = 74 mod 125 car f(50)=f(2*5^2) = (-1)^2 = 1 mod 125 (propriété 2)
f(70)=f(64)*66*67*68*69 = 26 mod 125
f(100) = f(4*5^2) = (-1)^4 = 1 mod 125
Pour la puissance de 2, on utilise la fonction indicatrice d'Euler:
phi(125) = 100, et 2^(-249 998) = 2^(-250 000+2) = (2^(100))^(-2500) 2^2= 1*4 = 4 mod 125
Donc on calcule x = 2*32*74*26*1 * 4 = 44 mod 125
et les congruences sont:
x=44 mod 125
x=0 mod 8
et on trouve par la méthode que l'on veut (théorème des restes chinois ou autre) que l'unique solution est x=544 mod 1000. Ce sont bien les 3 derniers chiffres de 10^6 ! avant les zéros à la fin.
Pour 100! et k=1 c'est encore plus facile:
x=f(100) f(20) f(4) f(0) 2^-24 mod 5
x = 0 mod 2
et on simplifie f(100) et f(20) par le propriété 1, etc.
Sinon, par programme (Python), en calculant le dernier chiffre à chaque itération :
dernier = 1
for i in range(1,101):
dernier = dernier * i
if (dernier%10 == 0) : dernier = dernier//10
if (dernier%10 == 0) : dernier = dernier//10
dernier = dernier - int(dernier/10)*10
print(i), ":", dernier, " ",
1 : 1 2 : 2 3 : 6 4 : 4 5 : 2 6 : 2 7 : 4 8 : 2 9 : 8
10 : 8 11 : 8 12 : 6 13 : 8 14 : 2 15 : 3 16 : 8 17 : 6 18 : 8 19 : 2
20 : 4 21 : 4 22 : 8 23 : 4 24 : 6 25 : 5 26 : 3 27 : 1 28 : 8 29 : 2
30 : 6 31 : 6 32 : 2 33 : 6 34 : 4 35 : 4 36 : 4 37 : 8 38 : 4 39 : 6
40 : 4 41 : 4 42 : 8 43 : 4 44 : 6 45 : 7 46 : 2 47 : 4 48 : 2 49 : 8
50 : 4 51 : 4 52 : 8 53 : 4 54 : 6 55 : 3 56 : 8 57 : 6 58 : 8 59 : 2
60 : 2 61 : 2 62 : 4 63 : 2 64 : 8 65 : 2 66 : 2 67 : 4 68 : 2 69 : 8
70 : 6 71 : 6 72 : 2 73 : 6 74 : 4 75 : 3 76 : 8 77 : 6 78 : 8 79 : 2
80 : 6 81 : 6 82 : 2 83 : 6 84 : 4 85 : 4 86 : 4 87 : 8 88 : 4 89 : 6
90 : 4 91 : 4 92 : 8 93 : 4 94 : 6 95 : 7 96 : 2 97 : 4 98 : 2 99 : 8
100: 8
Bonjour,
Oui, bizarre en effet : Le passage de 14! à 15! est raté.
Il se trouve que je possède un objet devenu rare : Une notice papier de TI89. je suis allée voir comment obtenir une factorielle et l'exemple donné est 100! 
Est expliqué ensuite comment faire apparaître la valeur de 100! en entier, suivi d'une image de l'écran obtenu...
Bon, je ne vais pas donner la réponse car l'objectif de l'exercice est de trouver une méthode analogue à celles indiquées par godefroy_lehardi et sylvainc2.
il suffit de compter le nombre de 5 dans la decomposition en facteurs premiers de n!
Sans sortir l'artillerie lourde on peut ecrire un programme niveau lycee.
En fait, compter le nombre de 5 c'est bien pour trouver le nombre de zéros à la fin.
Mais Est-ce suffisant ou utile pour trouver le dernier chiffre distinct de zéro ?
oui ici il suffit d'eliminer les 2*5 (inutile de les compter)
faire un produit de 1 à n
tant qu'on rencontre un 5 alors on divise par 10
retourner le produit modulo 10 pour avoir le dernier chiffre non nul
ou retourner le produit pour avoir la factorielle sans les zeros terminaux
en Xcasfr on ecrirait:
/* dernier chiffre non nul de factorielle n */
DernierNonNul(n):={
local P,j,k;
P:=1;
pour j de 2 jusque n faire
k:=j;
tantque irem(k,5)==0 faire // eliminer les 0
k:=k/10;
ftantque
P:=P*k;
fpour
//retourne P // tous les chiffres sans les zeros terminaux
retourne irem(P,10) // dernier chiffre non nul
}:;
Je ne connais pas ce langage, mais il faut penser à 25, 50 et 75 où deux zéros apparaissent. Le programme le prévoit-il ?
oups ce programme marche avec Xcas mais k/10 n'est pas necessairement entier !
/********************************************************
***** Factorielle n sans ses zeros terminaux *****
********************************************************/
SansZeros(n):={
local P,j,k,c;
P:=1;
pour j de 2 jusque n faire // on passe en revue tous les entiers de 2 à n
k:=j; // un entier de cette revue
c:=0; // pour compter la valuation 5-adique de cet entier
tantque irem(k,5)==0 faire
k:=k/5;
c:=c+1;
ftantque // ex: pour k=150 on a c=2
P:=P*k/2^c; // elimination de c zeros terminaux
fpour
retourne P // tous les chiffres sans les zeros terminaux
//retourne irem(P,10) // dernier chiffre non nul
}:;
je verifie en creant un tableau:
tab:=seq([n,n!,SansZeros(n)],n,10,25)
son code latex:
latex(tab)
me renvoie:
Bonsoir,
Une piste pour travailler "sans filet" c'est à dire sans tableur ou calculatrice :
Le produit 31x32x33x34x36x37x38x39 se termine par un 6.
Idem avec 4, 5 , 6 , 7, 8 ou 9 au lieu de 3. Et 6x6 se termine par un 6
Et aussi 10x20x30x40x60x70x80x90 avant les zéros.
Je garde les pairs jusqu'à 26 compris pour les combiner avec les multiples de 5.
Il reste à calculer d'autres produits, mais c'est faisable.
salut LeDino, le dernier chiffre non nul de 15! est 8
Je suis parti d'une analyse trop superficielle.
J'ai considéré que le produit des derniers chiffres suffisait pour déterminer le chiffre suivant.
Or c'est faux : dernier(14!) = 2 * 15 donne 30 qui donne 3
Il faut garder les deux derniers chiffres : deuxderniers(14!) = 12 * 15 donne 180 qui donne 8
J'ai modifié le programme de façon à travailler sur les deux derniers chiffres...
dernier = 1
for d in range(0,10):
for u in range(0,10):
i = 1 + u + 10*d
dernier = dernier * i
if (dernier%10 == 0) : dernier = dernier//10
if (dernier%10 == 0) : dernier = dernier//10
dernier = dernier - int(dernier/100)*100
print(i), ":", dernier - int(dernier/10)*10, " ",
print(" ")
1 : 1 2 : 2 3 : 6 4 : 24 5 : 12 6 : 72 7 : 4 8 : 32 9 : 88 10 : 88
11 : 68 12 : 16 13 : 8 14 : 12 15 : 18 16 : 88 17 : 96 18 : 28 19 : 32 20 : 64
21 : 44 22 : 68 23 : 64 24 : 36 25 : 9 26 : 34 27 : 18 28 : 4 29 : 16 30 : 48
31 : 88 32 : 16 33 : 28 34 : 52 35 : 82 36 : 52 37 : 24 38 : 12 39 : 68 40 : 72
41 : 52 42 : 84 43 : 12 44 : 28 45 : 26 46 : 96 47 : 12 48 : 76 49 : 24 50 : 12
51 : 12 52 : 24 53 : 72 54 : 88 55 : 84 56 : 4 57 : 28 58 : 24 59 : 16 60 : 96
61 : 56 62 : 72 63 : 36 64 : 4 65 : 26 66 : 16 67 : 72 68 : 96 69 : 24 70 : 68
71 : 28 72 : 16 73 : 68 74 : 32 75 : 24 76 : 24 77 : 48 78 : 44 79 : 76 80 : 8
81 : 48 82 : 36 83 : 88 84 : 92 85 : 82 86 : 52 87 : 24 88 : 12 89 : 68 90 : 12
91 : 92 92 : 64 93 : 52 94 : 88 95 : 36 96 : 56 97 : 32 98 : 36 99 : 64 100: 64
Donc 4 serait le dernier chiffre cherché.
LeDino, ta solution pour 100! est bonne, mais celle pour 25! ne l'est pas (9). Le dernier chiffre non nul de n! ne peut pas être impair, sauf pour 1!, car il y a toujours plus de facteurs 2 que de facteurs 5 dans n!, donc une fois les facteurs 10 enlevés, le nombre restant contient au moins un facteur 2, donc il est pair.
Bonjour,
Voici une solution qui nécessite seulement de connaître un peu ses tables de multiplication et qui utilise le plus possible cette propriété :
Deux nombres qui se terminent par un 6 donnent un produit qui se termine aussi par un 6.
Quand j'écris « se termine par » ou « chiffre terminal », je ne tiens pas compte des zéros à la fin.
C'est un peu alambiqué 
Le produit 31x32x33x34x36x37x38x39 se termine par un 6 (il n'y a pas 35).
Idem avec 4, 5 , 6 , 7, 8 ou 9 au lieu de 3.
Et aussi pour 10x20x30x40x60x70x80x90 (il n'y a pas 50).
Pour le justifier, on regroupe les chiffres terminaux autres que 1 et 6 pour n'obtenir que des 6 : 2x3 
6 4 x9 6 7x8 6 .
On peut associer les multiples de 25 avec des multiples de 4 :
25x4 = 100 1 50x8 = 100x4 4 75x12 = 25x4x3x3 9
Il reste les multiples de 5 non encore envisagés associés avec des multiples de 2 disponibles :
5x2 1 15x6 = 3x3x10 9 35x14 = 7x7x10 9 45x16 = 9x8x10 2 55x18 = 11x9x10 9 65x22 = 13x11x10 3 85x24 = 17x12x10 4 95x28 = 19x14x10 6 .
Chiffres terminaux à multiplier : 1,9,9,2,9,3,4,6 . 1x9x9 1 ; 2x3 6 ; 9x4 6 . le résultat est encore 6.
Il reste 26 comme pair non utilisé. Et les impairs non multiples de 5 jusqu'à 29 compris : 3, 7, 9, 11, 13, 17, 19, 21, 23, 27, 29
26 ne change pas le chiffre 6 terminal. 11 et 21 non plus.
Idem pour 3x7 9x19 11 13x17 21 et 23x27 .
Il ne reste que 29. Autrement dit 100!/29 se termine par un 6.
100 ! se termine donc par le chiffre des unités de 6x9 
Pour le problème avec 25! :
36x25 = 900 mais 24! se termine par 936 et 936x25 = 23400
Le 9 de 936 intervient dans le chiffre terminal.
On trouve aussi un topic de l'île : 
pb de maths : aidez moi
Un autre site aussi sur la question du concours Kangourou :
Avec des méthodes aussi alambiquées que la mienne car la calculatrice était interdite. Le terme "absorbant" pour le chiffre terminal 6 me plait bien.
Enfin un site avec quelques valeurs exactes :
Mais qui s'arrête à 212! ; donc raté pour 1000! .
Effectivement, il faut traiter au moins un chiffre de plus que le nombre de chiffres de la factorielle dont on veut le dernier non nul...
J'ai modifié mon algorithme en conséquence.
Il devrait ainsi marcher jusqu'à 1000...
Sauf erreur.
dernier = 1
for d in range(0,100):
print(d*10+1),"à",d*10+10, ": ",
for u in range(0,5):
i = 1 + u + 10*d
dernier = dernier * i
for k in range(6):
if (dernier%10 == 0) : dernier = dernier//10
dernier = dernier - int(dernier/10000)*10000
print dernier - int(dernier/10000)*10000, " ",
print(" ")
4 derniers chiffres jusqu'à 1000 :
1 à 10 : 1 2 6 24 12 72 504 4032 6288 6288
11 à 20 : 9168 16 208 2912 4368 9888 8096 5728 8832 7664
21 à 30 : 944 768 7664 3936 984 5584 768 1504 3616 848
31 à 40 : 6288 1216 128 4352 5232 8352 9024 2912 3568 4272
41 à 50 : 5152 6384 4512 8528 8376 5296 8912 7776 1024 512
51 à 60 : 6112 7824 4672 2288 2584 4704 8128 1424 4016 4096
61 à 70 : 9856 1072 7536 2304 4976 8416 3872 3296 7424 1968
71 à 80 : 9728 416 368 7232 5424 2224 1248 7344 176 1408
81 à 90 : 4048 1936 688 7792 6232 5952 7824 8512 7568 8112
91 à 100 : 8192 3664 752 688 6536 7456 3232 6736 6864 6864
101 à 110 : 3264 2928 1584 4736 9728 1168 4976 7408 7472 2192
111 à 120 : 3312 944 6672 608 6992 1072 5424 32 3808 5696
121 à 130 : 9216 4352 5296 6704 838 5588 9676 8528 112 1456
131 à 140 : 736 7152 1216 2944 9744 5184 208 8704 9856 7984
141 à 150 : 5744 5648 7664 3616 2432 5072 5584 6432 8368 2552
151 à 160 : 5352 3504 6112 1248 9344 7664 3248 3184 6256 96
161 à 170 : 5456 3872 1136 6304 4016 6656 1552 736 4384 4528
171 à 180 : 4288 7536 3728 8672 5176 976 2752 9856 4224 6032
181 à 190 : 1792 6144 4352 768 4208 2688 2656 9328 2992 6848
191 à 200 : 7968 9856 2208 8352 2864 1344 4768 4064 8736 7472
201 à 210 : 1872 8144 3232 9328 1224 2144 3808 2064 1376 8896
211 à 220 : 7056 5872 736 7504 1336 8576 992 6256 64 1408
221 à 230 : 1168 9296 3008 3792 8532 8232 8664 5392 4768 9664
231 à 240 : 2384 3088 9504 3936 2496 9056 6272 2736 3904 3696
241 à 250 : 736 8112 1216 6704 4248 5008 6976 48 1952 488
251 à 260 : 2488 6976 4928 1712 3656 5936 5552 2416 5744 9344
261 à 270 : 8784 1408 304 256 6784 4544 3248 464 4816 32
271 à 280 : 8672 8784 8032 768 2112 2912 6624 1472 688 9264
281 à 290 : 3184 7888 2304 4336 3576 2736 5232 6816 9824 4896
291 à 300 : 4736 2912 3216 5504 2368 928 5616 3568 6832 496
301 à 310 : 9296 7392 9776 1904 8072 32 9824 5792 9728 1568
311 à 320 : 7648 6176 3088 9632 3408 6928 6176 3968 5792 5344
321 à 330 : 5424 6528 8544 8256 6832 7232 4864 5392 3968 944
331 à 340 : 2464 8048 9984 4656 5976 7936 4432 8016 7424 2416
341 à 350 : 3856 8752 1936 5984 6448 1008 9776 2048 4752 6632
351 à 360 : 7832 6864 2992 9168 5464 5184 688 6304 3136 2896
361 à 370 : 5456 5072 1136 3504 7896 9936 6512 6416 7504 7648
371 à 380 : 7408 5776 4448 3552 1332 832 3664 4992 1968 4784
381 à 390 : 2704 2928 1424 6816 2416 2576 6912 1856 1984 7376
391 à 400 : 4016 4272 8896 5024 8448 5408 6976 6448 2752 1008
401 à 410 : 4208 1616 1248 4192 9776 9056 5792 3136 2624 7584
411 à 420 : 7024 3888 5744 8016 2664 8224 9408 2544 5936 9312
421 à 430 : 352 8544 4112 3488 4824 5024 5248 6144 5776 8368
431 à 440 : 6608 4656 6048 4832 192 3712 2144 9072 2608 4752
441 à 450 : 5632 9344 9392 48 2136 2656 7232 9936 1264 5688
451 à 460 : 5288 176 9728 6512 6296 976 6032 2656 9104 8784
461 à 470 : 9424 3888 144 6816 6944 5904 7168 4624 8656 6832
471 à 480 : 7872 5584 1232 3968 8848 1648 6096 3888 2352 2896
481 à 490 : 2976 4432 656 7504 3944 6784 3808 8304 656 2144
491 à 500 : 2704 368 1424 3456 1072 1712 864 272 5728 2864
501 à 510 : 4864 1728 9184 8736 1168 1008 1056 6448 2032 3632
511 à 520 : 5952 7424 8512 5168 6152 4432 1344 6192 3648 9696
521 à 530 : 1616 3552 7696 2704 4196 7096 9592 4576 704 7312
531 à 540 : 2672 1504 1632 1488 9608 9888 9856 2528 2592 9968
541 à 550 : 2688 6896 4528 3232 6144 4624 9328 1744 7456 1008
551 à 560 : 5408 5216 4448 4192 2656 6736 1952 9216 1744 7664
561 à 570 : 9504 1248 2624 9936 1384 3344 6048 5264 5216 7312
571 à 580 : 5152 6944 8912 5488 1556 6256 9712 3536 7344 5952
581 à 590 : 8112 1184 272 8848 7608 8288 5056 2928 4592 928
591 à 600 : 8448 1216 1088 6272 3184 7664 5408 3984 6416 8496
601 à 610 : 6096 9792 4576 3904 6192 2352 7664 9712 4608 1088
611 à 620 : 4768 8016 3808 8112 8888 5008 9936 448 7312 3344
621 à 630 : 6624 128 9744 256 16 16 32 96 384 4192
631 à 640 : 5152 6064 8512 6608 9608 688 8256 7328 2592 5888
641 à 650 : 4208 1536 7648 5312 2624 5104 2288 2624 2976 9344
651 à 660 : 2944 9488 5664 4256 8768 1808 7856 9248 4432 2512
661 à 670 : 432 5984 7392 8288 1152 7232 3744 992 3648 4416
671 à 680 : 3136 7392 4816 5984 392 4992 9584 7952 9408 9744
681 à 690 : 5664 2848 5184 5856 1136 9296 6352 176 1264 7216
691 à 700 : 6256 9152 2336 1184 2288 2448 6256 6688 4912 4384
701 à 710 : 3184 5168 3104 5216 7728 5968 9376 8208 9472 2512
711 à 720 : 6032 4784 992 8288 2592 5872 224 832 8208 976
721 à 730 : 3696 8512 4176 3424 4824 2224 6848 5344 5776 1648
731 à 740 : 4688 1616 4528 3552 1072 8992 7104 2752 3728 5872
741 à 750 : 1152 4784 4512 6928 6136 7456 9632 4736 7264 5448
751 à 760 : 1448 8896 8688 752 6776 2656 592 8736 624 7424
761 à 770 : 9664 3968 7584 4176 9464 9424 8208 3744 9136 3472
771 à 780 : 6912 6064 7472 3328 5792 4592 7984 1552 9008 2624
781 à 790 : 9344 7008 7264 4976 616 4176 6512 1456 8784 3936
791 à 800 : 3376 3792 7056 2464 5888 6848 7856 9088 1312 496
801 à 810 : 7296 1392 7776 1904 3272 7232 6224 8992 4528 6768
811 à 820 : 8848 4576 288 4432 1208 5728 9776 6768 2992 5344
821 à 830 : 7424 2528 544 8256 8112 512 3424 5072 4688 9104
831 à 840 : 5424 2768 5744 496 1416 3776 512 9056 7984 656
841 à 850 : 1696 8032 976 3744 6368 7328 6816 9968 2832 4072
851 à 860 : 5272 1744 7632 7728 744 6864 2448 384 9856 7616
861 à 870 : 7376 8112 656 6784 6816 2656 2752 8736 1584 7808
871 à 880 : 768 9696 4608 7392 6468 5968 3936 5808 5232 416
881 à 890 : 6496 9472 3776 7984 6584 3424 7088 4144 4016 7424
891 à 900 : 4784 7328 3904 176 5752 3792 1424 8752 8048 2432
901 à 910 : 1232 1264 1392 8368 7304 7424 3568 9744 7296 3936
911 à 920 : 5696 4752 8576 8464 4456 1696 5232 2976 4944 4848
921 à 930 : 5008 7376 8048 6352 8756 8056 7912 2336 144 3392
931 à 940 : 7952 1264 9312 7408 2648 8528 736 368 5552 1888
941 à 950 : 6608 4736 6048 9312 9984 4864 6208 5184 9616 1352
951 à 960 : 5752 5904 6512 2448 3784 7504 1328 2224 2816 336
961 à 970 : 2896 5952 1776 2064 9176 4016 3472 896 8224 7728
971 à 980 : 3888 9136 9328 5472 3352 1552 6304 5312 448 3904
981 à 990 : 9824 7168 6144 5696 1056 1216 192 9696 9344 5056
991 à 1000 : 496 2032 7776 9344 9728 9088 736 4528 3472 3472
Variante jusqu'à 10000 :
dernier = 1
for i in range(1,10001):
dernier = dernier * i
for k in range(10):
if (dernier%10 == 0) : dernier = dernier//10
dernier = dernier - int(dernier/100000)*100000
if (i%100 == 0): print(i), ":", dernier - int(dernier/100000)*100000, " "
Résultats de 100 en 100 (sauf erreur) :
100 : 16864
200 : 37472
300 : 70496
400 : 91008
500 : 12864
600 : 78496
700 : 64384
800 : 50496
900 : 62432
1000 : 53472
1100 : 7808
1200 : 59296
1300 : 90944
1400 : 8064
1500 : 2496
1600 : 76544
1700 : 74016
1800 : 11296
1900 : 83584
2000 : 39008
2100 : 94912
2200 : 77952
2300 : 28384
2400 : 84096
2500 : 17864
2600 : 78496
2700 : 60768
2800 : 95264
2900 : 68352
3000 : 42496
3100 : 32544
3200 : 50688
3300 : 1312
3400 : 48544
3500 : 46384
3600 : 91776
3700 : 15072
3800 : 41024
3900 : 43424
4000 : 2496
4100 : 76544
4200 : 16256
4300 : 34016
4400 : 11616
4500 : 44432
4600 : 37248
4700 : 62688
4800 : 68736
4900 : 32704
5000 : 33472
5100 : 91808
5200 : 70944
5300 : 88032
5400 : 10816
5500 : 89808
5600 : 22112
5700 : 53632
5800 : 80128
5900 : 19296
6000 : 87296
6100 : 87744
6200 : 63008
6300 : 45856
6400 : 78176
6500 : 98944
6600 : 67616
6700 : 94944
6800 : 15904
6900 : 46592
7000 : 52064
7100 : 39296
7200 : 56736
7300 : 84672
7400 : 61248
7500 : 62496
7600 : 72544
7700 : 22432
7800 : 23456
7900 : 43648
8000 : 32544
8100 : 2016
8200 : 21632
8300 : 13888
8400 : 57376
8500 : 32016
8600 : 65824
8700 : 87008
8800 : 53184
8900 : 79744
9000 : 3296
9100 : 67744
9200 : 77536
9300 : 63456
9400 : 61312
9500 : 77584
9600 : 28576
9700 : 20576
9800 : 16832
9900 : 88928
10000: 79008
@LeDino
il manque les zeros en tete comme avec 9000
Ci-dessous une fonction Xcas qui prend en parametres deux entiers n et p
qui renvoie les p chiffres avant les zeros terminaux de n!
// renvoie les p chiffres situes avant les zeros terminaux de n!
ChiffresAvantZeros(n,p):={
local N;
N:=n!;
tantque irem(N,10)==0 faire
N:=N/10
ftantque
N:=string(N);
retourne mid(N,size(N)-p,p)
}:;
ChiffresAvantZeros(9000,5) retourne 03296
ChiffresAvantZeros(100000,10) retourne 4957162496 en 33 secondes
Dis moi @alb...
Tu as la fonction factorielle toute cuite avec XCAS ou je me trompe ?
Si c'est le cas, c'est une bonne pub pour XCAS.
Mais comme algorithme ça vaut pas un pet de lapin ...
loin de moi l'idee de polluer olfactivement ce fil ...
je propose simplement une fonction pour verifier certains resultats.
Un logiciel de calcul formel comme Xcas (python n'en est pas un) permet de tester des conjectures qu'un humain ne fera pas.
Sur ce je vais apporter des carottes à mes lapins.
Je crois que je vais moderer leur consommation de feculents.
Cela dit, ta solution est plus qu'intéressante.
J'ai personnellement du mal à cerner exactement les limites de ma propre approche.
Je n'ai pas beaucoup de temps à y consacrer, alors je suis en mode "exploration rapide" plutôt qu'en réflexion approfondie
...
Voici une série de résultats pour des valeurs hautes avec mon algo.
Pourrais-tu vérifier (rien ne presse) certaines de ces valeurs avec ton programme ?
dernier = 1
n = 1000000
for i in range(1,n+1):
dernier = dernier * i
while (dernier%10 == 0) : dernier = dernier//10
dernier = dernier - int(dernier/n/10)*n*10
if (i%(n/10) == 0): print(i), ":", dernier - int(dernier/n*10)*(n//10), " "
Bonjour LeDino,
Toutes tes valeurs sont exactes.
J'avais écrit un programme sur ma calculatrice (TI92) il y a presque 20 ans (pour généraliser un problème posé à la finale 1993 du championnat FFJM: LE ROI DES NULS).
Si tu veux d'autres valeurs:
n=10^7: 94688
n=10^8: 54176
n=10^9: 38144
n=10^10: 46112
n=10^20: 36608
n=10^50: 09152
n=10^100: 35616 (en 30s sur ma calculatrice).
La factorielle de ce dernier nombre a environ 10^102 chiffres!
Merci pour la vérification jandri .
Vue l'énormité des nombres que tu arrives à traiter avec ton programme, j'imagine volontiers qu'il est plus sioux que le mien (qui est très élémentaire en fait).
Je n'ai pas trop de temps pour creuser... mais je suppose que des regroupements ou des "cycles" sont envisageables...
Très impressionnante en tout cas ta TI92 (avec son pilote aux commandes ).
salut les cuniculteurs !
ce programme ( de tricheur certes puisque j'utilise l'implementation de la factorielle)
ne va pas bien loin ( au-delà de 100000! mais pas jusqu'à 1000000!)
mais il permet d'afficher tous les chiffres que l'on veut.
// supprime les zeros terminaux de factorielle n
// l'utilisateur est averti de la longueur de la chaine tronquee
// il choisit p1 et p2
// renvoie les chiffres du rang p1 au rang p2
ChiffresFactorielle(n):={
local N,s,p1,p2;
N:=n!;
tantque irem(N,10)==0 faire
N:=N/10
ftantque
N:=string(N);
s:=size(N);
output("le nombre de chiffres de n! sans ses zeros finaux est "+s);
saisir("debut",p1,"fin",p2)
retourne mid(N,p1-1,p2-p1+1)
}:;
En tapant ChiffresFactorielle(102458) on obtient dans l'ordre:
une fenetre qui donne la longueur de la chaine tronquee 443267
une fenetre qui demande à l'utilisateur debut et fin par exemple 1 et 15
renvoie 294785429084949
@jandri
puis-je me permettre de te demander d'expliquer en 2 mots l'algo que tu utilises ?
Bonjour @alb12
Mon programme pour les p derniers chiffres non nuls de n! est un peu compliqué, mais pour les 3 derniers chiffres non nuls c'est plus simple.
On écrit d'où
avec
et
modulo 125.
On en déduit modulo 125.
Pour ,
est multiple de 8, on obtient donc
modulo 1000 en ajoutant un multiple de 125.
Ensuite on traite par récursivité (ou par itération).
Voici une fonction récursive en python (les points représentent l'indentation):
def rdn3(n):
.... if n<=5: return [1,1,2,6,24,12][n]
.... q,r = n//5,n%5
.... x=(12**(q%100))%125
.... for k in range(1,r+1): x=(x*(5*q+k))%125
.... while (x%8)!=0: x=x+125
.... return (rdn3(q)*x)%1000
Et la même itérative:
def rdn3b(n):
.... res=1
.... while n>5:
........ n,r = n//5,n%5
........ x=(12**(n%100))%125
........ for k in range(1,r+1): x=(x*(5*n+k))%125
........ while (x%8)!=0: x=x+125
........ res=(res*x)%1000
.... return ([1,1,2,6,24,12][n]*res)%1000
Elle donne instantanément les 3 derniers chiffres non nuls de la factorielle de : 912
Bonjour @jandri !
Votre algorithme est vraiment impressionnant dans sa vitesse d'exécution.
Je n'arrive pas à trouver une solution mathématique permettant de calculer la solution pour p derniers chiffres non nuls de n! de manière aussi efficace que celui pour les 3 derniers chiffres.
Vous évoquez dans votre dernier message un tel algorithme. Est-il aussi efficace?
Auriez vous la gentillesse de me l'expliquer?
Annuler
connectez vous
arithmétique en Bts