5.3. Arithmétique¶
5.3.1. Décomposition d’un entier dans une base¶
L’écriture d’un entier \(n\in\mathbb{N}^*\) dans une base \(b\) où \(b\) est un entier supérieur ou égal à \(2\) est une écriture de la forme
\[n=\sum_{k=0}^pa_kb^k\]
où les \(a_k\) sont des entiers compris entre \(0\) et \(b-1\) et où \(a_p\neq0\). Par exemple, la décomposition en base \(8\) de \(4621\) est
\[1455= 7\times8^0+5\times8^1+6\times8^2+2\times8^3\]
On peut obtenir la liste \([a_0,a_1,\dots,a_p]\) à l’aide d’une suite de divisions euclidiennes par \(b\). Par exemple,
\[\begin{split}\begin{align*}
1455 &= 7 + 8 \times 181\\
181 &= 5 + 8 \times 22\\
22 &= 6 + 8 \times 2
\end{align*}\end{split}\]
donc
\[1455= 7 + 8 \times (5 + 8 \times (6 + 8 \times 2)) = 7 + 5 \times 8 + 6 \times 8^2 + 2 \times 8^3\]
In [1]: def decomp(n, b):
...: l = []
...: while n != 0:
...: l.append(n % b)
...: n //= b
...: return l
...:
In [2]: decomp(24189, 10 )
Out[2]: [9, 8, 1, 4, 2]
In [3]: n, b = 3678, 7
In [4]: l = decomp(n, b)
In [5]: l
Out[5]: [3, 0, 5, 3, 1]
# On vérifie que la liste convient effectivement
In [6]: sum(a * b ** i for i, a in enumerate(l))