Mathématiques - Conjecture de Collatz

Conjecture de Collatz
(Cliquez-ici pour accéder à la version originale de cette discussion avec couleurs et images)

Posted by: guigui51250

Bonjour à tous

Il y a 2 semaines, notre prof de math nous a montré la conjecture de Collatz et on l'a un peu étudiée mais pas beaucoup. C'est une suite assez bizarre, je me suis demandé comment pourrait-on la représenter graphiquement mais ma prof de math ne sait pas donc si quelqu'un pourrai m'expliquer

(si c'est possible)

Merci

Posted by: anima

Citation:

Posté par guigui51250

Bonjour à tous

Il y a 2 semaines, notre prof de math nous a montré la conjecture de Collatz et on l'a un peu étudiée mais pas beaucoup. C'est une suite assez bizarre, je me suis demandé comment pourrait-on la représenter graphiquement mais ma prof de math ne sait pas donc si quelqu'un pourrai m'expliquer

(si c'est possible)

Merci

Elle est toute simple a énoncer, cette conjecture. Prends un nombre quelconque; s'il est pair, divise-le par deux. S'il est impair, triple le et ajoute 1. Réitere ad infinitum

D'apres Collatz, la suite converge vers 1. Et pour le moment, personne n'a réussi a le prouver.

(Elle me rappelle Syracuse, cette conjecture, d'ailleurs...)

Posted by: guigui51250

Citation:

Posté par anima

Oui sa j'ai bien compris mais est-ce qu'on peut la représenter graphiquement?

Posted by: anima

Citation:

Posté par guigui51250

Oui sa j'ai bien compris mais est-ce qu'on peut la représenter graphiquement?

Tu sais utiliser Excel, non?

Pour premier nombre C5, tous les suivants sont donnés par récurrence avec la formule:
=IF((C5/2) = ROUND(C5/2,0),C5/2,3*C5+1)

Posted by: guigui51250

Citation:

Posté par anima

Tu sais utiliser Excel, non?

Pour premier nombre C5, tous les suivants sont donnés par récurrence avec la formule:
=IF((C5/2) = ROUND(C5/2,0),C5/2,3*C5+1)

ok merci bonne journée a+

Posted by: cesar

Citation:

Posté par anima

C'EST la conjecture de syracuse... la suite converge vers 1, 4, 2, 1, 4....
cesar, interimaire du forum...

Posted by: Clembou

Citation:

Posté par cesar

C'EST la conjecture de syracuse... la suite converge vers 1, 4, 2, 1, 4....
cesar, interimaire du forum...

Une de mes recherches mathématiques portent sur ce type de suites qu'on peut appeler des suites (injectivement) pieuvres. Le tout c'est de savoir quand est-ce que ces suites convergent (vers une boucle) et quand est-ce qu'elles divergent (vers l'infini). J'ai une petite démonstration qui montre que la suite de Syracuse converge pour tout n mais j'ai supposé une proposition...

Posted by: Joker62

Euhhhhhhhhhhh
J'suis curieux moi ! j'veux voir !
Propose Clembou !

Posted by: Clembou

Citation:

Posté par Joker62

Euhhhhhhhhhhh
J'suis curieux moi ! j'veux voir !
Propose Clembou !

Ba voilà.

Proposition 1 : Soit n fixé tel que u0 = n. Si il existe un k tel que uk < u0 (= n) alors la suite de Syracuse converge.

C'est la proposition que j'ai supposé. Maintenant je pars du fait que tout nombre pair converge, reste plus qu'à démontrer pour les nombres impaires et pour cela je fais le processus inverse.

Proposition 2 : L'ensemble $3\mathbb{N} + 1$ est infini.

$3\mathbb{N} + 1 = \{n \in \mathbb{N}, \exists k \in \mathbb{N} \, | \, n = 3k+1\}$

Démonstration : il existe une bijection qui envoie entre $\mathbb{N}$ vers $3\mathbb{N}+1$ .

Maintenant on prend par exemple les 300 premiers nombres de $\mathbb{N}$ (fais sur MAPLE)

1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90, 91, 92, 93, 94, 95, 96, 97, 98, 99, 100, 101, 102, 103, 104, 105, 106, 107, 108, 109, 110, 111, 112, 113, 114, 115, 116, 117, 118, 119, 120, 121, 122, 123, 124, 125, 126, 127, 128, 129, 130, 131, 132, 133, 134, 135, 136, 137, 138, 139, 140, 141, 142, 143, 144, 145, 146, 147, 148, 149, 150, 151, 152, 153, 154, 155, 156, 157, 158, 159, 160, 161, 162, 163, 164, 165, 166, 167, 168, 169, 170, 171, 172, 173, 174, 175, 176, 177, 178, 179, 180, 181, 182, 183, 184, 185, 186, 187, 188, 189, 190, 191, 192, 193, 194, 195, 196, 197, 198, 199, 200, 201, 202, 203, 204, 205, 206, 207, 208, 209, 210, 211, 212, 213, 214, 215, 216, 217, 218, 219, 220, 221, 222, 223, 224, 225, 226, 227, 228, 229, 230, 231, 232, 233, 234, 235, 236, 237, 238, 239, 240, 241, 242, 243, 244, 245, 246, 247, 248, 249, 250, 251, 252, 253, 254, 255, 256, 257, 258, 259, 260, 261, 262, 263, 264, 265, 266, 267, 268, 269, 270, 271, 272, 273, 274, 275, 276, 277, 278, 279, 280, 281, 282, 283, 284, 285, 286, 287, 288, 289, 290, 291, 292, 293, 294, 295, 296, 297, 298, 299, 300

On retranche 1 à tous ses nombres :

0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90, 91, 92, 93, 94, 95, 96, 97, 98, 99, 100, 101, 102, 103, 104, 105, 106, 107, 108, 109, 110, 111, 112, 113, 114, 115, 116, 117, 118, 119, 120, 121, 122, 123, 124, 125, 126, 127, 128, 129, 130, 131, 132, 133, 134, 135, 136, 137, 138, 139, 140, 141, 142, 143, 144, 145, 146, 147, 148, 149, 150, 151, 152, 153, 154, 155, 156, 157, 158, 159, 160, 161, 162, 163, 164, 165, 166, 167, 168, 169, 170, 171, 172, 173, 174, 175, 176, 177, 178, 179, 180, 181, 182, 183, 184, 185, 186, 187, 188, 189, 190, 191, 192, 193, 194, 195, 196, 197, 198, 199, 200, 201, 202, 203, 204, 205, 206, 207, 208, 209, 210, 211, 212, 213, 214, 215, 216, 217, 218, 219, 220, 221, 222, 223, 224, 225, 226, 227, 228, 229, 230, 231, 232, 233, 234, 235, 236, 237, 238, 239, 240, 241, 242, 243, 244, 245, 246, 247, 248, 249, 250, 251, 252, 253, 254, 255, 256, 257, 258, 259, 260, 261, 262, 263, 264, 265, 266, 267, 268, 269, 270, 271, 272, 273, 274, 275, 276, 277, 278, 279, 280, 281, 282, 283, 284, 285, 286, 287, 288, 289, 290, 291, 292, 293, 294, 295, 296, 297, 298, 299

et on prend tous ceux qui sont divisible par 3 :

[3, 6, 9, 12, 15, 18, 21, 24, 27, 30, 33, 36, 39, 42, 45, 48, 51, 54, 57, 60, 63, 66, 69, 72, 75, 78, 81, 84, 87, 90, 93, 96, 99, 102, 105, 108, 111, 114, 117, 120, 123, 126, 129, 132, 135, 138, 141, 144, 147, 150, 153, 156, 159, 162, 165, 168, 171, 174, 177, 180, 183, 186, 189, 192, 195, 198, 201, 204, 207, 210, 213, 216, 219, 222, 225, 228, 231, 234, 237, 240, 243, 246, 249, 252, 255, 258, 261, 264, 267, 270, 273, 276, 279, 282, 285, 288, 291, 294, 297, 300]

Mais en divisant tous ses nombres par 3 on obtient l'intervalle [0,100]. Ainsi cela prouve que tous les nombres entre 0 et 100 sont convergent par la suite de Syracuse...

Or j'ai démontre que $3\mathbb{N}+1$ est infini donc tous les nombres convergent par la suite de Syracuse.

Posted by: Joker62

Alors, bon...

Déjà pour toi, tout nombre impair s'écrit de la forme 3k+1 ???

Ensuite, j'ai pas compris ta proposition 1, ce que représente u_0, ce que représente u tout cour en fait :^)

Enfin bref, j'trouve pas que ça prouve la moindre chose...

Posted by: Clembou

Citation:

Posté par Joker62

Alors, bon...

Déjà pour toi, tout nombre impair s'écrit de la forme 3k+1 ???

Ensuite, j'ai pas compris ta proposition 1, ce que représente u_0, ce que représente u tout cour en fait :^)

Enfin bref, j'trouve pas que ça prouve la moindre chose...

Hmmmm, j'avais une démonstration sur une feuille mais je l'ai perdu... Alors :

$(u_n)$ représente la suite de nombres obtenue par Syracuse, $u_0$ étant donc le terme initial de la suite choisi dans $\mathbb{N}$ .
Je réféchis sur le rapport entre 3N+1 et N

Posted by: ffpower

Pareil pour moi,j avais démontré Riemann en regardant la distribution des nombres premiers congrus a 3 modulo 17,mais j ai perdu ma feuille ya 2 semaines.c est con car c etait une demo vachement elegante en plus..

Posted by: Monsieur23

( Vue la récompense, on verra l'élégance après si tu veux bien... On fait fifty-fifty ? )

Posted by: Clembou

Citation:

Posté par Clembou

Hmmmm, j'avais une démonstration sur une feuille mais je l'ai perdu... Alors :

$(u_n)$ représente la suite de nombres obtenue par Syracuse, $u_0$ étant donc le terme initial de la suite choisi dans $\mathbb{N}$ .
Je réféchis sur le rapport entre 3N+1 et N

Ah oui ! J'ai oublié d'énoncer une autre proposition qui dit que si on trouve dans la suite pieuvre (Suite de Syracuse par exemple) de terme général quelconque, un élément convergeant alors la suite pieuvre des éléments de ce terme général converge.

Exemple : $7 \rightarrow ... \rightarrow 4 \rightarrow 2 \rightarrow 1$
7 est convergeant par Syracuse ainsi que 14, 28, ..., $7 \times 2^k$ , $\forall k \in \mathbb{N}$ .

et donc plus concrétement, si on applique à un nombre impair $k$ l'opération $3k+1$ , cela donne un nombre pair. Or tout nombre pair converge par la suite de Syracuse, il en est de même pour un nombre impair. Reste à démontrer la Proposition 1.

Tout est dans mon dossier Recherche mais il y a certaines pages qui manquent (je ne sais pas pourquoi

)...

Posted by: Patastronch

Citation:

Posté par Clembou

Tout est dans mon dossier Recherche mais il y a certaines pages qui manquent (je ne sais pas pourquoi

)...

Reste a montrer que tout nombre pair converge c'est ca ? Reste tout a montrer alors !

Posted by: morpho

On remarque des que k < n la suite serai convergente (<=>des qu'on trouve 1 on s'arrete) l'idée est suivant: on divise n par 4:

1) n=0 (mod 4) donc n=4m ===> etape suivant k=2m < n Ok on descend

2) n=1 (mod 4) donc n=4m+1 ===> k=12m+4 ===> k=6m+2 ===> k=3m+1 < n Ok on descend

3) n=2 (mod 4) donc n=4m+2 ===> etape suivant k=2m+1 < n Ok on descend

