FRACTRAN

FRACTRAN

FRACTRAN est un langage de programmation exotique et Turing-complet s'appliquant à des entiers naturels. Il a été inventé par le mathématicien John Conway qui en publie une description en 1987.

Il consiste à représenter toute fonction calculable sur des entiers par 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.

Exemple

Considérons le programme FRACTRAN correspondant à la liste de fractions $\left({\frac {3}{10}},{\frac {4}{3}}\right)$ .

Si on l'applique à l'entier 14, comme ni ${\frac {3}{10}}\times 14$, ni ${\frac {4}{3}}\times 14$ ne sont des entiers, le programme s'arrête immédiatement.

Si on l'applique à l'entier 15, on obtient successivement 20 (car seul ${\frac {4}{3}}\times 15$ est un entier), puis 6 (car ${\frac {3}{10}}\times 20$ est un entier) , puis 8 (car seul ${\frac {4}{3}}\times 6$ donne un entier), puis la procédure s'arrête.

Principe

Le principe s'appuie sur l'existence d'une décomposition en produits de facteurs premiers des entiers et sur la notion de valuation p-adique.

Tout entier A possède une décomposition en produit de facteurs premiers unique dans laquelle l'exposant du nombre premier p est appelé valuation de p dans A et est noté $v_{p}(A)$.

Pour un entier A donné, les $v_{p}(A)$ sont tous nuls sauf un nombre fini d'entre eux. Multiplier l'entier A par une fraction permettant d'obtenir un entier B, consiste à opérer des additions et des soustractions sur les $v_{p}$.

Ainsi la liste précédente opère sur les valuations de 2, 3 et 5. La première fraction enlève 1 aux valuations de 2 et 5 (si cela est possible) et augmente de 1 la valuation de 3, la seconde fraction n'agit que lorsque la valuation de 2 ou de 5 est nulle elle augmente la valuation de 2 de deux unités et baisse celle de 3 d'une unité.

Lorsque A s'écrit $2^{a}\times 3^{b}\times 5^{c}\times A'$ avec A' premier avec 30, et $c\leq a$ , à l'aide de deux boucles, la procédure transforme A en $B=2^{a-c}\times 3^{b+c}\times A'$ puis en $2^{a+2b+c}\times A'$ et s'arrête alors.

Le programme permet ainsi de définir des opérations sur les valuations.

Opérations basiques

Addition

La liste contenant l'unique fraction ${\frac {3}{2}}$ permet de faire la somme des valuations de 2 et de 3 : lorsque A s'écrit $2^{a}\times 3^{b}\times A'$ avec A' premier avec 6, la procédure s'applique jusqu'à ce que A soit transformé en $3^{a+b}\times A'$.

Multiplication

On peut créer une fonction multiplicative à l'aide d'une boucle additive. Pour cela, il faut introduire la notion d'état dans l'algorithme. Cet algorithme s'applique à un nombre $2^{a}3^{b}$ et le transforme en $5^{ab}$ et travaille sur les valuations de 2, 3, 5 mais aussi 7 , 11 et 13 :

État courant	Condition	Action	État suivant
A	v7 > 0	Soustraire1 à v7 ajouter 1 à v3	A
	v7 = 0 et v2 > 0	Soustraire 1 à v2	B
	v7 = 0 et v2 = 0 et v3 > 0	Soustraire 1 à v3	A
	v7 = 0 et v2 = 0 et v3 = 0	Stop
B	v3 > 0	Soustraire 1 à v3 Ajouter 1 à v5 Ajouter 1 à v7	B
	v3 = 0	Rien	A

L'état B est une boucle qui ajoute v3 à v5 et déplace aussi v3 en v7 et l'état A est une boucle qui répète la boucle B v2 fois. L'état A remet aussi dans v3 la valeur initiale (présente dans v7) quand la boucle B est terminée.

Pour gérer ces états, de nouvelles variables sont nécessaires : elles jouent le rôle d'indicateurs d'états. Les indicateurs d'état pour la boucle B sont v11 et v13. Deux indicateurs d'états sont nécessaires pour la seule boucle B : en effet, le premier indicateur (v11) étant consommé à l'entrée de la boucle, il est nécessaire d'en posséder un second (v13) pour indiquer au programme qu'il doit continuer dans le même état. L'indicateur v13 est basculé en v11 lors de l'instruction « next » de la boucle.

