Salut,

partant d'un entier positif quelconque :

S'il est pair on le divise par 2
S'il est impair on lui ajoute 3

Et on réitère le procédé avec le nouveau nombre obtenu.

Montrer que l'algorithme boucle à partir d'un moment

Généralisation?

dans l'idée : on voit clairement que partir de 1 fait une boucle (1 -> 4 -> 2 -> 1), il suffit donc de montrer que l'algorithme "emmène" n'importe quel nombre vers 1, ce qui est vrai puisqu'en réitérant les n/2 ou les (n+3)/2, on se rapprochera dangereusement de 1... après je vois pas comment l'écrire proprement

La conjecture de Syracuse n'est-elle pas indémontrée?

Si on est pair, on divise notre nombre par 2.

Si on est impair, on ajoute 3 puis on divise par 2, ce qui nous fait décroître si on partait au moins de 3, décroître strictement si on partait au moins de 5.

Note pour Meca : on a aussi une boucle 3 -> 6 -> 3 à prendre en compte.

Ensuite, on n'a plus qu'à examiner individuellement les cas des entiers jusqu'à 3 et on a fini.

Le 10 janvier 2016 à 21:33:29 Higgs a écrit :
La conjecture de Syracuse n'est-elle pas indémontrée?

c'est pas Syracuse là.
Syracuse c'est 3n+1

Oui, mais c'est dans la même idée.

C'est beaucoup plus simple que Syracuse ici.

Par quoi peut-on remplacer 2 et 3 pour généraliser?

Sauf que c'est beaucoup plus simple, vu que les impairs ne te font pas monter trop haut, c'est ce qui fait marcher la démo.

En fait, tant que l'enchaînement impair -> pair -> osef te fait descendre strictement pour peu que tu partes d'assez haut, t'as plus qu'un nombre fini (et restreint, si possible) de cas à examiner pour conclure.

Donc si on continue à diviser par deux tous les pairs qui nous passent sous le nez, il faut pas multiplier les impairs par plus que 2 (et si possible pas ajouter un truc fixe trop gros, sinon ça va être relou à faire à la main).

Pour la généralisation je propose, sans preuve :

p et q premiers entre eux

-> Si n est divisible par p on effectue la division
-> Sinon on ajoute q

Conjecture : Ca boucle...

Si p et q sont premiers entre eux, tu vas au plus ajouter p-1 fois q avant de re-diviser par p.

Cet enchaînement d'étapes te fait passer au pire de n à (n+q(p-1))/p et ceci est <= n dès que n >= q.

T'as plus qu'à recopier la preuve dans le cas avec 2 et 3 et c'est torché. C'pas une conjecture mais une proposition.

Ok, c'est net. Ca mène au fait qu'il y a une infinité de terme inférieurs à Max(nombre de départ ; q) donc qu'il y en a au moins deux identiques.

En faisant tourner Maple, on voit que la plus petite période peut être assez grosse... On va certainement pouvoir trouver des suites pour lesquelles la plus petite période est aussi grosse que l'on veut mais ce sera pour un autre jour!

En fait ça doit être tout con en prenant un grand nombre de départ, un petit p mais un gros q

un petit p mais un gros q

 *Fffuuuuit*

(Désolé, il se fait tard.)