Enigmes

Forum dédié aux énigmes et à toutes formes de jeux de logique.

Déconnexion

Tu n'es pas identifié sur Prise2tete : s'identifier.

accueil Accueil forum Forum
[+]

 #1 - 22-08-2017 10:57:04

nodgim
Elite de Prise2Tete
Enigmes résolues : 0
Messages : 3228

fin de factoriellr

Bonjour @ tous.

Quels sont les 2 derniers chiffres non nuls de 1 000 000 000 ! (factorielle 1 milliard) ?

Je ne sais pas si on peut s'en sortir avec l'informatique, mais son usage peut donner un résultat erroné....

Bon courage.



Annonces sponsorisées :
  • |
  • Répondre

#0 Pub

 #2 - 22-08-2017 15:14:26

caduk
Professionnel de Prise2Tete
Enigmes résolues : 45
Messages : 240

Fin de fatcorielle

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.

 #3 - 22-08-2017 19:42:39

nodgim
Elite de Prise2Tete
Enigmes résolues : 0
Messages : 3228

Fin de factoriellle

@ Caduk et @ tous : ça se calcule à la main facilement pour tout n ! une fois qu'on a mis au point la méthode et les calculs génériques, qui se font à la main également.

Caduk, tes distinctions de départ sont assez compliquées, je ne crois pas que tu puisses aboutir de cette façon. Tout le secret en fait est dans la bonne sélection des catégories de nombres à étudier.

 #4 - 22-08-2017 22:00:41

Ebichu
Professionnel de Prise2Tete
Enigmes résolues : 49
Messages : 494

Fin de factoriellee

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 smile

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.

 #5 - 22-08-2017 23:22:24

Ebichu
Professionnel de Prise2Tete
Enigmes résolues : 49
Messages : 494

FFin de factorielle

Le programme trouve que k=87 (100), d'où k.2^(a-b) = 87.2^(749 999 989) = 44 (100) : la réponse est 44.

 #6 - 23-08-2017 09:43:28

nodgim
Elite de Prise2Tete
Enigmes résolues : 0
Messages : 3228

Fin de factoriell

@ 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....

 #7 - 23-08-2017 17:50:20

Vasimolo
Le pâtissier
Enigmes résolues : 49
Messages : 4981

Fin de factroielle

Bonjour Nodgim smile

Chaque facteur de 00 à 99 modulo 100 apparaît 10 000 000 de fois . Il faut enlever tous les facteurs se terminant par 5 et un un nombre équivalent de facteurs 2 qui fabriquent les "0" de la fin . Après il faut regarder les 01^10 000 000  , 02^10 000 000 , ...  modulo 100 . Ce n'est pas franchement difficile mais plutôt laborieux .

A moins que j'ai raté quelque chose smile

Vasimolo

 #8 - 24-08-2017 11:53:37

nodgim
Elite de Prise2Tete
Enigmes résolues : 0
Messages : 3228

fin de factprielle

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

 #9 - 28-08-2017 19:22:01

caduk
Professionnel de Prise2Tete
Enigmes résolues : 45
Messages : 240

fin de factoeielle

Je serai intéressé par ta solution nodgim...
Après réflexion, je n'avais pas trouvé plus efficace de faire comme Vasimolo, en calculant tout les nombres à deux chiffres modulo 100 non divisible par 2 ou 5, après avoir compté pour chaque combien était présent (après avoir supprimé tout les 5 et les 2) ce qui est déjà très laborieux.

 #10 - 29-08-2017 08:47:30

nodgim
Elite de Prise2Tete
Enigmes résolues : 0
Messages : 3228

Finn de factorielle

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.

 #11 - 29-08-2017 11:07:34

Vasimolo
Le pâtissier
Enigmes résolues : 49
Messages : 4981

Fin de afctorielle

On peut limiter les calculs en regardant uniquement modulo 25 car pour les grands nombres le résultat sera très largement congru à 0 modulo 4 . On coupe l'entier en tranches de 25 et on compte combien de fois apparaissent 3,7,11,13,17,19 et 23 ( modulo 25 ) . Après on liste les puissances de ces entiers ( toujours modulo 25 ) et le reste est du calcul élémentaire que je laisse aux amateurs smile

