Dichotomie⚓︎
Un exemple⚓︎
>>> 2**(2**12) + 1 >= 10**1200
True
>>> 2**(2**12) + 1 >= 10**1300
False
Explications
- \(F_{12} = 2^{2^{12}} + 1\) est un nombre très grand.
- \(2^{10} = 1024 > 1000 = 10^3\), on déduit que
- \(2^{12} = 2^2 × 2^{10} > 4×1000\), et que
- \(F_{12} > 2^{4000} = 2^{10×400} = (2^{10})^{400} > (10^3)^{400} = 10^{1200}\)
Ceci explique le test 2**(2**12) + 1 >= 10**1200
qui renvoie True
.
Le test suivant est simplement choisi au hasard.
- On déduit que \(F_{12}\) possède de \(1201\) à \(1300\) chiffres.
- Par exemple si \(10^3 \leqslant n \lt 10^4\), alors \(n\) a \(4\) chiffres, et réciproquement.
- Pour tous les entiers \(n<1200\), on aura \(F_{12} \geqslant 10^n\)
- Pour tous les entiers \(n>1300\), on aura \(F_{12} \lt 10^n\)
Principe de la dichotomie
Définition
Dichotomie : principe de partager en deux.
Pour trouver un encadrement plus fin, on choisit le milieu entre \(1200\) et \(1300\), et on recommence... Ici, on ne travaille qu'avec des entiers, à la fin on se retrouve avec deux entiers consécutifs.
Exercice⚓︎
Indice, puis solution
- Si \(F_{12} < 10^{1250}\),
- alors on cherche entre \(1200\) et \(1250\).
- Sinon on cherche entre \(1250\) et \(1300\).
- Et on recommence.
Solution
>>> F(12) < 10**1200
False
>>> F(12) < 10**1300
True
>>> F(12) < 10**1250
True
>>> F(12) < 10**1225
False
>>> F(12) < 10**1237
True
>>> F(12) < 10**1231
False
>>> F(12) < 10**1234
True
>>> F(12) < 10**1232
False
>>> F(12) < 10**1233
False
L'entier cherché est 1234, trouvé en peu d'étapes.
Il s'agit du nombre de chiffre de \(F_{12}\).
Défi 💥
Encadrer \(F_{12}\) entre deux nombres de Mersenne consécutifs.