Aller au menu - Aller au contenu

Icône Les suites de Syracuse

Par Avatar shareman
Mise à jour : 24/05/2009
Difficulté : Facile Facile Creative Commons BY-SA
178 visites depuis 7 jours, classé 441/795
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.
Retour en haut
Sommaire du tutoriel :
Icône du chapitre
Retour en haut

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, 1inclue, 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.
Retour en haut

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à :
Code : OCaml
1
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) :
Code : OCaml
1
2
3
4
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 :
Code : OCaml
1
2
3
4
5
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.
Code : OCaml
1
2
3
4
5
6
7
8
# 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 :
Code : OCaml
1
2
3
4
5
6
7
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 :
Code : OCaml
1
2
3
4
# 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 !
Retour en haut
Merci pour la lecture de ce tutoriel !

ShareMan
Retour en haut

Partager

Retour en haut
39 commentaires pour "Les suites de Syracuse"
Note moyenne : 3.78 / 4 (9 votes)
Pseudo Commentaire
Hors ligne 666by # Posté le 20/09/2009 à 22:43:22
Avatar

Avis : Très bon

je me suis amuser a trouver un petit calcul pour éviter d'avoir a faire des condition (mon ordinateur n'a pas encore fait d'erreur avec le calcul mais si vous trouver une erreur dans le calcul prévenez moi) :
Code : C
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
int syracuse(unsigned int n, unsigned int *TempVol, unsigned int *AltMax)
{
    unsigned int x = n&1;
    unsigned int tps = 0;
    unsigned int max = n;

    while(n > 1)
    {
        x = n&1;
        n = (n*3+1)*x + n/2*!x; // on peut remplacer les '!x' par des '(x^1)' ou par des '0 exposant x'
        tps++;
        if(max < n)
            max = n;
    }

    if(TempVol != 0)
        *TempVol = tps;

    if(AltMax != 0)
        *AltMax = max;

    return 0;
}

je trouve que le calcul est plus facile a implémenter en assembleur que les conditions

EDIT:
C'est tout a fait normale que l'on retombe tout le temps sur 1 parce que:
si on tombe sur un nombre impair on le multiplie par 3,il et toujours impair mais certain bits sont passer de 1 à 0 jusqu'au moment ou tous les bits sont a 0 sauf le premier donc c'est une puissance de 2 et la on fait que diviser par 2, par exemple:

3 = 11b
3*3+1 = 10 = 1010b
10/2 = 5 = 101b
5*3+1 = 16 = 10000b
16/2 = 8 = 1000b
8/2 = 4 = 100b
4/2 = 2 = 10b
2/2 = 1 = 1b
1*3+1 = 4 = 100b
...
- Pourquoi on inventerai pas la bêtise artificiel ?
- Elle est déjà trop présente naturellement.
 
Hors ligne tit_toinou # Posté le 23/02/2011 à 16:17:07

Ton raisonnement ne tient pas.
Tu n'as pas prouvé le moment "où tous les bits sont a 0 sauf le premier donc c'est une puissance de 2".
Ton exemple est un cas spécial.
Image utilisateur

Image utilisateur jQuery : écrivez moins pour faire plus !
 
Hors ligne 666by # Posté le 08/05/2011 à 16:37:06
Avatar

Avis : Très bon

Si tous les bits sont a 0 sauf le premier c'est normal que sa soit une puissance de 2 non ?

Maintenant si y (l'altitude) est une puissance de 2 alors le programme ne va faire que diviser par 2 or quand je regarde les graphes des suites de Syracuse (avec y la valeur de l'altitude par rapport au nombre d'itération x) on voit qu'il y a un/de grand(s) 'envole(s)' (suppression des 1 dans y) puis (quand y devient une puissance de 2) il y a une grande descente jusqu’à y = 1.
- Pourquoi on inventerai pas la bêtise artificiel ?
- Elle est déjà trop présente naturellement.
 
Hors ligne Leryan # Posté le 10/09/2011 à 00:02:06
§ HAVE FUN AND FUCK DA WAY §
Avatar

Études : IUT Nancy-brabois

 666by : ton algorithme devient de moins en moins performant au fur et à mesure que les nombres grandissent, 10 minutes avec tests pour aller jusque 1412987847 (1000 termes dans la suite) contre 23 pour le tiens.
Hors ligne 666by # Posté le 23/09/2011 à 19:06:05
Avatar

Avis : Très bon

C’était juste pour le plaisir d’implémenter les suites sans aucune conditions

D'ailleurs j'ai trouver plus marrant avec le sinus et le cosinus

Pour les suites compressées:
( (3x+1)*sin(x*pi/2)^2 + x*cos(x*pi/2)^2 )/2

Pour les suites non compressées
(3x+1)*sin(x*pi/2)^2 + x/2*cos(x*pi/2)^2

Où 'x^2' signifie 'x puissance 2'

Sa ralentit encore plus l'ordinateur mais au moins la courbe est continue maintenant
- Pourquoi on inventerai pas la bêtise artificiel ?
- Elle est déjà trop présente naturellement.
 

Voir tous les commentaires