- Transformer N en binaire, enlever le caractère '1' à gauche
- Initialiser a = 1, b = 0
- Parcourir les caractères c ('0' ou '1' -> 0 ou 1) de la droite vers la gauche
- A chaque étape faire b = b + a*c et a = 3*a - a*c
- Renvoyer 7*a - b
Exemple :
N = 574 s'écrit '1000111110' en binaire, on enlève le '1' à gauche '000111110'
On parcourt les caractères de la droite vers la gauche, c'est-à-dire '0' puis '1' 5 fois et '0' 3 fois
Valeurs successives prises par a, b et c :
Code : Tout sélectionner
a b c
1 0 0
3 0 1
6 3 1
12 9 1
24 21 1
48 45 1
96 93 0
288 93 0
864 93 0
2592 93 -