Mis à jour le 31/10/2013
  • Facile
Connectez-vous ou inscrivez-vous gratuitement pour bénéficier de toutes les fonctionnalités de ce cours !

Introduction du cours

Les suites de Syracuse sont des suites mathématiques célèbres que les mathématiciens travaillent depuis de nombreuses années maintenant. Dans ce tutoriel, nous allons voir de quoi il s'agit réellement, le problème que posent ces suites aux mathématiciens avec la célèbre conjecture de Syracuse et enfin, nous aurons la joie de faire quelques tests de notre côté en implémentant l'algorithme de génération des valeurs de la suite de Syracuse voulue en OCaml.

Définition, conjecture et origine

Les suites de Syracuse sont des suites mathématiques d'entiers naturels, c'est-à-dire d'entiers positifs, très connues et très étudiées par les mathématiciens et ce depuis un peu moins d'un siècle. Le problème a été découvert en 1928 alors que Lothar Collatz, un mathématicien allemand, s'intéresse aux itérations dans les nombres entiers. À cette époque, ce problème était encore appelé "problème 3x+1". Par la suite, dans les années 50 et 60, le problème s'est diffusé un peu partout dans le monde et a pris le nom sous lequel on le connait actuellement.

Ce sont des suites récursives assez originales. Le principe, très simple à comprendre, est défini de la manière suivante :

  • On part d'une valeur entière positive $n$ plus grande que zéro.

  • Si cette valeur $n$ est paire alors la valeur suivante sera $n/2$.

  • Sinon, la valeur suivante sera $3 \times n + 1$.

La suite de Syracuse obtenue en partant de $n$ est appelée "suite de Syracuse du nombre $n$".
Si je pars de la valeur $7$, j'obtiens logiquement la suite suivante :

$7 \rightarrow 22 \rightarrow 11 \rightarrow 34 \rightarrow 17 \rightarrow 52 \rightarrow 26 \rightarrow 13 \rightarrow 40 \rightarrow 20 \rightarrow 10 \rightarrow 5 \rightarrow 16 \rightarrow 8 \rightarrow 4 \rightarrow 2 \rightarrow 1 \rightarrow 4 \rightarrow 2 \rightarrow 1 \rightarrow 4 \rightarrow 2 \rightarrow 1 ...$

On remarque vite qu'il y a quelque chose de remarquable à cette suite : dés qu'on arrive sur $1$, le cycle de longueur trois $4 \rightarrow 2 \rightarrow 1$, appelé "cycle trivial" ("trivial" signifiant "banal, ordinaire, commun, etc."), se forme. En effet, en se référant à la définition des suites de Syracuse, la valeur suivant $1$ est $3 \times 1 + 1$ donc $4$. Or, $4$ est pair, donc la valeur suivante sera $2$ et rebelote, comme $2$ est pair, on retombe sur $1$ et le tout recommence à zéro. En général, quand on expose les différentes valeurs d'une suite de Syracuse, on s'arrête à $1$ ou alors on écrit $\bar{4 \rightarrow 2 \rightarrow 1}$.

Mais en admettant ceci, je conjecture que toutes les suites de Syracuse arrivent à $1$. Or, vous vous en doutez bien, il existe une infinité de suites de Syracuse car on peut partir de n'importe quelle valeur entière naturelle, et il en existe une infinité. Ce qu'il y a de bien embêtant pour les mathématiciens là dedans, c'est que jusqu'à présent, personne n'a réussi à démontrer que toute suite de Syracuse tombe à $1$. On admet ceci, on conjecture et cette conjecture porte justement un nom, c'est la conjecture de Syracuse.

Tout ce qu'on est en mesure de faire, et qu'on a déjà bien fait d'ailleurs, c'est de tester différentes valeurs et de constater que pour ces valeurs, on tombe effectivement à $1$. En janvier 2008, on a ainsi vérifié la conjecture de Syracuse pour toute valeur inférieure à $2^{62}$. Mais les mathématiciens ne se sentent toujours pas à l'abri d'un cas non-trivial. En effet, ils n'excluent pas la possibilité qu'une suite de Syracuse puisse soit diverger vers l'infini, soit tomber dans un autre cycle.

