Conjecture de Syracuse

Deux Québécois font la preuve de la véracité de la conjecture de Syracuse. On l'attendait depuis 76 ans!

La conjecture de Syracuse ressemble à un jeu de calcul. On prend n’importe quel nombre entier plus grand que 1 (comme 2, 3, 4, etc.); s’il est pair, on le divise par 2; s’il est impair, on le multiplie par 3 et on ajoute 1. En réitérant l’opération plusieurs fois, on obtient une suite de nombres… qui finit toujours par aboutir à 1.

http://www.courrierbc.com/pages/article.php?noArticle=3780

Et si la conjecture était fausse ? Hein ?
Pour établir ceci, il suffit de construire un contre-exemple. Une fois qu'on en tient un, on en trouve autant que l'évêque en bénit...

tu as lu l'article?
ça a été prouvé pour tout chiffres, elle est vrai

1. J'ai lu l'article ;
2. La preuve qu'ils donnent est probabiliste ;
3. Question aux physiciens : la probabilité d'existence d'un phénomène est-elle équivalente à l'existence du phénomène ? Question aux autres : la probabilité de la vérité est-elle LA vérité ?
4. Nul n'empêchera un musicien de créer de la musique, si vous y croyez, essayez d'empêcher votre cerveau de produire des idées.
5. Zut, c'est vrai, je ne peux pas indiquer un autre forum où j'ai réussi à placer un lien puisqu'il me faudrait placer un lien...

Ah, j'allais oublier un tout petit détail... A vrai dire il est presque insignifiant, tellement c'est bête ! Et si démontrer Syracuse revenait strictement à démontrer... Syracuse ? Hein ? On aurait l'air fin... D'ailleurs, comment doit-on se comporter devant une telle situation ? On fait comme si on était des singes, on imite, on rigole, on se fait des grimaces ? Ou on évolue et on fait de la musique ?

je te conseil de télécharger ce logiciel de ma création : http://uploaded.to/file/jqog988e
il suffit d'entrer le nombre de départ que tu veux, il fait en moins d'une seconde tout les calcules lui même et te donne le nombre d'étape pour arriver a 1, si il y a une valeur pour laquelle ce n'est pas possible alors il ne pourra pas te donner le nombre d'étape,
essaye autant de chiffres que tu veux (tant qut tu ne dépasse pas le "maxint" de pascal (32767))
il te donnera la réponse,
si un essai ne te donne pas de résultat c'est que la conjecture est fausse comme tu semble le croire

5. Zut, c'est vrai, je ne peux pas indiquer un autre forum où j'ai réussi à placer un lien puisqu'il me faudrait placer un lien...

Et....? ou est le problème?

en tout cas je ne vois pas le rapport avec la véracité de la conjecture de Syracuse dans le reste de ton post o_O



EDIT: il se peut que si tu as la folie des grandeurs et que tu tentes un gros chiffre il te donne un résultat négatif, c'est que le calcul a dépassé maxint, par exemple pour 20 001 tu as un nombre impair donc (20 001*3) +1 = 60 003 > maxint,
je sais que ça serait plus pratique sans ce problème de valeur maximal, mais il faudrai le programme sous python pour éviter ce problème sauf que je sais pas faire
mais déjà si tu les test un par un tu as de quoi faire pour un certains temps

Merci, pour ce qui est de la terminaison, j'ai une idée assez précise de ce qu'il en est. On peut (presque) tout essayer, y'a rien à faire, à chaque fois ça finit toujours pareil...

Pour ce qui est des grands nombres, la folie des grandeurs, ça se maîtrise...

On peut, comme je le fais avec ma bonne vieille TI92+ utiliser des entiers jusqu'à des 640 chiffres.

Mais il y a beaucoup mieux : la base TROIS

Dans cette base, multiplier par trois est trivial, ajouter un au résultat obtenu tout autant.

La division par deux est bêtement mécanique : je fournis deux fonctions LISP qui utilisent Syracuse, partant d'une chaîne de caractères exprimant un nombre en base trois (elle n'est censée contenir que des 0, 1 et 2) et elle le réduit à un. Ce faisant, on jalonne chaque étape dans une chaîne exprimée en base deux, ce qui permet de faire machine arrière : de retrouver le nombre de départ en faisant tourner Syracuse à l'envers.

