Du nouveau sur la conjecture de Syracuse?

Olympiades mathématiques, énigmes et défis
nodjim
Membre Complexe
Messages: 3241
Enregistré le: 24 Avr 2009, 18:35

Du nouveau sur la conjecture de Syracuse?

par nodjim » 12 Aoû 2010, 20:07

Bonjour à tous.
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 FL'étape ci-dessus se résume ainsi:
(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.



Doraki
Habitué(e)
Messages: 5008
Enregistré le: 20 Aoû 2008, 13:07

par Doraki » 12 Aoû 2010, 21:43

Oui, y'a des gens qui utilisent (entre autres) un théorème sur Baker (qui précise comment on peut approcher log2/log3 par des fractions) pour dire que si y'a d'autres cycles, il est très très très grand (de longueur au moins 17087915)

nodjim
Membre Complexe
Messages: 3241
Enregistré le: 24 Avr 2009, 18:35

par nodjim » 13 Aoû 2010, 19:10

Salut Doraki.
J'explique justement dans ma démo que le nombre d'étapes en grandissant rend impossible l'égalité entre les nombres origine et résultat, du fait même qu'on compare une puissance de 2 et une puissance de 3. Je me souviens qu'il n'y a pas si longtemps, je disais que la puissance de 3 en base 2 comporte à peu près autant de 1 que de 0. J'ignore cependant si la démo existe de l'écart grandissant entre les puissances grandissantes de 2 nombres premiers entre eux.

Doraki
Habitué(e)
Messages: 5008
Enregistré le: 20 Aoû 2008, 13:07

par Doraki » 13 Aoû 2010, 21:07

Tu le disais mais tu ne l'as jamais prouvé
(j'ai vu un papier y'a pas longtemps qui utilisait le même résultat de Baker pour montrer que le nombre de chiffres 1 dans 3^n écrit en base 2 tendait vers l'infini, avec une borne inférieure très lente, genre log(log(n)). Ca devrait impliquer que |3^a - 2^b| tend en effet vers l'infini)

Même si le dénominateur 2^a - 3^b est grand, ça veut pas dire que le numérateur peut pas en être un multiple.

Dans les cycles de longueur 1000, y'a le cycle qui alterne entre parités paire et impaire, si on cherche le nombre correspondant, on a dénominateur de 2^1000-3^500, mais le numérateur en est un multiple vu que ça correspond au cycle (1,2...) répété 500 fois

nodjim
Membre Complexe
Messages: 3241
Enregistré le: 24 Avr 2009, 18:35

par nodjim » 14 Aoû 2010, 11:06

D'accord, j'ai compris. C'est critique quand le multiplicateur est une petite fraction de la puissance, cas qui m'avait échappé.

 

Retourner vers ⚔ Défis et énigmes

Qui est en ligne

Utilisateurs parcourant ce forum : Aucun utilisateur enregistré et 3 invités

Tu pars déja ?



Fais toi aider gratuitement sur Maths-forum !

Créé un compte en 1 minute et pose ta question dans le forum ;-)
Inscription gratuite

Identification

Pas encore inscrit ?

Ou identifiez-vous :

Inscription gratuite