Suite de Syracuse.

[Bony]

Salut à tous.

Pour mon TIPE j'ai décidé de traiter le problème de Syracuse, ou problème 3x+1.

Est-ce que certains d'entre vous auraient des documents / fichiers intéressants à me proposer sur la chose?

En vous remerciant

[acoustica]

Salut à tous.

Pour mon TIPE j'ai décidé de traiter le problème de Syracuse, ou problème 3x+1.

Est-ce que certains d'entre vous auraient des documents / fichiers intéressants à me proposer sur la chose?

En vous remerciant

Ouch ! Super intéressant, mais ça va être dur pour un TIPE. Tu ne pourras pas aller beaucoup plus loin que l'explication du problème, dire que pour l'instant c'est une conjecture, expliquer pourquoi le fait de l'avoir vérifié jusqu'à des millions ne suffit pas. Si tu y tiens vraiment, tu peux faire une petite procédure avec le logiciel Maple (un prof peut t'aider à le faire). Tu peux aussi prendre un autre problème d'arithmétique qui pose une affirmation vraie jusqu'à plusieurs milliards (on peut donc penser que c'est vrai), et qui au bout de plusieurs milliards a une bizarrerie : ça ne marche pas à un certain rang. Je sais qu'il en existe un comme ça, j'avais vu ça une fois, mais je ne m'en souviens plus. Si ça rappelle quelque chose à quelqu'un... Ca te permet de dire "vous voyez, essayer sur un grand nombre d'exemples ne prouve rien".


Edit : ah pardon, j'avais pas compris, je croyais que tu étais en première et que c'était pour ton TPE. Autant pour moi. Je suis crevé ce soir.

[Bony]

Je suis en spé je sais utiliser maple ^^
Je sias bien que c'est un sujet difficile mais ô combien intéressant c'est bien pour ça que j'ai voulu travailler là dessus

[nuage]

Je suis en spé je sais utiliser maple ^^
Je sias bien que c'est un sujet difficile mais ô combien intéressant c'est bien pour ça que j'ai voulu travailler là dessus

Bonne année.
Tu peut regarder "images des mathématiques" ici

[Bony]

Merci bien. Articles très intéressants

[lapras]

Le lien donné par Nuage est très bien : élémentaire et donne des applications aux calculs faits par les ordinateurs (pour minorer la longueur des cycles éventuels). D'ailleurs Terence Tao reformule l'existence d'un cycle non trivial en un problème arithmétique avec des puissances de 2 et de 3.

[Matt_01]

Ouch ! Super intéressant, mais ça va être dur pour un TIPE. Tu ne pourras pas aller beaucoup plus loin que l'explication du problème, dire que pour l'instant c'est une conjecture, expliquer pourquoi le fait de l'avoir vérifié jusqu'à des millions ne suffit pas. Si tu y tiens vraiment, tu peux faire une petite procédure avec le logiciel Maple (un prof peut t'aider à le faire). Tu peux aussi prendre un autre problème d'arithmétique qui pose une affirmation vraie jusqu'à plusieurs milliards (on peut donc penser que c'est vrai), et qui au bout de plusieurs milliards a une bizarrerie : ça ne marche pas à un certain rang. Je sais qu'il en existe un comme ça, j'avais vu ça une fois, mais je ne m'en souviens plus. Si ça rappelle quelque chose à quelqu'un... Ca te permet de dire "vous voyez, essayer sur un grand nombre d'exemples ne prouve rien".


Edit : ah pardon, j'avais pas compris, je croyais que tu étais en première et que c'était pour ton TPE. Autant pour moi. Je suis crevé ce soir.

Ce que tu dis en fin de message me fait penser à une expression sous forme de somme je crois, qui est très proche de pi.

[lapras]

Acoustica : il y a pire encore.
Pour un n donné, si on veut calculer la suite de collatz à partir de ce n, si ca diverge (vers l'infini), on ne pourra jamais le savoir algorithmiquement car même si l'ordinateur n'a pas trouvé de boucle à une certaine étape on ne sait jamais si la suite va boucler plus loin. C'est ce qu'on appelle un problème semi-décidable : si n vérifie la conjecture (i.e la suite ne diverge pas) alors on peut le prouver avec l'ordinateur mais si la suite diverge on ne peut pas le prouver avec l'ordinateur.
En fait on peut prouver que certaines variantes de la suite de collatz (avec d'autres coefficients que 3x+1 et x/2) sont algorithmiquement indécidables.

[nodjim]

Dans le même genre:
Je conjecture que cet algorithme aboutit toujours à zéro: On prend un nombre autre que composé que de 1. On le multiplie par le produit de ses chiffres. Ensuite on recommence.

[Bony]

ça a plutôt l'air de diverger ton truc

[lapras]

Effectivement et il y a une conjecture sur le temps de vol de cette suite, cf persistance d'un entier. En base 3 je crois que c'est lié à collatz, à vérifier. (ca ne diverge pas si il y a un 0 dans l'écriture : c'est tout le probleme)

[nodjim]

Bien vu Lapras: tôt ou tard, on trouvera bien un 5 (avec un pair) ou un 0 dans le nombre et alors le suivant sera un zéro. Oui, mais voilà, est ce tjs vrai ?
Notez bien que vous pourrez trouver de très très grands nombres, aussi grands que Wolfram permet, mais cela ne vous donnera pas la réponse.
Tout le confort ici est pour celui qui propose la conjecture!

[nodjim]

A noter tout de même dans la suite de Syracuse: Si une boucle existe, alors il y a une infinité de nombres qui tombent dans cette suite.

[lapras]

Voici un petit article sur le sujet (persistance d'un entier).
Article ici
En gros en base 3 les chiffres étant 0,1 ou 2, on a toujours une puissance de 2 quand on calcule le produit. Le truc c'est qu'il y a une conjecture d'erdos qui dit qu'une puissance de 2 en base 3 contient toujours un chiffre 0. C'est lié à une forme faible de Collatz, cf l'article de Terence Tao.

[acoustica]

Acoustica : il y a pire encore.
Pour un n donné, si on veut calculer la suite de collatz à partir de ce n, si ca diverge (vers l'infini), on ne pourra jamais le savoir algorithmiquement car même si l'ordinateur n'a pas trouvé de boucle à une certaine étape on ne sait jamais si la suite va boucler plus loin. C'est ce qu'on appelle un problème semi-décidable : si n vérifie la conjecture (i.e la suite ne diverge pas) alors on peut le prouver avec l'ordinateur mais si la suite diverge on ne peut pas le prouver avec l'ordinateur.
En fait on peut prouver que certaines variantes de la suite de collatz (avec d'autres coefficients que 3x+1 et x/2) sont algorithmiquement indécidables.

Indécidable, cela signifie qu'il n'y a pas assez de données pour conclure ?
Mais comment un problème tel que celui-là pourrait être improuvable ?

En fait, si j'ai bien compris, le problème avec Syracuse, c'est que certains pensent qu'on n'a pas assez d'éléments pour la prouver ?

[lapras]

Indécidable, cela signifie qu'il n'y a pas assez de données pour conclure ?
Mais comment un problème tel que celui-là pourrait être improuvable ?

En fait, si j'ai bien compris, le problème avec Syracuse, c'est que certains pensent qu'on n'a pas assez d'éléments pour la prouver ?

Là je parle d'incidabilité algorithmique. Un problème est indécidable si il n'existe pas d'algorithme (à définir proprement avec les machines de Turing par exemple, mais ca revient à dire un code en langage C avec des boucles for) qui à chaque n dit si n vérifie la conjecture (le problème) ou si il ne le vérifie pas.
A fortiori il n'existe pas de preuve mathématique que la conjecture est vraie ou fausse pour tout n car sinon un algorithme serait d'énumérer toutes les preuves possibles et de regarder lesquelles sont valides logiquement (l'algorithme termine car il existe une preuve de longueur finie).
Je sais que ca peut paraître choquant mais certains problèmes mathématiques bien définis ne sont pas prouvables ni réfutables. On ne sait pas si c'est le cas pour collatz.

[acoustica]

Là je parle d'incidabilité algorithmique. Un problème est indécidable si il n'existe pas d'algorithme (à définir proprement avec les machines de Turing par exemple, mais ca revient à dire un code en langage C avec des boucles for) qui à chaque n dit si n vérifie la conjecture (le problème) ou si il ne le vérifie pas.
A fortiori il n'existe pas de preuve mathématique que la conjecture est vraie ou fausse pour tout n car sinon un algorithme serait d'énumérer toutes les preuves possibles et de regarder lesquelles sont valides logiquement (l'algorithme termine car il existe une preuve de longueur finie).
Je sais que ca peut paraître choquant mais certains problèmes mathématiques bien définis ne sont pas prouvables ni réfutables. On ne sait pas si c'est le cas pour collatz.

D'accord, merci pour tes explications. =)
Elle est déprimante cette dernière phrase non ? :doh:

>

[vincentroumezy]

D'accord, merci pour tes explications. =)
Elle est déprimante cette dernière phrase non ? :doh:

>

C'est le théorème d'incompltude de Gödel.

[Le_chat]

Tu peux aussi prendre un autre problème d'arithmétique qui pose une affirmation vraie jusqu'à plusieurs milliards (on peut donc penser que c'est vrai), et qui au bout de plusieurs milliards a une bizarrerie : ça ne marche pas à un certain rang.

Salut. C'est la conjecture de polya: http://fr.wikipedia.org/wiki/Conjecture_de_P%C3%B3lya

[acoustica]

Salut. C'est la conjecture de polya: http://fr.wikipedia.org/wiki/Conjecture_de_P%C3%B3lya

Yep, c'est ça que je cherchais !