Enigme Fin de factorielle @ Prise2Tete

nodgim · #1

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.

caduk · #2

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 $m_2(n)$ la multiplicité de 2 dans le nombre n.

$m_2(n!) = \sum \limits_{i=1}^nm_2(i)$
On peut facilement démontrer par récurrence que

$m_2(n!) = 2\times m_2(\lfloor \log_2(n) \rfloor !) + 1 + m_2((n -\lfloor \log_2(n) \rfloor)!)$

Cela se démontre plutôt facilement par récurrence:
si

$n = 2^p$ ,

$m_2(n) = n-1$
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

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

$m_2(n!) = n - b(n)$
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

$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)!)$
On en déduit alors la formule miracle:

$m_5(n!) = \dfrac{n - q(n)}{4}$ 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.

nodgim · #3

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

Ebichu · #4

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

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.

Ebichu · #5

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.

nodgim · #6

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

Vasimolo · #7

Bonjour Nodgim

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

Vasimolo

nodgim · #8

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

caduk · #9

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.

nodgim · #10

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.

Vasimolo · #11

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

Vasimolo

nodgim · #12

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

enigmatus · #13

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

nodgim · #14

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

enigmatus · #15

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

nodgim · #16

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.

Vasimolo · #17

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

Vasimolo · #18

Une explication que j'espère claire :

Télécharger PDF

Vasimolo

LeJeu · #19

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);
}

enigmatus · #20

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

nodgim · #21

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.

caduk · #22

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

Ebichu · #23

Oui, jolie énigme !

scarta · #24

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

Forum dédié aux énigmes et à toutes formes de jeux de logique.	Déconnexion
Tu n'es pas identifié sur Prise2tete : s'identifier. Accueil Forum	[+]

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

Fin de factoriielle

#0 Pub

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

Fin de facorielle

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

fin de dactorielle

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

Fni de factorielle

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

Fin de factorielel

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

fin de facrorielle

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

Fin de factroielle

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

iFn de factorielle

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

Fin dde factorielle

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

Fin de factorielel

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

Fiin de factorielle

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

iFn de factorielle

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

Fin de fctorielle

Code:

Code:

Code:

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

fin de gactorielle

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

Fiin de factorielle

Code:

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

Fin de factoriele

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

fin de factirielle

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

Fin de factorieelle

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

gin de factorielle

Code:

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

fin de factorielme

Code:

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

in de factorielle

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

fin de factirielle

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

Fin de factoreille

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

fin fe factorielle

Réponse rapide

Sujets similaires

Pied de page des forums