En ajoutant les indicateurs d'états et les instructions au tableau d'algorithme de la multiplication, on obtient :

Instruction FRACTRAN	État courant	Indicateurs d'état	Condition	Action	État suivant
${\frac {3}{7}}$	A	Aucun	v7 > 0	Soustraire 1 à v7 Ajouter 1 à v3	A
${\frac {11}{2}}$			v7 = 0 et v2 > 0	Soustraire 1 à v2 Mettre v11 à 1	B
${\frac {1}{3}}$			v7 = 0 et v2 = 0 et v3 > 0	Soustraire 1 à v3	A
			v7 = 0 et v2 = 0 et v3 = 0	Stop
${\frac {5\cdot 7\cdot 13}{3\cdot 11}},{\frac {11}{13}}$	B	v11, v13	v3 > 0	Soustraire 1 à v3 Ajouter 1 à v5 Ajouter 1 à v7	B
${\frac {1}{11}}$			v3 = 0	Mettre v11 à 0	A

Quand on écrit la liste d'instructions FRACTRAN, on doit mettre les instructions de l'état A en dernier car l'état A n'a pas d'indicateur d'état, c'est l'état par défaut.

Ainsi le programme FRACTRAN de multiplication est la liste suivante :

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

Si on entre le nombre $2^{a}3^{b}$, le programme rend $5^{ab}$.

Simulation de la machine FRACTRAN ci-dessus lors du calcul de 3×2, donc en entrant 2³×3²=72, et en récupérant à la fin 5⁶.

Soustraction

La simple fraction ${\frac {1}{6}}$ permet de transformer le nombre $2^{a}3^{b}$ en

• $2^{a-b}3^{0}$ , si $a>b$ ;
• $2^{0}3^{b-a}$, si $b>a$ ;
• $2^{0}3^{0}$ si $a=b$.

Division euclidienne

La division euclidienne de a par b (a et b entiers naturels, b > 1) est la donnée de deux entiers naturels q et r tels que r < b et a = bq + r. Cette division euclidienne peut être vue comme une boucle de soustractions : diviser a par b, c'est ôter b à a autant de fois qu'il est nécessaire, le nombre de fois où cette soustraction est effectuée correspond à q, la dernière valeur dans a correspond au reste.

L'algorithme travaille lors sur v2 contenant a, v3 contenant b, v5 destiné à contenir q, et v7 destiné à contenir r. Ces variables sont complétées par 4 indicateurs d'états v11, v13, v17, v19.

Le programme FRACTRAN qui suit consiste en trois états :

• l'état A opère différemment selon que v3 est plus petit ou plus grand que v2;
  • si v3 ≤ v2, la boucle retranche v3 à v2, vide v3 dans v7, ajoute 1 à v5 et passe à l'état B ;
  • si v3 > v2, la boucle vide v2 dans v7 et passe à l'état X.
• l'état B est une sur-boucle qui ré-effectue la boucle A après avoir au préalable vidé v7 dans v3;
• l'état X consiste à vider v3 quand v2 est vide et v3 est non vide.

Instructions FRACTRAN	État courant	Indicateurs d'état	Conditions	Actions	État suivant
${\frac {7\cdot 13}{2\cdot 3\cdot 11}},{\frac {11}{13}}$	A	v11, v13	v2 > 0 et v3 > 0	Soustraire 1 à v2 Soustraire 1 à v3 Ajouter 1 à v7	A
${\frac {1}{3\cdot 11}}$			v2 = 0 et v3 > 0	Soustraire 1 à v3 Mettre v11 à 0	X
${\frac {5\cdot 17}{11}}$			v3 = 0	Ajouter 1 à v5 Mettre v11 à 0 Mettre v17 à 1	B
${\frac {3\cdot 19}{7\cdot 17}},{\frac {17}{19}}$	B	v17, v19	v7 > 0	Soustraire 1 à v7 Ajouter 1 à v3	B
${\frac {11}{17}}$			v7 = 0	Mettre v11 à 1 Mettre v17 à 0	A
${\frac {1}{3}}$	X		v3 > 0	Soustraire 1 à v3	X
			v3 = 0	Stop

L'écriture du programme est alors :

$\left({\frac {91}{66}},{\frac {11}{13}},{\frac {1}{33}},{\frac {85}{11}},{\frac {57}{119}},{\frac {17}{19}},{\frac {11}{17}},{\frac {1}{3}}\right)$

