2ⁿ

Plus petite puisance de 2 qui commence par un 7 ? un 9 ? par 100 ? par 1000 ? par 123456789 ?

Appelons de façon générale a le début de 2ⁿ
c'est à dire :
a×10^m ≤ 2ⁿ < (a+1)×10^m
En prenant le logarithme décimal :
log(a) + m ≤ n log(2) < log(a+1) + m, ou encore puisque log(2) > 0 :

log(a) / log(2) + m / log(2) ≤ n < log(a+1) / log(2) + m / log(2) [1]

C'est à dire qu'il faut trouver le plus petit entier qui soit entre des termes de même rang de ces deux progressions arithmétiques.
L'irrationalité de la raison 1 / log(2) ≈ 3.3219280948873... rend le problème "un peu chaotique"...

Donnons a = 7 pour fixer les idées
log(7) / log(2) + m / log(2) ≤ n < log(8) / log(2) + m / log(2)
soit 2.8073 + 3.3219 m ≤ n < 3 + 3.3219 m
A cause du "< 3" strict, la solution m = 0 ne convient bien sûr pas !
L'écart entre ces deux valeurs est constant et égal à d = (log(8) - log(7)) / log(2) ≈ 0.1926
On cherche donc le plus petit m tel que la partie fractionnaire v de log(7) / log(2) + m / log(2) soit v ≤ 1 < v + d ou encore v > 1 - d
Comme 0 ≤ v < 1 par définition, la condition d'égalité sur v ≤ 1 s'écrit en fait v = 0 et finalement :

soit v = frac(log(a) / log(2) + m / log(2)) et d = frac(log(1 + 1/a) / log(2))
v > 1 - d ou v = 0
Cette condition détermine m, on en déduit alors :
n = ceil(log(a) / log(2) + m / log(2))
(le plus petit entier ≥ ...)

On peut représenter cela sur un cercle, avec des angles en tours, c'est à dire faire des calculs "modulo 1".
Considérons donc les multiples de τ = frac(1 / log(2)) ≈ 0.3219
m = 1 : 0.3219...
m = 2 : 0.6438...
m = 3 : 0.9657...
m = 4 : 1.2876... > 1
Mais on peut considérer m = 3 comme un recul de 0.0342
En d'autres termes, chaque fois qu'on ajoute 3 fois τ, on recule de τ₁ ≈ 0.0342 sur notre cadran.
Au départ (m = 0) on est à v = frac(log(7) / log(2)) = 0.8073 = - 0.1926 "modulo 1"
On veut arriver à -d < v ≤ 0, c'est à dire -0.1926 < v ≤ 0.
On n'y est pas, à cause du "< v" strict.
L'avance de τ (m = 1) fait passer à v = +0.1292 > 0
Il faut alors reculer d'autant de fois trois que
0.1292 / 0.0342 = 3.77 soit 4 fois 3 à partir de 1, soit m = 13 arrivant à v = -0.0075 et c'est gagné.
n est alors le plus petit entier ≥ log(7)/log(2) + 13 / log(2) = 45.9924

2⁴⁶ commence par 7

Un calcul direct permet de vérifier que 2⁴⁶ = 70368744177664

a = 9

La même méthode en partant de log(9) / log(2) et log(10) / log(2) donne m = 15 et n = partie entière de log(10) / log(2) + 15 / log(2) = 53.15

2⁵³ commence par 9

en fait 2⁵³ = 9007199254740992

a = 100

La même méthode donne ici aussi la solution : m = 57 et n = 196

2¹⁹⁶ commence par 100...

Le calcul de 2¹⁹⁶ nécessite des moyens de calculs puissants, puisqu'il comporte m + 3 = 60 chiffres !
En une fraction de seconde, un programme adapté donne 2¹⁹⁶ = 100433627766186892221372630771322662657637687111424552206336
On peut se contenter d'un calcul approché avec une calculette : 1.004336277...×10⁵⁹ qui donne largement plus que les 3 chiffres significatifs "100..."

a = 1000

La méthode précédente échoue ici et nous allons étudier la méthode générale sur cet exemple.

