← Tous les textes du Grand Oral
MathsNSIHLP
Prenez un entier. S'il est pair, divisez-le par 2 ; s'il est impair, multipliez-le par 3 et ajoutez 1. Recommencez avec le résultat. Un enfant de dix ans sait appliquer cette règle. Pourtant, personne ne sait démontrer ce que tout le monde observe : quel que soit le nombre de départ, on finit toujours par tomber sur 1. Des ordinateurs l'ont vérifié pour des centaines de milliards de milliards de nombres, de très grands mathématiciens s'y sont attaqués, et la question reste ouverte depuis près de quatre-vingt-dix ans.
La conjecture de Syracuse est un terrain idéal pour comprendre ce qu'est une suite définie par récurrence, ce qu'est une démonstration et pourquoi des milliards de vérifications n'en sont pas une. Ce texte rassemble ces connaissances, avec les mathématiques de terminale : suites, raisonnement par récurrence et par l'absurde, divisibilité, logarithme, algorithmique. Il ne propose pas de Grand Oral tout fait : à chacun d'y choisir une direction et d'y construire sa question.
- La règle et trois vols calculés à la main
- Une suite définie par récurrence
- Ce que l'on sait démontrer en terminale
- Pourquoi la suite descend « en moyenne »
- Ce que disent les ordinateurs
- Ce que savent les chercheurs
- Les variantes $3n - 1$ et $5n + 1$
- Conjecture, vérification, démonstration
- Des directions pour construire sa question
On part d'un entier naturel $n \geqslant 1$ et l'on applique la règle :
- si le nombre est pair, on le divise par $2$ ;
- si le nombre est impair, on le multiplie par $3$ et on ajoute $1$.
$6$ est pair, on obtient $3$ ; $3$ est impair, on obtient $3 \times 3 + 1 = 10$ ; puis $5$, puis $3 \times 5 + 1 = 16$, puis $8$, $4$, $2$, $1$.
6 → 3 → 10 → 5 → 16 → 8 → 4 → 2 → 1
On arrive à $1$ en $8$ étapes, et le plus grand nombre rencontré est $16$.
7 → 22 → 11 → 34 → 17 → 52 → 26 → 13 → 40 → 20 → 10 → 5 → 16 → 8 → 4 → 2 → 1
Il faut $16$ étapes, et la suite monte jusqu'à $52$ avant de redescendre. Elle rejoint au passage la suite issue de 6 (à partir de $10$) : une fois que deux suites passent par le même nombre, elles sont identiques ensuite, puisque chaque terme ne dépend que du précédent.
Le nombre 27 est célèbre. Voici le début de sa suite :
27 → 82 → 41 → 124 → 62 → 31 → 94 → 47 → 142 → 71 → 214 → 107 → 322 → 161 → 484 → 242 → 121 → 364 → 182 → 91 → 274 → 137 → 412 → 206 → 103 → 310 → 155 → 466 → 233 → 700 → 350 → 175 → 526 → 263 → 790 → 395 → 1186 → 593 → 1780 → 890 → 445 → 1336 → 668 → 334 → 167 → 502 → 251 → 754 → 377 → 1132 → 566 → 283 → 850 → 425 → 1276 → 638 → 319 → 958 → 479 → 1438 → 719 → 2158 → 1079 → 3238 → 1619 → 4858 → 2429 → 7288 → 3644 → 1822 → 911 → 2734 → 1367 → 4102 → 2051 → 6154 → 3077 → 9232 → …
Partie de 27, la suite monte jusqu'à $9\,232$ (à la $77$e étape), soit plus de $340$ fois sa valeur de départ, puis elle redescend et atteint $1$ après $111$ étapes. Le nombre 26, juste avant, arrive à $1$ en $10$ étapes. Rien, dans l'écriture de 27, ne laissait prévoir un tel voyage : c'est ce comportement imprévisible qui rend le problème si difficile.
La figure trace la suite pour le nombre de départ choisi : en abscisse le numéro de l'étape, en ordonnée la valeur. Essayez 27, puis 97, 703 ou 871.
Notons $f$ la fonction définie sur les entiers naturels non nuls par
$$f(n) = \begin{cases} \dfrac{n}{2} & \text{si } n \text{ est pair,} \\[2mm] 3n + 1 & \text{si } n \text{ est impair.} \end{cases}$$Pour un entier de départ $N \geqslant 1$, la suite de Syracuse de $N$ est la suite $(u_k)$ définie par
$$u_0 = N$$et, pour tout entier naturel $k$,
$$u_{k+1} = f(u_k).$$C'est une suite définie par récurrence, comme celles du cours, avec une fonction $f$ définie « par morceaux » selon la parité. On utilise un vocabulaire imagé, venu de l'aviation :
- le vol de $N$ est la suite des valeurs $u_0$, $u_1$, $u_2$, … ;
- la durée de vol est le plus petit $k$ tel que $u_k = 1$ (8 pour 6, 16 pour 7, 111 pour 27) ;
- l'altitude maximale est la plus grande valeur atteinte (16, 52 et 9 232) ;
- la durée de vol en altitude est le nombre d'étapes pendant lesquelles la suite reste strictement au-dessus de $N$.
Pour tout entier $N \geqslant 1$, il existe un entier $k$ tel que $u_k = 1$.
Autrement dit : tous les vols ont une durée finie.
Deux choses pourraient la rendre fausse : un vol qui monte indéfiniment (une suite qui tend vers $+\infty$), ou un vol qui tourne en rond sur un cycle ne contenant pas $1$. Personne n'a jamais trouvé ni l'un ni l'autre, et personne n'a démontré qu'ils n'existent pas.
On ne sait pas démontrer la conjecture, mais on peut démontrer beaucoup de choses vraies sur ces suites, avec les outils du cours.
Exemple. $f(1) = 3 \times 1 + 1 = 4$, $f(4) = 2$, $f(2) = 1$ : on retombe sur $1$ après trois étapes.
Initialisation. Pour $m = 0$, $u_{k} = 1$ par hypothèse.
Hérédité. Supposons $u_{k+3m} = 1$ pour un certain $m$. Alors $u_{k+3m+1} = f(1) = 4$, $u_{k+3m+2} = f(4) = 2$ et $u_{k+3m+3} = f(2) = 1$, c'est-à-dire $u_{k+3(m+1)} = 1$.
Conclusion. Par récurrence, la propriété est vraie pour tout entier $m \geqslant 0$ : une fois arrivée à 1, la suite répète indéfiniment le cycle $1 \to 4 \to 2 \to 1$. C'est pourquoi on arrête le vol au premier passage par 1.
Exemple. $32 \to 16 \to 8 \to 4 \to 2 \to 1$ : avec $32 = 2^5$, la durée de vol est $5$.
Initialisation. $u_0 = 2^p = 2^{p-0}$.
Hérédité. Supposons $u_k = 2^{p-k}$ avec $k < p$. Alors $p - k \geqslant 1$, donc $u_k$ est pair, et $u_{k+1} = \dfrac{2^{p-k}}{2} = 2^{p-(k+1)}$.
Conclusion. En particulier $u_p = 2^0 = 1$, et pour $k < p$, $u_k = 2^{p-k} \geqslant 2$ : la durée de vol est exactement $p$.
Une conséquence : il existe des durées de vol aussi grandes qu'on veut, puisque $2^p$ a une durée de vol égale à $p$. Et dès qu'une suite tombe sur une puissance de 2, elle est sauvée. C'est ce qui arrive à 7, qui atteint $16 = 2^4$.
Si $N$ est pair, $u_1 = \dfrac{N}{2} < N$ : la suite passe tout de suite sous son départ.
Exemple. $13 = 4 \times 3 + 1$ : $13 \to 40 \to 20 \to 10$, et $10 < 13$.
Étape 1. $N = 2 \times 2k + 1$ est impair, donc $u_1 = 3(4k + 1) + 1 = 12k + 4$.
Étape 2. $12k + 4 = 2(6k + 2)$ est pair, donc $u_2 = 6k + 2$, qui est encore pair : $u_3 = 3k + 1$.
Étape 3. $N - u_3 = (4k + 1) - (3k + 1)$ $= k > 0$, donc $u_3 < N$.
Le même calcul, poussé plus loin, montre par exemple que tout $N = 16k + 3$ avec $k \geqslant 1$ descend sous lui-même en six étapes :
$$\begin{aligned} &16k + 3 \to 48k + 10 \to 24k + 5 \\ &\to 72k + 16 \to 36k + 8 \\ &\to 18k + 4 \to 9k + 2, \end{aligned}$$et $9k + 2 < 16k + 3$. Plus on regarde de chiffres de l'écriture en base 2 du nombre de départ, plus on trouve de familles qui descendent à coup sûr. Il reste toujours des cas non réglés, comme $N = 4k + 3$ en général, et c'est là que tout bloque.
Pourquoi s'intéresser au premier passage sous le départ ? Parce que cela suffirait à démontrer la conjecture.
Raisonnement par l'absurde. Supposons qu'il existe des entiers dont le vol n'atteint jamais $1$. Parmi eux, il y en a un plus petit (toute partie non vide de $\mathbb{N}$ a un plus petit élément) ; appelons-le $N$. On a $N \geqslant 2$, puisque le vol de 1 est déjà arrivé.
Étape 1. Par hypothèse, le vol de $N$ passe par un nombre $M < N$ : il existe $j$ tel que $u_j = M$.
Étape 2. $M$ est plus petit que $N$, qui est le plus petit « mauvais » nombre : le vol de $M$ atteint donc $1$.
Étape 3. À partir du rang $j$, le vol de $N$ est exactement le vol de $M$ (chaque terme ne dépend que du précédent). Il atteint donc $1$, ce qui contredit le choix de $N$.
Conclusion. Il n'existe aucun « mauvais » nombre.
D'après ce qui précède, la conjecture se ramène donc aux nombres de la forme $4k + 3$ : les nombres pairs et les nombres $4k + 1$ passent forcément sous leur départ. C'est aussi ce qui accélère les vérifications par ordinateur : en testant les nombres dans l'ordre, il suffit de suivre chaque vol jusqu'à ce qu'il passe sous son départ.
Quand $n$ est impair, $3n + 1$ est toujours pair (un impair fois un impair est impair, plus 1 donne un pair). On peut donc regrouper les deux étapes et utiliser la version « accélérée »
$$T(n) = \begin{cases} \dfrac{n}{2} & \text{si } n \text{ est pair,} \\[2mm] \dfrac{3n + 1}{2} & \text{si } n \text{ est impair.} \end{cases}$$Pour un grand nombre $n$, une étape multiplie donc la valeur par environ $\frac{1}{2}$ si $n$ est pair, et par environ $\frac{3}{2}$ s'il est impair. Faisons une hypothèse qui n'est pas démontrée : les termes successifs se comportent comme si leur parité était tirée à pile ou face, pair et impair ayant chacun la probabilité $\frac{1}{2}$.
Sur $2m$ étapes, on aurait alors « en moyenne » $m$ étapes paires et $m$ étapes impaires, donc une multiplication par environ
$$\left(\frac{3}{2}\right)^m \times \left(\frac{1}{2}\right)^m = \left(\frac{3}{4}\right)^m.$$Comme $0 < \frac{3}{4} < 1$, la suite géométrique $\left(\frac{3}{4}\right)^m$ tend vers $0$ : le vol devrait finir par descendre. Le logarithme dit la même chose en transformant le produit en somme : chaque étape ajoute $\ln\frac{1}{2} \approx -0{,}693$ ou $\ln\frac{3}{2} \approx 0{,}405$ au logarithme de la valeur, ce qui fait en moyenne
$$\frac{1}{2}\ln\frac{3}{2} + \frac{1}{2}\ln\frac{1}{2} = \frac{1}{2}\ln\frac{3}{4} \approx -0{,}144$$par étape. Le logarithme de la valeur perd environ $0{,}144$ par étape : la valeur est divisée en moyenne par $\mathrm{e}^{0{,}144} \approx 1{,}15$ à chaque étape.
La suite de Syracuse n'a rien d'aléatoire : chaque terme est entièrement déterminé par le précédent. L'hypothèse du pile ou face est une modélisation, qui explique pourquoi la conjecture est plausible, mais qui ne dit rien d'un nombre de départ particulier. Un seul nombre dont le vol aurait « toujours de la chance » (trop d'étapes impaires) suffirait à rendre la conjecture fausse.
On peut confronter ce modèle aux vrais vols. Le programme suivant calcule, pour tous les départs impairs d'un intervalle, la proportion d'étapes impaires dans la version accélérée, et la variation moyenne du logarithme par étape.
On obtient une proportion d'étapes impaires d'environ $0{,}506$ et une variation moyenne d'environ $-0{,}134$, proches des valeurs du modèle ($0{,}5$ et $-0{,}144$). Le petit écart s'explique : les vols qui comptent un peu plus d'étapes impaires que la moyenne durent plus longtemps, et pèsent donc davantage dans le décompte de toutes les étapes. Le modèle décrit bien le comportement d'ensemble, sans rien démontrer pour un départ donné.
Calculer un vol est un travail idéal pour un ordinateur. Le programme suivant calcule la durée de vol de chaque départ jusqu'à $N$ et affiche les records : les départs dont la durée de vol dépasse celle de tous les nombres plus petits.
On retrouve 27 et ses 111 étapes, puis notamment 97 (118 étapes), 871 (178 étapes) et, sous $10\,000$, le record de 6 171 avec 261 étapes. Le nuage ci-dessous place chaque départ $n$ en abscisse et sa durée de vol en ordonnée.
Les vérifications à grande échelle sont allées beaucoup plus loin. En 2020-2021, le Tchèque David Barina a publié une vérification de tous les départs jusqu'à $2^{68} \approx 2{,}95 \times 10^{20}$, grâce à des algorithmes très optimisés (qui utilisent les réductions de la section précédente et l'écriture en base 2) exécutés sur des cartes graphiques. Aucun contre-exemple. Mais $2^{68}$ n'est rien à côté de l'infinité des entiers : les nombres vérifiés forment un ensemble fini, et un ensemble fini représente une proportion nulle de tous les entiers.
On attribue le problème au mathématicien allemand Lothar Collatz, qui s'intéressait vers 1937, alors étudiant, aux itérations de fonctions sur les entiers. Il n'a rien publié sur ce sujet, et le problème a circulé de bouche à oreille. Dans les années 1950, Helmut Hasse en parle à l'université de Syracuse, dans l'État de New York, d'où le nom français ; on dit aussi problème de Collatz, problème $3x + 1$, problème de Kakutani ou d'Ulam, selon les personnes qui l'ont fait connaître. Ces dates et ces attributions sont celles que rapportent les historiens du problème, notamment Jeffrey Lagarias ; elles reposent en partie sur des souvenirs.
On raconte que, dans les années 1960, le problème a tellement occupé les universités américaines que Shizuo Kakutani a parlé, en plaisantant, d'un complot pour ralentir la recherche mathématique aux États-Unis. Et Paul Erdős, l'un des mathématiciens les plus prolifiques du XXe siècle, aurait dit : « les mathématiques ne sont pas encore prêtes pour de tels problèmes ».
- Terras, 1976. Riho Terras démontre que « presque tous » les entiers passent sous leur départ : la proportion des entiers de 1 à $N$ qui n'y parviennent pas tend vers $0$ quand $N$ tend vers $+\infty$. C'est le prolongement rigoureux des calculs sur $4k + 1$ et $16k + 3$ faits plus haut. « Presque tous » ne veut pas dire « tous » : une infinité d'exceptions reste possible, à condition qu'elles soient de plus en plus rares.
- Conway, 1972. John Conway montre que certaines généralisations du problème (avec d'autres règles selon le reste de la division par un entier fixé) sont indécidables : aucun algorithme ne peut répondre à la question pour toutes les règles de ce type. Cela ne dit rien de la règle $3n + 1$ elle-même, mais montre que la famille de problèmes à laquelle elle appartient peut être hors d'atteinte.
- Tao, 2019. Terence Tao, médaille Fields 2006, démontre un résultat beaucoup plus fort que celui de Terras. Choisissons n'importe quelle fonction $f$ qui tend vers $+\infty$, même très lentement, par exemple $f(N) = \ln(\ln N)$. Alors, pour « presque tous » les départs $N$ (en un sens précis), le vol de $N$ finit par descendre sous $f(N)$ : presque tous les vols descendent presque jusqu'en bas. C'est, selon les spécialistes, l'avancée la plus importante depuis des décennies, et Tao lui-même rappelle qu'elle laisse la conjecture ouverte.
Pourquoi croire à la conjecture plutôt qu'à son contraire ? Une bonne manière de tester son intuition est de changer légèrement la règle.
Remplaçons $3n + 1$ par $3n - 1$ pour les nombres impairs. Départ à 5 :
5 → 14 → 7 → 20 → 10 → 5
La suite revient à 5 sans jamais passer par 1 : c'est un cycle de longueur 5. Il en existe un autre, de longueur 18, qui passe par 17 :
17 → 50 → 25 → 74 → 37 → 110 → 55 → 164 → 82 → 41 → 122 → 61 → 182 → 91 → 272 → 136 → 68 → 34 → 17
Pour cette règle voisine, l'énoncé « tout vol atteint 1 » est donc faux. Remarque : la règle $3n - 1$ sur les entiers positifs revient exactement à la règle $3n + 1$ sur les entiers négatifs (changer $n$ en $-n$) ; la conjecture de Syracuse ne porte que sur les entiers positifs.
Avec $5n + 1$ pour les impairs, 13 entre dans un cycle de longueur 10 qui ne passe pas par 1 :
13 → 66 → 33 → 166 → 83 → 416 → 208 → 104 → 52 → 26 → 13
Et le vol de 7 semble monter sans fin : après 200 étapes, il dépasse 9 milliards. Le modèle du pile ou face l'explique : la multiplication moyenne sur deux étapes devient $\frac{5}{2} \times \frac{1}{2} = \frac{5}{4} > 1$, et la suite géométrique $\left(\frac{5}{4}\right)^m$ tend vers $+\infty$. Mais là encore, personne ne sait démontrer que le vol de 7 ne redescend jamais.
Le programme suivant cherche les cycles de la règle $an + b$ pour de petits départs ; on peut changer $a$ et $b$.
Une conjecture est un énoncé que l'on pense vrai, souvent appuyé sur de nombreux exemples, mais qui n'est pas démontré. En mathématiques, aucune quantité d'exemples ne remplace une démonstration, et l'histoire en donne des exemples frappants.
- Le polynôme d'Euler. $n^2 + n + 41$ est un nombre premier pour $n = 0$, $1$, …, $39$ : quarante vérifications réussies. Pourtant, pour $n = 40$, $40^2 + 40 + 41$ $= 40 \times 41 + 41$ $= 41^2$, qui n'est pas premier.
- La conjecture de Pólya (1919). Disons qu'un entier est de type « impair » s'il s'écrit comme produit d'un nombre impair de facteurs premiers, comptés avec leur multiplicité ($12 = 2 \times 2 \times 3$ en a trois), et de type « pair » sinon. George Pólya pensait que, de 1 à $N$ (pour $N \geqslant 2$), les entiers de type impair sont toujours au moins aussi nombreux que ceux de type pair. C'est vrai pour tous les $N$ jusqu'à plus de $900$ millions : le premier contre-exemple, trouvé en 1980, est $N = 906\,150\,257$.
La conjecture de Syracuse a été vérifiée bien plus loin, jusqu'à $2^{68}$, mais un contre-exemple éventuel pourrait être encore plus grand. Elle pose ainsi des questions qui intéressent aussi la philosophie : qu'est-ce qu'une preuve, et en quoi diffère-t-elle d'une expérience répétée ? Peut-on « savoir » qu'un énoncé est vrai sans l'avoir démontré ? Une règle si simple peut-elle produire des questions sans réponse, comme le suggère le résultat de Conway sur les généralisations indécidables ?
Ce texte n'est pas un Grand Oral. Il rassemble des connaissances dans lesquelles chacun peut choisir une direction, la creuser et formuler sa propre question. Quelques directions possibles :
- Mathématiques : les suites définies par récurrence avec une fonction par morceaux ; le raisonnement par récurrence (cycle 4-2-1, puissances de 2) et par l'absurde (le plus petit contre-exemple) ; la divisibilité et les familles $4k + 1$, $16k + 3$ ; le modèle probabiliste, la suite géométrique $\left(\frac{3}{4}\right)^m$ et le logarithme ; la comparaison avec les variantes $3n - 1$ et $5n + 1$.
- NSI : boucles, fonctions et efficacité des programmes de vérification ; réutiliser les résultats déjà calculés (mémoïsation) ; le calcul en base 2 ; la notion d'indécidabilité (Turing, Conway).
- Philosophie : vérifier et démontrer ; l'induction (au sens des sciences expérimentales) face à la preuve ; les limites de la connaissance mathématique.
Le jury peut interroger sur les chapitres de spécialité mobilisés. Avec ce thème, il est utile de connaître parfaitement : les suites
définies par récurrence et leur représentation ; le raisonnement par récurrence ; le raisonnement par l'absurde ; les suites
géométriques et leur limite selon la raison ; les propriétés de la fonction logarithme (produit et somme) ; la parité et la
divisibilité ; les boucles while et for en Python.
Pour réviser ces chapitres, l'application Maths FlashBac reprend tout le cours de spécialité en cartes.
- Conjecture de Syracuse et conjecture de Pólya (Wikipédia).
- Sur ce site : Suites récurrentes et chaos, La spirale d'Ulam et les nombres premiers (le polynôme d'Euler), Aristote et l'infini et l'animation suites définies par récurrence.