Mathématice, intégration des Tice dans l'enseignement des mathématiques  
Sommaire > N°54 - En cours d’élaboration - Les nouveautés de MathémaTICE > La conjecture de Collatz et ses effets de (...)

La conjecture de Collatz et ses effets de bord
Ce qu’un problème ouvert peut apporter aux mathématiques
Moteur de recherche
Mis en ligne le 10 février 2017, par Alain Busser, Patrice Debrabant

La conjecture de Collatz est un petit problème amusant qui a tenu en haleine plusieurs générations de mathématiciens.
L’un d’eux, Shizuo Kakutani, en vint à subodorer que c’était une arme fatale inventée par le KGB pour paralyser la recherche américaine !

La Science pouvait être le jouet du jouet, mais ce serait sans compter sur les vertus érotiques du ludique inutile : la recherche sur cette conjecture, par des "effets de bord", a produit des applications inattendues à ce problème supposé sans application ; parmi elles, on verra ici des jeux combinatoires ainsi qu’un langage de programmation.

Avant-dernier rebondissement : en 2016, une équipe belge dit avoir prouvé la conjecture.

Dernier rebondissement : c’était une histoire belge, la "preuve" est devenue une "quantification du degré" dans le titre...

Article placé sous licence CC-by-SA : http://creativecommons.org/licenses/by-sa/3.0/fr/legalcode

La conjecture

Dans les années 1930, Lothar Collatz étudiait l’application des graphes à la théorie des nombres, en représentant par des graphes les itérées de fonctions de N dans N, en particulier celle définie par ces remarques :

  • si un nombre n est divisible par 3, ses deux tiers sont un nombre entier 2n/3 ;
  • si un nombre n est congru à 1 modulo 3, (4n-1)/3 est encore entier ;
  • si n est congru à 2, c’est (4n+1)/3 qui est entier.

Alors cette fonction est une bijection sur N, c’est-à-dire une permutation des entiers naturels. Elle commence par (0 1 3 2 5 7 4 9 11 6...). Or on sait que l’étude des permutations bénéficie de celle de ses cycles : Ici, 5 va sur 7 qui va sur 9 qui va sur 6 qui va sur 4 qui va sur 5 qui retourne à 7 : Est-ce que tous les entiers font partie d’un cycle fini de ce genre ?

Et la réponse est...

La réponse est non.
1 va sur 1.
2 va sur 3 qui retourne sur 2.

Mais voyons comment ça se passe pour l’orbite de 8.
On peut écrire un petit programme avec CaRMetal :

8 va sur 11 qui va sur 15 qui va sur 10 qui va sur 13 qui va sur 17...

Manifestement, 8 a quitté l’orbite terrestre.

CarMetal - 890 octets

Ce problème a amené Collatz à itérer toutes sortes de fonctions de N dans N similaires à celle-ci (mais non nécessairement bijectives), dont la variante suggérée par ces remarques :

  • Si n est pair, n/2 est un entier ;
  • Sinon c’est (3n+1)/2 qui est entier.

Il semblerait que Collatz ait découvert en 1937, que le cycle (1-2) soit souvent le stade final de cette suite. C’est la conjecture à laquelle cet article est dédié.

L’algorithme de Collatz en Sofus

J’aimerais tant voir Syracuse

L’un des collègues de Collatz, Helmut Hasse, fit connaître la conjecture de Collatz, en particulier lors d’une conférence à l’université de Syracuse, ce qui explique que souvent la suite de Collatz soit appelée algorithme de Hasse ou de Syracuse, et la conjecture soit appelée conjecture de Syracuse.

La conjecture dans tous ses états

Il existe plusieurs variantes équivalentes de la conjecture de Collatz, dont celle dite "3x+1" où on ne divise pas 3n+1 par 2. C’est cette variante qu’il décrit dans cette lettre à Mays rédigée en 1980, soit, selon lui, une cinquantaine d’années après sa découverte :

Sofus permet de facilement décrire le problème : Si on triple un nombre impair, on a encore un nombre impair, mais en ajoutant 1, on obtient un nombre pair ; l’algorithme suivant ne donne donc que des nombres entiers :

L’instruction du début a pour effet d’effacer le cadre de sortie numérique de Sofus, afin de permettre d’y placer de nouvelles sorties à la place. D’où son nom de palimpseste, en référence à cette antique coutume datant de l’époque où on écrivait sur du parchemin...

Pour explorer numériquement cette suite, on peut utiliser ce laboratoire en DGPad ou la version R et pour les courageux qui cherchent avant tout la performance, la version bash (voir aussi plus bas). Pour de la manipulation directe, la technique exposée dans cet article permet d’utiliser le tableur (onglet "Basic"). Et on obtient le genre de fichier que voici (actionner le curseur pour voir l’effet) :

OpenDocument Spreadsheet - 46.3 ko

Le jeu d’Isbell

John Isbell a inventé un jeu basé sur la suite de Collatz, basé sur les résultats suivants, eux-mêmes issus de recherches destinées à prouver la conjecture :
Il remarque qu’au lieu d’utiliser 3x+1 on peut utiliser 3x-1, avec un phénomène similaire (3x-1 est de même parité que 3x+1).

