Fin de factorielle

[nodgim]

Une question restée sans réponse pour l'instant sur un autre site :
Trouver, à la main, les 2 derniers chiffres non nuls de la factorielle de 1 milliard (ou de tout autre nombre....)

Bonne recherche.

[WillyCagnes]

bjr

facile pour 1 000 000 000! se termine par 9 zeros au minimum

à partir de factoriel 10! = 3 628 800 les factorielles suivantes se terminent par 2 zeros au minimum

[Pseuda]

Bonjour,

Il s'agit des 2 derniers chiffres non nuls ! On sait déjà que ces 2 derniers chiffres se terminent par 2, 4, 6 ou 8.

[WillyCagnes]

bjr
sorry, je n'avais pas mis mes lunettes....

cas pour le dernier chiffre
Soit p et q les exposants respectifs de 2 et 5 dans n!.
soit n! = a*(2^p)*(5^q)
Le dernier chiffre cherché est donc égal à
a*2^(p-q) mod 10


http://mathprepa.fr/2017/02/dernier-chi ... -nul-de-n/

[Pseuda]

La formule de Stierling fournit un équivalent je crois, et ici il faut une valeur exacte. Je verrais bien d'abord un dénombrement du nombre de zéros (nombre de 5 dans la décomposition en facteurs premiers), puis congrence du ratio modulo 10^2. Il n'y a plus de 5 et beaucoup de 2 dans le ratio, donc des 4.

Ah tu as modifié ton message entre-temps, tant pis je laisse.

[pascal16]

C'est faisable au tableur avec des 'petits' nombres.
des tests de modulo 5/25/125/.../5^x permettent d'éliminer les zéros qui ne ne sont pas utiles.
un modulo 100 permet de réduire les calculs aux deux derniers chiffres et de ne pas exploser la longueur des chiffres.
Vite fait, je ne suis pas allé loin, la cyclicité qui ne m'a pas apparue évidente.

en tout cas, ça fini par xy avec x€{0;2;4;6;8} et y €{2;4;6;8}

