Cantorisation

 

Appelons période le bloc de décimales d’un nombre rationnel qui se répète à l’infini juste après la virgule. Ainsi la fraction F = 26/37 (qui vaut 0,702702702…) a-t-elle 702 pour période. En revanche la fraction 13/6 = 2,16666666... ne nous intéresse pas car le 1 après la virgule ne revient jamais.

Nous avons le projet de faire entrer dans l’OEIS de Neil Sloane et Simon Plouffe une suite de nombres entiers positifs a(n), tous distincts, où a(n) code à la Cantor la plus petite fraction F de période n.

Nous nous sommes inspirés du célèbre mathématicien diagonal pour transformer sans ambiguïté deux nombres x et y en un seul ; il suffit d’alterner de manière ad hoc les chiffres de x et de y. Voici comment coder une fraction F = x/y.

Trois cas peuvent se présenter (selon la longueur de x et y – longueur vue ici comme quantité de chiffres de x et y) :

1) x est plus court que y ;

2) x est de même longueur que y ;

3) x est plus long que y.

1) x plus court que y

Nous formons une chaîne de caractères ayant un nombre PAIR de caractères, en commençant par y ; cette chaîne se décomposera facilement en x et y car x aura obligatoirement un (ou des) leading zero(s) que nous effacerons.

Pour F = 129/4587 par exemple, on a x = 129 et y = 4567 : on forme 40518279 [qui se décompose en 4587 et 0129] ; la sous-chaîne qui commence par des leading zeros (à effacer) donne x (0129 devient 129) et l’autre y.

2) x de même longueur que y

Nous formons une chaîne de caractères ayant un nombre PAIR de caractères, en commençant par y ; y est la première des deux sous-chaînes intriquées et x l’autre.

Pour F = 1299/4587 par exemple, on a x = 1299 et y = 4587 : on forme 41528979.

3) x plus long que y

Nous formons ici une chaîne de caractères ayant un nombre IMPAIR de caractères ; la sous-chaîne la plus longue vaudra x, l’autre y (avec ou sans leading zeros).

Pour F = 1299333/4587 par exemple on a x = 1299333 et y = 4587 : on forme 1020949538373 [le nombre de chiffres étant IMPAIR, le plus long des intriqués est x, l’autre y (donné ici par 004587, donc 4587 après purge des leading zeros)].

Ainsi, quand on lit une chaîne, comptera-t-on d’abord le nombre de chiffres qu’elle contient ; c’est la convention bleue :

Chaîne IMPAIRE ?

... alors la plus longue des deux sous-chaînes est x (omettre les leading zeros éventuels de y)

Chaîne PAIRE ?

... alors la deuxième des sous-chaînes est x (purgée éventuellement de ses leading zeros) et l’autre est y.

Quelques exemples de chaînes paires :

  91 se lit  1/9  = 0,11111111...  n =  1 (c’est la période codée par 91)
  92 se lit  2/9  = 0,22222222...  n =  2 (c’est la période codée par 92)
3034 se lit  4/33 = 0,12121212...  n = 12 (c’est la période codée par 3034)
9193 se lit 13/99 = 0,13131313...  n = 13 (...)
9194 se lit 14/99 = 0,14141414...  n = 14
3035 se lit  5/33 = 0,15151515...  n = 15
9196 se lit 16/99 = 0,16161616...  n = 16
9197 se lit 17/99 = 0,17171717...  n = 17
1012 se lit  2/11 = 0,18181818...  n = 18
9199 se lit 19/99 = 0,19191919...  n = 19
9290 se lit 20/99 = 0,20202020,..  n = 20
3037 se lit  7/33 = 0,21212121...  n = 21

Remarque grise #1  :

Si 91 code 0,11111111… comment codera-t-on la période 11 ? Et la période 111 ? Et la période 1111 par exemple ? Adoptons la convention grise, en plus de la convention bleue que nous venons de voir :

La longueur de la période est donnée par le nombre avant la virgule, augmenté de 1.

la période 1 est donnée par 91 qui se lit 1/9 = 0,11111111...
la période 11 est donnée par 190 (long. imp.) qui se lit 10/9 = 1,11111111...
la période 111 est donnée par 199 qui se lit 19/9 = 2,11111111...
la période 1111 est donnée par 298 qui se lit 28/9 = 3,11111111...
la période 11111 est donnée par 397 qui se lit 37/9 = 4,11111111...
etc.

