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 29^e point visité sera celui de la fraction 3/2. Et le 20^e 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]

________________

Quelques remarques encore de Nicolas :

> La spirale est effectivement la bonne méthode pour numéroter tous les couples d’entiers relatifs. Mais pour des fractions il suffit de

considérer les couples d’entiers positifs, en faisant éventuellement

précéder le résultat final d’un signe "-" (d'ailleurs dans la suite tu

ne traites implicitement que des fractions positives). Il suffit donc de numéroter un quart du plan, ce qui se fait plus facilement par des diagonales successives (méthode de Cantor) que par une spirale.

> 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 !