Le choix entre 3x+1 et 3x-1 peut être assimilé à un tour de jeu, et Isbell a un jeu combinatoire à deux joueurs, qu’il a appelé "beanstalk" (gousse de haricot) parce que les deux joueurs s’appellent, selon lui, Jack et le géant (inspiré par Jack et le haricot magique. Voici la règle du jeu (à jouerétudier de préférence en cycle 3) :

  • un des joueurs choisit un nombre entier non nul.
  • ensuite, chacun son tour le divise par 2 si c’est possible, sinon, choisit entre 3x+1 et 3x-1, à appliquer au nombre ;
  • le premier arrivé à 1 a gagné.

Ce jeu est intéressant à expérimenter parce qu’on perçoit vite la nécessité de modifier les règles (par exemple choisir 4 fait gagner à coup sûr : On peut par exemple interdire les puissances de 2 comme choix initial). Une amélioration du jeu beanstalk d’Isbell est beans don’t talk de John Horton Conway, où la division par 2 est effectuée systématiquement après chaque tour de jeu, jusqu’à ce que le résultat soit impair. On peut y jouer en ligne avec le fichier ci-dessous :

HTML - 2.4 ko

L’idée de Conway est intéressante : Diviser par 2 autant que possible pour n’avoir que des nombres impairs. Par exemple, la suite classique, en partant de 17, donne ceci :

indices 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
termes 17 52 26 13 40 20 10 5 16 8 4 2 1 4 2 1 4 2 1 4 2

alors que la version Conway avec seulement des nombres impairs, donne

indices 0 1 2 3 4
termes 17 13 5 1 1

c’est quand même nettement plus court !

En terme d’algorithme, cela revient à utiliser une variante d’algorithme qui produit une suite "concentrée" (mais qui a le même goût ou la même nature).

Si l’on veut étudier toutes les parties possibles dans le jeu d’Isbell (ou de Conway), on peut envisager une version non déterministe de la suite (dans le cas d’imparité, le terme suivant peut être 3x-1 ou 3x+1) et se demander si la conjecture semble encore vérifiée.

Ou alors écrivons un petit programme CaRMetal (ci-dessous) pour déterminer l’ensemble des valeurs possibles au rang n (pour une valeur initiale donnée).
Quand on part d’une puissance de 2, par exemple 8, pas de surprise : c’est la remarque que dans le jeu il faut interdire les puissances de 2 comme choix initial.

Mais y a-t-il des parties interminables ?

Mais si on part de 3, ça se gâte...

Pour que ce soit plus clair, on peut afficher toutes les valeurs atteintes depuis le départ (pour trier on a utilisé la fonction sort en Javascript).

CarMetal - 1 ko

Quand on part de 3, apparemment on obtient tous les nombres sauf les multiples de 3 (hormis 3 évidemment) :

Essayer de démontrer la conjecture : le mur arithmétique...

On va maintenant "creuser" un peu la conjecture (et s’y casser les dents...).

La conjecture est que, quelle que soit la valeur initiale, la suite des itérés finit toujours par entrer dans le cycle (1 - 2), autrement dit qu’il n’existe pas :
- de suite qui diverge à l’infini ;
- de suite qui entre dans un autre cycle.

Un argument naïf, de nature probabiliste, tend à indiquer que la suite ne peut pas diverger. En effet, on diminue davantage en divisant par 2 qu’en multipliant par 3/2 (ou un chouïa de plus), l’effet cumulé étant de multiplier par 3/4.
Donc au bout d’un certain temps on diminue... moyennant l’hypothèse qu’à l’infini la suite atteint une fois sur deux un nombre pair.

Mais cela ne constitue pas une démonstration.
Et on notera qu’un argument du même type (bien que plus difficile à énoncer) tend à indiquer l’existence d’un autre cycle. Et si la conjecture était fausse ?... C’est difficile à imaginer car d’autres l’ont envisagé et lancé des ordinateurs à l’assaut. Jusqu’à $10^{20}$ la conjecture est vérifiée par la force brute... Et la finesse a du mal à s’exprimer au delà de $10^{20}$. [1]

Pour poursuivre l’étude, on va modifier le point de vue et "aller à l’envers". On obtient à nouveau une suite non déterministe [2].

Tous les nombres impairs sont atteints. La question devient alors de savoir si tout nombre peut être visité par un chemin partant de 1.

La fonction réciproque de la fonction $\dfrac{3x+1}{2}$ est la fonction $\dfrac{2x-1}{3}$.
$\dfrac{2x-1}{3}$ est entier si et seulement si $2x≡1$ [modulo 3], donc si et seulement si $x≡2$ [modulo 3].

On débouche sur un problème de graphe orienté, qui semble assez simple à résoudre. Qui semble...

Ecrivons un petit programme qui détermine les nombres atteints à chaque rang :

CarMetal - 1 ko

On obtient :

Intéressons aux nombres "difficiles à atteindre", à savoir ceux pas atteints et qui sont inférieurs au maximum atteint.

CarMetal - 1.1 ko


... puis au premier d’entre eux :

CarMetal - 1.1 ko

On a une vedette : 27. Il truste (il trumpe ?) le podium jusqu’à l’étape 69.

Essayons de représenter graphiquement le comportement de la suite pour u0 = 27. La première idée qui vient est d’utiliser la traditionnelle représentation graphique avec la bissectrice comme on le fait au lycée pour illustrer la convergence.
Pour cela, on peut utiliser la tortue de CaRMetal.

CarMetal - 1.6 ko

Par comparaison, voici ce que l’on obtient pour 26 :

Mais cette représentation graphique n’est pas très parlante, on va lui préférer une représentation où l’axe des x est l’axe des temps.

On dit que le temps de vol de 27 est 72.
Pourquoi cette métaphore ?
Parce qu’il est naturel de considérer que la division par 2 est une descente, et que $\dfrac{3x+1}{2}$ est une montée. Tout se passe comme si le nombre était soumis à des courants ascendant et descendant, et finissait par retomber au "sol" (les niveaux 1-2).
C’est cette idée que l’on va utiliser pour une nouvelle représentation graphique :

CarMetal - 1.6 ko

D’autres profils (temps de vol longs)





On retrouve le profil de 27, car on entre dans le même courant d’air.


Mais pour 703, ce n’est pas le cas.



On voit que les profils sont variés, et difficilement prévisibles a priori.
Mais on peut noter que le temps de vol maximal n’augmente pas très vite.

Intéressons-nous aux zones de courant ascensionnel :

Pour que la suite croisse, le terme courant doit être de la forme $2u-1$ et on obtient alors $3u-1$.

  • Par conséquent, pour que la suite augmente k fois de suite, il faut que le terme courant soit de la forme $2^k.P-1$ avec P premier avec 2, et on obtient alors $3^k.P-1$.
  • Les zones de courant ascensionnel sont les zones $2^k.P-1$

Et de façon évidente, les zones de courant descendant sont les zones $2^k.P$.

A 1 près, on est aspiré vers le haut ou vers le bas. Mais si on est aspiré vers le bas, la chute est plus vertigineuse.

Ce passage de $2^k.P$ à $3^k.P$ est caractéristique d’un langage de programmation pour le moins exotique développé par Conway, le Fractran, que nous présenterons plus loin.

Négativons un peu

L’algorithme de Collatz peut également être appliqué aux nombres négatifs, et on peut se demander ce qu’il advient dans ce cas.
On observe cette fois qu’il y a trois cycles :

- (-1)
- (-5 ; -7 ; -10)
- (-17 ; -25 ; ... ; -34) (11 éléments)


On peut facilement se convaincre que cette suite pour les nombres négatifs correspond à la suite des nombres positifs pour une variante de Collatz où l’on prendrait $\dfrac{3x-1}{2}$ au lieu de $\dfrac{3x+1}{2}$.

(C’est la même courbe que celle au dessus, mais les barres sont tracées plus fines).

Pour cette variante (qui diffère peu de la conjecture de Collatz), il y a trois cycles.

On trouvera d’autres développements sur la conjecture sur ce site très intéressant qui lui est consacré.

Les variantes

Voyons maintenant les autres variantes que l’on peut envisager :

Généralisations

Au lieu de 3, on pouvait prendre un autre nombre impair comme 5 :

et dans ce cas on peut même changer d’ordonnée à l’origine :

(On pourrait bien sûr factoriser la division par 2 comme on l’a fait précédemment.)

On peut alors se demander si l’on observe la même chose que pour l’algorithme de Collatz.
Mais le problème est ici radicalement différent si l’on reprend l’argument naïf probabiliste : $\dfrac{1}{2} \times \dfrac{5}{2}=\dfrac{5}{4} > 1$

Par conséquent si l’on passe une fois sur deux par un terme pair, alors la suite augmente, et donc elle diverge.

Reprenons les outils précédents pour étudier la variante $\dfrac{5x+1}{2}$

- En partant de 5, on rejoint le cycle (13 ; 33 ; 83 ; 208 ; 104 ; 52 ; 26).

- En partant de 7 et 9, on diverge.

Pour avoir une meilleure appréhension de la conjecture de Collatz, on peut s’intéresser plus particulièrement aux variantes $3x+b$.

- Variante $3x+3$
1 donne 3 ; 3 donne 6. Il semble y avoir un seul cycle (3,6) et tous les nombres semblent finir par entrer dans ce cycle.

- Variante $3x+5$
Il y a plusieurs cycles : (1, 4, 2), (5, 10), (19, 31, 49, 76, 38), (23, 37, 58, 29, 46), un cycle de 27 éléments (187, 283, ..., 374), ... ?

Voici le vol 187 :
cycle à 27 éléments : 187,...

Quand on augmente b, il apparaît des "trous" plus grands, ce qui semble générer plus de cycles.
On peut conjecturer que les cycles restent en nombre fini.

Concentrons nous maintenant sur $3x+1$ (Collatz) et $3x+3$, et créons des hybrides à partir d’un mot binaire de la façon suivante :

si le nombre binaire est 100 :
- pour 1, on applique $3x+3$
- pour 3, on applique $3x+3$
- pour 5, on applique $3x+1$

- pour 7, on applique $3x+3$
- pour 9, on applique $3x+3$
- pour 11, on applique $3x+1$

etc

On représente le temps de vol en altitude pour les 200 premiers entiers.
Un carré rouge signifie que la suite n’entre pas dans le cycle prévu.
Soit elle n’est pas bornée (ou plus précisément, ne semble pas bornée).
Soit elle entre dans un cycle différent (c’est plus probable).


C’est $3x+3$



C’est $3x+1$



C’est encore $3x+3$.



si $n=4k+1$, $3(4k+1)+1=12k+4$
si $n=4k+3$, $3(4k+3)+3=12k+12$
Le terme suivant est pair et on redescend. Temps de vol en altitude $\leqslant 2$



si $n=4k+1$, $3(4k+1)+3=12k+6$
si $n=4k+3$, $3(4k+3)+1=12k+10$
Le terme suivant est toujours impair, la suite croît et le temps de vol en altitude est infini.





Ici, il y a "clairement" un autre cycle.








Il s’agit encore d’un autre cycle, ce ne sont pas des vols non bornés.



C’est perturbant.




Je dirais même plus : c’est troublant.



Cette fois, il y a (semble-t-il) des vols non bornés.




On voit que certains mixtes semblent nettement plus "simples" (plus bornés) que $3x+1$ et $3x+3$, ce qui est assez troublant.
Par ailleurs, on a des cas "non évidents" de suites non bornées, mais dont on peut probablement montrer (via les modulo) la croissance. On aurait pu s’attendre à ce que ces cas ne se produisent pas en dehors des avatars de (10)*, mais ce n’est pas vrai : ces cas semblent se produire ponctuellement (pour certaines sous-suites).


Dans ce fichier CaRMetal, on convertit un nombre en base 2 et on enlève le premier chiffre qui est toujours égal à 1.

CarMetal - 3.3 ko

Il y a une infinité de Collatz généralisés, intéressants à étudier en eux-mêmes, mais surtout à l’origine d’un théorème de Conway laissant planer l’ombre d’un doute sur la possibilité de prouver la conjecture de Collatz un jour :

Théorème : Le "problème ax+b" est indécidable.

La fonction de Collatz peut se présenter ainsi :

$f(n)=\begin{cases} \dfrac{1}{2}n & \text{si } n \equiv 0 \text{ mod } 2\\ \dfrac{3}{2}n+\dfrac{1}{2} & \text{si } n \equiv 1 \text{ mod } 2 \end{cases}$

John Conway a alors envisagé une généralisation à p cas :

$g(n)=\begin{cases} a_0.n + b_0 & \text{si } n \equiv 0 \text{ mod } p\\ ... & \\ a_k.n+b_k & \text{si } n \equiv k \text{ mod } p \\ ... & \\ a_{p-1}.n+b_{p-1} & \text{si } n \equiv (p-1) \text{ mod } p \end{cases}$

où $a_k$ et $b_k$ sont des fractions telles que g est toujours à valeurs entières.

Et il a démontré que le comportement des itérés $g^m(n) $ de ces fonctions est indécidable : il n’existe pas d’algorithme permettant de savoir, juste à partir de la donnée des $a_k$ et $b_k$, si la suite des itérés finit par un cycle.

Un aspect particulièrement intéressant de ce théorème est que sa démonstration est basée sur le caractère Turing-complet de ces suites de Collatz généralisées, et cela a amené Conway à inventer un langage de programmation plutôt original : FRACTRAN (nommé par contraction de "fractions" et "Fortran").

FRACTRAN

Fractran par l’OVNI Pico

Dans ce jeu Pico marche sur le chemin du contraire [3], chemin parsemé de fractions. Pico porte un nombre entier (l’entrée du programme) et parcourt les fractions l’une après l’autre, en multipliant mentalement (ou pas) la fraction par le nombre qu’il transporte avec lui.

Par exemple, avec 16 comme nombre de départ, Pico a 4 fois de suite réussi la multiplication de son nombre par $\frac{5}{2}$ et se retrouve avec 625 (après avoir successivement eu 16, 40, 100 et 250) et a été à chaque fois téléporté au départ. La multiplication de 625 par $\frac{5}{2}$ ayant échoué, Pico se dirige hardiment vers $\frac{3}{25}$ qui va accepter la multiplication, ce qui aura pour effet de téléporter Pico au départ, avec 75 pour nouveau nombre à soumettre :

Voici les règles du jeu :

  • dès que le résultat est entier, Pico remplace le nombre par le produit entier, et se téléporte au début du programme (juste avant la première fraction), avec ce nouveau nombre dans la tête ;
  • sinon, il finit par arriver au bout sans avoir réussi une seule multiplication, et le programme s’arrête sur le nombre entier qu’il a avec lui.

Les gobelets de Gödel

Ces célèbres problèmes d’algorithmique suggèrent un méta-exercice, avec des billes dans des gobelets au lieu d’eau dans des seaux : Comment "montrer" l’addition 5+4 avec ces deux gobelets, contenant au départ, respectivement, 5 billes et 4 billes ?

Vous avez réussi ? Bravo ! La solution, comme souvent, se trouve plus facilement en vidant un verre ! On peut modéliser cela avec la programmation objet, ici, à l’aide d’alcoffeethmique qui combine la concision de CoffeeScript avec la langue française. On crée un objet rg ("registres-gobelets") ayant deux "propriétés" appelées 2 et 3 (on verra plus bas pourquoi). Au départ, la valeur de la propriété 2 est 5 puisque le gobelet numéro 2 contient 5 billes ; et de même la propriété 3 a la valeur 4. On fait ici un peu du "Sofus++" pusque, alors que la spécialité de Sofus est d’incrémenter ou décrémenter une variable, le transfert d’une bille depuis le registre 3 vers le registre 2 est décomposé en deux opérations sofusiennes :

  • On commence par retirer la bille du registre 3, ce qui revient à le décrémenter (noté rg[3] -= 1) ;
  • Puis on la place dans le registre 2, ce qui a pour effet d’incrémenter celui-ci (note rg[2] += 1)

Pour effectuer l’addition, on recommence ces transferts jusqu’à ce que le gobelet de droite soit vide :

  1. rg = { '2': 5, '3': 4 }
  2. jusqu'à ce que rg[3] == 0
  3. rg[3] -= 1
  4. rg[2] += 1
  5. affiche rg[2]

Télécharger

On a vu dans cette revue qu’Hao Wang avait amélioré les machines de Turing en les dotant de programmes (suites d’instructions). Cela a inspiré Marvin Minsky qui a doté d’instructions similaires des registres similaires aux gobelets ci-dessus : Ils contiennent des entiers naturels et on peut savoir s’ils sont vides ou non, les incrémenter, les décrémenter (sauf s’ils sont vides) et donc effectuer le genre de transfert envisagé ici. Cette machine à compteurs est un calculateur universel ("Turing-complet"). C’est ce modèle que Conway a transformé en un autre modèle de calculabilité, lui aussi Turing-complet, à l’aide d’une astuce déjà utilisée par Minsky, et dûe à Kurt Gödel, comme le montre sa description dans ce célèbre article de 1931 :

Toute suite finie d’entiers (comme les contenus des différents registres) peut être représentée de façon unique par un entier, dit "de Gödel". Par exemple la suite (5,4) dans les gobelets ci-dessus est représentée par l’entier 25×34=32×81=2592. Dans le bloc "pour aller plus vite" plus bas, on montre comment le langage de programmation bash permet de facilement effectuer un "décodage de Gödel" : Passer de 2592 à 5 et 4. C’est parce que la numérotation de Gödel est basée sur la décomposition d’un entier (de Gödel) en facteurs premiers, que les registres sont étiquetés par des nombres premiers. Pour faire l’addition ci-dessus, on a eu besoin de deux registres que l’on a donc nommés 2 et 3 respectivement.

Voyons maintenant comment la variation d’un registre (ou plusieurs) modifie le nombre de Gödel n :

  • incrémenter le registre 2 a pour effet de multiplier n par 2 ;
  • augmenter le registre 2 de 2 unités a pour effet de multiplier n par 4 ;
  • augmenter le registre 2 de 3 unités a pour effet de multiplier n par 8, etc.
  • décrémenter le registre 2 a pour effet de diviser n par 2, etc.
  • incrémenter le registre 3 a pour effet de multiplier n par 3 ;
  • décrémenter le registre 3 a pour effet de diviser n par 3 ;
  • du coup, on peut faire du calcul parallèle en Fractran : En multipliant n par 2/3, on incrémente le registre 2 et on décrémente le registre 3 en même temps.

Le programme d’addition en Fractran, est donc constitué de la seule fraction 2/3, par laquelle on multiplie (transfert d’une bille à la fois) tant que c’est possible, c’est-à-dire tant que le produit est entier.

Pour soustraire 4 à 5, on ne transfère plus de billes, mais on en enlève autant de chaque gobelet jusqu’à ce que le gobelet 3 soit vide :

  1. rg = { '2': 5, '3': 4 }
  2. tant que rg[3] > 0
  3. rg[3] -= 1
  4. rg[2] -= 1
  5. affiche rg[2]

Télécharger

La seule différence par rapport au cas de l’addition est qu’au lieu de multiplier le nombre de Gödel par 2, on le divise par 2 : L’unique fraction constituant le programme de soustraction est 1/6.

Avec les soustractions, on peut calculer un reste euclidien, par soustractions successives jusqu’à ce que le résultat soit plus petit que le nombre à soustraire ; en rajoutant un comptage du nombre de boucles, on peut aussi calculer le quotient euclidien. Et une multiplication est faite d’additions itérées.

Pour calculer le plus petit de deux entiers, on peut décrémenter les deux registres 2 et 3 comme tout-à-l’heure, mais en comptant (par incrémentations successives du registre 5) le nombre de fois qu’on a enlevé une bille à chaque gobelet. Ce qui se fait par multiplication par la fraction 5/6. Ensuite, il reste éventuellement une bille dans un des registres 2 et 3, à enlever, soit par multiplication par 1/2, soit par multiplication par 1/3 :

  1. rg = { '2': 5, '3': 4, '5': 0 }
  2. tant que rg[2] > 0 et rg[3] > 0
  3. rg[5] += 1
  4. rg[3] -= 1
  5. rg[2] -= 1
  6. tant que rg[2] > 0
  7. rg[2] -= 1
  8. tant que rg[3] > 0
  9. rg[3] -= 1
  10. affiche rg[5]

Télécharger

La concision de Fractran est donc considérable, grâce au codage de Gödel : Tout le script ci-dessus se résume à la liste de 3 fractions (5/6,1/2,1/3).

Pour la multiplication, voici l’évolution temporelle des registres 2, 3, 5, 7, 11 et 13 pendant la multiplication de 3 par 2 (nombre de Gödel initial : 23×32=72) :

Ce graphique a été obtenu avec le programme bash exposé en bas de l’article. On voit que les registres 7, 11 et 13 servent à stocker provisoirement des données alors que le registre 2 décroît et le registre 3 évolue cycliquement (parties entière et modulaire d’un indice allant vers 0) ; le registre 5 croît vers le produit, calculé en recopiant le registre 3 vers le 5 pour chaque unité du registre 2 : 2+2+2=2×3.

En fait, la version Minsky avec incrémentations et décrémentations de registres présente sur Fractran quelques avantages :

  • les ordinateurs des années 1960-1980 effectuaient les additions bien plus rapidement que les multiplications, et les programmes de la machine de Minsky s’exécutaient bien plus vite que les programmes Fractran ;
  • Les nombres de Gödel tendent à être grands et on risque moins le dépassement de capacité avec les registres de Minsky ;
  • Quand on n’effectue pas le codage de Gödel, on n’a pas besoin de faire le décodage après avoir exécuté le programme.

Par contre la concision de Fractran lui donne un charme indéniable, et faire des exercices de programmation en Fractran au cycle 4, permet de faire travailler les collégiens à la fois sur les fractions et la programmation, ce qui n’est pas dénué d’intérêt lorsqu’on dispose de si peu d’heures pour traiter ce programme de collège...

Fractran par Conway

Voici la présentation de Fractran par son auteur, rédigée sous la forme d’une parodie de publicité :

John Conway n’est pas seulement un grand génie mais il a un indubitable talent comique.

En pratique, voici un programme en Fractran calculant les nombres premiers :

Et tant qu’à faire le programme Fractran simulant n’importe quelle machine de Turing :

  • sous forme de graphe :
  • sous forme d’une liste de fractions :

Fractran pour les nuls

Fractran est un langage de programmation invraisemblable qui s’applique à des nombres entiers.

Le programme est constitué d’une liste de fractions (!).

Pour chercher l’image d’un entier A, on regarde dans la liste la première des fractions qui multipliée par A donne un entier B, puis on applique de nouveau la procédure sur l’entier B. Si aucune des fractions de la liste multipliée par A ne donne un entier, la procédure s’arrête. [4]

On notera la correspondance avec les fonctions de Collatz généralisées, mais c’est tout de même différent.

Le programme Fractran vu dans le bloc sur Pico, noté $\left( \frac{5}{2}, \frac{3}{25}, \frac{1}{5} \right)$, a pour effet de diviser par 2 (quotient entier) l’exposant du nombre $2^a$ qu’on lui soumet au départ : Si $a=2b$ ou $a=2b+1$ alors en sortie on a $3^b$. Il est à noter que le programme $\left( \frac{3}{4}, \frac{1}{2} \right)$ a le même effet avec moins de fractions. Quant au contraire (doubler l’exposant en transformant $2^a$ en $3^{2a}$), il se fait plus simplement, avec une seule fraction $\frac{9}{2}$. Au fait, l’addition se fait avec la seule fraction $\frac{3}{2}$ et la soustraction est le programme Fractran le plus simple qui soit :

$$\frac{1}{6}$$

Voici un programme Fractran plus complexe, il multiplie deux nombres a et b en transformant 2a×3b en 5a×b :

On peut le manipuler en ligne en suivant ce lien

Son écriture comme programme Fractran est la suivante :

$$\left( \frac{455}{33}, \frac{11}{13}, \frac{1}{11}, \frac{3}{7}, \frac{11}{2}, \frac{1}{3} \right)$$

Pour les scratchophobes, voici la version Snap ! [5] :

XML - 952.6 ko

Les heureux possesseurs d’une machine Android©GoogleTM peuvent aussi essayer l’application Android ci-dessous (Pico s’est transformé en coccinelle, en anglais "ladybug", nom risqué...) :

Zip - 1.6 Mo

(télécharger, d’un clic, le fichier zip ci-dessus, le dézipper, puis le transférer vers la machine Android, et là installer en touchant le fichier apk obtenu, après avoir accepté cette application venant d’un développeur "non digne de confiance" :-/ )

Interpréteur Fractran et exemples de programmes

Pour décrire ces exemples, on a créé un interpréteur Fractran avec CaRMetal (encore un effet de bord !). Cet interpréteur permettra de programmer en Fractran, en entrant les numérateurs et dénominateurs dans des cases réservées à cet effet. On adaptera le programme en fonction du codage du nombre initial, et du résultat.
On visualise l’évolution des valuations (échange de fluide entre les éprouvettes). La tortue de CaRMetal joue le rôle de Pico.

L’interpréteur s’utilise ainsi :

  • on entre les fractions dans les cases du haut ;
  • on entre le premier nombre dans la case entrée ;
  • s’il y en a un, on entre le deuxième nombre dans la case entrée 2 ;
  • on coche la (ou les cases) qui correspondent au nombre premier dont la valuation sera le résultat.

- Pour la multiplication, le programme est :

$$\left( \frac{455}{33}, \frac{11}{13}, \frac{1}{11}, \frac{3}{7}, \frac{11}{2}, \frac{1}{13}\right)$$

Les entiers donnés, x et y, sont encodés sous la forme, $n = 2^x3^y$. Au terme du calcul, le produit s’affiche en exposant de 5.

On a donc cet état de l’interface (à la fin du programme) :

- PGCD :
Voici un programme donnant le pgcd :

$$\left( \frac{2}{7}, \frac{3}{11}, \frac{13}{17}, \frac{19}{23}, \frac{51}{65}, \frac{1}{13}, \frac{46}{95}, \frac{1}{19}, \frac{5}{6}, \frac{91}{2}, \frac{209}{3} \right)$$

Les entiers donnés, x et y, sont encodés sous la forme, $n = 2^x3^y$. Au terme du calcul, le PGCD s’affiche en exposant de 5.

- Suite des nombres premiers :
Le programme $\left( \dfrac{17}{91}, \dfrac{78}{85}, \dfrac{19}{51}, \dfrac{23}{38},\dfrac{29}{33}, \dfrac{77}{29}, \dfrac{95}{23}, \dfrac{77}{19}, \dfrac{1}{17}, \dfrac{11}{13}, \dfrac{13}{11}, \dfrac{15}{2}, \dfrac{1}{7}, \dfrac{55}{1}\right)$, appliqué à n = 2, passe successivement (sans s’arrêter) par toutes les puissances $2^p$ où p est premier.

- Ce serait dommage que le langage Fractran, né de recherches sur la suite de Collatz, ne serve pas aussi à programmer la suite de Collatz elle-même.
Le défi a été relevé par Kenneth Monks.
Le programme $\left( \dfrac{1}{11}, \dfrac{136}{15}, \dfrac{5}{17}, \dfrac{4}{5}, \dfrac{26}{21}, \dfrac{7}{13}, \dfrac{1}{7}, \dfrac{33}{4}, \dfrac{5}{2}, \dfrac{7}{1}\right)$ appliqué à $2^n$, calcule une suite dont on ne retient que les puissances de 2 : les exposants sont les termes de la suite démarrant à n. On adapte le programme pour obtenir l’affichage souhaité.

Voici un véritable classeur CaRMetal avec dans les différents onglets le programme de l’addition puis ceux évoqués plus haut :

CarMetal - 24.1 ko
interpréteur Fractran avec CaRMetal
classeur CaRMetal (cliquer pour télécharger)
addition, multiplication, PGCD, premiers, Collatz

Remarque : les programmes sont en Javascript francisé avec des instructions tortue en français, sauf celui pour les nombres premiers, qui est en Javascript classique avec des instructions tortue en anglais.
Ces deux versions du programme donnent le même résultat lors de la compilation.

On trouvera d’autres exemples de programmes fractran sur cette page. Et des interpréteurs Fractran figurent sur cette page.

Pour aller plus vite

On peut aussi programmer un interpréteur Fractran en bash (disponible notamment chez tout épicier spécialisé en Raspberry Pi), avec ce script (ici il s’agit de la multiplication de 3 par 2, codée 23×32=72 ; les tableaux ns et ds désignent respectivement les numérateurs et les dénominateurs) :

  1. #! /bin/bash
  2. ns=( 1 455 11 1 3 11 1 )
  3. ds=( 1 33 13 11 7 2 3 )
  4. t=0
  5. n=72
  6. echo stages > stages.csv
  7. while [ $t -le 6 ]; do
  8. if [ $(($n*${ns[$t]}%${ds[$t]})) -eq 0 ]; then
  9. let "n=$(($n*${ns[$t]}/${ds[$t]}))"
  10. let "t=0"
  11. factor $n >> stages.csv
  12. fi
  13. let "t=$t+1"
  14. done

Télécharger

Voici quelques explications sur ce script :

  1. La ligne 1 explique à Linux ou à Mac OS que c’est le logiciel bash qui doit être utilisé et non un autre shell. Il s’agit d’un commentaire et ne sera pas exécuté.
  2. La ligne 2 définit ns, la liste des numérateurs (on doit donc la modifier si on veut changer de programme) ;
  3. La ligne 3 définit de même la liste ds des dénominateurs (elle doit donc être de même taille que ns, soit 6+1 car il y a une fraction "pour de rien" pour éviter les problèmes de comptage à partir de 0 au lieu de 1 ; et le programme de multiplication est formé de 6 fractions) ;
  4. La ligne 4 initialise à zéro la variable entière t qui est la position actuelle de Pico ;
  5. La ligne 5 initialise à 8×9 (pour calculer 3×2) la variable n qui est l’entier porté par Pico.
  6. La ligne 6 crée place dans le fichier stages.csv le texte stages ("étapes") ;
  7. La ligne 7 boucle jusqu’à ce que Pico traverse la ligne d’arrivée (autrement dit, tant que la valeur de t est inférieure ou égale ("less or equal", abrégé en "le") à 6) ;
  8. La ligne 8 est un test sur le caractère entier de n : bash ne teste pas par défaut les entiers, parce que le type entier est le seul type numérique de bash ; alors pour savoir un une fractions est entière, on calcule son numérateur (par lecture dans la liste ns et multiplication ) modulo son dénominateur et on regarde si le résultat est équal ("eq") à 0 ; dans ce cas seulement, on effectue les lignes 9 à 12.
  9. La ligne 9 ne s’applique que si le produit de n par la fraction courante est entier ; elle effectue la division et place le quotient dans n (nouvelle valeur que Pico va transporter dans le circuit) ;
  10. La ligne 10 renvoie Pico au point de départ t=0 ;
  11. La ligne 11 rajoute dans la fichier stages.csv l’écriture en facteurs premiers de n (décodage de Gödel) ;
  12. La ligne 12 est la fin du test "fi", c’est "if" à l’envers : La saveur toute particulière de bash) ;
  13. que la multiplication ait réussi ou échoué, de toute manière, Pico doit ensuite avancer d’un pas ; ce qu’il fait en incrémentant t ;
  14. La ligne 14 est la fin du "while". Le contraire de "do" n’est pas "od" mais "done", bash échappe un peu à sa propre logique !