Remarque rouge #2  :

Les périodes 9, 99, 999, … exigent une dernière convention – rouge  : toute fraction de  dénominateur 1  renvoie à une période exclusivement composée de 9. [On sait en effet que tout nombre entier n admet deux écritures : n et (n-1),99999999...]

Nous décidons donc de représenter la période 9 par 11  ; ce 11 se lit 1/1 (dénominateur 1), fraction qui vaut bien 0,9999999…

Quant à la longueur de la période, elle est toujours fixée par la convention verte (c’est le nombre avant la virgule, augmenté de 1).

la période 9 est donnée par 11 qui se lit 1/1 = 0,99999999...
la période 99 est donnée par 12 qui se lit 2/1 = 1,99999999...
la période 999 est donnée par 13 qui se lit 3/1 = 2,99999999...
la période 9999 est donnée par 14 qui se lit 4/1 = 3,99999999...
la période 99999 est donnée par 15 qui se lit 5/1 = 4, 999999999...
etc.

Le tableau ci-dessous (dû aux calculs de Carole D.) reprend le codage des 36 premières valeurs de n :

  91 se lit  1/9  = 0,11111111...  n =  1 (c’est la période codée par 91)
  92 se lit  2/9  = 0,22222222...  n =  2 (2 est la période codée par 92)
  31 se lit  1/3  = 0,33333333...  n =  3 (3 est la période codée par 31)
  94 se lit  4/9  = 0,44444444...  n =  4 (...)
  95 se lit  5/9  = 0,55555555...  n =  5
  32 se lit  2/3  = 0,66666666...  n =  6
  97 se lit  7/9  = 0,77777777...  n =  7
  98 se lit  8/9  = 0,88888888...  n =  8
  11 se lit  1/1  = 0,99999999...  n =  9
9190 se lit 10/99 = 0,10101010,..  n = 10
 190 se lit 10/9  = 1,11111111...  n = 11 (11 est la période codée par 190)
3034 se lit  4/33 = 0,12121212...  n = 12 (12 est la période codée par 3034)
9193 se lit 13/99 = 0,13131313...  n = 13 (...)
9194 se lit 14/99 = 0,14141414...  n = 14
3035 se lit  5/33 = 0,15151515...  n = 15
9196 se lit 16/99 = 0,16161616...  n = 16
9197 se lit 17/99 = 0,17171717...  n = 17
1012 se lit  2/11 = 0,18181818...  n = 18
9199 se lit 19/99 = 0,19191919...  n = 19
9290 se lit 20/99 = 0,20202020,..  n = 20
3037 se lit  7/33 = 0,21212121...  n = 21
 191 se lit 11/9  = 1,22222222...  n = 22 (22 est la période codée par 191)
9293 se lit 23/99 = 0,23232323...  n = 23 (23 est codé par 9293)
3038 se lit  8/33 = 0,24242424...  n = 24 (...)
9295 se lit 25/99 = 0,25252525...  n = 25
9296 se lit 26/99 = 0,26262626...  n = 26
1013 se lit  3/11 = 0,27272727...  n = 27
9298 se lit 28/99 = 0,28282828...  n = 28
9299 se lit 29/99 = 0,29292929...  n = 29
3130 se lit 10/33 = 0,30303030,..  n = 30
9391 se lit 31/99 = 0,31313131...  n = 31
9392 se lit 32/99 = 0,32323232...  n = 32
  34 se lit  4/3  = 1,33333333...  n = 33 (33 est la période codée par 34)
9394 se lit 34/99 = 0,34343434...  n = 34 (34 est codé par 9394)
9395 se lit 35/99 = 0,35353535...  n = 35 (...)
1014 se lit  4/11 = 0,36363636...  n = 36
...

Tous les termes de S sont maintenant distincts et déterminent sans ambiguïté la plus petite fraction (distincte de celles qui précèdent) dont la période correspond à n ; voici le début de S :

S = 91, 92, 31, 94, 95, 32, 97, 98, 11, 9190, 190, 3034, 9193, 9194, 3035, 9196, 9197, 1012, 9199, 9290, 3037, 191, 9293, 3038, 9295, 9296, 1013, 9298, 9299, 3130, 9391, 9392, 34, 9394, 9395, 1014, …

Merci à CGaeroorlge (Carole & Georg) !