La fonction peut manger des nombres assez gros... de l'ordre du gigaoctet, voire plusieurs...

Le sujet n'est pas ici de dire à quoi ça peut bien servir, mais en gros, c'est le jeu du petit Poucet...

Code:


(defun ks:resbuild (ks:istring / ks:lstring)
  (setq ks:lstring (ks:/2 ks:istring ""))
  (while (/= "1" (car ks:lstring))                ;;; tant qu'on n'a pas atteint 1...
    (setq ks:lstring (ks:/2 (car ks:lstring) (cadr ks:lstring))) ;;; on divise par deux après avoir triplé plus un si besoin
  )
  ks:lstring
)

(defun ks:/2 (ks:istring ks:restring / ks:ostring ks:flip)
  (setq ks:ostring "")
  (while (= "0" (substr ks:istring 1 1))
    (setq ks:istring (substr ks:istring 2)) ;;; c'est un ltrim
  )
  (while (and (/= "1" (substr ks:istring 1 1)) (/= "" ks:istring)) ;;; on attend l'apparition du premier 1
    (cond ((= "0" (substr ks:istring 1 1))
          (setq ks:ostring (strcat ks:ostring "0")) ;;; et on conserve les chiffres zéro
          (setq ks:istring (substr ks:istring 2))
          )
          ((= "2" (substr ks:istring 1 1))
          (setq ks:ostring (strcat ks:ostring "1")) ;;; et on remplace les 2 par des 1
          (setq ks:istring (substr ks:istring 2))
          )
    )
  ) ;;; c'est fini, ou on vient de trouver un chiffre 1
  (while (/= "" ks:istring) ;;; tant qu'il reste quelque chose
    (cond ((and ks:flip (= "0" (substr ks:istring 1 1))) ;;; cas flip et chiffre 0
          (setq ks:ostring (strcat ks:ostring "1")) ;;; on le transforme en 1
          )
          ((and ks:flip (= "1" (substr ks:istring 1 1))) ;;; cas flip et chiffre 1
          (setq ks:ostring (strcat ks:ostring "2")) ;;; on le transforme en 2
          (setq ks:flip nil) ;;; et on bascule en mode flop
          )
          ((and ks:flip (= "2" (substr ks:istring 1 1))) ;;; cas flip et chiffre 2
          (setq ks:ostring (strcat ks:ostring "2")) ;;; on conserve le 2
          )
          ((and (not ks:flip) (= "0" (substr ks:istring 1 1))) ;;; cas flop et chiffre 0
          (setq ks:ostring (strcat ks:ostring "0")) ;;; on conserve 0
          )
          ((and (not ks:flip) (= "1" (substr ks:istring 1 1))) ;;; cas flop et chiffre 1
          (setq ks:ostring (strcat ks:ostring "0")) ;;; on le transforme en 0
          (setq ks:flip t) ;;; et on bascule en mode flip
          )
          ((and (not ks:flip) (= "2" (substr ks:istring 1 1))) ;;; cas flop et chiffre 2
          (setq ks:ostring (strcat ks:ostring "1")) ;;; on le transforme en 1
          )
    )
    (setq ks:istring (substr ks:istring 2)) ;;; on passe au chiffre suivant
  ) ;;; il ne reste plus rien de la chaîne entrée, y'a plus qu'à syracuser
  (if ks:flip
    (setq ks:ostring  (strcat ks:ostring "2") ;;; on sort en mode flip : le nombre était impair, on le triple plus un et on divise par deux dans la foulée
          ks:restring (strcat ks:restring "1") ;;; on signale le fait dans la chaîne de restes
    )
    (setq ks:restring (strcat ks:restring "0")) ;;; on sort en mode flop : le nombre était pair, on a fini et on le signale dans la chaîne des restes
  )
  (list ks:ostring ks:restring) ;;; on retourne les deux chaînes produites
)



Tiens, dans mon infinie bonté, je fournis aussi de quoi revenir au point de départ...

Code:


(defun ks:buildres (ks:istring / ks:lstring)
  (setq ks:lstring (ks:*2 "1" ks:istring))
  (while (/= "" (cadr ks:lstring))
    (setq ks:lstring (ks:*2 (car ks:lstring) (cadr ks:lstring)))
  )
  (car ks:lstring)
) ;;; Syracuse à l'envers