L’avantage du langage bash sur d’autres outils est qu’il possède l’instruction factor utilisée à la ligne 11 et qui affiche non seulement les différents nombres portés successivement par Pico mais aussi leurs facteurs premiers. Le fichier stages.csv obtenu ressemble à ceci :

72: 2 2 2 3 3
396: 2 2 3 3 11
5460: 2 2 3 5 7 13
4620: 2 2 3 5 7 11
63700: 2 2 5 5 7 7 13
53900: 2 2 5 5 7 7 11
4900: 2 2 5 5 7 7
2100: 2 2 3 5 5 7
900: 2 2 3 3 5 5
4950: 2 3 3 5 5 11
68250: 2 3 5 5 5 7 13
57750: 2 3 5 5 5 7 11
796250: 2 5 5 5 5 7 7 13
673750: 2 5 5 5 5 7 7 11
61250: 2 5 5 5 5 7 7
26250: 2 3 5 5 5 5 7
11250: 2 3 3 5 5 5 5
61875: 3 3 5 5 5 5 11
853125: 3 5 5 5 5 5 7 13
721875: 3 5 5 5 5 5 7 11
9953125: 5 5 5 5 5 5 7 7 13
8421875: 5 5 5 5 5 5 7 7 11
765625: 5 5 5 5 5 5 7 7
328125: 3 5 5 5 5 5 5 7
140625: 3 3 5 5 5 5 5 5
46875: 3 5 5 5 5 5 5
15625: 5 5 5 5 5 5

