Un ami mathématicien m’a demandé de résoudre un petit problème paru dans la rubrique “Affaire de logique” du journal Le Monde datée du 2 octobre 2007 :
La numération binaire, tout le monde connaît. Elle permet d’écrire les nombres entiers positifs sous forme de sommes de puissances de 2. Mais connaissez-vous le système « binaire moins » ? Eh bien, cela consiste à écrire les entiers sous forme de somme de puissances de (– 2), avec bien sûr, là encore, des exposants tous différents.
Par exemple, 7 s’écrit sous la forme : 7 = 16 – 8 – 2 + 1. Soit, dans ce système : 7 = (– 2)^4 +(– 2)^3 +(– 2)^1+ (– 2)^0
Sauriez-vous écrire 2007 en système « binaire moins » ?
Au fait, tout entier peut-il s’écrire dans ce système ?
J’ai écrit rapidement le programme Smalltalk suivant qui de manière brutale résoud la première question du problème :
l := (1 to:10000) collect:[:i|
|number mult|
number := 0.
mult := 1.
(i radix:2) reverseDo:[:n|
number := n digitValue *mult + number.
mult := mult*(-2).
].
number.
].
l est la liste des 1000 “premiers entiers dans le système binaire moins.
(l indexOf:2007) radix:2.
Je cherche la position de 2007 dans la liste que je convertis en binaire et cela donne :
‘1100000101011′
Jeu de briques
Snake
Pacman
Bubble