Il suffit d'entrer $2^{a}3^{b}11$ pour obtenir en sortie $5^{q}7^{r}$ où $a=bq+r$ avec $0\leq r<d$.

Génération de suites

Certains programmes bouclent indéfiniment, et génèrent des suites infinies.

Algorithme de Conway des nombres premiers

Le programme suivant est présenté par John Conway dans le livre coécrit avec Richard Guy The Book of Numbers. John Conway les appelle « les 14 fractions fantastiques ».

$\left({\frac {17}{91}},{\frac {78}{85}},{\frac {19}{51}},{\frac {23}{38}},{\frac {29}{33}},{\frac {77}{29}},{\frac {95}{23}},{\frac {77}{19}},{\frac {1}{17}},{\frac {11}{13}},{\frac {13}{11}},{\frac {15}{14}},{\frac {15}{2}},{\frac {55}{1}}\right)$

Ce programme, appliqué à l'entier 2, génère une suite qui contient tous les termes de la forme $2^{p}$ où $p$ est un nombre premier. Réciproquement, toute puissance de 2 dans cette suite a pour exposant 1 ou un nombre premier. Cette suite porte le nom de Conway primegame.

L'algorithme est essentiellement un algorithme de division euclidienne. Le principe est le suivant : partant d'un nombre de la forme $2^{n}7^{m}$ où 0 ≤ m < n, l'algorithme tente de diviser n+1 par tous les nombres de n à 1, jusqu'à ce qu'il trouve le plus grand entier k tel que k divise n+1 et retourne alors $2^{n+1}7^{k-1}$. Les seuls cas où l'algorithme rend une puissance de 2 sont les cas où k = 1, c'est-à-dire les cas où n+1 est premier.

Suite de Fibonacci

Le programme suivant :

$\left({\frac {23}{95}},{\frac {57}{23}},{\frac {17}{39}},{\frac {130}{17}},{\frac {11}{14}},{\frac {35}{11}},{\frac {19}{13}},{\frac {1}{19}},{\frac {35}{2}},{\frac {13}{7}},7\right)$

appliqué à l'entier 3, génère une suite qui contient tous les termes de la forme $2^{a}3^{b}$ où a et b sont deux termes consécutifs de la suite de Fibonacci. Réciproquement, tout terme de la suite de la forme $2^{a}3^{b}$ a pour exposant deux termes consécutifs de la suite de Fibonacci.

L'algorithme est essentiellement un algorithme d'addition qui consiste, en partant de $2^{a}3^{b}$ à fournir $2^{b}3^{a+b}$.

Démonstration

En effet :

• pour $a>0$, la fraction ${\frac {35}{2}}$ transforme $2^{a}\times 3^{b}$ en $5\times 7\times 2^{a-1}\times 3^{b}$, puis les fractions ${\frac {11}{14}}$ et ${\frac {35}{11}}$ transforment itérativement ce dernier en $5^{a}\times 7\times 3^{b}$. Dans le cas où $a=0$, on arrive directement à $7\times 3^{b}$ grâce au 7 final de la liste ;
• La fraction ${\frac {13}{7}}$ transforme alors $5^{a}\times 7\times 3^{b}$ en $5^{a}\times 13\times 3^{b}$, puis les fractions ${\frac {17}{39}}$ et ${\frac {130}{17}}$ le transforment itérativement en $5^{a+b}\times 13\times 2^{b}$ ;
• La fraction ${\frac {19}{13}}$ le transforme en $5^{a+b}\times 19\times 2^{b}$, puis les fractions ${\frac {23}{95}}$ et ${\frac {57}{23}}$ le transforment en $3^{a+b}\times 19\times 2^{b}$ ;
• Enfin, la fraction ${\frac {1}{19}}$ supprime le facteur 19.

 

La suite des points $(n,x_{n})$ où $x_{n}$ est le nombre calculé à la n-ème étape, sortis par cette machine FRACTRAN, est assez chaotique (les coordonnées des premiers points sont (0,3), (1,21), (2,39), (3,17), (4,130), (5,190), (6,46), (7,114) et (8,6)…) mais les nombres $x_{n}$ n'ayant que 2 et 3 comme facteurs premiers (en rouge) représentent bien les termes successifs de la suite de Fibonacci :