On y voit non seulement que le programme, avec l’entrée 72, donne 15625, mais aussi que ce nombre n’est autre que 56 et effectivement, il se trouve que 3×2=6, ce qui permet de vérifier que dans ce cas au moins, le programme a bel et bien effectué le produit de 3 par 2. Mais ce n’est pas tout : Le fichier "csv" (comma separated values) peut s’ouvrir avec un tableur (en cochant la case "espace" comme séparateur possible) et on peut alors transformer les listes de facteurs premiers en nombres entiers : Les contenus des "registres" 2, 3, 5, 7, 11 et 13. Pour cela on entre dans L1 à Q1 les nombres premiers 2, 3, 5, 7, 11 et 13, puis, dans L2, la formule suivante :

=NB.SI($B2:$J2;L$1)

Ensuite, en recopiant vers la droite (jusqu’à Q) puis vers le bas (jusqu’à 28) cette formule, on a dans L2:Q28 les contenus successifs des registres 2 (colonne L) jusqu’à 13 (colonne Q), et ces contenus ne sont autres que l’historique du calcul. Le tableur (ici, Libre Office Calc) peut d’ailleurs représenter graphiquement cet historique, et le fichier ci-dessous comprend ce graphique, où on voit bien que le registre 2 décroit alors que le registre 5 croit au cours du calcul :

