On voudrait remplacer nb bits(n) par floor(log2(n)) + 1 , qui semble…

Sur les petites valeurs, les deux coïncident : la boucle de nb_bits et len(vers_base(n, 2)) donnent le même résultat pour tous les $n$ testés.

L'échec. math.log2 calcule en flottant, sur un nombre fixe de bits de mantisse. Pour $n=2^{49}-1$, l'arrondi rend $49,0$ tout rond, au lieu d'une valeur légèrement inférieure à $49$ :

import math
n = 2**49 - 1
print(math.log2(n))                    # 49.0
print(math.floor(math.log2(n)) + 1)    # 50  -> FAUX
print(nb_bits(n))                      # 49  -> juste

Le plus petit contre-exemple de cette forme est $k=49$.

Ce qu'il faut en retenir. nb_bits n'emploie que des divisions entières : elle est exacte pour tout $n$, aussi grand soit-il. La formule logarithmique passe par les flottants, et les flottants approchent — c'est le sujet du chapitre suivant. Une fonction exacte et lente vaut mieux qu'une fonction rapide et fausse.

Piège : tester sur mille petites valeurs et conclure que c'est correct. Un jeu de tests ne prouve rien s'il ne contient pas les cas limites (chapitre 3).