transformation du pb de Syracuse en plus compact mais pas plus résolu
Répondre à la discussion
Affichage des résultats 1 à 1 sur 1

transformation du pb de Syracuse en plus compact mais pas plus résolu



  1. #1
    mike.p

    transformation du pb de Syracuse en plus compact mais pas plus résolu


    ------

    Bonjour à tous,

    cela m'a amusé d'apprendre que des forumistes avaient annoncé avoir résolu le pb de Syracuse et après avoir lu les quelques sujets, m'être documenté et posé quelques questions aux réponses heureuses , je vous propose , sans prétention , de valider cette simplification du problème, qui malheureusement reste entier mais abordable à tous niveaux.

    Je rappelle la définition initiale
    pour tout k > 2 de N , on définit la suite telle que S(1) = k et si S(n-1) est impair , S(n)= 3 S(n-1) + 1 sinon S(n)=S(n-1)/2
    La conjecture : toutes ces suites convergent vers la une suite dite triviale ( 4 , 2 , 1 ) qui se répétera ensuite indéfiniment

    Ca devrait se prouver par récurrence :
    Il faut démontrer que c'est vrai pour 5 , puis que si c'est vrai pour n-1, ca l'est aussi pour n.
    Notons en passant que c'est vrai pour 5.

    1re modification :
    pour tout k > 2 de N , on définit la suite telle que S(1) = k et si S(n-1) est impair , S(n)= 3 S(n-1) + 1 sinon itérer S(n)=S(n-1)/2 jusqu'à obtenir un S(n) impair. S'arrêter à 1.
    La suite est composée maintenant d'impairs uniquement hormis éventuellement le 1er élément. Elle s'arrêtera quand 3*S(n-1)+1 donnera 2^u qui sera réduit à 1

    2me modification :
    Il faut utiliser le théorême de récurrence forte qui permet dans une démonstration par récurrence, de devoir démontrer
    vrai pour 1 , 2 , jusqu'à n-1 => vrai à n
    au lieu de
    vrai pour n-1 => vrai à n

    Ceci permet de modifier à nouveau la définition en
    pour tout k > 2 de N , on définit la suite telle que S(1) = k et si S(n-1) est impair , S(n)= 3 S(n-1) + 1 sinon itérer S(n)=S(n-1)/2 jusqu'à obtenir un S(n) impair. S'arrêter quand S(n) < S(1)
    Pourquoi ? parce que à ce stade, la suite a été vérifiée pour tous les débuts inférieurs à S(1)

    3me modification :
    Exclusion des suites vérifiant la conjecture de manière triviale :
    1 ) exclusion de toutes les suites commençant par un nombre pair p=2m , puisque l'élément suivant est inférieur et a donc été déjà démontré
    2 ) exclusion de tous les nombres de la forme 4m+1 puisque le suivant aussi sera inférieur. En effet S(2) = 3*4m+3+1 = 4(3m+1) transformé au pire en 3m+1 ; or 3m+1 < 4m+1

    Il ne reste plus que les nombres de la forme 4m+3 pour lesquels il faut montrer que cette définition mène toujours à un nombre inférieur à S(1).

    forme compacte
    pour tout k > 2 et de la forme 4m+3 , k et m de N , on définit la suite telle que S(1) = k et A = 3 S(n-1) + 1 puis itérer S(n)=A/2 jusqu'à obtenir un S(n) impair. S'arrêter quand S(n) < S(1).
    La conjecture : toutes ces suites s'arrêtent.

    Une piste :
    A chaque mauvaise itération, on multiplie par 3 + epsilon et on divise au moins une fois par 2. La suite est équivalente à une succession de divisions par 2 entrecoupées par des multiplications par 3 et quelque. Pour atteindre un nombre inférieur à S(1), il faut un peu plus de divisions.
    par exemple f pour une valeur de m défavorable en partant de 4m+3 avec uniquement des divisions par 2 pour borner le rapport : f(n) = (m+1)/4 (3/2)^(n-1) -1

    une autre piste :
    Eliminer par algorithme les débuts triviaux et essayer de construire le S(1) qui ne finira jamais en itérant les conditions pair/impair ( et en passant aux nombres de la forme 2^d k + p ). Ou bien montrer qu'on ne peut pas le construire de la sorte.
    Pour construire la famille des nombres difficiles, la base 4 est notre amie. Notons qu'un nombre finissant par des 1 et commencant par un 3 ou un 1 est un bon précurseur de la fin. Sinon la base 2 est pas mal aussi.
    Pour voir ce qui se passe avec un difficile , passez le développement de la suite en base 4 pour chercher les ressemblances ...

    Il y aurait pas mal de choses à dire sur ces 2 pistes et d'autres du même genre pour construire des nombres intéressants.

    NB : par le théorème de récurrence forte, on pourrait aussi conserver les résultats en avant et donc si u apparait dans la suite dont S(1)=v avec u > v , alors la validité pour la suite commençant par u est acquise pour traiter le cas v+1 et suivants.
    On peut se demander , juste comme ca , si les nombres difficiles construits ne sont pas tous des nombres déjà vus pendant les "vols" des résolutions d'ordre inférieur.

    -----
    Dernière modification par mike.p ; 06/09/2013 à 01h47.

Discussions similaires

  1. Un produit de compact est compact.
    Par inviteaa7fccc7 dans le forum Mathématiques du supérieur
    Réponses: 1
    Dernier message: 15/12/2012, 18h12
  2. Conjecture de syracuse
    Par Nobel_prize_of_music dans le forum Mathématiques du supérieur
    Réponses: 1
    Dernier message: 29/01/2012, 12h42
  3. Syracuse:
    Par leg dans le forum Mathématiques du supérieur
    Réponses: 1
    Dernier message: 03/08/2011, 17h30
  4. [Thermique] Veilleuse Chauffe eau ELM LEBLANC ONDEA COMPACT ! [résolu]
    Par invitefbc9e143 dans le forum Dépannage
    Réponses: 5
    Dernier message: 12/07/2011, 19h01
  5. [Thermique] panne chaudiere city compact 24 bic [résolu]
    Par invite1e297352 dans le forum Dépannage
    Réponses: 3
    Dernier message: 05/11/2007, 17h39