On constate au passage que Pico a été téléporté 27 fois au point de départ du chemin du contraire.

Voici le fichier tableur obtenu :

OpenDocument Spreadsheet - 83.2 ko

Et la multiplication de 5 par 3 (obtenue en remplaçant 72 par 864 dans le fichier bash) suit cette chronologie :

Cette fois-ci, Pico est retourné 57 fois au point de départ.

En remplaçant la ligne "while" du programme bash, par quelque chose du genre

for i in `seq 1 200`

on peut aussi n’afficher que les premières étapes du calcul, ce qui est pratique s’il s’agit d’un calcul sans fin, comme les nombres de Fibonacci, les nombres premiers de Conway ou cette variante [6] donnant, à des moments du calcul, 100, 1000, 100000, 10000000 etc (les nombres premiers sous forme de puissances de 10) :

$$\left( \frac{3}{11}, \frac{847}{45}, \frac{143}{6}, \frac{7}{3}, \frac{10}{91}, \frac{3}{7}, \frac{36}{325}, \frac{1}{2}, \frac{36}{5} \right)$$

le dernier rebondissement avant le prochain

L’histoire belge

Voici le dernier effet de bord évoqué dans cet article : L’article lui-même a été initié par l’annonce par les belges, de la preuve de Collatz, qui a ramené cette conjecture sur le devant de la scène...