Les suites de Syracuse possèdent encore une autre particularité. On remarque qu'en partant de n'importe quelle valeur, la courbe représentant la suite commence par croitre avant de retomber "à la manière d'une feuille emportée par le vent". On parle du "vol de la suite" pour désigner la courbe de la suite sur un graphique. Le "temps de vol" de la suite de Syracuse du nombre $n$ désigne le nombre de valeurs de cette suite avant de tomber sur $1$, $1$inclue, $n$ exclue. "L'altitude maximale" désigne la plus grande valeur atteinte.

On se rend compte que si l'on a un nombre $n$ impair, alors $3 \times n + 1$ sera forcément un nombre pair. On peut donc anticiper en "compressant" le nombre de valeurs d'une suite de Syracuse en admettant que si $n$ est impair, alors la valeur suivante sera $\frac{3 \times n + 1}{2}$. On appelle ceci "suite de Syracuse compressée" et en admettant la conjecture, le cycle se répétant toujours serait $\bar{2 \rightarrow 1}$.

Voici le graphe de la suite de Syracuse compressée du nombre 15 : lien.

Implémentation (OCaml)

Nous venons de voir ce que sont exactement les suites de Syracuse. Je suppose donc que vous êtes à peu près au clair avec cette notion. Dans cette sous-partie, nous allons implémenter l'algorithme de génération des nombres de la suite de Syracuse voulue dans le langage fonctionnel OCaml sous la forme d'une fonction récursive.

En Ocaml, les fonctions se déclarent avec le mot clef let . Si la fonction est récursive, ce qui est bien le cas ici, on le précise avec le mot clef rec . Notre fonction prend en paramètre un entier $n$. On obtient déjà :

let rec syracuse n =

Ce code peut facilement se traduire par : "Soit syracuse une fonction récursive prenant en paramètre un entier n". Ensuite, il faut définir la fonction. On sait que si $n$ est pair, la prochaine valeur sera $n/2$, sinon, c'est à dire si $n$ est impair, la prochaine valeur sera $3 \times n + 1$. En gros, si $n$ est pair, on appelle syracuse(n/2) sinon on appelle syracuse(3*n+1). Le problème, c'est qu'avec cette définition de fonction, on n'a pas de condition d'arrêt. Pour la condition d'arrêt, ça va être un peu particulier, car on va devoir admettre la conjecture de Syracuse, c'est à dire qu'on va s'arrêter dès que $n$ vaut $1$. On obtient donc ceci (notez que j'utilise function , je n'explicite donc plus $n$) :

let rec syracuse = function
| 1 -> 1
| n when n mod 2 = 0 -> syracuse(n/2)
| n -> syracuse(3*n+1)

On peut même éviter la boucle infinie des appels récursifs qui survient quand l'utilisateur du programme envoie une valeur inférieure ou égale à $0$ en paramètre de la fonction et ce avec un petit test supplémentaire :

let rec syracuse = function
| 1 -> 1
| n when n <= 0 -> 1
| n when n mod 2 = 0 -> syracuse(n/2)
| n -> syracuse(3*n+1)

Testons cette fonction avec différentes valeurs.

# syracuse 3;;
- : int = 1
# syracuse 5;;
- : int = 1
# syracuse 42;;
- : int = 1
# syracuse 127;;
- : int = 1

En gros, on constate que la fonction nous retourne $1$ pour les valeurs $3$, $5$, $42$ et $127$. D'ailleurs vous pouvez tester toutes les valeurs jusqu'à $2^{62}$, vous tomberez toujours sur $1$.^^ Maintenant, nous allons afficher les différentes valeurs de la suite de Syracuse voulue. Il suffit d'apporter une toute petite modification au précédent code :

let rec syracuse n =
  print_int n; print_char ' ';
  match n with
  | 1 -> 1
  | n when n <= 0 -> 1
  | n when n mod 2 = 0 -> syracuse(n/2)
  | n -> syracuse(3*n+1)

Et on exécute :

# syracuse 3;;
3 10 5 16 8 4 2 1 - : int = 1
# syracuse 7;;
7 22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1 - : int = 1

C'est pas bien compliqué au final. Voilà, on a à peu près fait le tour de l'implémentation de l'algorithme. Ce que je vous conseille maintenant, c'est de faire quelques tests de votre coté. L'étude des suites de Syracuse se fait depuis assez longtemps maintenant sur ordinateur. Have a lot of fun !

Merci pour la lecture de ce tutoriel !

ShareMan

Exemple de certificat de réussite
Exemple de certificat de réussite