Vasimolo

 #12 - 29-08-2017 13:16:34

nodgim
Elite de Prise2Tete
Enigmes résolues : 0
Messages : 3228

fin se factorielle

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

 #13 - 29-08-2017 15:03:43

enigmatus
Professionnel de Prise2Tete
Enigmes résolues : 0
Messages : 460

fin de factorirlle

Bonjour,
Après avoir lu avec intérêt les messages des intervenants, j'ai écrit le script fac.py, en python3, dont le résultat est en accord avec ceux de Ebichu #5 et nodgim #6.

Code:

#!/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])

#---------------------------------------------------
# Exposant de k dans N!
def expo_k(k):
   expo=0; i=k
   while i<=N: expo+=N//i; i*=k
   return expo
#---------------------------------------------------
# Calcul des 2 derniers chiffres de 2**n
def der2(n):
   n20=n%20
   ret=(2**n20)%100
   if n>1:
      if   n20==0: ret=76
      elif n20==1: ret=52
   return ret
#---------------------------------------------------
# Multiplication d'entiers en ne gardant que les 2 derniers chiffres
def mul2(n1,n2): return (n1*n2)%100
#---------------------------------------------------
expo2=expo_k(2); expo5=expo_k(5)
print("%d expo2=%d expo5=%d expo2-expo5=%d"%(N,expo2,expo5,expo2-expo5))

# Calcul de la factorielle en éliminant les puissances 2 et 5
fact=1
for n in range(2,N+1):
   k=n
   while (k%2)==0: k//=2 # Elimination des puissances de 2
   while (k%5)==0: k//=5 # Elimination des puissances de 5
   fact=mul2(fact,k)
# Ajout du terme correspondant aux puissances de 2 non appariées à 5
fact=mul2(fact,der2(expo2-expo5))
print("%02d"%fact)

À lancer ainsi (du moins sous linux) :

Code:

./fac.py 1000000000

En voici le résultat :

Code:

1000000000 expo2=999999987 expo5=249999998 expo2-expo5=749999989 lonzer=249999998
44

Ajouté : Calul effectué chez moi en 16 à 17 minutes

 #14 - 29-08-2017 17:10:29

nodgim
Elite de Prise2Tete
Enigmes résolues : 0
Messages : 3228

fon de factorielle

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

 #15 - 30-08-2017 09:55:53

enigmatus
Professionnel de Prise2Tete
Enigmes résolues : 0
Messages : 460

fin de facyorielle

Édité :
J'ai simplifié le script en #13, qui tourne maintenant en environ 11 minutes.
1) Calcul du nombre total de puissances de 5 dans la factorielle
2) Calcul pas à pas, en ne conservant que les 2 derniers chiffres, de la factorielle, en éliminant les puissances de 2 tant que leur nombre est inférieur ou égal au nombre total de puissances de 5

Code:

#!/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])

#---------------------------------------------------
# Nb total de puissances de 5
expo5_tot=0; i=5
while i<=N: expo5_tot+=N//i; i*=5
print("N=%d expo5_tot=%d"%(N,expo5_tot))

# Calcul de la factorielle en éliminant les puissances de 5,
# et une partie des puissances de 2
fact=1; expo2=0
for n in range(2,N+1):
   k=n
 # Elimination des puissances de 2, à concurrence du nb total de puissances de 5
   while expo2<expo5_tot and (k%2)==0:
      expo2+=1
      k//=2
 # Elimination des puissances de 5
   while (k%5)==0: k//=5
   fact=(fact*k)%100
print("%02d"%(fact))

 #16 - 31-08-2017 09:19:50

nodgim
Elite de Prise2Tete
Enigmes résolues : 0
Messages : 3228

fin de factoriemle

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.

 #17 - 31-08-2017 10:29:07

Vasimolo
Le pâtissier
Enigmes résolues : 49
Messages : 4981

Fin de faactorielle