Voici l’idée de leur preuvefiasco :

  • On a vu ci-avant un argument heuristique selon lequel le nombre est multiplié parfois par 3/2 et parfois par 1/2, donc globalement la suite de Collatz fluctue autour d’une suite géométrique de raison la moyenne géométrique de 3/2 et 1/2, soit environ 0,86 : On dit que la transformation de Collatz est globalement contractante. Autrement dit, qu’elle se comporte comme cette version aléatoire :
  • Dans ce cas, un théorème de Barnsley dit que la probabilité que la suite aléatoire ci-dessus ne soit pas bornée, est nulle. Pour illustrer cette suite aléatoire "à la Barnsley", on peut considérer ce "jeu du chaos", tout-à-fait au programme du cycle 4 (chapitres homothéties, probabilités et programmation) :
    • On choisit un point (mettons, d’abscisse entière non nulle et d’ordonnée nulle) ;
    • On lance une pièce :
      • Si elle tombe sur pile, on transforme le point par une homothétie de rapport 3/2 ;
      • Sinon on le transforme par une homothétie de rapport 1/2 ;
    • On recommence à l’∞
    • L’évènement "le nuage de points converge vers l’origine" a pour probabilité 1
      Le problème est que, transposé à la suite de Collatz, on ne peut pas exclure que quelques entiers constituent un ensemble de valeurs exceptionnelles de probabilité nulle sans être vide.
  • Les chercheurs belges ont alors eu l’idée de regarder, non les nombres de Collatz eux-mêmes, mais leur reste dans la division euclidienne par 8. Et en plus, ce n’est pas la transformation de Collatz qui est considérée, mais sa troisième itérée, pour laquelle la conjecture devient "la suite est ultimement constante égale à 1".
  • Alors certains circuits ne peuvent être parcourus, par exemple si u est congru à 7 modulo 8, son troisième itéré ne peut pas être divisible par 8 [7] : On définit un graphe qui suggère une chaîne de Markov [8], auquel cas il y aurait une probabilité stationnaire.
  • En comptant le nombre d’origines possibles pour chaque reste modulo 8, on définit cette probabilité invariante, et on démontre qu’elle est invariante ...
  • ... en définissant à partir de la probabilité "invariante", par la formule de Bayes, la chaîne de Markov.
  • La théorie ergodique des chaînes de Markov permet alors de "conclure" que la probabilité considérée est invariante, et qu’elle est atteinte avec probabilité 1 : La troisième itérée de la transformation de Collatz est globalement contractante quand on la regarde modulo 8.
  • Mais cela ne suffit pas à prouver qu’il n’y a pas d’orbite de probabilité nulle, sur laquelle la suite diverge...

