Fractions —> entiers
Son nom même l’indique : l’Encyclopédie
en ligne des suites de nombres entiers de Neil Sloane ne contient pas
de nombres décimaux. Il y a pourtant moyen d’y introduire des fractions par une
voie détournée. Voici trois techniques relativement simples qui permettent de transformer
un quotient n/d (numérateur/dénominateur) en entier k
unique.
La première consiste à dénombrer toutes
les fractions et à leur associer un nombre entier k propre. Voici, par
exemple, comment associer 29 à la fraction 3/2.
On se munit d’un repère du plan où les
numérateurs sont portés en abscisse et les dénominateurs en ordonnée. Ainsi n
= 3 et d = 2 formeront-ils un point dans le premier quadrant. Donner une
adresse unique à ce point est simple : on utilise une spirale carrée qui
part de (0,0), tourne autour d’elle-même et visite un à un tous les points de coordonnées
entières. Le 29e point visité sera celui de la fraction 3/2. Et le 20e sera, par exemple, celui qui correspond à la fraction -2/-2 (illustration #1).
Illustration #1
La deuxième technique consiste à écrire n
et d à la suite l’un de l’autre en les séparant par deux zéros. On remplace
ensuite tous les 0 de n et d par 01 (sans toucher
au double zéro de la « soudure »). Le nombre k obtenu est
unique et permet facilement de retrouver la fraction de départ (on remplacera
tous les 01 de k par 0, puis on effacera la soudure 00).
Illustration #2
n = 101013450
et d = 678009.
On soude (en jaune ici) n et d
pour former 10101345000678009.
On remplace ensuite tous les zéros par 01 (sans
toucher à la soudure) et on obtient k :
k = 1011011345010067801019.
L’opération inverse redonnera n et d
sans ambiguïté.
Une troisième méthode consiste à entrelacer
les chiffres de n et d pour former k. Si le nombre de
chiffres de k est pair alors le numérateur est formé des chiffres qui occupent les rangs pairs de k ; si le nombre de chiffres de k est
impair alors le numérateur est formé des chiffres qui occupent les rangs impairs de k
(on effacera les 0 initiaux éventuels affectant n ou d).
Illustration #3
Transformer n/d = efghi/WXYZ en k :
9 chiffres
en tout (9 est impair), n est plus long que d : on fait k
= eWfXgYhZi (le numérateur efghi se lit aux rangs impairs de k).
Transformer n/d = abc/WXYZ en k :
7 chiffres
en tout, mais comme n est plus court que d, on ajoute un 0 devant
abc pour arriver à 8 chiffres (8 est pair) ; on fait
ensuite k = W0XaYbZc (le numérateur 0abc se lit aux rangs pairs de k, devenant abc).
Transformer n/d = abc/XYZ en k :
6 chiffres
en tout (6 est pair), n aussi long que d : on fait k
= XaYbZc (le numérateur abc se lit aux rangs pairs de k).
Transformer n/d = ab/WXYZ
en k :
6 chiffres
en tout (6 est pair), on fait k = W0X0YaZb (le numérateur 00ab se lit aux rangs pairs
de k, devenant ab).
Transformer n/d = abcd/YZ en k :
6 chiffres
en tout, mais comme n est plus long que d, on ajoute un 0 devant YZ
pour arriver à 7 chiffres (7 est impair) ; on fait ensuite k
= a0bYcZd (le numérateur abcd se lit aux rangs impairs de k et le dénominateur 0YZ
devientt YZ).
__________________________________
[Merci à Nicolas Graner pour son aide]
> Petit détail de rédaction : plutôt que de coller les deux nombres par
00 puis de remplacer les 0 par 01 « sans toucher à la soudure », il me
paraît plus simple de remplacer 0 par 01 dans chacun des deux nombres
puis de les coller par 00. C'est la même chose mais ça évite
d’introduire un cas particulier pour certains 0.
> Ton histoire de pair/impair me paraît bien compliquée. Je trouverais
plus simple de ramener numérateur et dénominateur à la même longueur en
ajoutant des 0 initiaux au plus court des deux, puis de les entrelacer
en commençant toujours par le numérateur. Si tu ne veux pas de 0
initiaux dans le résultat final, il suffit d’ajouter systématiquement un
1 en tête : ab + WXYZ -> 10W0XaYbZ. D’ailleurs, dans ce cas, au lieu
d’intercaler on peut aussi bien concaténer : ab + WXYZ -> 100abWXYZ.
Le codage et le décodage sont beaucoup plus simples à décrire qu’avec ta
méthode.
Il est vrai que ta méthode peut économiser un ou deux chiffres par
rapport à celle-ci, mais du moment qu’on accepte le principe d’ajouter
des 0 initiaux pour équilibrer les deux nombres, on n’est plus à un
chiffre près.
____________________
EA:
Merci Nicolas !
Commentaires
Enregistrer un commentaire