Si on trouve une cyclicité (du genre c'est le même résultat pour 100!, 200! .... et 1 00000 000 !) on peut alors passer à la démonstration

[nodgim]

Y a de l'idée, Pascal 16, c'est cette voie là à suivre (la cyclicité ou, plus chic, le modulo)
En revanche, le x du xy n'est pas toujours pair.

[pascal16]

toujours pas mieux.
il y a des 'trucs' 20-100-500-2500' ou '80 400 2000 10000' ont la même fin (multiplication par 5), mais j'ai rien démontré.
par le même truc, on aurait 44 comme chiffres finaux.

j'ai essayé de voir en découpant la factorielle par centaine.
Mais si in multiplie par 311 ou 411, les deux derniers chiffres sans zéro sont les mêmes, mais par 310 et 410, ils sont différents. Donc pas de décomposition.

[nodgim]

Le résultat est bien 44, bravo !
Il faudrait que tu expliques comment tu es arrivé à ce nombre.

[pascal16]

j'ai divisé 1 000 000 000 par 5 plusieurs fois et vu qu'il suivait la logique que je n'ai pas démontré.

[nodgim]

OK. Bien que tu n'as pas démontré, le bon résultat prouve que tu ne dois pas être si loin que ça.
La question reste posée. La résolution n'est pas bien méchante pourtant. En calcul générique préparatoire, il y a 100 petites multiplications à faire, et pour chaque application, quelques unités, selon le nombre cherché.

[pascal16]

faire 100 multiplication, c'est déjà préférer la solution programmatique.

[LeJeu]

Le résultat est bien 44, bravo !
Il faudrait que tu expliques comment tu es arrivé à ce nombre.

Bonsoir Nodgim,

Je propose de reprendre les techniques déjà publiées sur le net, entre autres sur prise2tête et ilemaths.net
J'ai fait les vérifications élémentaires pour 20! ..512! avec Wolfram, mes calculs semblent ok

Code: Tout sélectionner

j'appelle F(n) les deux derniers chiffres non nuls de n!

L'idée est de regrouper les facteurs non multiple de 5 quatre par quatre
ex pour 20 ! = (1*2*3*4) *5 *(6*7*8*9) *10 *(11*12*13*14)* 15 *(16*17*18*19) * 20

de diviser chaque groupe de 4 par 2 et de l'associer au multiple de 5
20 ! = (1*2*3*4)/2 * (6*7*8*9) /2 * (11*12*13*14)/2 * (16*17*18*19)/2 * 10^4 * 4!

Chaque groupe  (x*x+1*x+2*x+3) = 12 [100]

donc  F(20) = 12^4 *4! [100]
=64

donc pour n! n multiple de 5 ,
on a F(n) =  12^(n/5) [100] * (n/5)! [100]

pour calculer les 12^k[100], on calcul préalablement les puissances jusqu'à trouver un cycle

k     12^k[100]
1   12
2   44
3   28
4   36
5   32
6   84
7   8
8   96
9   52
10   24
11   88
12   56
13   72
14   64
15   68
16   16
17   92
18   4
19   48
20   76
21   12

le cycle est de 20 , pour calculer 12^k[100] on calculera r le reste de la division par 20 de k et on a
12^k[100] = 12^r[100]

toute les égalités sont données mod 100 :

F (10^9)=  12^(200 000 000)* F(200 000 000) = 76 * F(200 000 000)
F(200 000 000) = 12^(40 000 000) * F(40 000 000)= 76 *F(40 000 000)
F(40 000 000) = 12^(8 000 000) * F(8 000 000) = 76 *F(8 000 000)
F(8 000 000) = 12^(1 600 000) * F(1 600 000)= 76 * F(1 600 000)
F(1 600 000) = 12^(320 000) * F(320 000) = 76 * F(320 000)
F(320 000) = 12^(64 000) * F(64 000) = 76 * F(64 000)
F(64 000)= 12^(12 800) * F(12 800)= 76 * F(12 800)
F(12 800)= 12^(2 560) *F(2 560) = 76 * F(2 560)

F(2 560)= 12^(512)* F(512) = 56 * F(512)
F(512)= 512 * 511 * 12^(102) *F(102) = 512*511*44* F(102)
F(102)= 102 * 101 * 12^(20) *F(20) = 102*101*76 *F(20)
F(20)= 12^4 * F(4) = 36* F(4)
F(4)= 4! = 24

donc

F(20) = 24 *36 = 64
F(102) = 102*101*76*64 = 28
F(512) = 512*511*44*28 = 24
F(2560) = 56*24 = 44

et comme coup de chance 44* 76 = 44

F (10^9) = F(200 000 000) = F(40 000 000) = F(8 000 000) = F(1 600 000) = F(320 000) = F(64 000) = F(12 800)= 44


Très peu d'opérations au final !

Merci aux auteurs des articles originaux, je ne connaissais pas , j'en étais resté à calculer le dernier chiffre en faisant des horribles associations de chiffres finaux....

[nodgim]

C'est ça Lejeu, à certaines nuances près pour ma part...Bravo à toi.
Et puis, le 76 élément neutre, ce n'est pas un coup de chance du tout, mais bien le résultat de ce qui ressemble à du Wilson.

Sinon, tu fais référence à des "techniques" publiées sur prise de tête, peux tu en dire plus ?
En fait, ma question initiale est sur prise de tête, et par manque de réponse, elle a été reproduite ici.

[nodgim]

faire 100 multiplication, c'est déjà préférer la solution programmatique.

On peut tout de même encore aujourd'hui, je l'espère, faire 100 multiplications modulo 100 à la main !
On ne le fait qu'une fois, et pour les applications, on se sert de ces résultats.

[LeJeu]

C'est ça Lejeu, à certaines nuances près pour ma part...Bravo à toi.
Et puis, le 76 élément neutre, ce n'est pas un coup de chance du tout, mais bien le résultat de ce qui ressemble à du Wilson.

Sinon, tu fais référence à des "techniques" publiées sur prise de tête, peux tu en dire plus ?
En fait, ma question initiale est sur prise de tête, et par manque de réponse, elle a été reproduite ici.

Le premier fil sur Prise de tête -topic 5987- date de 26-02-2010 17:25:10 " Quel est le dernier chiffre différent de 0 du produit entre les nombres entiers de 1 à 100?"

C'est en 2015 que Scarta vient compléter le fil en regroupant par 4 pour calculer le denier chiffre, et dit que ca doit se généraliser pour les deux derniers... ce que j'ai fait

Un dénommé Nodgim a validé les calculs de Scarta..

(Il est noté que par la technique ci dessus on obtient F(100) = 76*36*24 = 64 , ce qui n'est pas mal)

Le deuxième sur Ile des maths : Y-t-il une astuce ou méthode pr savoir le dernier chiffre non null de 100! ? le 08-08-15 à 21:22 Sylvainc2 nous parle d'une fonction factorielle modifiée qui ressemble un peu , mais que je n'ai pas bien suivi... voire, me semble obscure....

Je veux bien que tu me dises pourquoi 76 : élément neutre te parait évident , je ne vois pas....

[nodgim]

Le Nodgim qui avait validé Scarta à l'époque, c'était bien moi, j'avais oublié depuis le temps.
Pour le 76, c'est évident.....une fois qu'on y a réfléchi un bon peu....

Tout d'abord, 1*2*3*4*6*7*8*9*11*12*13*14*16*17*18*19*21*22*23*24, c'est à dire 25! auquel on a ôté les multiples de 5, donne -1 modulo 25.
Ceci se prouve parce que:
-seuls 1 et -1(24) sont inverses d'eux mêmes mod 25.
-tous les autres nombres s'apparient pour donner 1. (bezout)
Ne reste donc que le -1 .
D'autre part, modulo 25, 100! vaut 1 (sans les multiples de 5), puisque (-1)*(-1)*(-1)*(-1) = 1
Or les 2 derniers chiffres non nuls sont divisibles par 4. Donc modulo 100, un nombre de la forme 25k+1 et 4j, il n'y a que 76.
Or 76*4j = 4j + 100 k car
76*j = j + 25 k et comme 76 = 1 mod 25. j = j + 25k
76 est donc bien élément neutre pour les multiples de 4 mod 100.

[zygomatique]

salut

tout simplement modulo 100 : 76 * 4j = (3 * 25 + 1) * 4j = 300j + 4j = 4j

c'est aussi vrai pour 26 et 51 bien évidemment comme tu l'as dit mais ces derniers ne sont pas multiple de 4 ...