Etude de la fonction de Syracuse

Vous êtes ici : Accueil / Cours / Dossiers mathématiques / La conjecture de Syracuse

Dans cette partie seront démontrés quelques résultats personnels.

Pour les démonstrations qui vont suivre, nous aurons recours à une des variantes de la suite de Syracuse :

$(u_n) = \left \{ \begin{array}{lr} u_0\\ u_{n+1} = \frac{3u_n+1}{2^{a_{n+1}}} \end{array} \right.$

avec $u_0$ un nombre impair et $a_{n+1}$ la plus grande puissance de 2 tel que $2^{a_{n+1}}$ divise $3u_n+1$

La suite précédente est souvent présentée comme la fonction de Syracuse suivante :

$f( n ) = \frac{3n+1}{2^{sup(n)}}$

Avec $sup(n)$ la plus grande puissance de 2 telle que $2^{sup(n)}$ divise $3n+1$ . Cependant, nous avons préféré la présenter sous forme d’une suite pour pouvoir mettre en relief les liens entre les suites $(a_n)$ et $(u_n)$ .

Etude de la suite $(a_n)$

Dans cette partie, nous allons étudier la suite $(a_n)$ .

La notion de suite périodique est à prendre au sens large, c’est-à-dire qu’il existe un rang à partir duquel la suite sera périodique.

Autrement dit : $\exists T \in \mathbf{N^*}, \exists N \in \mathbf{N}, \forall n \in \mathbf{N}, n > N \Rightarrow u_{n+T} = u_n$

Commençons par construire quelques égalités que l’on aura à réutiliser à plusieurs occasions sous plusieurs formes. Elles seront donc considérées comme acquises.

Le $n$ ième terme de la suite est de la forme suivante :

$u_n = \frac{3 ... \left(\frac{3\left(\frac{3u_0+1}{2^{a_1}}\right)+1}{2^{a_2}}\right) ... +1}{2^{a_n}}$

En développant la fraction, nous obtenons

$u_n = \frac{3^nu_0}{2^{a_1+a_2+...+a_n}} + \frac{3^{n-1}}{2^{a_1+a_2+...+a_n}} + \frac{3^{n-2}}{2^{a_2+...+a_n}} + ... + \frac{1}{2^{a_n}}$

Ou en l’écrivant autrement :

$u_n = \frac{3^nu_0}{\prod_{i=1}^{n} 2^{a_i}} + \sum_{i=0}^{n-1} \frac{3^{i}}{\prod_{j=0}^{i} 2^{a_{n-j}}}\ \ \ (1)$

En multipliant par $\prod_{i=1}^{n} 2^{a_i}$ chaque membre de l’égalité, nous obtenons

$\left(\prod_{i=1}^{n} 2^{a_i}\right)u_n = 3^nu_0 + \sum_{i=0}^{n-1} \left(3^{i}\prod_{j=1}^{n-i-1} 2^{a_j}\right)\ \ \ (2)$

Si la suite $(u_n)$ est périodique de période $n$ , alors $u_n = u_0$ . En reportant dans (1), et en mettant $u_0$ en facteur, nous obtenons

$u_0\left(1-\frac{3^n}{\prod_{i=1}^{n} 2^{a_i}}\right) = \sum_{i=0}^{n-1} \frac{3^{i}}{\prod_{j=0}^{i} 2^{a_{n-j}}}\ \ \ (3)$

En reportant $u_n = u_0$ dans (2) et en mettant $u_0$ en facteur, nous obtenons

$\left(\prod_{i=1}^{n} 2^{a_i} -3^n\right)u_0 = \sum_{i=0}^{n-1} \left(3^{i}\prod_{j=1}^{n-i-1} 2^{a_j}\right)\ \ \ (4)$

Proposition 1 : Si la suite $(a_n)$ est la suite constante 1, ou ne contient aucune occurrence égale à 1, alors la suite $(u_n)$ vérifie la conjecture de Syracuse

Démonstration :

Si $a_{n+1}>1$ pour tout $n$ , alors $u_{n+1} = \frac{3u_n+1}{2^{a_n}} < u_n$ si $u_n > 1$ . Sachant que la suite $(u_n)$ est minorée par 1 et est à valeurs dans $\mathbf{N}$ , donc elle va devenir stationnaire et va valoir 1.

Si $a_n = 1$ pour tout $n$ , alors $\forall n \in \mathbf{N}, u_{n+1} = \frac{3u_n+1}{2}$

Reprenons l’égalité (1) en remplaçant les $a_i$ par 1

$u_n = \frac{3^nu_0}{2^n} + \sum_{i=0}^{n-1} \frac{3^{i}}{2^{i+1}}$

Le second terme étant la somme des $n$ premiers termes d’une suite géométrique de premier terme $v_0 = \frac{1}{2}$ et de raison $\frac{3}{2}$

$u_n = \left(\frac{3}{2}\right)^nu_0 + \frac{1}{2}\left(\frac{1-\left(\frac{3}{2}\right)^n}{1-\frac{3}{2}}\right)$

En simplifiant le membre de droite, l’égalité devient :

$u_n = \left(\frac{3}{2}\right)^nu_0 + \left(\frac{3}{2}\right)^n-1$

En multipliant par $2^n$ de part et d’autre

$2^nu_n = 3^n(u_0 + 1) - 2^n$

Ainsi $2^n$ divise $3^n(u_0+1)$ or est premier avec $3^n$ , donc d’après le théorème de Gauss, $2^n$ divise $u_0+1$ et cela pour tout entier naturel n. 0 est le seul nombre divisible par toutes les puissances de 2, donc $u_0 + 1 = 0$ , or $u_0$ est un entier naturel, donc cela est impossible.

Proposition 2 : Si $(a_n)$ est une suite stationnaire, alors $(u_n)$ vérifie la conjecture de Syracuse.

Démonstration :

Si $(a_n)$ vaut 1 à partir d’un certain rang, il suffit d’appliquer la proposition 5.
Si $(a_n)$ vaut $k$ , $k \not = 1$ à partir d’un certain rang, alors la suite ne contient aucune occurrence de 1 à partir d’un certain rang. La proposition 5 s’applique encore.

Proposition 3 : Soit une suite de Syracuse, périodique et ne vérifiant pas la conjecture de Syracuse, alors la période est strictement supérieure à 1.

Démonstration :

Raisonnons par l’absurde : si la suite a une période égale à 1, alors $a_i$ est stationnaire. La proposition 2 nous permet donc de dire qu’elle vérifie alors la conjecture de Syracuse.

Théoreme 4 : La suite $(u_n)$ est une suite périodique si et seulement si la suite $(a_n)$ est périodique.

Démonstration :

Dans le sens direct, l’implication est triviale. En effet, si $(u_n)$ est périodique, alors sachant que pour chaque terme $u_n$ , il n’existe qu’un seul entier naturel tel que ce soit la puissance de 2 la plus grande divisant $3u_n+1$ , la suite $(a_n)$ sera également périodique.

Démontrons la réciproque :

Soit $k$ la période de la suite $(a_n)$ . Alors, la sous-suite $(v_n)$ donnée par $v_n = u_{k*n}$ est une suite arithmético-géométrique.

Elle peut être écrite sous la forme

$v_{n+1} = \frac{3 ... \left(\frac{3\left(\frac{3v_n+1}{2^{a_1}}\right)+1}{2^{a_2}}\right) ... +1}{2^{a_k}}$

Donc

$v_{n+1} = \frac{3^kv_n}{\prod_{i=1}^{k} 2^{a_i}} + \sum_{i=0}^{k-1} \frac{3^{i}}{\prod_{j=0}^{i} 2^{a_{k-j}}}$

Notons $v_{n+1} = A v_n + B$ avec $A=\frac{3^k}{\prod_{i=1}^{k} 2^{a_i}}$ et $B=\sum_{i=0}^{k-1} \frac{3^{i}}{\prod_{j=0}^{i} 2^{a_{k-j}}}$

Exprimons $v_n$ en fonction de $v_0$ , donc de $u_0$

$v_n = A^nv_0 + \sum_{i=0}^{n-1} A^iB$

Nous retrouvons à droite la somme des $n$ premiers termes d’une suite géométrique.

$v_n = A^nv_0 + B\left(\frac{1-A^n}{1-A}\right)$

En multipliant par $(1-A)$ chaque membre de l’égalité :

$(1-A)v_n = (1-A)A^nv_0 + B\left(1-A^n\right)$

$(1-A)v_n = A^n\left( (1-A)v_0 -B \right) + B$

Or $A=\frac{3^C}{2^D}$ avec $D > 0$ , donc

$(1-A)v_n = \left(\frac{3^C}{2^D}\right)^n\left( (1-A)v_0 -B \right) + B$

En multipliant par $\left(2^D\right)^n$ de part et d’autre :

$\left(2^D\right)^n(1-A)v_n = \left(3^C\right)^n\left( (1-A)v_0 -B \right) + \left(2^D\right)^nB\ \ \ (5)$

Donc $\left(2^D\right)^n$ divise $\left(3^C\right)^n\left( (1-A)v_0 -B \right)$

or est premier avec $\left(3^C\right)^n$ , donc d’après le théorème de Gauss, $\left(2^D\right)^n$ divise $(1-A)v_0 -B$

et cela pour tout entier naturel n. Donc $(1-A)v_0 -B = 0$

Ainsi, en reportant dans (5) :

$\left(2^D\right)^n(1-A)v_n = \left(2^D\right)^nB$

Donc

$(1-A)v_n = B$

La suite $(v_n)$ est donc une suite constante, donc la suite $(u_n)$ est périodique.

Proposition 5 : Pour tout terme $u_n$ , si $a_n$ est pair, alors $u_n$ est de la forme $6k+1$ , sinon il est de la forme $6k+5$ .

Démonstration :

Reprenons l’égalité (2) et changeons la somme de côté :

$3^nu_0 = \left(\prod_{i=1}^{n} 2^{a_i}\right)u_n - \sum_{i=0}^{n-1} \left(3^{i}\prod_{j=1}^{n-i-1} 2^{a_j}\right)$

Tous les termes de la somme sont multiples de 3 sauf pour $i=0$ . Ainsi,

$\left(\prod_{i=1}^{n} 2^{a_i}\right)u_n - \prod_{i=1}^{n-1} 2^{a_i} \equiv 0\ [3]$

Or $2 \equiv -1\ [3]$ et $2^2 \equiv 1\ [3]$

Il se présente 4 cas. Examinons-les un par un :

Si la somme des $a_i$ est paire et $a_n$ aussi $u_n - 1 \equiv 0\ [3]$
Si la somme des $a_i$ est paire mais pas $a_n$ $u_n + 1 \equiv 0\ [3]$
Si la somme des $a_i$ est impaire et $a_n$ aussi $-u_n + 1 \equiv 0\ [3]$ .
Si la somme des $a_i$ est impaire mais pas $a_n$ $-u_n - 1 \equiv 0\ [3]$ .

Ainsi, lorsque $a_n$ est pair, $u_n \equiv 1\ [3]$ et lorsque $a_n$ est impair, $u_n \equiv 2\ [3]$ . Lorsque $a_n$ est pair, $u_n$ est donc de la forme $3k+1$ et sinon est de la forme $3k+2$ .

Comme $u_n$ est un nombre impair, il s’ensuit que s’il est de la forme $3k+1$ , alors $k$ est pair et que s’il est de la forme $3k+2$ , $k$ est impair. Nous obtenons donc le résultat de la proposition.

Longueur minimale des cycles

Nous allons ici mettre en relation la longueur minimale des cycles non-triviaux de Syracuse et la vérification empirique de la conjecture.

Commentaires

rollandfrederic480@neuf.fr a dit le 17 juillet 2008

Je pense avoir résolu syracuse. Si cela vous intéresse,je peux vous l’envoyer.
Auriez-vous l’adresse e mail de Jean-Paul Delahaye ,je n’ai pas réussi à la trouver sur le net
frederic

Ludovic PATEY a dit le 17 juillet 2008

Bonjour, Les coordonnées de Jean-Paul Delahaye sont

Tél. : (33) 03-28-77-85-64
Fax : (33) 03-28-77-85-37
Email : jean-paul.delahaye hat lifl.fr
http://www.lifl.fr

Pourriez-vous également m’envoyer la preuve ? Je suis curieux d’en prendre connaissance. Mon adresse email est ludovic.patey hat supinfo.com

frederic rolland a dit le 19 juillet 2008

Bonjour et merci pour les coordonnées de Jean-Paul Delahaye.
Pour la preuve, voir http://conjectures.blogvie.com/
Il reste encore une grosse lacune. Je sais comment syracuse fonctionne, mais je ne sais pas encore pourquoi elle fonctionne ainsi.
La formule donnant la distribution des durées de vol en altitude peut surprendre par sa simplicité bien qu’elle soit encore inexpliquée.
Quand je saurais pourquoi 1/2 après m=0 devient 1/4 après m=1 puis 1/8 après m=3 etc... alors il s’agira vraiment d’une preuve.
La raréfaction des fractions intéressantes et l’augmentation rapide des espaces de nombres consécutifs donnant un fractionnement exact et non une moyenne peuvent expliquer pourquoi cette formule n’a pas été trouvée par les ordinateurs.
Vous pouvez laisser un message sur mon blog
ou à cette adresse rollandfrederic480@neuf.fr

Dossiers mathématiques

La conjecture de Syracuse

Annonces

Derniers articles

Articles populaires

Liens

Accueil

Envoyer à un ami

Télécharger

Plan du site

Rechercher

Le site

Divers