(defun ks:*2 (ks:istring ks:restring / ks:ostring ks:flip)
  (setq ks:istring (ks:reversestring ks:istring))
  (setq ks:ostring "")
  (while (/= "" ks:istring)
    (cond ((and ks:flip (= "2" (substr ks:istring 1 1)))
          (setq ks:ostring (strcat "2" ks:ostring))
          )
          ((and ks:flip (= "1" (substr ks:istring 1 1)))
          (setq ks:ostring (strcat "0" ks:ostring))
          )
          ((and ks:flip (= "0" (substr ks:istring 1 1)))
          (setq ks:ostring (strcat "1" ks:ostring))
          (setq ks:flip nil)
          )
          ((and (not ks:flip) (= "2" (substr ks:istring 1 1)))
          (setq ks:ostring (strcat "1" ks:ostring))
          (setq ks:flip t)
          )
          ((and (not ks:flip) (= "1" (substr ks:istring 1 1)))
          (setq ks:ostring (strcat "2" ks:ostring))
          )
          ((and (not ks:flip) (= "0" (substr ks:istring 1 1)))
          (setq ks:ostring (strcat "0" ks:ostring))
          )
    )
    (setq ks:istring (substr ks:istring 2))
  )
  (if ks:flip
    (setq ks:ostring (strcat "1" ks:ostring))
  )
  (if (and (/= "" ks:restring)
          (= "1" (substr ks:restring (strlen ks:restring) 1))
      )
    (setq ks:ostring (substr ks:ostring 1 (1- (strlen ks:ostring))))
  )
  (setq ks:restring (substr ks:restring 1 (1- (strlen ks:restring))))
  (list ks:ostring ks:restring)
)


J'ai oublié de mettre en commentaire un de mes commentaires... ça risque de planter si on ne rajoute pas au moins un ";" avant "on retourne les deux chaînes produites"...

C'est la joie du direct... juste un peu dommage que l'indentation ait été supprimée au passage, c'est un peu moins lisible

Tu peux utiliser la balise code :

Code:

[code][/code]

Et tu peux éditer ton message pour ajouter le ';'.

Bon à savoir !
Merci


Bon, j'ai effectué les corrections... C'est vrai que ça a un peu plus de gueule

Pour ce qui est de la non-terminaison pour certains machins qui ressemblent à des nombres, il s'agit d'une ruse de sioux et d'un raisonnement trivial... le tout de mon cru

Il existe des séquences qui peuvent néanmoins laisser subsister le doute, ce qui, même à l'aide d'une démonstration statistique quasi-certaine, exige en toute rigueur que l'on s'y intéresse.

L'une de ces séquences est la série x6->x8->x9->x8->...->x9->x8->x4 où x6, x8, x9 et x4 sont des nombres dont le dernier chiffre est respectivement 6, 8, 9 et 4

Dans mon jargon perso, j'ai baptisé ces séquences "trilles 8989", pour leur ressemblance avec un ornement musical
Il est assez facile d'établir :

• que les trilles 8989 sont initiés par les entiers de la forme 40n+76 (avec n )
  
• que les trilles 8989 sont terminés par les entiers de la forme 30n+14 (avec n )
  
• qu'il n'existe pas de limite à la longueur des trilles 8989
  
• que les trilles 8989 se terminent toujours
  

La dernière proposition de cette liste exclut un bouclage direct (ce qui est d'ailleurs trivial sinon bête...). Mais rien n'empêche *a priori* l'existence d'un entier qui amènerait à de telles séquences en cascade... indéfiniment.

Pour ceux que ça intéresse, voici deux liens qui donnent une image :

Sous forme graphique (gribouillis approximatif, mais qui permet de se donner une idée assez précise du comportement de l'algorithme pour tous les entiers) :

http://www.archibald-birseaufoys.dtdns.net/Espace%20Tout%20Public/Math%C3%A9matiques/Syracuse/Images/Syracuse-graphe-plot.jpg

Et une autre image, qui représente la même chose, sous forme audible...

http://www.archibald-birseaufoys.dtdns.net/Espace%20Tout%20Public/Musique/Etats%20d%27Ame/1-Syracuse%2027.wma

D'autres formats sont disponibles sur mon site... j'ai indiqué ici celui dont le fichier est le moins obèse