Aller au contenu

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⚓︎

Lien dans une autre page

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.