MP/MP*: Option Informatique
Devoir à rendre le jeudi 23 février 2006
Deux exercices autour de la numération

Présentation

Le premier exercice s'intéresse au problème d'algorithmique suivant: déterminer les naturels compris entre 1 et n, dont les écritures en bases b et b+1 sont palindromes. On met en œuvre une première méthode, de coût O(n ln(n)); puis une idée simple ramène le coût à un O(sqrt(n) ln(n)).

Le deuxième exercice présente la numération en base p/q, où p et q sont deux naturels premiers entre eux, et tels que p>q.