4) il reste le cas n=3 (mod 4) donc n=4m+3 la on ne sait pas, car on descend et on monte !!!!!

mais quand meme 3/4 cas qu'on descend donc la probabilite que la suite soit convergent est de 3/4 c'est quand meme beaucoups !!!!

Posted by: anima

Citation:

Posté par morpho

On remarque des que k < n la suite serai convergente (<=>des qu'on trouve 1 on s'arrete) l'idée est suivant: on divise n par 4:

Reste a la prouver, ton inférence que des que la suite descend en dessous du premier nombre, elle converge. Ca me semble vraiment léger.

Posted by: morpho

Citation:

Posté par anima

Reste a la prouver, ton inférence que des que la suite descend en dessous du premier nombre, elle converge. Ca me semble vraiment léger.

je pense que le raisonnement tient debout !!! en effet supposons que quelque soit n il existe une étape k tel que k<n alors la suite converge.

En effet on reprend le meme raisonnement pour k=n. comme on ne peut pas descendre indefiniment on tombe donc surment sur 1 (desque n=1 on s'arrete)

ce que j'ai démontrer:
quelque soit n la probabilite(k<n) = 3/4

la dificulté c'est la cas n=4m+3 on n'en sait rien!!!! par contre pour les autres cas on est sur qu'on descend tot ou tard

Posted by: anima

Citation:

Posté par morpho

Tu veux que je formule ma critique autrement? Prouve la décroissance globale de la suite de Syracuse et le prix est (surement) pour toi. Car, jusqu'a présent, tu as prouvé qu'il y a 0.75 de chance que pour n'importe quel nombre n, n+1 ou n+2 sont inférieurs a n. Etends cela a l'infini, avec un peu de probas, en considérant ta proba indépendante (en vérité, elle ne l'est pas vraiment, mais c'est pas grave): il y a une proba non-nulle (mais tres petite) que ta suite ait divergé pour tout n. Or, la conjecture dit bien que toute suite de Syracuse converge.
Le probleme reste entier.

Posted by: morpho

Citation:

Posté par anima

tu as raison, je ne prétends pas de prouver la conjecture (relis bien mes posts) !!!! Juste une petit remarque qu'on a la chance de tomber sur 1 à à 3/4 c'est tout! et encore c'est la chance (la probabilité).

Relis bien mes posts. Je ne prétend pas d'avoir démontré la conjecture ( pour un entier n quelconque) ni pour une famille particuliere de n.

Posted by: cesar

ben, moi, je l'ai demontré pour les 20 000 premiers chiffres...

avec un programme informatique qui a calculé toutes les limites de chaque suite.... c'est pas fin, mais cela marche.

cesar

oui, je sors, je sors....

Posted by: Clembou

Citation:

Posté par anima

Reste a la prouver, ton inférence que des que la suite descend en dessous du premier nombre, elle converge. Ca me semble vraiment léger.

Réfere toi à mes propositions et surtout celle ci :
Si on trouve dans la suite pieuvre (Suite de Syracuse par exemple) de terme général quelconque, un élément convergeant alors la suite pieuvre des éléments de ce terme général converge.
[Voir post précédent]

Posted by: ffpower

J appelerai pas ca une proposition perso..

Posted by: Clembou

Citation:

Posté par ffpower

J appelerai pas ca une proposition perso..

T'appelles ça comment alors ?

Posted by: Joker62

Euh !
Une conjecture ? :D

Posted by: Clembou

Citation:

Posté par Joker62

Euh !
Une conjecture ? :D

Citation:

Posté par Clembou

Si on trouve dans la suite pieuvre (Suite de Syracuse par exemple) de terme général quelconque, un élément convergeant alors la suite pieuvre des éléments de ce terme général converge.

On parlait de ça je pense

Posted by: ffpower

j appellerai ca une remarque tout au plus lol..ou un corollaire direct du fait tout aussi direct que si u(n) est une suite,u(n) et u(n+p) ont meme comportement a l infini..

Posted by: _-Gaara-_

Salut ^^

moi j'ai une démonstration mais elle n'est pas assez petite pour tenir dans un post xD

je sors je sors..

Posted by: Imod

Je pense que ces suites pieuvres ont déjà fait couler trop d'encre

Imod

Posted by: Clembou

Citation:

Posté par anima

Reste a la prouver, ton inférence que des que la suite descend en dessous du premier nombre, elle converge. Ca me semble vraiment léger.

Tant que j'y pense, ça, ça s'appelle le raisonnement par réccurence... Si tu supposes que $n$ est un terme convergeant alors tu dois le montrer pour $n+1$ . Or tu l'as déjà montré pour des nombres inférieurs à $n$ ... CQFD !

Edit : Oh ! Bien sûr ! Reste à démontrer cette réccurence (facile pour les nombres pairs mais impossible pour les nombres impairs).