log(1000) / log(2) + m / log(2) ≤ n < log(1001) / log(2) + m / log(2)
d = log(1001) / log(2) - log(1000) / log(2) = 0.00144
v = log(1000) / log(2) = 9.96578 = -0.03421 (mod 1)
m = 1 donne -0.03421 + τ = 0.28771 (mod 1)
0.28771 / τ₁ = 8.408... donc 3×9 = 27 de plus, soit m = 28
Mais ici on arrive à -0.020229 (mod 1) < -0.00144
Il faut ici un découpage "plus fin" de notre cadran pour continuer et repartir dans l'autre sens.
Nous avons vu que m = 3 donne un recul de τ₁ ≈ 0.0342
Pour obtenir des précisions meilleures, exprimons 1/log(2) en fractions continues :
1/log(2) = [3,3,9,2,2,4,6,2,1...] et les réduites
3 /1, 10 / 3, 93 / 28, 196 / 59, 485 / 146, 2136 / 643, 13301 / 4004, 28738 / 8651, 42039 / 12655...
Ceci nous donne les "restes"
1 / log(2) = τ = 0.3219280948873626
3 / log(2) = τ₁ = -0.034215715337911234
28 / log(2) = τ₂ = +0.013986656846157075
59 / log(2) = τ₃ = -0.0062424016456077425
146 / log(2) = τ₄ = +0.0015018535549415901
643 / log(2) = τ₅ = -0.00023498742575611686
4004 / log(2) = τ₆ = +0.00009192899960908107
8651 / log(2) = τ₇ = -0.000051129427447449416
12655 / log(2) = τ₈ = +0.000040799575799610466 ...

L'explication théorique est que |1/log(2) - P/Q| < 1/Q² ou encore |Q/log(2) - P| < 1/Q et en passant modulo 1 : |Q/log(2)| < 1/Q
(à condition de définir Q/log(2) modulo 1 entre -0.5 et +0.5, avec Q > 2)
L'erreur τ = Q/log(2) modulo 1 est alors décroissante en valeur absolue, alternativement >0 et <0
Les réduites étant les "meilleures" approximation de 1/log(2), ceci veut dire qu'il n'y a pas de fraction plus simple et plus précise.
Ceci garantit ainsi que le procédé suivant donne la plus petite valeur de m.

Nous en sommes à m = 28 et au point v = -0.020229
Chaque fois qu'on ajoute 28 à m, on avance de τ₂ = +0.013986
(0.020229 - 0.00144) / 0.013986 = 1.34 ajoute encore 2×28 et donne m = 84 et la position +0.00774
On poursuit ainsi successivement avec les restes partiels et les dénominateurs des réduites de 1/log(2) :
0.00774 / 0.006242 = 1.24 soit 2×59 de plus, m = 202 et -0.00474
(0.00474 - 0.00144) / 0.0015018 = 2.197 et 3×146 de plus, soit m = 640 et la position -0.00023,
enfin dans les limites cherchées et donc m = 640 et n = ceil((log(1000)+640)/log(2)) = 2136.

2²¹³⁶ commence par 1000...

Juste pour le fun, les m+4 = 644 chiffres de 2²¹³⁶ :
2²¹³⁶ = 10 001 628 941 376 155 308 880 915 246 104 270 298 810 685 162 565 506 437 939 608 978 762 397 229 766 722 098 208 242 223 894 114 313 837 158 249 014 168 629 715 364 097 724 368 650 073 378 194 388 688 404 077 175 390 045 633 771 984 867 595 072 456 337 463 316 463 909 268 799 585 391 503 973 045 508 316 373 223 223 926 155 308 741 239 141 068 960 122 710 921 665 929 557 901 631 961 640 497 025 361 442 178 706 587 502 469 190 798 252 768 106 649 374 801 279 503 181 281 565 946 703 422 435 165 833 819 633 365 433 393 564 466 380 840 063 545 050 741 040 787 043 182 442 816 711 050 464 968 675 767 779 353 162 682 580 231 080 796 536 117 757 639 648 256 288 003 445 725 534 239 759 248 144 219 561 002 275 344 111 063 984 773 298 801 161 511 901 735 311 083 095 286 192 300 009 093 315 064 989 366 771 214 296 182 148 631 829 229 883 439 596 475 252 736
Bien entendu, on n'a besoin que des 4 premiers chiffres significatifs et la calculette suffit à vérifier que 2²¹³⁶ ≈ 1.00016289...×10⁶⁴³

Tous ces calculs avec la décomposition en fraction continue de 1/log(2) nous ont permis d'obtenir le résultat avec "quelques" divisions seulement (sans avoir besoin de boucler sur les 640 valeurs de m comme avec un programme par force brute) et une simple calculette.
On peut ainsi programmer la méthode précédente pour chercher de façon efficace la plus petite puissance de 2 qui commence par 123456789.
Le script suivant effectue le calcul pour n'importe quelle valeur de a (raisonnable, car les calculs sont fait en Javascript, donc avec une précision limitée).

