13 novembre 2011

23 messages - Retourner à l'article

Le problème 3n+1 : élémentaire mais redoutable (I)

Échos de la recherche
Parmi tous les problèmes mathématiques actuellement non résolus, quel est celui dont l’énoncé est le plus élémentaire ? C’est peut-être bien le problème présenté ici : accessible à tout écolier de 8 ans, il défie les chercheurs depuis des décennies.
Piste verte
Le 13 novembre 2011, par Shalom Eliahou - 23 commentaires

  • Trajectoires divergentes

    le 13 novembre 2011 à 21:53, par Pierre Colmez

    Il est plus raisonnable de ne regarder que les nombres impairs de la suite, et on peut se demander quelle est la taille de $u_{n+1}$ en fonction de $u_n$. Or pour passer de $u_n$ à $u_{n+1}$ on commence par multiplier par $3$ et ensuite on divise par une puissance de $2$, à savoir $2$ une fois sur deux, $4$ une fois sur quatre, $8$ une fois sur huit, etc. En moyenne, on a $u_{n+1}\sim 3(\frac{1}{2^2}+\frac{1}{4^2}+\frac{1}{8^2}+\cdots)u_n=u_n$. Donc en moyenne la suite de Collatz ne bouge pas alors que celle basée sur $5x+1$ fournit une dilatation moyenne de rapport $5/3$.

    Répondre à ce message

    • Trajectoires divergentes

      le 14 novembre 2011 à 13:06, par électron

      Oui, à un « détail » près : il faut ici raisonner en moyenne géométrique. Pour le problème 3n+1, on arrive à la formule heuristique $(\frac{3}{2})^{\frac{1}{2}} (\frac{3}{4})^{\frac{1}{4}} (\frac{3}{8})^{\frac{1}{8}} \cdots$ ce qui donne, tous calculs faits, un facteur moyen égal à $\frac{3}{4}$ entre deux termes impairs d’une même suite. Il y a donc contraction en moyenne, ou du moins on s’attend à observer un comportement « globalement » décroissant. Nous obtenons de cette manière une estimation effective de la vitesse de contraction, qui semble fonctionner pour « la plupart » des suites. Cet argument a été formulé dans les articles de Crandall (1978), Lagarias (1985), et plus récemment Jean-Paul Delahaye (1998, Pour la Science no 247). Il est possible de simplifier le raisonnement en considérant « l’accélération » $n -> (3n+1)/2$ pour tout $n$ impair ...

      Dans le cas de la variante 5n+1, le même argument conduit à un facteur moyen égal à $\frac{5}{4}$ entre les termes impairs.

      Olivier

      Répondre à ce message

      • Trajectoires divergentes

        le 6 avril 2016 à 13:32, par AITYOUSSEF ABDELKARIM

        Que veut dire trajectoire divergente ?

        Répondre à ce message

    • Élémentaire

      le 8 janvier 2018 à 21:20, par ayoub dz

      Pour comprendre l’énoncé du problème 3n+1=12=3
      3*3+4*4=5*5=1212+2222=3434=196 = 7**1/2

      Répondre à ce message

  • Le problème 3n+1 : élémentaire mais redoutable (I)

    le 17 novembre 2011 à 08:08, par Marc JAMBON

    Si on remplace 3n + 1 par 3n -1 on obtient :
    2 ; 1
    3 ; 8 ; 4 ; 2 ; 1
    4 ; 2 ; 1 
    mais
    5 ; 14 ; 7 ; 20 ; 10 ; 5
    là on a un cycle non trivial, le procédé se poursuit sans fin.

    Répondre à ce message

    • Le problème 3n+1 : élémentaire mais redoutable (I)

      le 17 novembre 2011 à 12:45, par Shalom Eliahou

      Effectivement, remplacer 3n+1 par 3n-1 revient à considérer 3n+1 sur les entiers négatifs. On retrouve alors les trajectoires cycliques de -5 et de -17.

      Shalom

      Répondre à ce message

  • Le problème 3n+1 : élémentaire mais redoutable (I)

    le 20 mai 2012 à 20:53, par Sve@r

    Bonjour
    Je pense que ce problème ne peut pas se résoudre parce que la formulation « si n est pair » ne possède pas d’opérateur mathématique. En effet, on peut formuler « ajouter » par le signe « + » qui possède ses propriétés (commutativité, associativité, etc) et on peut ensuite le lier aux autres par des factorisations ou des développement pour simplifier ses opérations comme a * (b+c) mais en revanche on n’a pas de symbole ou d’outil pour signifier « si » et donc on ne peut pas simplifier la formulation « si n pair => n/2 sinon 3n+1 »...

    Répondre à ce message

    • Autre définition de la suite

      le 20 mai 2016 à 02:19, par PANTAGO

      (Ne sachant pas comment noter ici les indices et les exposants, je note u1 le terme qui suit u).
      La définition de la suite peut s’écrire :
      u1=( 7u + 2)/4 -[ (-1)^u] (5u +2 )/4
      Ca ne résout pas le problème, mais c’est amusant.

      Répondre à ce message

  • Le problème 3n+1 : élémentaire mais redoutable (I)

    le 25 novembre 2014 à 09:58, par CHEHIKIAN Raymond

    J’ai pu vérifier - par ordinateur avec un programme que j’ai personnellement réalisé - la conjecture « jusqu’à »
    x.10^1200 (temps de calcul et affichage de l’ordre de 6 minutes). Je puis vous adresser un document de vol d’un nombre
    défini aléatoirement et ayant exactement 1200 chiffres.
    Je précise que j’ai pu vérifier pour un tel nombre et non pas de 4 à ce nombre..

    Répondre à ce message

    • Le problème 3n+1 : élémentaire mais redoutable (I)

      le 25 novembre 2014 à 17:00, par Shalom Eliahou

      Je voudrais préciser qu’avec des gros systèmes de calcul formel comme Sage (gratuit), Mathematica ou Maple par exemple, on peut faire de l’arithmétique exacte sur des nombres entiers arbitrairement grands — la seule limite étant la mémoire disponible. Mais typiquement, avec ces systèmes, on peut faire des calculs exacts rapides sur des nombres à 100000 chiffres par exemple.

      Votre mérite, bien sûr, est d’avoir tout programmé vous-même ! Alors oui, volontiers, envoyez-moi un tel document généré par votre programme.

      Répondre à ce message

  • Le problème 3n+1 : élémentaire mais redoutable (I)

    le 19 mai 2015 à 18:45, par madec

    C’est effectivement un très beau problème d’arithmétique.

    Répondre à ce message

  • Une manière d’aborder le problème ?

    le 18 juin 2015 à 19:06, par Olivier Madec

    Voici, peut-être, une manière d’aborder le problème :
    A un nombre entier n on peut définir une trajectoire libre ou naturelle par la transformation de Collatz.
    A un nombre entier m on peut définir une trajectoire contrainte
    à partir de la trajectoire libre d’un autre entier n en essayant de forcer l’entier m à suivre la trajectoire de n
    au lieu de sa trajectoire naturelle.
    Ou encore, de manière plus large, on peut définir une trajectoire contrainte de m en définissant pour cet entier
    une trajectoire guidée par celle libre de n.
    On pourra essayer de définir une trajectoire contrainte ou bien, inversement, essayer de retrouver une définition possible à partir d’exemples.

    L’avantage d’une trajectoire contrainte est qu’elle pourra être définie pour des réels et dépendre de paramètres.

    Comme il a plusieurs façons de définir des trajectoires contraintes pour une même trajectoire libre d’un entier, il est utile de
    les faire apparaître sur une même table.Toutes ces trajectoires apparaissent alors comme des trajectoires
    conjointes ce qui pourrait éventuellement permettre une analyse d’ensemble.

    Voici quelques exemples :
    En première ligne se trouve la trajectoire libre de n
    (Sortie : Console du logiciel R).

    [,1] [,2] [,3] [,4] [,5] [,6] [,7] [,8] [,9] [,10] [,11] [,12] [,13] [,14] [,15] [,16] [,17] [,18] [,19] [,20] [,21]
    [1,] 19 58 29 88 44 22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1
    [2,] 15 65 65 225 225 225 225 687 687 2079 2079 2079 6251 6251 6251 6251 18759 18759 18759 18759 18759
    [3,] 58 175 87 262 131 65 32 97 48 145 72 36 109 54 27 13 40 20 10 5 2
    [4,] 131 452 2 94 -608 2 2 39 -223 -620 2 -179 -500 2 -134 2 20 -90 -95 2 2

    [,1] [,2] [,3] [,4] [,5] [,6] [,7] [,8] [,9] [,10] [,11] [,12] [,13] [,14] [,15] [,16] [,17] [,18] [,19] [,20] [,21]
    [1,] 19.00000 58.00000 29 88 44 22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1
    [2,] 15.00000 65.00000 65 225 225 225 225 687 687 2079 2079 2079 6251 6251 6251 6251 18759 18759 18759 18759 18759
    [3,] 10.75833 33.27499 16 49 24 12 6 19 9 28 14 7 22 11 5 2 7 3 1 0 0
    [4,] 131.00000 404.75833 14 59 -93 2 -29 -80 2 16 -62 -66 -190 -150 2 2 9 -13 -14 2 1

    [,1] [,2] [,3] [,4] [,5] [,6] [,7] [,8] [,9] [,10] [,11] [,12] [,13] [,14] [,15] [,16] [,17] [,18] [,19]
    [1,] 29.00000 88.0000 44 22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1
    [2,] 15.00000 75.0000 75 75 75 237 237 729 729 729 2201 2201 2201 2201 6609 6609 6609 6609 6609
    [3,] 16.53183 50.5955 25 12 6 19 9 28 14 7 22 11 5 2 7 3 1 0 0
    [4,] 131.00000 410.5318 10 2 -29 -80 2 16 -62 -66 -190 -150 2 2 9 -13 -14 2 1

    [,1] [,2] [,3] [,4] [,5] [,6] [,7] [,8] [,9] [,10] [,11] [,12] [,13] [,14] [,15] [,16] [,17] [,18] [,19]
    [1,] 29.00000 88.0000 44 22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1
    [2,] 15.00000 75.0000 75 75 75 237 237 729 729 729 2201 2201 2201 2201 6609 6609 6609 6609 6609
    [3,] 16.53183 50.5955 25 12 6 19 9 28 14 7 22 11 5 2 7 3 1 0 0
    [4,] 531.00000 1610.5318 2 2 -29 -80 2 16 -62 -66 -190 -150 2 2 9 -13 -14 2 1

    [,1] [,2] [,3] [,4] [,5] [,6] [,7] [,8] [,9] [,10] [,11] [,12] [,13] [,14] [,15] [,16] [,17] [,18] [,19] [,20] [,21]
    [1,] 19.000000 58.00000 29 88 44 22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1
    [2,] 125.000000 395.00000 395 1215 1215 1215 1215 3657 3657 10989 10989 10989 32981 32981 32981 32981 98949 98949 98949 98949 98949
    [3,] 10.758330 33.27499 16 49 24 12 6 19 9 28 14 7 22 11 5 2 7 3 1 0 0
    [4,] 3.141593 21.18311 5 32 2 -59 2 13 -41 -113 2 -34 -94 -102 2 2 9 -13 -14 2 1

    Remarquons alors la suite 2, 2, 9, -13, -14, 2, 1.

    Répondre à ce message

    • Une manière d’aborder le problème ?

      le 26 juin 2015 à 18:01, par Olivier Madec

      Je voudrais apporter quelques précisions à la suite
      de mon commentaire.

      Nous avons vu que nous pouvions définir la notion de trajectoire
      contrainte d’un nombre m par rapport à un entier n, et en
      particulier, celle qui consiste à obliger à m à suivre, le plus
      possible, le mouvement libre de n.

      Dans ce cas, la trajectoire contrainte de n par rapport à lui-même
      doit correspondre à sa propre trajectoire libre.

      je donne 2 exemples où la trajectoire contrainte de m par rapport à n rejoint la trajectoire libre de n,
      les deux trajectoires ayant la même longueur.

      2 exemples (Sortie : Console du logiciel R) :

      Avec n=180 et m=216.6779 (lignes 1 et 3).
      Les trajectoires se rejoignent au rang 14 avec 5 comme nombre conjoint.

      Avec n=720 et m=832.6968 (lignes 1 et 3).
      Les trajectoires se rejoignent au rang 15 avec 10 comme nombre conjoint.

      Exemple 1 :

      [,1] [,2] [,3] [,4] [,5] [,6] [,7] [,8] [,9] [,10] [,11] [,12] [,13] [,14] [,15] [,16] [,17] [,18] [,19]
      [1,] 180.0000 90 45 136 68 34 17 52 26 13 40 20 10 5 16 8 4 2 1
      [2,] 125.0000 125 125 421 421 421 421 1281 1281 1281 3857 3857 3857 3857 11577 11577 11577 11577 11577
      [3,] 216.6779 108 54 163 81 40 20 61 30 15 46 23 11 5 16 8 4 2 1
      [4,] 180.0000 5 2 61 2 -3644 -3622 -10845 2 -1349 -4031 2 -1034 -1012 -3030 -2235 2 -179 2

      Exemple 2 :

      [,1] [,2] [,3] [,4] [,5] [,6] [,7] [,8] [,9] [,10] [,11] [,12] [,13] [,14] [,15] [,16] [,17] [,18] [,19] [,20] [,21]
      [1,] 720.0000 360 180 90 45 136 68 34 17 52 26 13 40 20 10 5 16 8 4 2 1
      [2,] 125.0000 125 125 125 125 421 421 421 421 1281 1281 1281 3857 3857 3857 3857 11577 11577 11577 11577 11577
      [3,] 832.6968 416 208 104 52 157 78 39 19 58 29 14 43 21 10 5 16 8 4 2 1
      [4,] 720.0000 2 -74879 2 -18719 -56104 -56312 -42196 -28118 -84334 -52607 2 21 2 -3779 2 12 -2874 -2877 2 -359

      Pour un entier n donné, il pourrait être intéressant de trouver « son nombre conjoint » (on suppose que
      l’on peut lui associer un réel de manière privilégiée, de sorte que les deux trajectoires se rejoignent comme dans les deux exemples précédents) ...

      Répondre à ce message

      • Une manière d’aborder le problème ?

        le 22 juillet 2015 à 19:00, par Olivier Madec

        Précisons encore... Un entier naturel (supérieur à deux) possède un nombre conjoint qui lui est
        strictement inférieur. Mais ce nombre conjoint possède lui-même un nombre conjoint pourvu
        qu’il soit supérieur à deux. De proche en proche on aboutit soit à 2 soit à 1.
        Autrement dit, il existe une sous-suite décroissante et convergente vers 1 ou 2 dans la trajectoire de Collatz. Ce résultat, si on pouvait le démontrer, suffirait pour pouvoir conclure quant à la conjecture de Collatz.

        Il me semble intéressant de donner ici la table de ces sous-suites pour chaque entier de 3 à 50.
        (Sortie logiciel R).

        [1] 3 1
        [1] 4 1
        [1] 5 1
        [1] 6 1
        [1] 7 2
        [1] 8 1
        [1] 9 4 1
        [1] 10 2
        [1] 11 2
        [1] 12 4 1
        [1] 13 2
        [1] 14 4 1
        [1] 15 4 1
        [1] 16 2
        [1] 17 4 1
        [1] 18 4 1
        [1] 19 4 1
        [1] 20 4 1
        [1] 21 2
        [1] 22 4 1
        [1] 23 4 1
        [1] 24 4 1
        [1] 25 4 1
        [1] 26 4 1
        [1] 27 5 1
        [1] 28 4 1
        [1] 29 4 1
        [1] 30 4 1
        [1] 31 5 1
        [1] 32 2
        [1] 33 5 1
        [1] 34 4 1
        [1] 35 4 1
        [1] 36 13 2
        [1] 37 4 1
        [1] 38 5 1
        [1] 39 5 1
        [1] 40 4 1
        [1] 41 5 1
        [1] 42 2
        [1] 43 13 2
        [1] 44 4 1
        [1] 45 4 1
        [1] 46 4 1
        [1] 47 5 1
        [1] 48 3 1
        [1] 49 13 2
        [1] 50 5 1

        Répondre à ce message

  • Le problème 3n+1 : Où est le problème ?

    le 11 décembre 2015 à 13:58, par Kimyh

    Avant de savoir si l’ont peux échapper à 1, il faut réfléchir à comment arriver à 1.

    Selon la formule, deux possibilités :

    * Diviser le chiffre pair 2
    * Avoir un nombre impair qui multiplié par 3 donne 0 (ce qui est donc exclut)
    La seule solution réside dans le fait de tomber sur le chiffre 2

    Hors, la configuration du calcul nous fait immanquablement tomber sur un nombre pair, qui sera donc divisible par 2. Et même si le résultats est impair, le résultat suivant le sera.
    De ce fait, quel que soit la grandeur du nombre, selon le schéma de ce calcul, il nous ramènera à 2, et donc à 1.

    Je peux également l’expliquer d’une autre façon :

    Je peux multiplier 1 par 2.
    Tout nombre entier qui est multipliable par 2 me ramènera à 1 selon la formule proposée.
    Est-ce qu’il existe un nombre entier que je ne peux pas multiplier par 2 ? Non.
    De ce fait, quel que soit le nombre, et la trajectoire qui en découlera, le résultat final sera 1

    Quelqu’un peut-il prouver que je me trompe ?

    Kimyh

    Répondre à ce message

    • Le problème 3n+1 : Où est le problème ?

      le 22 juillet 2016 à 18:30, par Olivier Madec

      Il me semble que si votre raisonnement était juste il devrait pouvoir également s’appliquer aux entiers négatifs.
      Or pour -5 cela ne fonctionne pas à cause du cycle -5 -14 -7 -20 -10 (ce qui exclut qu’on puisse « arriver » à 1 pour -5).

      Répondre à ce message

  • Le problème 3n+1 : élémentaire mais redoutable (I)

    le 5 avril 2016 à 20:34, par AITYOUSSEF ABDELKARIM

    Est-il vrai qu’il n’y a aucune trajectoire divergente ?

    A ma connaissance toute trajectoire est limitée et est divergente : ne possède pas de limite finie ou infinie.

    Répondre à ce message

  • Le problème 3n+1 : élémentaire mais redoutable (I)

    le 18 novembre 2018 à 09:47, par Pierre Cami

    Si la conjecture est vérifiée tout nombre entier a(i) conduit à 1 après une suite d’opérations qui suivent :
    si a(i) est de la forme (2*n+1)*2^j, a(i-1)=2*n+1 et si a(i) est impair de la forme 2*n+1, a(i-1)=6*n+4
    à la fin a(0) est toujours égal à 1 si la conjecture est vérifiée.
    Définissons l’ensemble des suites u(i) qui contiennent tout prédécesseur possible de u(i-1).
    On commence par U(0)=1et on ne considère que les nombres impairs.
    Les termes de la suite U(1) sont donnés par la formule (4^n-1)/3 pour n de 1 à N.
    Les termes de la suite U(2) sont donnés par : (((4^n-1)/3)*4^j-1)/3 si (4^n-1)/3 est 1 modulo 6 ou par((4^n-1)/3) *2^(2*j-1)-1)/3 si (4^n-1)/3 est 5 modulo 6 pour n de 1 à N et j de 1 à N.
    Les termes de la suite U(i) sont donnés par (U(i-1)*4^k-1)/3 si U(i-1) est 1 modulo 6 ou par (U(i-1)*2^(2*k-1)-1)/3 si U(i-1) est 5 modulo 6 pour toutes les valeurs de U(i-1) et k de 1 à N.
    Il est facile de vérifier que chaque nombre impair est présent une fois et une seule fois dans l’ensemble des suites U(i) ci-dessus définies, d’où la vérification de la conjecture de Collatz.

    Répondre à ce message

    • Le problème 3n+1 : élémentaire mais redoutable (I)

      le 18 novembre 2018 à 15:24, par Pierre Cami

      Ci-joint un premier tableau pour le cas 1modulo 6

      Répondre à ce message

  • Le problème 3n 1 : élémentaire mais redoutable (I)

    le 18 novembre 2018 à 16:41, par Pierre Cami

    Définissons l’ensemble des suites u(i) qui contiennent tout prédécesseur possible de u(i-1).
    On commence par U(0)=1et on ne considère que les nombres impairs.
    Les termes de la suite U(1) sont donnés par la formule (4^n-1)/3 pour n de 1 à N.
    Les termes de la suite U(2) sont donnés par : (((4^n-1)/3)*4^j-1)/3 si (4^n-1)/3 est 1 modulo 6 ou par((4^n-1)/3) *2^(2*j-1)-1)/3 si (4^n-1)/3 est 5 modulo 6 pour n de 1 à N et j de 1 à N.
    Les termes de la suite U(i) sont donnés par (U(i-1)*4^k-1)/3 si U(i-1) est 1 modulo 6 ou par (U(i-1)*2^(2*k-1)-1)/3 si U(i-1) est 5 modulo 6 pour toutes les valeurs de U(i-1) et k de 1 à N.
    Il est facile de vérifier que chaque nombre impair est présent une fois et une seule fois dans l’ensemble des suites U(i) ci-dessus définies, d’où la vérification de la conjecture de Collatz.
    Voir tableaux ci-dessous .
    A(L) = 6*(L-1)+1 , L de 1 à N
    T(L,C) = (A(L)*4^C-1)/3 , L et C de 1 à N
    A(L) L
    1 1 1 5 21 85 341
    7 2 9 37 149 597 2389
    13 3 17 69 277 1109 4437
    19 4 25 101 405 1621 6485
    25 5 33 133 533 2133 8533
    31 6 41 165 661 2645 10581
    37 7 49 197 789 3157 12629
    43 8 57 229 917 3669 14677
    49 9 65 261 1045 4181 16725
    55 10 73 293 1173 4693 18773
    61 11 81 325 1301 5205 20821
    67 12 89 357 1429 5717 22869
    73 13 97 389 1557 6229 24917
    79 14 105 421 1685 6741 26965
    85 15 113 453 1813 7253 29013
    91 16 121 485 1941 7765 31061
    97 17 129 517 2069 8277 33109
    103 18 137 549 2197 8789 35157
    109 19 145 581 2325 9301 37205
    115 20 153 613 2453 9813 39253
    121 21 161 645 2581 10325 41301
    127 22 169 677 2709 10837 43349
    133 23 177 709 2837 11349 45397
    139 24 185 741 2965 11861 47445
    145 25 193 773 3093 12373 49493
    151 26 201 805 3221 12885 51541
    157 27 209 837 3349 13397 53589
    163 28 217 869 3477 13909 55637
    169 29 225 901 3605 14421 57685
    175 30 233 933 3733 14933 59733
    181 31 241 965 3861 15445 61781
    187 32 249 997 3989 15957 63829
    193 33 257 1029 4117 16469 65877
    199 34 265 1061 4245 16981 67925
    205 35 273 1093 4373 17493 69973
    211 36 281 1125 4501 18005 72021

    A(L) = 6*(L-1)+5 , L de 1 à N
    T(L,C) = (A(L)*2^(2*C-1)-1)/3 , L et C de 1 à N
    A(L)
    6*(L-1)+5 L
    5 1 3 13 53 213 853
    11 2 7 29 117 469 1877
    17 3 11 45 181 725 2901
    23 4 15 61 245 981 3925
    29 5 19 77 309 1237 4949
    35 6 23 93 373 1493 5973
    41 7 27 109 437 1749 6997
    47 8 31 125 501 2005 8021
    53 9 35 141 565 2261 9045
    59 10 39 157 629 2517 10069
    65 11 43 173 693 2773 11093
    71 12 47 189 757 3029 12117
    77 13 51 205 821 3285 13141
    83 14 55 221 885 3541 14165
    89 15 59 237 949 3797 15189
    95 16 63 253 1013 4053 16213
    101 17 67 269 1077 4309 17237
    107 18 71 285 1141 4565 18261
    113 19 75 301 1205 4821 19285
    119 20 79 317 1269 5077 20309
    125 21 83 333 1333 5333 21333
    131 22 87 349 1397 5589 22357
    137 23 91 365 1461 5845 23381
    143 24 95 381 1525 6101 24405
    149 25 99 397 1589 6357 25429
    155 26 103 413 1653 6613 26453
    161 27 107 429 1717 6869 27477
    167 28 111 445 1781 7125 28501
    173 29 115 461 1845 7381 29525
    179 30 119 477 1909 7637 30549
    185 31 123 493 1973 7893 31573
    191 32 127 509 2037 8149 32597
    197 33 131 525 2101 8405 33621
    203 34 135 541 2165 8661 34645
    209 35 139 557 2229 8917 35669
    215 36 143 573 2293 9173 36693

    Répondre à ce message

    • Le problème 3n 1 : élémentaire mais redoutable (I)

      le 22 décembre 2018 à 15:47, par électron

      Bonjour Pierre,
      Votre matrice permet de décrire intégralement le graphe qui relie entre eux les entiers positifs impairs via l’application répétée de la transformation de Collatz. Il est donc exact que chaque entier impair y figure une fois et une seule. Toute la question est de savoir si ce graphe est connexe, comme le suggère l’image en préambule. C’est précisément là que réside le coeur du problème !
      Olivier R.

      Répondre à ce message

      • Le problème 3n 1 : élémentaire mais redoutable (I)

        le 23 décembre 2018 à 10:03, par Pierre Cami

        Je pense que vous n’avez pas compris, si on est d’accord que tous les nombres impairs sont présents une fois et une fois seulement dans tous les U(i) pour i de 0 à N (sauf 1 présent dans U(0) et U(1) cycle trivial oblige) il est évident que la conjecture est vérifiée puisque tout nombre impair est généré par l’inverse transformation de Collatz de façon univoque.
        Il est donc démontré qu’on peut aller de 1 à 11111111111111111111 de façon univoque mais on ne peut dire par quel chemin on arrive à 111111111111111111111 là est peut être votre incompréhension.
        La démonstration est donc que tout nombre impair est généré par l’inverse transformation de Collatz de façon unique en partant de 1, et il n’est pas nécessaire de connaitre le chemin pour en faire la preuve.

        Répondre à ce message

      • Le problème 3n 1 : élémentaire mais redoutable (I)

        le 20 janvier 2020 à 11:22, par CAMI

        Tout nombre entier impair X positif a une représentation unique utilisant deux variables L et C entières positives > 0.
        X = ((3L-2)2^C-1)/3 pour L impair et C pair
        X = ((3L-1)2^C-1)/3 pour L pair et C impair

        Démonstration :

        X = 3X/3 = ((3X+1)-1)/3
        3X+1 est pair, 1 modulo 3.
        3X+1 ne peut être que le produit d’un nombre impair 1 modulo 3 par une puissance de 2 qui doit être 1 modulo 3, ou le produit d’un nombre impair -1 modulo 3 par une puissance de 2 qui doit être -1 modulo 3.
        Les puissances de 2 paires sont 1 modulo 3
        Les puissances de 2 impaires sont -1 modulo 3
        Donc deux représentations possibles pour X en fonction de L et C
        Pour L impair et C pair X = ((3L-2)2^C-1)/3
        Pour L pair et C impair X = ((3L-1)2^C-1)/3
        On peut donc construire un tableau qui contient tout nombre impair X une fois et une fois seulement en utilisant les deux formules ci-dessus, le tableau a pour lignes L et pour colonnes C, L > 0 et C > 0.

        Trajectoire de Collatz :

        A tout nombre entier positif impair X(1) et on fait succéder le nombre pair 3X(1)+1, et le nombre pair est divisé par 2 jusqu’à obtenir le nombre impair X(2) suivant, et ainsi de suite.
        La conjecture de Collatz dit que pour tout X(1) entier positif de départ on arrive après n nombres impairs à X(n)=1 puis répétition du cycle trivial 4, 2, 1.
        Tout nombre impair a une représentation unique pour 2 variables entières positives L et C,
        - soit ((3L-2)2^C-1)/3 pour L impair et C pair
        - soit ((3L-1)2^C-1)/3 pour L pair et C impair
        Tout nombre X = ((3L-2)2^C-1)/3 a pour successeur impair 3*L-2, L impair>0.
        Tout nombre X = ((3*L-1)*2^(2*C-1)-1) a pour successeur impair 3*L-1, L pair >0.
        Tous les nombres impairs de la trajectoire sont donc obligatoirement différents les uns des autres et toujours 3*L-2 pour L impair et 3*L-1 pour L pair sauf si L=1 car alors on tombe sur le cycle trivial 4, 2, 1 et perpétuelle répétition du cycle dit trivial.
        Ceci apporte la preuve qu’il ne peut exister d’autre cycle que le cycle trivial.

        Répondre à ce message
Pour participer à la discussion merci de vous identifier : Si vous n'avez pas d'identifiant, vous pouvez vous inscrire.

Actualités des maths