NOMBRES - Curiosités, théorie et usages

 

Accueil                           DicoNombre            Rubriques           Nouveautés      Édition du: 25/08/2017

Orientation générale        DicoMot Math          Atlas                   Références                     M'écrire

Barre de recherche          DicoCulture              Index alphabétique                               

     

Suite de nombres

 

Débutants

Général

Itérations – Cycles

 

Glossaire

Suites

et Séries

 

 

INDEX

Rubriques

 

 

 

 

Suite de Fibonacci

Triangle de Pascal

Triangle de Leibniz

Procédé de Kaprekar

Cycle de Syracuse

Cycle des Carrés

Nombres Chanceux

Suite de Padovan

Suite de Steinhaus

Syracuse – Débutant

 

Sommaire de cette page

 

>>> Cycle 3x + 1

>>> Hauteur et temps de vol

>>> Comportement de la conjecture

>>> Records

>>> Démonstration

>>> Historique

>>> Conjectures équivalentes

 

Syracuse – Développement

Syracuse – Variantes

Syracuse – Algèbre (2x3y)

Syracuse – Tables

Syracuse et nombre 27

Syracuse – Programmation

 

 

 

Le CYCLE ou le PROBLÈME 3x + 1

Conjecture ou problème ou cycle ou transformation

 de SYRACUSE, COLLATZ …  Autres noms

 

 

Il s'agit d'une séquence très simple d'opérations sur les nombres qui ramène toujours au même endroit, le nombre 1. D'abord un amusement, cette étonnante suite est devenue troublante pour les mathématiciens qui ne se lassent pas de l'explorer sans avoir encore réussi à la domestiquer.

Statistique sur les temps d'arrêt jusqu'à 100 millions =>

Voir Découverte Junior des cycles tels que celui de Syracuse / Conjectures

 

 

Citations

 

Selon Paul Erdös (1913-1996), Richard Guy (1983) et Jeffrey Lagarias (2010), les mathématiques ne seraient pas encore assez mûres pour espérer résoudre cet innocent petit problème.

*      Mathematics may not be ready (or ripe1) for such problems – Erdös.

*      Don’t try to solve these problems – Richard Guy.

*      This is an extraordinarily difficult problem, completely out of reach of present day mathematics – Lagarias.

1 Ripe (mûr) semble être l'original plutôt que ready (prêt).
  Toutes ces citations sont rapportées par Lagarias.

Traduction: Les mathématiques sont sans doute pas prêtes (mûres) pour de tels problèmes. Ne tentez pas de résoudre de tels problèmes. C'est un problème extraordinairement difficile, complètement hors d'atteinte des mathématiques actuelles.

 

 

CYCLE

 

Approche

*    Il s'agit d'une itération sur un nombre entier de départ telle que

si le nombre est impair on le gonfle

s'il est pair on l'amorti.

 

*    Au cours des itérations, le nombre va osciller en croissant et décroissant, parfois atteignant des hauteurs insoupçonnées, mais il finira toujours par se poser en finissant par la valeur 1. Incroyable!

 

Règle

 

5 se transforme en 3 x 5+ 1 = 16

     6 devient 6/2 = 3

 

Exemple départ avec 5

 

La procédure nous entraîne vers 1.

En poursuivant nous entrons dans une boucle avec le 4.

 

Exemple départ avec 13

 

Après quelques étapes, nous rencontrons le 5, objet de l'exemple précédent. Avec 13, la procédure conduit également vers le 1 et sa boucle en 4.

 

 

 

HAUTEUR ET TEMPS DE VOL

 

*    Départ: 5

*    Altitude ou hauteur du vol : 16

*    Durée du vol en altitude: 2

*    Durée du vol: 5

*    Fin de cycle: 1

*    Temps d'arrêt: 3

Quantité d'étapes pour atteindre le nouveau passage par n (en rose).
Pour n = 27, il vaut 59.

 

*    Taux d'expansion: 8/5 = 1,6

Numérateur = max / 2, et
Dénominateur = n.
Pour n = 27, il vaut 171.

 

 

Note: chaque auteur précise ces notions en tête de leurs articles.

 

 

Voir ce même graphique pour n = 27

 

 

 

Comportement de la série

 

Conjecture

 

Pour tout n, la fin de cycle est 1.

 

Pas encore démontrée, mais vérifiée jusqu'à n = 1018 .

 

 

