Ci-après, petite réflexion sur cette fameuse conjecture qui nargue le monde des mathématiciens depuis longtemps.
De nombreuses imperfections dans la présentation, j'espère que ça ne découragera pas les plus passionnés.
Bonne lecture à tous.
La conjecture de Syracuse énonce que cette suite revient toujours à 1:
On prend un nombre quelconque, s'il est pair, on le divise par 2, s'il est impair, on le multplie par 3 et on lui ajoute 1.
On applique cette règle au nouveau nombre obtenu pour en obtenir un autre et ainsi de suite.
L'une des possibilités pour qu'un nombre traité par cet algorithme ne revienne pas à 1 est qu'il revienne sur lui même dans une boucle. N donne N après un certain nombre d'opérations.
Tentons de démontrer l'impossibilité de construire une boucle autre que 1,4,2,1.
S'il existe une boucle, son plus petit nombre est impair.
Soit D=2n-1 ce nombre, avec n entier>0. (D comme le début de la boucle)
Appliquons lui une première itération:
Comme il est impair: 3(2n-1)+1=6n-2 qui donne F=3n-1.(F comme fin de boucle)
La parité de 3n-1 est indéterminée, et dépend de la parité de n.
Si n s'écrit 2n (pair), on a alors D=2(2n)-1=4n-1 et F=3(2n)-1=6n-1.
Quel que soit n, F>D (car F impair)
Si n s'écrit 2n-1 (impair) on a:
D=2(2n-1)-1=4n-3
F=3(2n-1)-1=6n-4 qui donne 3n-2.
Si n=1 F=D c'est la boucle 1 donne 1.
Si n>1, F
Reste donc à étudier le seul cas possible:
D=4n-1
F=6n-1
Appliquons à nouveau l'algorithme à F
3F+1=18n-2 qui donne 9n-1
Parité de 9n-1 indéterminée, discussion sur parité en fonction de n:
Si n=2n
D=8n-1
F=18n-1 donc F>D quel que soit n.
Si n=2n-1
D=8n-5
F=18n-10 qui donne 9n-5, à parité indéterminée.
Nouvelle discussion:
Si n=2n D=16n-5 et F=18n-5 donc F>D.
Si n=2n-1 D=16n-13 et F=18n-14 donne 9n-5 F
On appelle "étape" l'ensemble des opérations qui, à partir de tout couple (D0,F0), donne, après application de l'algorithme, un ou plusieurs autres couples (Di,Fi) tel que, soit F impair et>D, soit F
(D0,F0)=(4n-1,6n-1) est le couple origine
(D1,F1)=(8n-1,18n-1)
(D2,F2)=(16n-5,18n-5)
(D3,F3)=(16n-3,9n-5) ce dernier couple étant éliminé pour la recherche de la boucle .
On peut écrire un D sous la forme an-b et un F sous la forme cn-d.
D=an-b
F=cn-d
Examinons l'expression dR=(b/a)-(d/c)
L'étape appliquée à (D,F) débute en faisant (3F+1)/2
3(cn-d)+1=3cn -(3d-1). Le rapport d/c devient (3d-1)/3c=d/c-1/3c. Cela explique que b/a>d/c. Mais la différence de -(1/3c) est
faible, et inversement proportionnelle à c.
Ensuite on remplace n soit par 2n soit par 2n-1.
Si n=2n
D=2an-b le rapport b/a devient b/2a
F=6cn-(3d-1) le rapport (3d-1)/3c est devient (3d-1)/6c proche de d/2c.
Comme 3F+1 n'a que peu modifié le rapport d/c, on peut écrire:
dR diminue de moitié quand on remplace n par 2n
Si n=2n-1
D=2an-(a+b) le rapport b/a devient (a+b)/2a=(1/2)+(b/2a)
F=6cn-(3c+3d-1) le rapport d/c s'écrit: (3c+3d-1)/6c=(1/2)+(3d-1)/6c.
dR=(1/2)+(b/2a)-(1/2)-(3d-1)/6c=(b/2a)-(3d-1)/6c
dR a la même valeur que quand n=2n
dR diminue aussi de moitié quand on remplace n par 2n-1.
dR est positif au départ. Il reste positif car on a vu que d/c diminuait légèrement avec 3F+1
Les rapports b/a et d/c évoluent pareillement en remplaçant n par 2n ou par 2n-1.
dR diminue de moitié, au moins, à chaque étape.
dR a donc comme limite zéro au bout d'un nombre infini d'étapes.
Comme b/a-d/c tend vers 0, on a b/a=d/c approximativement.
On peut remplacer b par ka et d par kb
D=an-ka=a(n-k)
F=cn-kc=c(n-k)
a est obtenu par mutiplications successives de 2.
c est otenu par multplications successives de 3, avec une seule fois 2 pour sa parité.
D=(2^a)(n-k)
F=(2*3^c)(n-k)
Comparer D et F revient à comparer une puissance de 2 et une puissance de 3.
Plus le nombre d'étapes pour trouver une boucle sera important, plus on cherchera une égalité entre une forte puissance de 2 et une forte puissance de 3. La boucle n'est donc possible que pour des petits nombres.
On ne peut pas trouver de boucles pour des grands nombres nécessitant de longues étapes.