Les restes τ_i sont ramenés "modulo 1" entre -0.5 et +0.5
Soit v la valeur courante = frac((log(a) + m) / log(2)), 0≤ v < 1
Soit Q le dénominateur de la réduite, et τ = Q/log(2) modulo 1 le reste courant signé. -0.5 < τ < +0.5
   si τ > 0, v≠0 et v + d ≤ 1 : m est augmenté de Q×(floor((1 - v - d) / τ) + 1)
   si τ < 0, v≠0 et v + d ≤ 1 : m est augmenté de Q×(floor(v / |τ|) + 1)
   si v = 0 ou v < 1 < v + d, c'est fini, sinon on prend le terme suivant de la fraction continue.
Nota : floor(x) + 1 est non pas ceil(x) car si x = 0, on veut ajouter 1.

En prime la base (ici 2) est au choix dans ce script, tout ce qui précéde étant immédiatement adaptable avec log(base) au lieu de log(2).

Précision

Avec ces nombres "astronomiques" on atteint très vite les limites de précision du Javascript, ce qui donne des résultats aberrants.
La précision requise est de l'ordre de (log(a+1) - log(a)) / log(2), soit de l'ordre de log(1 + 1/a) / log(2) ≈ 1.5 / a.
Ainsi avec 15 chiffres significatifs, on est limité à a ≈ 10¹⁵
Pour se garder une marge, disons une douzaine de chiffres maximum pour a.
Toutefois, tout dépend de la valeur de a !
Par exemple a = 184467440 correspond aux premiers chiffres de 2⁶⁴ = 18446744073709551616 et la précision est largement suffisante, le dernier τ étant τ₂ ≈ 0.01399 !
a = 98765432 pourtant inférieur dépasse la précision des calculs, la dernière valeur de τ étant 0.0 (sic, log(2) est irrationnel ! )
a = 123456789 est OK et donne le résultat cherché 2^62759188 ≈ 1234567891438... (nombre à 18892399 chiffres)
Nous allons toutefois jeter un doute sur le calcul en Javascript de cette valeur...

Lors de la décomposition de 1/log(2) en fraction continue, avec les réduites P/Q, la précision est dépassée quand 1/Q² devient < 10^-16, ou ce qui revient au même τ = 0.
On peut aussi dépasser la précision de calcul dans le test "v = 0". Si v est en fait > 0, l'algoritme s'arrête prématurément.

Notons aussi que le calcul direct et l'affichage des premiers chiffres de 2ⁿ, n grand, est impossible car les nombres représentables sont < 10³⁰⁸ (2¹⁰²⁴) environ en virgule flottante "standard" utilisée ici.
On le divise alors par 10^m+m'-1, m' = nombre de chiffres de a, pour se ramener à un nombre inférieur à 10 et afficher l'exposant de 10 à part.
Les logarithmes en Javascript étant en natif les logarithmes néperiens (ln), on peut écrire :
2ⁿ = exp(n ln(2) - (m + m' - 1)ln(10)) × 10^{m + m' - 1}
Si n < 50, le calcul de 2ⁿ est exact et le nombre entier correspondant est affiché directement.
Sinon, on applique la formule précédente.

Estimons la précision de ce calcul, c'est à dire le nombre de chiffres exact qu'il fournit.
Le calcul des ln( ) étant estimé à 10^-16 près, le calcul de la différence est entaché d'une erreur n fois plus importante et donc avec 16 - log(n) chiffres exacts seulement. Ainsi avec a = 123456789, n = 62759188, on n'a plus que 16 - 8 = 8 chiffres exacts !
En fait les erreurs se compensent (différence) et la précision effective est meilleure. Il n'empêche...

Le script suivant estime la précision de ce calcul en ajoutant et retranchant des erreurs volontaires ε sur ln(2) et ln(10) :

On voit ainsi que ε = 10^-16 correspond bien à la précision du Javascript, et que ... la valeur affichée est fantaisiste puisque la seule chose qu'on peut affirmer est 12345678822... < 2ⁿ < 12345679006...
Le dernier "89" de 123456789 n'est même pas garanti !

Le même calcul effectué à la main avec la calculette de Windows et ε = 10^-25 donne

123456789991991542... < 2^62759188 < 123456789991991544...

On peut donc garantir les chiffres suivants 99199154... (Javascript prétendait 14383997)