Défis mathématiques-informatique saison 2
C'est le retour des défis : sup ou spé, tout le monde peut jouer.
Trouver la plus grande puissance de 2 inférieure ou égale à un nombre x donné, ce n'est pas dur lorsque le nombre est petit.
Par exemple si x=25 nous avons : 2^4 = 16 et 2^5=32 ; l'exposant cherché c'est 4.
C'est toujours possible avec des nombres un peu plus grands.
Voici le défi 1 : le faire avec x = 1000000!
Tentez votre chance : postez vos réponses en commentaires à ce message. De nombreux lots à gagner !
Note historique sur le symbole ! : dans cet extrait vous pouvez semble-t-il voir la première utilisation du point d'exclamation pour désigner la factorielle.
2 réactions
1 De Valentin Thirion - 08/10/2014, 23:22
2^n = x!
<=> n = ln(x!)/ln(2)
On remarque que ln(x!) = ln (x*(x-1)*...*1) = ln(x)+ln(x-1)+...+0 = Somme pour i allant de 1 à x des ln(i). Je note cette somme S(x)
Donc n = S(x)/ln(2)
Pour x = 1 000 000 on a alors n = S(1 000 000)/ln(2)
Cela semble calculable à l'aide d'un algorithme assez simple . J'obtiens n = 18488884.819967285
La plus grande puissance de 2 telle que 2^n inférieur ou égal à 1 000 000! (avec n entier) serait donc 18488884.
Je ne suis pas sur que ce soit tout à fait la démarche attendue, mais cela me semble correct... à moins, bien entendu, qu'une erreur m'ait échappée.
2 De Romain Validire - 09/10/2014, 21:04
C'est exactement la bonne solution ; plus efficace qu'un calcul direct du nombre 1000000!.
Félicitations à Valentin qui remporte le premier point de la saison 2014/2015.