notes

[1"Quand les types de 130 kilos disent certaines choses, les types de 60 kilos les écoutent" (Audiard : 100 000 dollars au soleil)

[2L’arbre ainsi obtenu avait déjà été esquissé par Collatz

[3en anglais, "con way"...

[4d’après Wikipédia

[5réalisé avec l’aimable concours de Nathalie Carrié, qui connaît bien mieux Snap ! que les auteurs de cet article.

[6dûe à D. Kilminster

[7Si u est congru à 7, il est impair donc son premier itéré est 3u+1, qui est congru à 6 modulo 8 ; alors le second itéré est la moitié (3u+1)/2 qui est congrue à 3 modulo 8, et le troisième itéré est 3((3u+1)/2)+1 qui est congru à 3×3+1 modulo 8, soit 2, et pas 0

[8en regardant non où on va en itérant 3 fois, mais d’où on vient, d’où le caractère non déterministe

Documents associés à l'article
     |   (HTML - 2.5 ko)
Réagir à cet article
Vous souhaitez compléter cet article pour un numéro futur, réagir à son contenu, demander des précisions à l'auteur ou au comité de rédaction...
À lire aussi ici
MathémaTICE est un projet
en collaboration avec
Suivre la vie du site Flux RSS 2.0  |  Espace de rédaction  |  Nous contacter  |  Site réalisé avec: SPIP  |  N° ISSN 2109-9197