Problème du Monde résolu en Smalltalk
Friday, October 5th, 2007Un 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′