Écrire une fonction addition base(s, t, b) qui additionne deux…

On aligne les deux écritures à la même longueur en complétant à gauche par des zéros — l'ajout d'un zéro de poids fort ne change pas la valeur — puis on parcourt les positions de droite à gauche en propageant la retenue.

def addition_base(s, t, b):
    """Somme de deux écritures en base b, rendue en base b.

    Précondition : s et t ne contiennent que des chiffres
    valides en base b (donc d'indice < b dans CHIFFRES).
    """
    n = max(len(s), len(t))
    s = s.rjust(n, "0")
    t = t.rjust(n, "0")
    res = ""
    retenue = 0
    for i in range(n - 1, -1, -1):
        somme = CHIFFRES.index(s[i]) + CHIFFRES.index(t[i]) + retenue
        res = CHIFFRES[somme % b] + res
        retenue = somme // b
    if retenue > 0:
        res = CHIFFRES[retenue] + res
    return res

L'invariant. Après avoir traité les positions $i$ à $n-1$, la chaîne res contient l'écriture des chiffres de poids faible de la somme, et retenue vaut $0$ ou $1$ : c'est ce qui « déborde » vers la position suivante. La retenue reste toujours inférieure à $b$ car $2(b-1)+1<2b$, donc $\lfloor \text{somme}/b\rfloor \le 1$.

La validation.

for b in range(2, 17):
    for x in range(0, 60):
        for y in range(0, 60):
            got = addition_base(vers_base(x, b), vers_base(y, b), b)
            assert depuis_base(got, b) == x + y

$54000$ cas passent. Exemples : addition_base("1101", "111", 2) rend "10100" ($13+7=20$), et addition_base("7EA", "1F", 16) rend "809" ($2026+31=2057$).

Piège : oublier la dernière ligne. Si la retenue finale est non nulle et qu'on ne l'écrit pas, le résultat est faux d'exactement $b^n$ — et il est faux silencieusement.