NOMBRES – Curiosités, Théorie et Usages

 

Accueil                           DicoNombre            Rubriques           Nouveautés      Édition du: 15/03/2024

Orientation générale        DicoMot Math          Atlas                   Actualités                       M'écrire

Barre de recherche          DicoCulture              Index alphabétique        Références      Brèves de Maths

             

Suite de nombres

 

Débutants

Général

Itérations – Cycles

 

Glossaire

Suites

et Séries

 

 

INDEX

 

Itérations

 

 

Rubriques

 

 

 

 

 

 

Suite de Fibonacci

Triangle de Pascal

Triangle de Leibniz

Algorithme de Kaprekar

Cycle de Syracuse

Cycle des Carrés

Nombres de Kaprekar

Cycle de Syracuse Géné.

Suite de Padovan

Cycle-cube et 153

Nombres Chanceux

Suite de Steinhaus

Cycle de Keith

Racines numériques

Somme x Produit

Powertrain

De base en base

Nombres de Gilda

Hauteur des nbs premiers

Suite de Goodstein

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.

 

Actualités de septembre 2019

Le mathématicien Terence Tao vient de démontrer que:

 

Théorème

La conjecture est "presque" vraie pour "presque" tous les entiers.

 

Presque vrai pour une propriété P en math signifie que le rapport n(P) / n tend vers 1 pour n tendant vers l'infini. Sachant que l'on compte n(P), la quantité de nombres plus petits que n et vérifiant la propriété P.

La démonstration de Terence Tao est plus générale et s'applique à une fonction f(n) qui associe un nombre réel à un entier n et qui tend vers l'infini lorsque n tend vers l'infini. Il choisit des entiers représentatifs. Pour cette conjecture, il s'agit de la congruence par toutes les puissances de 3.

Cette démonstration ne conclut pas que l'aboutissement est le nombre 1, mais passe toujours par un minimum. 

 

Tao conclut: You can get as close as you want to the Collatz conjecture, but it’s still out of reach. (La conjecture de Collatz peut être approchée d'aussi près que l'on veut, mais elle est toujours hors de portée).

Tous les nombres jusqu'à environ 1020 ont été testés positivement à cette conjecture.

 

 

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

On donne le nombre et son temps de vol (comme 7 avec un temps de vol de 16). Le nombre qui suit est celui qui produit un temps de vol supérieur (ici 9 avec un temps de vol de 19).

On a effectivement:

[7, 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1] – 16 étapes

[8, 4, 2, 1]

[9, 28, 14, 7, 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1]

Voir Programme

 

 

Table des records 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.

*    Marc Riberpray me signale son point de vue:

J'ai été étonné de trouver (chez beaucoup d'amateurs de cette suite) un nombre pair le 54 (vol 112) juste après le 27 (vol 111), ce qui me semble une évidence car 54 est l'antécédent de 27 (54/2) et dans ce cas 108, 216, etc. vont être des records trop faciles à atteindre.
Réponse: Le nombre 54 est légitime car il constitue le prochain record avec 112; son double 108 ne l'est pas car il est supplanté par 73 et 97 qui donnent des temps de vols supérieurs à 113.

En fait seul les multiples de 3 sont des records intéressants car ils n'ont pas d'antécédents en dehors des multiples de 2, les nombres de la forme 3x+1 ou 3x+2 ont un antécédent relativement simple à calculer. Puisqu'on parle de vol, disons qu'ils sont sur la même "ligne".

Par exemple j'ai trouvé ce record sur le site Calculis: durée de vol 2284 du nombre 2361235441021745907775 avec la Calculatrice en ligne webCalc.

N = 2361235441021745907775 (3x + 1) pour remonter vers l'antécédent on calcule [(N – 1)/ 3]  × 4 + 1 car les successeurs des nombres de la forme 4X + 1 sont 3 × (4X + 1) + 1 = 4 × (3X + 1) soit 3X + 1 après les divisions par 2.

      3148313921362327877033 (3x + 2) dans ce cas il faut multiplier par 2 ce qui nous ramène à un nombre de la forme 3 × (2x + 1) + 1 et on peut calculer [(N – 1) / 3] × 4 + 1

      8395503790299541005421 (3x + 1)

    11194005053732721340561 (3x + 1)

    14925340071643628454081 (3x + 0) =3 × 4975113357214542818027 fin de la remontée mais nouveau RECORD.

Calcul des antécédents:

  7   (3 × 2 + 1) antécédent     9=  4 × 2 + 1 => 3 × 9 + 1 = 28 => 14 => 7

25   (3 × 8 + 1) antécédent   33=  4 × 8 + 1 

73 (3 × 24 + 1) antécédent   97= 4 × 24 + 1 

97 (3 × 32 + 1) antécédent 129= 4 × 32 + 1 

 

Voir Cas du nombre 27/ Suite en Tables valeurs et records

 

 

Organisation en rond des suites de Collatz

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

Figure aussi en Mathematician Proves Huge Result on ‘Dangerous’ Problem – Kevin Hartnett

 

 

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 mod 3 (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)

·      Nombres maisons (home)

Suite

·      Syracuse – Variantes

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

·      Syracuse – Tables

·      Syracuse – Découverte junior

·      Syracuse généralisée avec premiers et composés

·      Fractales et cycles

·      Autres, voir en haut de page

Voir

·      Boucle infernale

·      Boucle SP (Somme x Produit)

·      Calcul mentalIndex

·      Division qui retourne le nombre

·      GéométrieIndex

·      Nombre Harshad

·      Nombres narcissiques

·      Nombres retournés

·      Palindrome retard

·      Persistance additive (racine numérique de la preuve par 9)

·      Persistance multiplicative

·      Preuve par neuf en pratique

·      Récurrence

·      Retournés et premiers

·      Suite de Goodstein

·      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

·      Conjecture de Syracuse : avancées inédites: ou conjecture de Collatz ou problème 3x+1 – Un document de 344 pages qui fait une approche novatrice du sujet.

·      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

·      De la lumière sur Syracuse par Yves Roques – Une vidéo de 2019 qui donne une piste sur la convergence de la suite vers 1

 

·      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.

·      OEIS A006885 - Record highest point of trajectory before reaching 1 in '3x+1' problem

·      Almost all Collatz orbits attain almost bounded values** – What's new by Terence Tao

 

Cette page

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