J'avais fini par aboutir avec une méthode assez proche de la tienne que je vais essayer d'expliciter sur un exemple mais pas avec le Latex du site .

Vasimolo

 #18 - 31-08-2017 23:15:38

Vasimolo
Le pâtissier
Enigmes résolues : 49
Messages : 4981

fin de factoroelle

Une explication que j'espère claire :



Vasimolo

 #19 - 01-09-2017 08:36:36

LeJeu
Amateur de Prise2Tete
Enigmes résolues : 19
Messages : 1

Finn de factorielle

Bonjour,

la même chose sur trois chiffres avec  un petit programme qui donne le résultat instantanément :144 pour 10^9

( 12^100 = 376 mod[1000] et 376 *12=12 mod [1000])


Code:

#include <stdio.h>
int main()
{
    // on cherche le 3 derniers chiffres de n !
    long  n = 1000*1000*1000 ;    // 10^9 

    long p = n;    // le nb de départ divisé par 5 à chaque tour
    int r;        // le reste de la division par 5 à chaque tour
    int res=1;    // ce que l'on cherche    
    int k ;        //  indice de boucle
    
    while (p>0)
    {
        r = p % 5;
        p = p / 5;

        // la contribution des 'paquets de 4' ( périodicité de 100)
        for (k = 1 ; k<= p % 100; k++)
            res = (res*12) % 1000 ;

        // la contribution des facteurs restants
        for (k = 1 ; k <= r; k++)
            res = (res*(5*p+k)) % 1000;
    }    
    printf( "les trois derniers chiffres non nuls de factorielle %ld sont %03d \n",n,res);
}

 #20 - 01-09-2017 08:55:26

enigmatus
Professionnel de Prise2Tete
Enigmes résolues : 0
Messages : 460

Fin de factoriellle

@Vasimolo #18 : Explications très claires

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

Code:

#!/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)))

 #21 - 01-09-2017 08:57:54

nodgim
Elite de Prise2Tete
Enigmes résolues : 0
Messages : 3228

Fn de factorielle

OK Vasimolo, tu as travaillé modulo 20 au lieu de modulo 100 comme je l'ai fait, sinon c'est exactement la même démarche.

A noter la prestation de Lejeu pour les 3 derniers chiffres, qu'on peut aussi, à la limite, faire à la main en s'aidant d'un tableur.

Le 76, élément neutre de la multiplication des multiples de 4 modulo 100, n'est pas du tout un hasard, comme le 376 modulo 1000 pour les multiples de 8. Il se déduit de la même façon qu'on prouve que (p-1) ! = -1 mod p, qu'un certain Wilson avait énoncé.....

C'était un peu pour cette propriété, bien utile dans ce problème, que j'avais proposé cette énigme.

Merci @ tous pour votre participation.

 #22 - 02-09-2017 11:04:45

caduk
Professionnel de Prise2Tete
Enigmes résolues : 45
Messages : 240

fin de factoriekle

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

 #23 - 02-09-2017 18:11:48

Ebichu
Professionnel de Prise2Tete
Enigmes résolues : 49
Messages : 494

Fn de factorielle

Oui, jolie énigme !

 #24 - 04-09-2017 14:18:13

scarta
Elite de Prise2Tete
Enigmes résolues : 49
Messages : 1533

fin de facyorielle

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!)

 

Réponse rapide

Rédige ton message
| | | | Upload | Aide
:) :| :( :D :o ;) :/ :P :lol: :mad: :rolleyes: :cool:
Sécurité

Répondez à la devinette suivante : 

Le père de toto a trois fils : Pif, Paf et ?

Sujets similaires

Pied de page des forums

P2T basé sur PunBB
Screenshots par Robothumb

© Copyright 2002–2005 Rickard Andersson

Prise2Tete Forum Statistiques Liste des membres Hall of Fame Contact
© Prise2tete - Site d'énigmes et de réflexion.
Un jeu où seules la réflexion, la logique et la déduction permettent de trouver la solution.

Flux RSS de Prise2Tete Forum Jeux & Prise2Tete Test & Prise2Tete Partenariat et Publicité sur Prise2Tete