Valeurs pour n de 10 à 30

 

*    Pour chaque nombre, la colonne donne la séquence complète qui s'arrête à 1.

*    En violet, les nouveautés. La suite vers le bas est déjà vue dans une séquence située à gauche.

Voir Présentation sous forme d'un arbre

 

 

Record de durée de vol pour n de 1 à 1 000 000

 

*    Par exemple, pour n = 18, la durée de vol (la quantité d'itérations) est égale à 20.
Résultat lisible aussi sur le tableau situé juste au-dessus en colonne 18.
Pour n = 27, c'est 111.
 

Voir Cas du nombre 27/ Suite en Tables

 

 

Organisation en rond des suites de Collatz

Extrait de la séquence animée sur 19 itérations de Jason Davies – À voir absolument!

 

 

Démonstration

 

*    Il existe de nombreuses tentatives de démonstration de cette conjecture.

*    Par exemple, on a prouvé que:

 

 Il existe une constante C telle que, si n est assez grand, alors le nombre de valeurs inférieures à n qui atterrissent en 1 est supérieur à nC.

 

*    En partant de C = 0,05 en 1978,  on a atteint C = 0,81 en 1999.
Il faut aboutir à C = 1 pour démontrer la conjecture.

 

Cycle

*    S'il existe un autre cycle que [1, 4, 2, 1], alors son plus petit élément a0 est impair car si a0 était pair sont successeur serait a1 = a0/2, plus petit que a0; soit une contradiction avec notre hypothèse. D'autre part, la boucle étant différente de celle connue, a0 est plus grand que 3. Ce nombre impair a pour successeur a1 = 3 a0 + 1 qui est pair.

 

Approche probabiliste

*    Statistiquement, pour une suite compressée, un nombre pair est multiplié par 1/2, alors qu'un nombre impair l'est par 3/2.  On montre que la tendance générale tend à la baisse dans un rapport (3/4)1/2 = 0,866…

*    On imagine que la suite ne peut pas croître indéfiniment, mais sans en avoir la preuve.

*    La théorie ergodique est également appelée au secours pour tenter de trouver quelque chose …

Voir Point de la situation concernant la démonstration

 

 

 

Historique de la conjecture de Collatz

 

*    Origine diffuse: pas de correspondance ou de publication attestée. Le problème circulait de bouche à oreille entre mathématiciens. La conjecture est traditionnellement créditée à Lothar Collatz (1910-1990), mathématicien allemand (Hambourg). 

Photo de 1990 =>

Dans les années 1930, il étudie les œuvres d'Edmund Landau, Oskar Petron et Isaac Schur. Il s'intéresse aux fonctions en théorie des nombres et à la théorie des graphes. Il a l'idée de conjuguer les deux domaines et de s'interroger sur la structure graphes en relations avec le comportement des fonctions.

En 1932, il s'intéresse à une fonction qui progresse selon le mod3 (voir encadré).

 

Il formalise la conjecture qui porte son nom en 1937 sans la publier. En 1950, il la présente dans divers séminaires. En 1952, il la présente à Helmut Hasse, lequel la diffuse à l'université de Syracuse. De son côté, Stanislas Ulam en fait état au Laboratoire national de Los Alamos. La conjecture atteint Yale et Chicago dans les années 1960 avec Shizuo Kakutani.

Elle créa un tel engouement auprès des mathématiciens durant la guerre froide que certains plaisantaient en faisant croire à un complot soviétique destiné à ralentir le recherche américaine.

 

*    C'est ainsi que l'on connaît ce sujet sous divers noms:

*        Problème 3n + 1, dénomination la plus courante; problème pouvant être remplacé par conjecture lorsqu'on signifie quelle se termine toujours par 1;

*        Problème de Collatz; de Kakutani; de Hasse; d'Ulam; de Thwaites

*        Problème de Syracuse du nom de l'université des États-Unis qui a étudié ce problème, suite à sa diffusion par un collègue de Collatz;

*        Suite de grêlons (hailstones), nom parfois donné en littérature pour tous.

*        Wondrous numbers (nombres merveilleux)

*    Dans les années 1970, intérêt renouvelé pour ce problème du fait de la disponibilité des ordinateurs.

De nombreux mathématiciens se sont cassés les dents sur un problème pourtant bien simple en apparence. La conjecture à ce jour n'est toujours pas démontrée. Elle a été testée à maintes reprises avec de puissants moyens de calcul. Le record actuel est de 262 (= 4.6… 1018) obtenu par Tomas Oliveira e Silva depuis 2009.

 

*    En 1972, J.H. Conway a prouvé que la généralisation naturelle du problème de Collatz est logiquement indécidable par algorithme.

 

*    En 2011, Jeffrey Lagarias publie: The Ultimate Challenge: Th 3x+1 Problem. Depuis 1985, cet expert tient à jour une liste commentée de toutes les publications consacrées à la conjecture de Collatz.



  

 

Conjectures équivalentes

 

*    Toutes les trajectoires formées par la transformation de Collatz finit par atteindre 1. Si ce n'était pas le cas n serait supérieur à 5.1018.

*    Le vol se termine toujours par 1;

*    Les trajectoires de Collatz ne comporte qu'un seul cycle: 1, 4, 2, 1. S'il existait un autre cycle on sait que sa longueur serait supérieure à 17 milliards.

*    Les trajectoires de Collatz ne sont jamais divergentes.

*    Tout nombre > 4 a une durée de vol en altitude finie;

*    La durée de tout vol est finie;

*    Tout vol a un nombre fini d'étapes paires;

*    Tout vol a un nombre fini d'étapes paires en altitude;

*    Tout vol a un nombre fini d'étapes impaires;

*    Tout vol a un nombre fini d'étapes impaires en altitude.
 

Voir Variantes du cycle de Collatz

 

 

 

 

Retour

*    Syracuse – Débutant (familiarisation avec tableur)

Suite

*    Syracuse – Variantes

*    Syracuse – Algèbre (sommes en 2x3y)

*    Syracuse – Tables

*    Syracuse – Découverte junior

*    Fractales et cycles

*    Autres, voir en haut de page

Voir

*    Boucle infernale

*    Boucle SP (Somme x Produit)

*    Calcul mentalIndex

*    GéométrieIndex

*    Nombre Harshad

*    Nombres narcissiques

*    Nombres retournés

*    Palindrome retard

*    Preuve par neuf en pratique

*    Récurrence

*    Retournés et premiers

*    Théorie des nombres Index

Diconombre

*    Nombre 0,866 …

*    Nombre 9

*    Nombre 495

*    Nombre 6 174

*    Nombre 82 962 & 98 622

 

Livres

*      La conjecture Syracuse par Jean-Paul Delahaye - Pour la science - 247- mai 1998

*      Dites un chiffe – Malcom Lines – Champs Flammarion – 1999 – Ch.3

*    The Ultimate Challenge: The 3x+1 Problem – Jeffery C. Lagarias – 2010

*      The 3x+1 Problem: An Annotated Bibliography, II (2000-2009) – Jeffrey C. Lagarias

Animation

Interactif

*      Collatz Graph – All numbers Lead to One – Jason Davies – 2012 – Une superbe animation montrant la formation des suites de Collatz sur 19 étapes.

Sites

*      Conjecture de Syracuse – Wikipédia

*      Le problème 3n+1: élémentaire mais redoutable – Shalom Eliahou – 2011 – CNRS

*      Le problème 3n+1: cycles de longueur 5 – Shalom Eliahou – 2011 – CNRS

*      Le problème 3n+1: y a-t-il des cycles non triviaux – Shalom Eliahou – 2011 – CNRS

*      Suite impaire symbolique de Collatz étendue à kn + 1 par Wilfrid Poulain – 2017

 

*      Uncrackable? The Collatz Conjecture – Numberphile (Vidéo 8 min)

*      The 3x + 1 problem and its generalizations – Jeffrey Lagarias

*      The Collatz conjecture, Littlewood-Offord theory, and powers of 2 and 3Terence Tao- 2011

*      The 3x+1 Problem: Status and Recent Work Part 1 (29 min) and Part 2 (22 min) – Vidéos – 2013

*      Collatz and self-similariry – Inigio Quilez – Vidéo (11 min)

 

*      OEIS A006877In the `3x+1' problem, these values for the starting value set new records for number of steps to reach 1.

*      OEIS A006577 – Number of halving and tripling steps to reach 1 in '3x+1' problem

*      OEIS A060412 – In the `3x+1' problem, these values for the starting value set new records for the "dropping time", number of steps to reach a lower value than the start.

 

Cette page

http://villemin.gerard.free.fr/Wwwgvmm/Iteration/Syracuse.htm