Un entier s'écrit avec k chiffres 1 et rien d'autre en base b (par…

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

Énoncé

Un entier s'écrit avec $k$ chiffres $1$ et rien d'autre en base $b$ (par exemple $1111111 1_{2}$ , ou $11 1_{16}$ ). Montrer qu'il vaut $\frac{b ^{k} - 1}{b - 1}$ , puis vérifier cette formule sur machine pour toutes les bases de $2$ à $16$ et tous les $k$ de $1$ à $10$ .

Corrigé

La démonstration. Par définition de l'écriture en base $b$ , ce nombre vaut

$i = 0 \sum k - 1 b^{i} = \frac{b ^{k} - 1}{b - 1},$

somme des termes d'une suite géométrique de raison $b \neq = 1$ .

La vérification. On ne vérifie pas un cas : on les vérifie tous, ce qui est précisément ce que la machine sait faire.


def repunit(k, b):
    """Valeur de l'entier écrit avec k chiffres 1 en base b."""
    return (b**k - 1) // (b - 1)

for b in range(2, 17):
    for k in range(1, 11):
        assert depuis_base("1" * k, b) == repunit(k, b)

Aucune assertion ne se déclenche : $150$ cas passent.

Contrôle : $k = 8$ , $b = 2$ donne $255 = 2^{8} - 1$ , le plus grand entier sur un octet — c'est exactement la proposition « capacité de $n$ bits » du cours. Et $k = 3$ , $b = 16$ donne $273$ .