Rang	Nombre	Facteurs premiers
8	6	$2^{1}\times 3^{1}$
18	18	$2^{1}\times 3^{2}$
32	108	$2^{2}\times 3^{3}$
54	1944	$2^{3}\times 3^{5}$

Suite de Syracuse

Ce programme présenté par Kenneth G. Monks :

$\left({\frac {1}{11}},{\frac {136}{15}},{\frac {5}{17}},{\frac {4}{5}},{\frac {26}{21}},{\frac {7}{13}},{\frac {1}{7}},{\frac {33}{4}},{\frac {5}{2}},7\right)$

appliqué à $2^{N}$, génère une suite qui contient successivement tous les termes $2^{b}$, où b parcourt les termes de la suite de Syracuse de premier terme N. Réciproquement, toute puissance de 2 dans cette suite a pour exposant un élément de la suite de Syracuse.

Démonstration

• Partant de $2^{N}$, les fractions ${\frac {33}{4}}$ et ${\frac {1}{11}}$ le transforme en $3^{k}\times 2^{N-2k}$ pour les valeurs croissantes de k jusqu'à arriver à $3^{p}$ si N est pair égal à 2p, ou bien $3^{p}\times 2$ si N est impair égal à 2p+1.
• Dans le premier cas, le terme final 7 transforme $3^{p}$ en $3^{p}\times 7$, puis les fractions ${\frac {26}{21}}$ et ${\frac {7}{13}}$ le transforment itérativement en $2^{p}\times 7$. La fraction ${\frac {1}{7}}$ supprime ensuite le 7 superflu. On est alors passé de $2^{N}$ à $2^{N/2}$.
• Dans le deuxième cas, la fraction ${\frac {5}{2}}$ transforme $3^{p}\times 2$ en $3^{p}\times 5$, puis les fractions ${\frac {136}{15}}$ et ${\frac {5}{17}}$ le transforment itérativement en $5\times 2^{3p}$. La dernière fraction ${\frac {4}{5}}$ le transforme enfin en $2^{3p+2}$ qui n'est autre que $2^{(3N+1)/2}$.

Ainsi, l'exposant N a été modifié en N/2 si N est pair et (3N+1)/2 si N est impair, ce qui est le principe de la suite de Syracuse.

 

L'idée de Kenneth Monks est d'étudier les suites de Syracuse cycliques en cherchant les propriétés des suites cycliques générées par ce programme.

Programme universel

Conway a également défini un programme FRACTRAN universel, constitué des fractions suivantes :

$\left({\frac {583}{559}},{\frac {629}{551}},{\frac {437}{527}},{\frac {82}{517}},{\frac {615}{329}},{\frac {371}{129}},{\frac {1}{115}},{\frac {53}{86}},{\frac {43}{53}},{\frac {23}{47}},{\frac {341}{46}},{\frac {41}{43}},{\frac {47}{41}},{\frac {29}{37}},{\frac {37}{31}},{\frac {37}{31}},{\frac {299}{29}},{\frac {47}{23}},{\frac {161}{15}},{\frac {527}{19}},{\frac {159}{7}},{\frac {1}{17}},{\frac {1}{13}},{\frac {1}{3}}\right)$

On peut alors montrer que, pour toute fonction partielle récursive f, il existe un entier c tel que, pour tout entier n, en appliquant le programme FRACTRAN avec la liste ci-dessus au nombre $c\times 2^{2^{n}}$, on atteint le nombre $2^{2^{f(n)}}$ si et seulement si le calcul de f(n) se termine. Cette propriété montre qu'on obtient en FRACTRAN toutes les fonctions calculables.

Notes et références

Références

• (en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « FRACTRAN » (voir la liste des auteurs).

Voir aussi

Articles connexes

• Nombre premier
• Liste de nombres premiers

Ressources bibliographiques

• John Conway, « FRACTRAN: A simple universal programming language for arithmetic », in Open Problems in Communication and Computation, Thomas M. Cover (relecteur), B. Gopinath (relecteur), Springer ; 1^re éd. (9 novembre 1987) ;
• Julian Havil, Nonplussed!: Mathematical Proof of Implausible Ideas, Princeton University Press, 2007 ;
• Kenneth G. Monks, « 3x+1 minus the + », in Discrete Mathematics and Theoretical Computer Science 5, 2002, 47–54.