Écrire zeros terminaux(n) , qui renvoie le nombre de zéros terminant…

Représenter les entiers · Écrire un nombre dans une base · niveau 2

Énoncé

Écrire zeros_terminaux(n), qui renvoie le nombre de zéros terminant l'écriture binaire de $n \geq 1$ . Quel renseignement arithmétique ce nombre donne-t-il sur $n$ ? Le vérifier sur machine pour tous les $n$ de $1$ à $4999$ .

Corrigé


def zeros_terminaux(n):
    """Nombre de 0 à la fin de l'écriture binaire de n >= 1."""
    k = 0
    while n % 2 == 0:
        n = n // 2
        k = k + 1
    return k

Ce que ce nombre dit. Terminer par $k$ zéros en base deux, c'est être divisible par $2^{k}$ et pas par $2^{k + 1}$ — exactement comme, en base dix, terminer par $k$ zéros signifie être divisible par $1 0^{k}$ et pas par $1 0^{k + 1}$ . Le $k$ cherché est donc l'exposant de $2$ dans la décomposition de $n$ en facteurs premiers.

La vérification :


for n in range(1, 5000):
    k = zeros_terminaux(n)
    assert n % 2**k == 0 and n % 2**(k + 1) != 0

Contrôle : zeros_terminaux(2026) vaut $1$ ( $2026 = 2 \times 1013$ avec $1013$ impair), et zeros_terminaux(2048) vaut $11$ , puisque $2048 = 2^{11}$ s'écrit 100000000000.

Terminaison : la boucle divise $n$ par $2$ à chaque tour et s'arrête dès que $n$ est impair ; comme $n \geq 1$ , elle s'arrête au plus tard quand $n$ vaut $1$ . Pour $n = 0$ elle ne s'arrêterait jamais : d'où la précondition $n \geq 1$ .