@nodgim
147 à un $i(n),p(n)$ = 042_070
225 à un $i(n),p(n)$ = 017_031
147 passe en étape 17 par un $i(n),p(n)$ = 017_032 puis passe par 002_005 en avant-dernière étape
225 commence par 017_031 puis passe par 002_003 en avant-dernière étape
Donc pour aller de 225 à 147 il faut passer par 001_000, c'est le chemin le plus long qui est le seul possible dans le graphe
on peut comparer le classement des sommets entre les 60.000 premiers impairs et les 100 n tirés aléatoirement entre 10^9 et 10^12 (les deux premières colonnes)
il est facile de constater que les sommets en tête de ces deux classements occupent sensiblement les mêmes places
Le "plot" de Rstudio et la librairie igraph ne le permettent pas mais la disposition (layout) idéale serait un système de cercles concentriques, 1 étant au centre; et le premier cercle serait celui des sommets 001_000 qui sont les $i(n),p(n)$ des $D(n)$.
Chacun de ces cercles est donc celui d'un $i(n)$. On trouvera sur chaque cercle un ou deux sommets qui représentent le gros des passages, comme on peut le voir ici pour le deuxième cercle pour les stats des 60.000 premiers impairs
002_003 et 002_005 c'est 93% des cas. J'avance l'idée que quelque soit la manière de collecter les données (de manière ordonnée depuis 3 et avec des n assez petits, ou de manière aléatoire avec des n assez grands), ces deux sommets auront la même fréquentation.
Question au passage : pourquoi 002_003 et 002_005 sont-ils si fréquentés et pas 002_004 qui est juste entre les deux ?
Ce que l'on appelle le cobra depuis l'intervention de gerbrane est simplement la visualisation des sommets les plus prévalents. Le graphe de Syracuse montrent que les chemins vers 1 convergent majoritairement vers un tronc principal (le corps du serpent composé des cercles les plus fréquentés).
Le shtam est en ce moment très riche en approches théoriques sur cette conjecture. Je défend de mon côté une approche expérimentale. Nous vivons à une époque où il est matériellement possible de calculer des données et de les visualiser de manière performante. Pourquoi ne pas passer par cette étape avant de théoriser ?
L'observation statistique des chemins vers 1 ne peut pas être balayée d'un revers de main. Plus je collecte ces observations et que je varie les moyens pour les obtenir, plus je vois une structure et un modèle de comportement. Collectivement, ou à grande échelle, les chemins vers 1 dessinent un réseau très organisé : un graphe.
Ma conclusion personnelle est très simple. Il ne s'agit pas de monter qu'un entier converge vers 1. Il s'agit plutôt de montrer que le chemin de cet entier a beaucoup plus de chances de venir se relier à un des sommets $i(n),p(n)$ les plus fréquentés que de trouver un chemin exotique vers 1.
Les chemins exotiques sont d'ailleurs connus. Il suffit de prendre un $D(n)$ différent de 5 comme cible. Par exemple 477218133 à un $i(n),p(n) $ de 002_012 et un $D(n)$ égal à 349525. Mais on va trouver des milliers de $D(n)=5$ pour un seul comme celui-ci. Il y a un seul exemple pour n<120.001 c'est 116053 (dont le $D(n)$ = 85) soit 1 cas pour 60.000 impairs.
tu me demandes comment passer de 147 à 225 par rapport aux chemins vers 1 ou pas ????
Je te dis comment ça passe dans le graphe de Syracuse qui repose sur les $i(n),p(n)$. C'est intéressant parce que la connectivité entre sommets est aussi une propriété du graphe au même titre que la convergence vers 1.
Aucun sommet commun entre les deux sauf celui qui est commun à tous 000_001
Donc dans le graphe il faut faire depuis un des sommets le chemin complet vers 000_001 puis repartir en sens inverse vers le deuxième sommet. C'est la distance maximale en nbr de sommets et c'est un cas assez rare car il y a le plus souvent un sommet commun à deux chemins bien avant 000_001
Tu attends visiblement une autre réponse mais dans le graphe on fait comme ça pour aller de 147 à 225 ;-)
le plus drôle est que la réponse de PMF se fonde sur sa base de données !
Il fallait lire : PMF n'a pas compris que ta phrase "l'algorithme donne, au choix, ..." excluait les suites de Collatz, dans lesquelles aucun choix n'est offert pour la valeur du successeur.
je comprends que ta question se pose sur une variante de l'algorithme mais pour celui de Syracuse ça se passe comme ça
Je ne suis pas convaincu que la comparaison entre plusieurs algorithmes éclaire beaucoup la question de ce qui se passe avec celui de Syracuse. On ne peut pas définir un algorithme "concurrent" ou "alternatif" que de manière subjective... Pourquoi multiplier par x et diviser par y, pourquoi prendre une partie entière ?
Il faudrait quelque chose de plus cohérent dont le test serait : comment modifier l'algorithme de Syracuse sans qu'il perde sa propriété de convergence vers 1. Ce qui me semble impossible.
Pour PMF : Vous semblez tenir pour acquis que la suite de Syracuse fini par boucler sur 1.
Je viens d'aller vérifier et ce n'est toujours pas démontré.
Pour ma part, j'aimerais savoir en combien d'étapes se termine votre algorithme sur l'exemple suivant : $10^{10^{10^{10^{10000}}}}+1$.
D'avance merci.
A bientôt.
Cherche livres et objets du domaine mathématique :
Intégraphes, règles log et calculateurs électromécaniques.
On peut certainement en trouver d'autres. Mais la règle est simple : si un seul chemin passant par un certain $i(n),p(n)$ rejoint 1_0 en $i(n)$ étapes; tout chemin passant par ce $i(n),p(n)$ rejoindra 1_0 par le même nombre d'étapes quelque soit les $i(n),p(n)$ intermédiaires qu'il choisira de prendre. Par contre statistiquement un de ces chemins regroupera une grande partie des passages. Dans ce cas c'est
1_0<--2_5<--3_6<--4_7<--5_10<--6_14<--7_16<--8_18<--9_22<--10_23<--11_24<--12_25
qui représente au moins 90% des passages par 12_25
memo : les chemins passant par 12_25 correspondent à 25589 impairs sur 60000. Voici les les plus petites valeurs de n pour chaque chemin :
27, 255, 367, 375, 747, 813, 817, 819, 837, 843, 7119, 11259, 14235, 16005, 16011, 16017, 16029, 16095, 19023, 19087, 28551, 28623, 42811, 42847, 42895, 42903, 42915, 42927, 57243, 64197, 64213, 64227, 64245, 64261, 64275, 64285, 64329, 64335, 64357, 64369, 64371, 64387, 64389, 64401, 64411, 64429, 64431, 64491
ce n'est pas prouvé ! C'est d'ailleurs une extrapolation assez douteuse, vu que PMF n'a fait que examiner des petits nombres, sans aucun rapport de taille avec le tien (une dizaine de chiffres, pas $10^{10^{10^{10000}}}$. Et, en gros, fait des statistiques avec ça. Il n'y a aucune raison que les treès grands nombres se comportent comme les petits.
@ Lourran : si tu as dû sortir l'artillerie lourde pour résoudre le petit problème, c'est que tu n'as pas vu qu'on pouvait s'en sortir facilement, moyennant une astuce qu'il faut trouver, et qui permet de résoudre n'importe quel couple de nombres proposé.
Une astuce qu'il faut trouver ... et qui permet de trouver la solution pour (147 ; 225) en moins de 3 minutes ?
Peut-être cette piste. Partons à l'envers, un nombre N a 3 antécédents possible s'il est de la forme 3k+1, ou 2 dans le cas contraire. Et s'il n'est pas de la forme 3k+1, il a un de ses 2 antécédents 2N ou 2N+1 qui est de la forme 3k+1.
Et ainsi, on va pouvoir 'descendre' ( 225 <-- 451 <-- 150 : 150 est plus petit que 225) ... et en descendant systématiquement, on peut descendre aussi bas qu'on veut.
Idem, en partant du point de départ, en divisant systématiquement par 2, on descend aussi bas qu'on veut.
Et forcément, à un moment, les chemins se rejoignent.
Ce n'est pas forcément le chemin le plus court, mais effectivement, ça marche sans se prendre trop la tête.
Tu me dis, j'oublie. Tu m'enseignes, je me souviens. Tu m'impliques, j'apprends. Benjamin Franklin
Disons que la feuille la plus haute de la canopée d'un arbre est tout autant reliée à la racine que celle qui pousse sur la branche la plus basse. Et que la sève qui ira aux deux feuilles fera chemin commun quelque part dans le tronc.
Heu .. tu ne sais manifestement pas ce qu'est un grand nombre, puisque tu te limites à moins de 15 chiffres (tableur oblige). Dreamer parlait d'un nombre qui est tellement grand que tu ne pourras jamais écrire les chiffres de son nombre de chiffres (*); même s'il est simple à écrire 1 suivi d'une quantité fantastique de 0.
Mais tu peux continuer à faire joujou avec des logiciels, et même à croire bêtement que tu apportes quelque chose au problème de Collatz. Comme mon petit voisin, qui a 5 ans, se prend pour Messi quand il tape dans un ballon. Mais lui a 5 ans.
(*) à priori, aucun ordinateur n'est capable de mettre ce nombre, écrit en décimal, en mémoire.
si si je sais ce que c'est qu'un grand nombre.... mais ils ne servent à rien si on ne peut les mettre en mémoire ou calculer leur chemin.
Qu'apportent-ils à la conjecture comme information ?
Je dis simplement qu'il est facile de montrer qu'il y a majoritairement des chemins communs entre des n <10^5 et des n dans les 10^15.
C'est déjà ça.
Avec d'autres programmes on ferait la même constatation avec des puissances nettement plus élevées.
C'est une histoire d'arborescence. Fais une expérience de pensée toute simple : ton n immensément grand il est pair ou impair ? Même sans pouvoir le calculer, l'algorithme va donner théoriquement un autre n peut-être plus grand, peut-être plus petit mais qui aura un $i(n)$ plus petit...Forcément mon cher Watson. Donc ton n astronomique il vient de passer d'un cercle $i(n)$ à un autre plus près de 1 comme tout le monde !
"... mais ils ne servent à rien si on ne peut les mettre en mémoire ou calculer leur chemin. "
Ils ne te servent à rien; parce que tu fais joujou avec des logiciels, que tu ne fais pas des maths, que tu connais tellement peu les maths que tu racontes cette idiotie.
Tu ne parles donc pas de maths, même pas de la conjecture de Collatz (on te l'a expliqué du début, mais comme tout bon monomaniaque, tu continues sur ta lancée), tu fais joujou : de tableaux, des dessins depuis quelques temps, du vide mathématique.
Mon cher Gerard0 , tu présentes un paradoxe intéressant : le mathématicien qui n'aimait pas les nombres
Le comportement statistique de la suite de Syracuse que je décris, je ne l'invente pas. Ce sont les nombres qui font le boulot !
Mais pour le grand GerardO rien n'est jamais trop grand ni assez mathématique
Ce que font les entiers en pratique n'a aucun intérêt pour lui : c'est connu qu'aucun mathématicien digne de ce nom ne s'abaisse à des telles pratiques. Compter, beurk ! et puis quoi encore ...
Les grands nombres, qu'apportent-ils à la conjecture comme information ?
Les grands nombres sont le coeur de la conjecture. Sans les grands nombres, point de conjecture !
Tant que tu regardes la façon dont les nombres se comportent quand ils se dirigent vers le cycle (4,2,1), tu ne regardes que les nombres qui arrivent vers ce cycle. Et donc tu ne te poses pas la question de savoir si certains nombres n'aboutissent pas à ce cycle.
Par nature, tu n'explores pas la conjecture de Syracuse.
Je t'ai soumis ces derniers jours 2 ou 3 suites, à partir desquelles tu pourrais bâtir des clusters , des cobras etc etc, tout comme tu le fais pour la suite que tu regardes.
Ce serait ni plus, ni moins utile dans un objectif de résolution de la conjecture de Syracuse.
Ces autres suites ne t'intéressent pas, pour 1000 raisons.
Eventuellement, on peut rêver un peu, ce serait utile de regarder ces autres suites. Soit la fameuse suite (3x+1) se comporte comme les suites qui convergent systématiquement (même forme de graphe) , et différemment des suites qui ne convergent pas systématiquement. Et alors, on aurait une piste, une petite étincelle.
Soit à l'opposé, cette fameuse suite (3x+1) a un graphe similaire aux suites qui ne convergent pas systématiquement ... et là aussi, on aurait une petite étincelle.
Je suis convaincu que ça n'aboutirait pas, mais au moins, c'est un plan. Je me pose une question, et selon la réponse à cette question, j'avance dans une direction, ou dans une autre.
Là, tu t'extasies parce que tu obtiens des graphes 'esthétiques'. Mais fais au moins le test.
Prend une des suites que je t'ai proposées. Soit tu obtiens des graphes moches, et tu pourras continuer de t'extasier, parce que la suite (3x+1) est la seule à produire des graphes esthétiques, soit tu obtiens d'autres graphes tout aussi esthétiques, et du coup, tu conclueras que le coté 'esthétique' n'est pas lié à Syracuse, c'est simplement lié au fait qu'un arbre déséquilibré donne un graphe esthétique, et peu importe la formule qui a servi à produire ce graphe.
Tu me dis, j'oublie. Tu m'enseignes, je me souviens. Tu m'impliques, j'apprends. Benjamin Franklin
Un mathématicien ne doit pas forcément être fort en calcul, même si cela aide parfois.
Par contre tenir pour vérité inflexible des constatations statistiques sur un échantillon négligeable de l'ensemble des naturels, c'est un sacré acte de foi.
Cela dit, les images sont jolies mais rien dans le comportement du fameux "cobra" n'a encore été prouvé ou je me trompe ?
Ce qui serait vraiment chouette, parce que soit on a droit à des jolies images, soit on a droit à des tableaux de chiffres (je ne vois pas de nombres, juste des suites de chiffres avec de temps en temps des flèches), ce serait de pouvoir faire une synthèse qui ne soit pas trop lourde.
J'en demande trop si je veux voir les résultats sous forme de formule ?
A bientôt
Cherche livres et objets du domaine mathématique :
Intégraphes, règles log et calculateurs électromécaniques.
Je ne suis pas contre ta méthode. Je comprends que tu veux faire une sorte d'étalonnage des graphes pour d'autres types de suites.
Tu voudrais en priorité essayer laquelle ?
A part ça en ce moment ça me semble intéressant de mettre en valeur les propriétés de ces suites. Je sais que tout cela ne se passe que pour des n<=10^15 honte à moi... mais bon
L'expérience a donc consisté à tirer des n assez grands dans les limites de Excel et regarder le pourcentage de points communs avec les sommets obtenus pour n de 3 à 120.001. J'utilise toujours le système des $i(n),p(n)$ pour cela.
Sur 10.000 tirages, on obtient cette distribution où 1 tirage sur 2 à au moins 57% de sommets communs avec la base.
Sur la deuxième illustration, on voit que le nombre 100 000 001 à 93% de sommets communs avec la bdd des 60.000 premiers impairs.
Il est donc très probable que les sommets que je trouve avec ma petite bdd sont très courants même pour des n bien plus grands.
Enfin une jolie question dans ce fil. Merci nodgim.
Je n'ai pas (encore) trouvé ton astuce et donc, si tu la donnes, sois gentil de la donner en encre sympathique: tu l'écris normalement puis tu la colorie en blanc: celui qui veut la lire (moi, par exemple, si je finis par me lasser de la chercher) la lit en passant la souris sur ce blanc.
Je raconte un truc proche de ce que vient d'écrire lourrran:
R1) := Il existe une infinité de chemins qui mènent de $147$ à $225$ , plus généralement de $x$ à $y$, dans $A(x)$:="arbre de nodgim de racine $x$" où:
Pour tout $x$, $A(x):= (x, A(g(x)), A(d(x)))$ où
$g(x):=\lfloor \frac{x}{2}\rfloor$
$d(x):=3x+1$
Preuve de R1:
Pour tout $x $, pour tout $m$ tel que $2^m>x$, $g^{(m)}(x)=0$.
Pour finir, il suffit de prouver que tout $y$ appartient à $A(0)$:
On note que:
pour tout $z$,
$0\in A(0)$,
$3z+1=d(g(2z))$ (et donc, si $3z+1$ ( qui est supérieur à $2z$) n'appartient pas à $A(0)$, $2z$ n'appartient pas non plus à $A(0)$)
$3z+2=g(d(2z+1))$(et donc, si $3z+2$ ( qui est supérieur à $2z+1$) n'appartient pas à $A(0)$, $2z+1$ n'appartient pas non plus à $A(0)$)
$3z+3=g(d(2z+2))$ (et donc, si $3z+3$ ( qui est supérieur à $2z+2$) n'appartient pas à $A(0)$, $2z+2$ n'appartient pas non plus à $A(0)$).
S'il existait des $y$ qui n'appartiennent pas à $A(0)$, leur ensemble aurait un plus petit élément (:=$u$). Cet $u$ ne saurait être $0$ ou d'une des trois formes $3z+1,3z+2, 3z+3$ d'après les quatre remarques précédentes. Donc cet $u$ n'existe pas. Donc tout $y$ est dans $A(0)$.
Donc R1.
R2) Vu que, maintenant, on sait que l'on trouvera $225$ dans $A(147)$, yapluka (faire) écrire $A(147)$ de haut en bas et s'arrêter quand on trouve $225$, puis (faire) écrire le chemin qui mène de $147$ à $225$: sa longueur est assurément minimale. Pour éviter cette méthode "bourrine", nodgim a une astuce et je présuppose bien sûr qu'il prouve que son chemin solution est de longueur minimale ;-)
Ce qui serait vraiment chouette, parce que soit on a droit à des jolies images, soit on a droit à des tableaux de chiffres (je ne vois pas de nombres, juste des suites de chiffres avec de temps en temps des flèches), ce serait de pouvoir faire une synthèse qui ne soit pas trop lourde.
Mon but étant uniquement de faire un travail statistique à la disposition de ceux qui voudront s'y intéresser, pas de soucis pour accéder à ta demande. Je pense d'ailleurs que c'est le bon moment pour faire cette synthèse.
Ce que je fais sous Excel et Rstudio est certainement programmable autrement et de manière plus performante mais c'est déjà une base.
tu n'as pas vu qu'on pouvait s'en sortir facilement, moyennant une astuce qu'il faut trouver
A mon avis, l'astuce consiste à partir de 225 pour créer la suite à l'envers. En effet, au lieu de calculer $\left( \lfloor n/2 \rfloor,3\,n+1 \right)$ on calcule dans ce cas $\left( 2\,n+1,(n-1)/3 \right)$. L'un des deux nombres est entier, et si les deux le sont on prend le plus petit. Avec $n=225$ on obtient successivement
Quand je dis que j'ai utilisé l'artillerie lourde, j'ai en fait fait une macro excel.
147 a 2 successeurs possibles, chacun en a 2 etc etc et comme il a fallu 15 étapes pour arriver à 225, j'ai donc exploré 2+4+8+16...+2^15 nombres.
Dans le lot, il y avait pas mal de doublons. C'est assurément le plus court chemin de 147 à 225.
Un autre méthode, ce serait de parcourir l'arbre par les 2 extrémités :
Les 2 successeurs pssibles de 147 sont 73 et 442, et les 2 prédécesseurs possibles de 225 sont 450 et 451
Les 4 'petits-fils' possibles de 147 sont 36, 220, 221 et 1327, et les différents grands-parents possibles de 225 sont 150, 900, 901,902 et 903.
Et on s'arrête quand nos 2 arbres ont 1 élément en commun. Ainsi, au lieu de construire un arbre avec 2^16 éléments, on construit 2 arbres, avec 2^8 éléments pour l'un et un peu plus pour l'autre.... En gros 2 fois moins d'éléments analysés, mais un programme un peu plus compliqué à écrire.
Tu me dis, j'oublie. Tu m'enseignes, je me souviens. Tu m'impliques, j'apprends. Benjamin Franklin
PMF
Oui , on peut parler d'étalonnage. Mais pas d'étalonnage pour d'autres types de suite. Mais un étalonnage à partir d'autres types de suites.
Je te rappelle que l'objectif que tu t'es fixé, c'est d'analyser la suite de Syracuse.
Donc on part de suites connues, on regarde les graphes obtenus avec ces suites. Idéalement, il faudrait avoir plusieurs suites, qui donneraient des graphes très différents les uns des autres.
Puis on trace le graphe obtenu avec la suite de Syracuse, et on regarde si ce graphe se rapproche de tel graphe ou de tel autre.
Soyons honnête, l'espoir que ça mène quelque part est (à peu près) nul, mais ça occupe !
Et ça donne l'illusion d'avoir une méthode de travail.
Et donc, tu peux utiliser les suites que j'avais proposées. Ou d'autres de ton choix.
Tu me dis, j'oublie. Tu m'enseignes, je me souviens. Tu m'impliques, j'apprends. Benjamin Franklin
@ Wilfrid : Pour la suite à l'envers ( c'est bien ce qu'il faut faire ) si le nombre -1 n'est pas divisible par 3, on multiple par 2 et si nécessaire on ajoute 1, de manière à retrouver un nombre de la forme 3n+1.
J'ai bien dit que je "convertissais" les valeurs des impairs en couples $i(n),p(n)$ et que le graphe se faisait sur des sommets définis par ces couples.
Je pensais que cela piquerait un peu plus votre curiosité et déclencherait quelques critiques. Donc la question est : "Le graphe des couples $i(n),p(n)$ est-il aussi légitime que celui que l'on ferait avec les entiers impairs ? "
N'importe quel impair a une valeur $i(n),p(n)$. Le chemin de n'importe quel impair vers 1, donc la suite des étapes impaires jusqu'à 1 devient un ensemble de liaisons (arêtes) d'une certaine valeur $p(n)$ qui s'associe à la valeur $i(n)$ suivante. Donc pour les étapes $i(n)$ 12 à 1 un certain impair passera par des $p(n)$ tel que 0, 5, 6, 7, 10, 14, 16, 18, 22, 23, 24, 25. Toujours décroissant avec un mini de -1 mais pas mal de "sauts" aussi. Mais il y a plein de combinaisons possible comme montré ici : http://www.les-mathematiques.net/phorum/read.php?43,2058452,2109088#msg-2109088
Je suis sûr d'une chose : si une certaine valeur $i(n),p(n)$ va vers 1, tout entier passant par ce même couple ira vers 1 quelque soit la combinaison qu'il choisira. Il y a peut-être beaucoup de ces combinaisons mais pas une infinité car il y a une limite due à la décroissance obligée des $p(n)$.
Par exemple pour la serie $i(n)$ 12 à 1 la suite des $p(n)$ aurait pour limite 0, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25
Quelqu'un peut-il "démonter" ça ? Moi je conclus de ce raisonnement que l'on ne pourrait pas trouver un sommet plus "grand" que 002_015 en étape 2 dont le chemin passerai par 012_025...
j'ai choisi pour fabriquer un autre graphe la suite $U_{n+1}=U_n/2$ si $U_n$ est pair , et $U_n+1 $ sinon.
J'applique le même traitement que pour la suite de Syracuse : conversion des étapes impaires en couples $i(n),p(n)$ pour définir les sommets et les arêtes du réseau puis comptage de leurs occurrences
Par exemple pour l'entier 78593,
son cluster est : 12_17_3_30
son chemin (impairs) est : 3, 5, 39, 77, 615, 1229, 2457, 4913, 9825, 19649, 39297, 78593
et ses arêtes :
001_002<--002_001
002_001<--003_003
003_003<--004_001
004_001<--005_003
005_003<--006_001
006_001<--007_001
007_001<--008_001
008_001<--009_001
009_001<--010_001
010_001<--011_001
011_001<--012_001
J'ai aussi choisi de calculer dans un range 10^9 sur 10.000 tirages aléatoires
Non ce n'est pas ça que Lourran veut faire. Il vaut avoir une possibilité d'étalonner un type de suite sur un type de graphe.
J'ai déjà fait des graphes sur les suites de Syracuse et je constate des structures. Lourran pense qu'une autre suite pas trop loin de celle de Syracuse aura aussi une structure. Si les graphes montrent des effets trop semblables pour des suites qui ne sont pas les mêmes, on pourra dire que ces structures sont "triviales" et n'apportent pas d'information décisive.
J'ai mis un peu de temps à me faire à cette idée mais je pense que lourran a raison sur ce coup-là. J'ai donc choisi la suite la plus proche de celle de Syracuse et qui est sure de converger vers 1 pour faire ce test
Je publie à suivre son graphe, le calcul vient de finir.
L'idée, c'est quoi :
-1- tempérer l'enthousiasme qu'on peut voir dans ce message PMF ou les suivants.
Les graphes obtenus à partir des clusters laissent apparaître une structure ... cette structure serait 'propre' à Syracuse ? Non, je pense qu'à peu près n'importe quel arbre déséquilibré donne un graphe de ce type.
-2- donner du grain à moudre à PMF
PMF a du temps, il veut occuper ce temps en explorant la conjecture de Collatz, aidons-le à occuper son temps.
Est-ce qu'un début de piste pour la résolution de la conjecture sortira de ça ? Non, bien entendu.
Tu me dis, j'oublie. Tu m'enseignes, je me souviens. Tu m'impliques, j'apprends. Benjamin Franklin
suite aux étranges encouragements de lourran (je suppose peut-être un peu d'acidité gastrique post-déjeuner)
voici "tout de même" le graphe de la suite $U_{n+1}=U_n/2$ si $U_n$ est pair , et $U_n+1$ sinon.
Ce graphe comporte 232 sommets et 1194 arêtes. Il est issu du calcul de 10.000 chemins d'impairs tirés aléatoirement entre 3 et 10^9
Cette suite convergeant vers 1 de manière évidente, on cherche à comparer son graphe à celui de la suite de Collatz qui elle converge "peut-être" vers 1.
Donc que voit-on ?
La structure est organisée en une série de convergence par i(n). Pour chaque sommet "target" d'une valeur i(n) donnée, on va trouver un certain nombres de sommets "source" de manière que cet ensemble d'arêtes fasse passer tous les chemins. Il faut jeter un œil au pdf joint où on voit que le premier couple avec le $p(n)$ le plus petit a le plus de passages, et que les passages décroissent avec les $p(n)$ plus grands.
Cette suite ne fait donc rien d'autre que de connecter un "cercle" $i(n)$ à un autre et de collecter dans chaque cercle des p(n) de valeurs décroissantes. Des ronds dans l'eau avec les vagues concentriques de force décroissante serait une bonne analogie.
Aucun chemin exotique n'est possible comme le fait la suite de Syracuse, et il n'y a pas cet effet de toron si particulier (comme des lianes entrelacées qui finiraient pas former un tronc)
Le graphe et les clusters tout ça c'est une façon de montrer comment les chemins se rejoignent en grands tronçons.
Ces deux parcours sont de véritables autoroutes pour les entiers :
5, 53, 35, 23, 61, 325, 433, 577, 3077, 2051, 1367, 911
ou sous la forme de $i(n),p(n)$
001_000<--002_005
002_005<--003_006
003_006<--004_007
004_007<--005_010
005_010<--006_014
006_014<--007_016
007_016<--008_018
008_018<--009_022
009_022<--010_023
010_023<--011_024
011_024<--012_025
Il y a une raison à ces "mots" ou à ces "phrases" si populaires dans le langage de Syracuse : c'est nettement plus organisé que chaotique comme structure !
J'ai extrait des données les liaisons entre les i(n)=2 et i(n)=3 pour mieux identifier ce qui se passe dans le graphe complet
Cette suite est de type 1x+1 si on veut la comparer au 3x+1 de Syracuse. On divise par deux tant que c'est pair et si c'est impair on "rend un point" pour redevenir pair à nouveau. Ce 1x+1 à chaque retour au pair est le chemin le plus rapide vers 1 pour n'importe quel entier. La convergence est tellement évidente que personne ne se demande ce qui se passe dans les grands nombres... Assez marrant que le passage de l'instruction 1x+1 à 3x+1 puisse changer tant de choses.
Donc les entiers convergent gentiment vers 1 si on leur donne une instruction simple pour le faire. Exactement comme pour 3x+1 il faut toujours passer d'un i(n) à un i(n)-1 pour aller vers 1. Ce qui est compliqué c'est le p(n) qui est associé au i(n). Dans le cas de 1x+1 il faut comprendre qu'un sommet $(i(n),p(n)$ va se raccorder à toutes les associations de sommets de i(n)-1 avec les p(n) possibles comme le montre le graphe et cette liste :
C'est juste le nombre de divisions par 2 consécutives qui joue ici. Si la liaison 002_001<--003_001 est la plus fréquente c'est que la première division par 2 d'un pair donne un pair ou un impair. Donc on a une chance sur 2 de tomber sur un impair. Une chance sur 4 de tomber sur un impair après 2 divisions... Et on a forcément au final le type de données de la liste ci-dessus.
On peut donc dire qu'un entier pair a une probabilité 1/n de donner un nombre impair au bout de n divisions par 2. S'il est une puissance de 2 il file directement à 1. Ce que fait 1x+1 c'est simplement utiliser cet ordre possible des entiers.
L'ordre des entiers qui est a l'œuvre avec 3x+1 n'a jamais réussi à être expliqué... pourtant il repose sur un système de probabilités (un ordre comme en parle Serge Burckel) au même titre que 1x+1....
D'abord mea culpa il y avait une erreur dans le calcul des p(n) de la suite x+1
Donc on oublie le graphe publié hier et on recommence.
De manière à encore mieux "étalonner" la suite 3x+1 (Syracuse) par rapport à la suite x+1, voici le principe de la macro
1) Un entier impair est tiré au hasard entre 10^4 et 10^9 (10.000 tirages)
2) son chemin est calculé à la fois en 3x+1 et en x+1 en ne gardant que les étapes impaires
3) ces étapes impaires sont converties en $i(n),p(n)$
4) on ne garde que la liaison entre l'étape 3 et l'étape 2 et on compte toutes les occurrences que l'on trouve
Il se crée donc des liaisons spécifiques avec les deux types de suites. Le pdf joint donne les résultats complets pour les 10.000 tirages
La suite x+1 a un comportement régulier : les liaisons se font vers les sommets 002_003 à 002_013 avec 50% des cas pour liaisons vers 002_003 et 002_004. A partir de 002_005 les cas diminuent progressivement. Pour chaque sommet il se passe toujours la même chose : il y a une décroissance de moitié à partir de la première liaison dont le sommet "source" à le plus petit p(n).
La suite 3x+1 est nettement plus irrégulière. Deux liaisons concentrent 90% des cas :
002_005<--003_006 avec 4488 cas et 002_003<--003_005 avec 4621 cas.
Elle est aussi beaucoup plus sélective avec seulement 32 types de liaisons au lieu de 91 pour la suite x+1.
Contrairement à la suite x+1, 3x+1 peut se connecter avec les sommets 002_001 et 002_002 mais presque jamais avec le 002_004 (2 cas sur 10.000)
On peut voir ci-dessous les liaisons avec le sommet 002_003 pour les suites x+1 et 3x+1 :
Source____________Target_____________x+1________3x+1
003_001___________002_003______________________
003_002___________002_003______________________
003_003___________002_003______________________
003_004___________002_003___________1347_______
003_005___________002_003___________726________4621
003_006___________002_003___________337________1
003_007___________002_003___________157________
003_008___________002_003___________82_________
003_009___________002_003___________42_________55
003_010___________002_003___________25_________
003_011___________002_003___________17_________97
003_012___________002_003___________7__________
003_013___________002_003___________3__________
003_014___________002_003______________________
003_015___________002_003___________1__________8
003_016___________002_003___________1__________
003_017___________002_003______________________
003_018___________002_003______________________
La dernière étape impaire avant 1 ou $D(n)$ est très spécifique pour 3x+1. C'est toujours de type $\frac{2^m-1}{3}$ avec une énorme prédominance pour le 5 (93%)
Pour la suite x+1, on trouve des $D(n) : 3, 7,15,31,63,127,255...$ donc de forme 2^m-1
Sur 1000 tirages aléatoires on trouve :
D(n) x+1______nbr
3____________543
7____________272
15___________134
31___________30
63___________10
127__________7
255__________2
511__________2
Encore le coté très régulier de x+1: la fréquence des D(n) décroit de moitié au fur à mesure que m augmente
Pour info sur le même test de 1000 tirages, les D(n) de la suite 3x+1 sont :
D(n) 3x+1_____nbr
5____________925
85___________32
341__________42
5461_________1
C'est globalement une bonne idée de comparer 3x+1 à x+1. La règle qui en découle est évidente : tout ce qui est simple avec x+1 devient complexe avec 3x+1.
Avec x+1 c'est la répartition pair/impair des entiers qui fait le boulot. Il y a une chance sur 2 que la division par 2 d'un pair soit un impair, une chance sur 4 pour la division par 2^2, une sur 3 pour la division par 2^3, etc... Donc quand l'instruction x+1 travaille, elle ne fait que faire fonctionner ce très simple mécanisme de probabilité. Et la convergence vers 1 est évidente car le nombre d'impairs trouvés n'ajoute que très peu à la valeur à diviser.
3x+1 arrive à converger vers 1 de manière expérimentale mais on arrive pas comprendre comment. Il y a pourtant un "mécanisme de probabilité" qui est à l'œuvre comme pour x+1...
La suite x+1 converge vers 1. Donc toutes les affirmations suivantes sont vraies :
1) Tout entier impair s'écrit sous une forme $i(n),p(n)$
2) Tout entier impair passe par un chemin d'étapes impaires consécutives, elles-mêmes exprimables en $i(n),p(n)$, jusqu'à la dernière étape impaire $D(n)$
3) L'étape $D(n)$ est en relation avec une puissance de 2 : $D(n) = 2^m-1$ avec m>=2
4) La valeur de l'entier diminue en allant d'une étape impaire à l'autre : elle est au moins égale à $\frac{x}{2}+1$ mais elle peut être bien plus petite en fonction du nombre de divisions par 2
5) La valeur du $p(n)$ diminue d'au moins une unité d'une étape à l'autre.
6) Le graphe des relations $i(n);p(n)$ est entièrement connecté (aucun sommet "libre")
La suite 3x+1 converge (peut-être) vers 1. Donc toutes les affirmations suivantes sont (peut-être) vraies :
1) Tout entier impair s'écrit sous une forme $i(n),p(n)$
2) Tout entier impair passe par un chemin d'étapes impaires consécutives, elles-mêmes exprimables en $i(n),p(n)$, jusqu'à la dernière étape impaire $D(n)$
3) L'étape $D(n)$ est en relation avec une puissance de 2 : $D(n) = \frac{2^m-1}{3}$ avec m>=4 et toujours pair
4) Dans un cas sur deux, la valeur de l'entier ne diminue pas en allant d'une étape impaire à l'autre parce que le résultat de 3x+1 divisé par deux est impair. Dans tous les autres cas, la valeur de l'entier diminue en allant d'une étape impaire à l'autre
5) La valeur du $p(n)$ diminue d'au moins une unité d'une étape à l'autre.
6) Le graphe des relations $i(n);p(n)$ est entièrement connecté (aucun sommet "libre")
Il n'y a donc qu'une seule vraie grosse différence[/b] avec le point 4 (mais dans un seul cas) et expérimentalement les 6 points de la suite 3x+1 sont vrais. On constate bien sûr que les liaisons du graphe sont nettement plus irrégulières avec 3x+1 http://www.les-mathematiques.net/phorum/read.php?43,2058452,2110414#msg-2110414 mais le graphe est tout aussi connecté. C'est simplement un autre ordre.
On passe donc de quelque chose de très simple à quelque chose de très compliqué (voire inexplicable) pour la seule raison qu'il y a une chance sur deux que la valeur de l'impair de l'étape suivante soit plus grande que la valeur d'origine.
5, 53, 35, 23, 61, 325, 433, 577, 3077, 2051, 1367, 911
Rageant, non ?
Soit le chemin de 99 :
5, 13, 17, 11, 7, 149, 99
il y a 3 cas où l'étape antérieure est plus petite : 149<--99, 11<--7 et 17<--11
dont on peut tirer une liste L1 des liaisons $i(n),p(n)$ :
003_005<--004_006
004_006<--005_007
006_013<--007_014
Et inversement on peut en déduire une autre liste L2 où l'étape antérieure est plus grande :
001_000<--002_003
002_003<--003_005
005_007<--006_013
En tirant tous les chemins des impairs de 3 à 99, on trouve deux listes d'arêtes L1 et L2 ne présentant aucun élément commun (tableau)
SI vous regardez bien L1, la différence des p(n) est toujours de -1 entre la source et la destination :
par exemple 007_015<--08_016
Donc on a une liste de "force divergente" L1 et une liste de "force convergente" L2. La force divergente présente ici plus de membres et plus d'occurrences : 48 membres vs 41 et 341 occurrences vs 289.
Le bilan des deux forces se finit toujours pour chaque chemin par la victoire de la force convergente. Si on est dans le cas de la force divergente, le p(n) ne diminue que de 1 au changement d'étape. Mais il diminue quand même. Donc dans cette optique, la force divergente ralentit la convergence mais ne peut pas l'empêcher.
Evidemment quand je dis ça je me place comme si ça convergeait toujours, ce qui n'est pas prouvé même si on le sait expérimentalement. Le chemin du 27, bien connu pour sa longueur (111) et son altitude maximale (101440) qui semblent disproportionnés par rapport à 27 n'est en fait qu'un chemin qui descend doucement comme le montre les valeurs successives de ses $p(n)$ :
0, , 5, 6, 7, 10, 14, 16, 18, 22, 23, 24, 25, 28, 29, 30, 31, 32, 33, 35, 36, 38, 39, 40, 43, 45, 46, 47, 48, 50, 51, 52, 54, 55, 57, 59, 60, 61, 62, 63, , 65, 66,
Imaginons qu'il existe un n n'atteignant pas 1. Dans cette expérience on l'a tiré par hasard et on lance l'algorithme pour constater que le calcul ne s'arrête pas. L'expérimentateur a un tableau de bord avec le nombre d'étapes parcourues et la valeur n de chacune. Il se dit qu'en toute logique, toutes ces valeurs d'étapes n'ont jamais été tirées dans aucun calcul précédant puisque tous les calculs faits par le passé ont toujours convergés. Donc si cet n existe parce son calcul n'aboutit pas, il va automatiquement s'accompagner d'une infinité des nombres qui sont ses interminables étapes intermédiaires.
Le seule problème est que cette expérience est infaisable. La seule chose que la réalité dit est que tant que c'est calculable ça converge. Tant que c'est calculable, au pire la descente des p(n) vers 0 est un peu lente.
Je peux d'ailleurs affirmer ceci pour finir. Ce chemin de décroissance de p(n) vers 0 est impossible à trouver expérimentalement.
0, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20
Je vous laisse deviner pourquoi.
Réponses
A un entier n positif donné, l'algorithme donne, au choix, soit 3n+1, soit la partie entière de n/2.
Comment passer du nombre 147 au nombre 225 ?
147 à un $i(n),p(n)$ = 042_070
225 à un $i(n),p(n)$ = 017_031
147 passe en étape 17 par un $i(n),p(n)$ = 017_032 puis passe par 002_005 en avant-dernière étape
225 commence par 017_031 puis passe par 002_003 en avant-dernière étape
Donc pour aller de 225 à 147 il faut passer par 001_000, c'est le chemin le plus long qui est le seul possible dans le graphe
je te dédie ce nouveau cobra que j'ai fait juste pour toi
ce graphe vient du tirage aléatoire de 100 chemins de n assez grands (entre 10^9 et 10^12)
le réseau est bien plus complexe avec 2820 sommets ce qui est beaucoup pour aussi peu de tirages
mais, mais, mais... le joli cobra jaune est parfaitement visible
donc quelque soit la façon de construire le graphe, on retrouve la même structure
il est facile de constater que les sommets en tête de ces deux classements occupent sensiblement les mêmes places
ID_____________Weight____________ID_____________Weight
001_000________100_______________001_000________59992
009_022________52________________002_003________28587
008_018________50________________003_005________28113
002_005________48________________004_006________27790
003_005________48________________002_005________27291
003_006________48________________004_007________26847
004_007________48________________003_006________26836
006_014________47________________008_018________26791
010_023________47________________009_022________26510
011_024________47________________016_031________26342
012_025________47________________010_023________25843
016_031________47________________012_025________25541
002_003________46________________011_024________25260
004_006________45________________006_014________25194
005_010________45________________017_032________25186
007_016________45________________007_016________25153
017_032________44________________005_010________24655
014_029________43________________014_029________23968
013_028________42________________015_030________23809
015_030________41________________013_028________23461
018_033________39________________019_035________22860
019_035________39________________018_033________22252
020_036________35________________020_036________20570
021_038________35________________021_038________20442
On atteint 225 après avoir construit un arbre binaire de hauteur 16 et dont la racine est 147.
Je ne vois pas le rapport entre Syracuse et un arbre binaire, mais le plus drôle est que la réponse de PMF se fonde sur sa base de données !
Pour l'instant, j'attends la réponse, celle de Wilfrid n'étant pas très convaincante.
Chacun de ces cercles est donc celui d'un $i(n)$. On trouvera sur chaque cercle un ou deux sommets qui représentent le gros des passages, comme on peut le voir ici pour le deuxième cercle pour les stats des 60.000 premiers impairs
002_001________2219
002_002________1248
002_003________28587
002_004________3
002_005________27291
002_006________76
002_007________5
002_008________139
002_009________318
002_010________0
002_011________80
002_012________0
002_013________0
002_015________2
002_003 et 002_005 c'est 93% des cas. J'avance l'idée que quelque soit la manière de collecter les données (de manière ordonnée depuis 3 et avec des n assez petits, ou de manière aléatoire avec des n assez grands), ces deux sommets auront la même fréquentation.
Question au passage : pourquoi 002_003 et 002_005 sont-ils si fréquentés et pas 002_004 qui est juste entre les deux ?
Ce que l'on appelle le cobra depuis l'intervention de gerbrane est simplement la visualisation des sommets les plus prévalents. Le graphe de Syracuse montrent que les chemins vers 1 convergent majoritairement vers un tronc principal (le corps du serpent composé des cercles les plus fréquentés).
Le shtam est en ce moment très riche en approches théoriques sur cette conjecture. Je défend de mon côté une approche expérimentale. Nous vivons à une époque où il est matériellement possible de calculer des données et de les visualiser de manière performante. Pourquoi ne pas passer par cette étape avant de théoriser ?
L'observation statistique des chemins vers 1 ne peut pas être balayée d'un revers de main. Plus je collecte ces observations et que je varie les moyens pour les obtenir, plus je vois une structure et un modèle de comportement. Collectivement, ou à grande échelle, les chemins vers 1 dessinent un réseau très organisé : un graphe.
Ma conclusion personnelle est très simple. Il ne s'agit pas de monter qu'un entier converge vers 1. Il s'agit plutôt de montrer que le chemin de cet entier a beaucoup plus de chances de venir se relier à un des sommets $i(n),p(n)$ les plus fréquentés que de trouver un chemin exotique vers 1.
Les chemins exotiques sont d'ailleurs connus. Il suffit de prendre un $D(n)$ différent de 5 comme cible. Par exemple 477218133 à un $i(n),p(n) $ de 002_012 et un $D(n)$ égal à 349525. Mais on va trouver des milliers de $D(n)=5$ pour un seul comme celui-ci. Il y a un seul exemple pour n<120.001 c'est 116053 (dont le $D(n)$ = 85) soit 1 cas pour 60.000 impairs.
tu me demandes comment passer de 147 à 225 par rapport aux chemins vers 1 ou pas ????
Je te dis comment ça passe dans le graphe de Syracuse qui repose sur les $i(n),p(n)$. C'est intéressant parce que la connectivité entre sommets est aussi une propriété du graphe au même titre que la convergence vers 1.
Voici ces deux chemins :
pour 147
001_000<--002_005
002_005<--003_006
003_006<--004_007
004_007<--005_010
005_010<--006_014
006_014<--007_016
007_016<--008_018
008_018<--009_022
009_022<--010_023
010_023<--011_024
011_024<--012_025
012_025<--013_028
013_028<--014_029
014_029<--015_030
015_030<--016_031
016_031<--017_032
017_032<--018_033
018_033<--019_035
019_035<--020_036
020_036<--021_038
021_038<--022_039
022_039<--023_040
023_040<--024_043
024_043<--025_045
025_045<--026_046
026_046<--027_047
027_047<--028_048
028_048<--029_050
029_050<--030_051
030_051<--031_052
031_052<--032_054
032_054<--033_055
033_055<--034_057
034_057<--035_059
035_059<--036_060
036_060<--037_061
037_061<--038_062
038_062<--039_065
039_065<--040_066
040_066<--041_069
041_069<--042_070
pour 225
001_000<--002_003
002_003<--003_005
003_005<--004_006
004_006<--005_009
005_009<--006_012
006_012<--007_015
007_015<--008_019
008_019<--009_021
009_021<--010_022
010_022<--011_023
011_023<--012_024
012_024<--013_025
013_025<--014_026
014_026<--015_027
015_027<--016_029
016_029<--017_031
Aucun sommet commun entre les deux sauf celui qui est commun à tous 000_001
Donc dans le graphe il faut faire depuis un des sommets le chemin complet vers 000_001 puis repartir en sens inverse vers le deuxième sommet. C'est la distance maximale en nbr de sommets et c'est un cas assez rare car il y a le plus souvent un sommet commun à deux chemins bien avant 000_001
Tu attends visiblement une autre réponse mais dans le graphe on fait comme ça pour aller de 147 à 225 ;-)
147 73 36 18 9 28 14 7 22 67 33 100 301 150 451 225
Je disais qu'il fallait un arbre binaire de hauteur 16 pour atteindre 225, ce que lourran a confirmé avec ses 16 nombres 147, ..., 225.
Il fallait lire : PMF n'a pas compris que ta phrase "l'algorithme donne, au choix, ..." excluait les suites de Collatz, dans lesquelles aucun choix n'est offert pour la valeur du successeur.
5, 53, 35, 23, 61, 325, 433, 577, 3077, 2051, 1367, 911, 2429, 1619, 1079, 719, 479, 319, 425, 283, 377, 251, 167, 445, 593, 395, 263, 175, 233, 155, 103, 137, 91, 121, 161, 107, 71, 47, 125, 83, 221, 147
5, 13, 17, 11, 29, 77, 205, 1093, 1457, 971, 647, 431, 287, 191, 127, 169, 225
je comprends que ta question se pose sur une variante de l'algorithme mais pour celui de Syracuse ça se passe comme ça
Je ne suis pas convaincu que la comparaison entre plusieurs algorithmes éclaire beaucoup la question de ce qui se passe avec celui de Syracuse. On ne peut pas définir un algorithme "concurrent" ou "alternatif" que de manière subjective... Pourquoi multiplier par x et diviser par y, pourquoi prendre une partie entière ?
Il faudrait quelque chose de plus cohérent dont le test serait : comment modifier l'algorithme de Syracuse sans qu'il perde sa propriété de convergence vers 1. Ce qui me semble impossible.
chemin qui n'a strictement rien à voir avec les chemins de la conjecture
utilité ????
Pour PMF : Vous semblez tenir pour acquis que la suite de Syracuse fini par boucler sur 1.
Je viens d'aller vérifier et ce n'est toujours pas démontré.
Pour ma part, j'aimerais savoir en combien d'étapes se termine votre algorithme sur l'exemple suivant : $10^{10^{10^{10^{10000}}}}+1$.
D'avance merci.
A bientôt.
Cherche livres et objets du domaine mathématique :
Intégraphes, règles log et calculateurs électromécaniques.
1_0<--2_1<--3_2<--4_6<--5_8<--6_11<--7_12<--8_13<--9_14<--10_16<--11_18<--12_25
1_0<--2_1<--3_2<--4_6<--5_8<--6_11<--7_12<--8_13<--9_14<--10_16<--11_24<--12_25
1_0<--2_1<--3_2<--4_6<--5_8<--6_11<--7_12<--8_13<--9_14<--10_18<--11_23<--12_25
1_0<--2_1<--3_2<--4_6<--5_8<--6_11<--7_12<--8_13<--9_16<--10_19<--11_21<--12_25
1_0<--2_1<--3_2<--4_6<--5_8<--6_11<--7_12<--8_13<--9_22<--10_23<--11_24<--12_25
1_0<--2_1<--3_2<--4_6<--5_8<--6_11<--7_12<--8_17<--9_19<--10_21<--11_22<--12_25
1_0<--2_1<--3_2<--4_6<--5_8<--6_9<--7_11<--8_12<--9_15<--10_17<--11_21<--12_25
1_0<--2_1<--3_2<--4_6<--5_8<--6_9<--7_11<--8_12<--9_15<--10_19<--11_22<--12_25
1_0<--2_1<--3_2<--4_6<--5_8<--6_9<--7_11<--8_12<--9_17<--10_22<--11_23<--12_25
1_0<--2_1<--3_2<--4_6<--5_8<--6_9<--7_11<--8_16<--9_18<--10_19<--11_20<--12_25
1_0<--2_1<--3_2<--4_6<--5_8<--6_9<--7_17<--8_18<--9_20<--10_21<--11_24<--12_25
1_0<--2_1<--3_2<--4_8<--5_13<--6_15<--7_16<--8_17<--9_19<--10_23<--11_24<--12_25
1_0<--2_1<--3_2<--4_8<--5_9<--6_12<--7_14<--8_18<--9_21<--10_22<--11_23<--12_25
1_0<--2_1<--3_2<--4_8<--5_9<--6_14<--7_17<--8_19<--9_22<--10_23<--11_24<--12_25
1_0<--2_1<--3_4<--4_5<--5_11<--6_12<--7_16<--8_18<--9_22<--10_23<--11_24<--12_25
1_0<--2_1<--3_4<--4_5<--5_9<--6_13<--7_15<--8_16<--9_17<--10_20<--11_24<--12_25
1_0<--2_1<--3_4<--4_5<--5_9<--6_13<--7_15<--8_16<--9_21<--10_23<--11_24<--12_25
1_0<--2_1<--3_4<--4_5<--5_9<--6_15<--7_16<--8_17<--9_18<--10_19<--11_21<--12_25
1_0<--2_1<--3_4<--4_7<--5_10<--6_11<--7_14<--8_20<--9_22<--10_23<--11_24<--12_25
1_0<--2_1<--3_4<--4_7<--5_10<--6_11<--7_16<--8_17<--9_18<--10_20<--11_22<--12_25
1_0<--2_1<--3_4<--4_7<--5_8<--6_10<--7_11<--8_13<--9_15<--10_18<--11_24<--12_25
1_0<--2_1<--3_4<--4_7<--5_8<--6_10<--7_11<--8_13<--9_15<--10_20<--11_21<--12_25
1_0<--2_1<--3_4<--4_7<--5_8<--6_10<--7_11<--8_13<--9_19<--10_21<--11_24<--12_25
1_0<--2_1<--3_4<--4_7<--5_8<--6_10<--7_11<--8_15<--9_16<--10_17<--11_23<--12_25
1_0<--2_1<--3_4<--4_7<--5_8<--6_10<--7_11<--8_15<--9_16<--10_19<--11_20<--12_25
1_0<--2_1<--3_4<--4_7<--5_8<--6_10<--7_13<--8_16<--9_18<--10_20<--11_23<--12_25
1_0<--2_1<--3_4<--4_7<--5_8<--6_10<--7_13<--8_16<--9_20<--10_21<--11_24<--12_25
1_0<--2_1<--3_4<--4_7<--5_8<--6_10<--7_19<--8_20<--9_21<--10_22<--11_24<--12_25
1_0<--2_1<--3_4<--4_7<--5_8<--6_14<--7_16<--8_18<--9_19<--10_20<--11_21<--12_25
1_0<--2_1<--3_8<--4_12<--5_13<--6_17<--7_18<--8_19<--9_20<--10_22<--11_24<--12_25
1_0<--2_2<--3_5<--4_11<--5_13<--6_14<--7_16<--8_18<--9_19<--10_21<--11_22<--12_25
1_0<--2_2<--3_5<--4_7<--5_10<--6_16<--7_17<--8_18<--9_22<--10_23<--11_24<--12_25
1_0<--2_2<--3_7<--4_8<--5_11<--6_12<--7_17<--8_18<--9_20<--10_21<--11_23<--12_25
1_0<--2_2<--3_7<--4_8<--5_9<--6_11<--7_12<--8_16<--9_18<--10_19<--11_21<--12_25
1_0<--2_2<--3_7<--4_8<--5_9<--6_11<--7_12<--8_18<--9_19<--10_22<--11_24<--12_25
1_0<--2_2<--3_7<--4_8<--5_9<--6_11<--7_14<--8_17<--9_18<--10_20<--11_23<--12_25
1_0<--2_2<--3_7<--4_8<--5_9<--6_11<--7_14<--8_17<--9_20<--10_21<--11_24<--12_25
1_0<--2_3<--3_5<--4_6<--5_7<--6_11<--7_13<--8_15<--9_16<--10_20<--11_22<--12_25
1_0<--2_3<--3_5<--4_6<--5_7<--6_11<--7_13<--8_15<--9_18<--10_19<--11_23<--12_25
1_0<--2_3<--3_5<--4_6<--5_7<--6_11<--7_13<--8_15<--9_18<--10_21<--11_24<--12_25
1_0<--2_3<--3_5<--4_6<--5_7<--6_11<--7_15<--8_16<--9_21<--10_22<--11_24<--12_25
1_0<--2_3<--3_5<--4_6<--5_9<--6_10<--7_12<--8_18<--9_21<--10_22<--11_23<--12_25
1_0<--2_3<--3_5<--4_6<--5_9<--6_10<--7_14<--8_15<--9_17<--10_18<--11_21<--12_25
1_0<--2_3<--3_5<--4_6<--5_9<--6_10<--7_14<--8_15<--9_17<--10_22<--11_24<--12_25
1_0<--2_3<--3_5<--4_6<--5_9<--6_10<--7_14<--8_17<--9_18<--10_19<--11_22<--12_25
1_0<--2_3<--3_5<--4_6<--5_9<--6_12<--7_15<--8_21<--9_22<--10_23<--11_24<--12_25
1_0<--2_5<--3_6<--4_7<--5_10<--6_14<--7_16<--8_18<--9_22<--10_23<--11_24<--12_25
1_0<--2_8<--3_9<--4_10<--5_14<--6_15<--7_18<--8_21<--9_22<--10_23<--11_24<--12_25
On peut certainement en trouver d'autres. Mais la règle est simple : si un seul chemin passant par un certain $i(n),p(n)$ rejoint 1_0 en $i(n)$ étapes; tout chemin passant par ce $i(n),p(n)$ rejoindra 1_0 par le même nombre d'étapes quelque soit les $i(n),p(n)$ intermédiaires qu'il choisira de prendre. Par contre statistiquement un de ces chemins regroupera une grande partie des passages. Dans ce cas c'est
1_0<--2_5<--3_6<--4_7<--5_10<--6_14<--7_16<--8_18<--9_22<--10_23<--11_24<--12_25
qui représente au moins 90% des passages par 12_25
memo : les chemins passant par 12_25 correspondent à 25589 impairs sur 60000. Voici les les plus petites valeurs de n pour chaque chemin :
27, 255, 367, 375, 747, 813, 817, 819, 837, 843, 7119, 11259, 14235, 16005, 16011, 16017, 16029, 16095, 19023, 19087, 28551, 28623, 42811, 42847, 42895, 42903, 42915, 42927, 57243, 64197, 64213, 64227, 64245, 64261, 64275, 64285, 64329, 64335, 64357, 64369, 64371, 64387, 64389, 64401, 64411, 64429, 64431, 64491
Merci pour cet éclairage, il va faire ma journée.
A bientôt.
Cherche livres et objets du domaine mathématique :
Intégraphes, règles log et calculateurs électromécaniques.
Ma réponse à la question de Nodgim n'a ni plus ni moins d'utilité que l'ensemble de mes messages dans cette discussion depuis plusieurs mois.
ce n'est pas prouvé ! C'est d'ailleurs une extrapolation assez douteuse, vu que PMF n'a fait que examiner des petits nombres, sans aucun rapport de taille avec le tien (une dizaine de chiffres, pas $10^{10^{10^{10000}}}$. Et, en gros, fait des statistiques avec ça. Il n'y a aucune raison que les treès grands nombres se comportent comme les petits.
Cordialement
Peut-être cette piste. Partons à l'envers, un nombre N a 3 antécédents possible s'il est de la forme 3k+1, ou 2 dans le cas contraire. Et s'il n'est pas de la forme 3k+1, il a un de ses 2 antécédents 2N ou 2N+1 qui est de la forme 3k+1.
Et ainsi, on va pouvoir 'descendre' ( 225 <-- 451 <-- 150 : 150 est plus petit que 225) ... et en descendant systématiquement, on peut descendre aussi bas qu'on veut.
Idem, en partant du point de départ, en divisant systématiquement par 2, on descend aussi bas qu'on veut.
Et forcément, à un moment, les chemins se rejoignent.
Ce n'est pas forcément le chemin le plus court, mais effectivement, ça marche sans se prendre trop la tête.
non pas du tout mais si ça éclaire ta journée....
Les grands nombres quand on considère leurs chemins $i(n),p(n)$ passent majoritairement par les mêmes endroits que les petits (du moins pour leur partie commune qui se situera dans la banlieue de 1)
J'ai fait un test ici http://www.les-mathematiques.net/phorum/read.php?43,2058452,2108806#msg-2108806
Disons que la feuille la plus haute de la canopée d'un arbre est tout autant reliée à la racine que celle qui pousse sur la branche la plus basse. Et que la sève qui ira aux deux feuilles fera chemin commun quelque part dans le tronc.
Mais tu peux continuer à faire joujou avec des logiciels, et même à croire bêtement que tu apportes quelque chose au problème de Collatz. Comme mon petit voisin, qui a 5 ans, se prend pour Messi quand il tape dans un ballon. Mais lui a 5 ans.
(*) à priori, aucun ordinateur n'est capable de mettre ce nombre, écrit en décimal, en mémoire.
Qu'apportent-ils à la conjecture comme information ?
Je dis simplement qu'il est facile de montrer qu'il y a majoritairement des chemins communs entre des n <10^5 et des n dans les 10^15.
C'est déjà ça.
Avec d'autres programmes on ferait la même constatation avec des puissances nettement plus élevées.
C'est une histoire d'arborescence. Fais une expérience de pensée toute simple : ton n immensément grand il est pair ou impair ? Même sans pouvoir le calculer, l'algorithme va donner théoriquement un autre n peut-être plus grand, peut-être plus petit mais qui aura un $i(n)$ plus petit...Forcément mon cher Watson. Donc ton n astronomique il vient de passer d'un cercle $i(n)$ à un autre plus près de 1 comme tout le monde !
Mes amitiés à ton petit voisin...
Ils ne te servent à rien; parce que tu fais joujou avec des logiciels, que tu ne fais pas des maths, que tu connais tellement peu les maths que tu racontes cette idiotie.
Tu ne parles donc pas de maths, même pas de la conjecture de Collatz (on te l'a expliqué du début, mais comme tout bon monomaniaque, tu continues sur ta lancée), tu fais joujou : de tableaux, des dessins depuis quelques temps, du vide mathématique.
Le comportement statistique de la suite de Syracuse que je décris, je ne l'invente pas. Ce sont les nombres qui font le boulot !
Mais pour le grand GerardO rien n'est jamais trop grand ni assez mathématique
Ce que font les entiers en pratique n'a aucun intérêt pour lui : c'est connu qu'aucun mathématicien digne de ce nom ne s'abaisse à des telles pratiques. Compter, beurk ! et puis quoi encore ...
Les grands nombres sont le coeur de la conjecture. Sans les grands nombres, point de conjecture !
Tant que tu regardes la façon dont les nombres se comportent quand ils se dirigent vers le cycle (4,2,1), tu ne regardes que les nombres qui arrivent vers ce cycle. Et donc tu ne te poses pas la question de savoir si certains nombres n'aboutissent pas à ce cycle.
Par nature, tu n'explores pas la conjecture de Syracuse.
Je t'ai soumis ces derniers jours 2 ou 3 suites, à partir desquelles tu pourrais bâtir des clusters , des cobras etc etc, tout comme tu le fais pour la suite que tu regardes.
Ce serait ni plus, ni moins utile dans un objectif de résolution de la conjecture de Syracuse.
Ces autres suites ne t'intéressent pas, pour 1000 raisons.
Eventuellement, on peut rêver un peu, ce serait utile de regarder ces autres suites. Soit la fameuse suite (3x+1) se comporte comme les suites qui convergent systématiquement (même forme de graphe) , et différemment des suites qui ne convergent pas systématiquement. Et alors, on aurait une piste, une petite étincelle.
Soit à l'opposé, cette fameuse suite (3x+1) a un graphe similaire aux suites qui ne convergent pas systématiquement ... et là aussi, on aurait une petite étincelle.
Je suis convaincu que ça n'aboutirait pas, mais au moins, c'est un plan. Je me pose une question, et selon la réponse à cette question, j'avance dans une direction, ou dans une autre.
Là, tu t'extasies parce que tu obtiens des graphes 'esthétiques'. Mais fais au moins le test.
Prend une des suites que je t'ai proposées. Soit tu obtiens des graphes moches, et tu pourras continuer de t'extasier, parce que la suite (3x+1) est la seule à produire des graphes esthétiques, soit tu obtiens d'autres graphes tout aussi esthétiques, et du coup, tu conclueras que le coté 'esthétique' n'est pas lié à Syracuse, c'est simplement lié au fait qu'un arbre déséquilibré donne un graphe esthétique, et peu importe la formule qui a servi à produire ce graphe.
Un mathématicien ne doit pas forcément être fort en calcul, même si cela aide parfois.
Par contre tenir pour vérité inflexible des constatations statistiques sur un échantillon négligeable de l'ensemble des naturels, c'est un sacré acte de foi.
Cela dit, les images sont jolies mais rien dans le comportement du fameux "cobra" n'a encore été prouvé ou je me trompe ?
Ce qui serait vraiment chouette, parce que soit on a droit à des jolies images, soit on a droit à des tableaux de chiffres (je ne vois pas de nombres, juste des suites de chiffres avec de temps en temps des flèches), ce serait de pouvoir faire une synthèse qui ne soit pas trop lourde.
J'en demande trop si je veux voir les résultats sous forme de formule ?
A bientôt
Cherche livres et objets du domaine mathématique :
Intégraphes, règles log et calculateurs électromécaniques.
Je ne suis pas contre ta méthode. Je comprends que tu veux faire une sorte d'étalonnage des graphes pour d'autres types de suites.
Tu voudrais en priorité essayer laquelle ?
A part ça en ce moment ça me semble intéressant de mettre en valeur les propriétés de ces suites. Je sais que tout cela ne se passe que pour des n<=10^15 honte à moi... mais bon
L'expérience a donc consisté à tirer des n assez grands dans les limites de Excel et regarder le pourcentage de points communs avec les sommets obtenus pour n de 3 à 120.001. J'utilise toujours le système des $i(n),p(n)$ pour cela.
Sur 10.000 tirages, on obtient cette distribution où 1 tirage sur 2 à au moins 57% de sommets communs avec la base.
Sur la deuxième illustration, on voit que le nombre 100 000 001 à 93% de sommets communs avec la bdd des 60.000 premiers impairs.
Il est donc très probable que les sommets que je trouve avec ma petite bdd sont très courants même pour des n bien plus grands.
Enfin une jolie question dans ce fil. Merci nodgim.
Je n'ai pas (encore) trouvé ton astuce et donc, si tu la donnes, sois gentil de la donner en encre sympathique: tu l'écris normalement puis tu la colorie en blanc: celui qui veut la lire (moi, par exemple, si je finis par me lasser de la chercher) la lit en passant la souris sur ce blanc.
Je raconte un truc proche de ce que vient d'écrire lourrran:
R1) := Il existe une infinité de chemins qui mènent de $147$ à $225$ , plus généralement de $x$ à $y$, dans $A(x)$:="arbre de nodgim de racine $x$" où:
Pour tout $x$, $A(x):= (x, A(g(x)), A(d(x)))$ où
$g(x):=\lfloor \frac{x}{2}\rfloor$
$d(x):=3x+1$
Preuve de R1:
Pour tout $x $, pour tout $m$ tel que $2^m>x$, $g^{(m)}(x)=0$.
Pour finir, il suffit de prouver que tout $y$ appartient à $A(0)$:
On note que:
pour tout $z$,
$0\in A(0)$,
$3z+1=d(g(2z))$ (et donc, si $3z+1$ ( qui est supérieur à $2z$) n'appartient pas à $A(0)$, $2z$ n'appartient pas non plus à $A(0)$)
$3z+2=g(d(2z+1))$(et donc, si $3z+2$ ( qui est supérieur à $2z+1$) n'appartient pas à $A(0)$, $2z+1$ n'appartient pas non plus à $A(0)$)
$3z+3=g(d(2z+2))$ (et donc, si $3z+3$ ( qui est supérieur à $2z+2$) n'appartient pas à $A(0)$, $2z+2$ n'appartient pas non plus à $A(0)$).
S'il existait des $y$ qui n'appartiennent pas à $A(0)$, leur ensemble aurait un plus petit élément (:=$u$). Cet $u$ ne saurait être $0$ ou d'une des trois formes $3z+1,3z+2, 3z+3$ d'après les quatre remarques précédentes. Donc cet $u$ n'existe pas. Donc tout $y$ est dans $A(0)$.
Donc R1.
R2) Vu que, maintenant, on sait que l'on trouvera $225$ dans $A(147)$, yapluka (faire) écrire $A(147)$ de haut en bas et s'arrêter quand on trouve $225$, puis (faire) écrire le chemin qui mène de $147$ à $225$: sa longueur est assurément minimale. Pour éviter cette méthode "bourrine", nodgim a une astuce et je présuppose bien sûr qu'il prouve que son chemin solution est de longueur minimale ;-)
Cordialement
Paul
Mon but étant uniquement de faire un travail statistique à la disposition de ceux qui voudront s'y intéresser, pas de soucis pour accéder à ta demande. Je pense d'ailleurs que c'est le bon moment pour faire cette synthèse.
Ce que je fais sous Excel et Rstudio est certainement programmable autrement et de manière plus performante mais c'est déjà une base.
A mon avis, l'astuce consiste à partir de 225 pour créer la suite à l'envers. En effet, au lieu de calculer $\left( \lfloor n/2 \rfloor,3\,n+1 \right)$ on calcule dans ce cas $\left( 2\,n+1,(n-1)/3 \right)$. L'un des deux nombres est entier, et si les deux le sont on prend le plus petit. Avec $n=225$ on obtient successivement
225 -> (451, 224/3)
451 -> (903, 150)
150 -> (301, 149/3)
301 -> (603, 100)
100 -> (201, 33)
33 -> (67, 32/3)
67 -> (135, 22)
22 -> (45, 7)
7 -> (15, 2)
Malheureusement, les entiers suivants croissent constamment.
147 a 2 successeurs possibles, chacun en a 2 etc etc et comme il a fallu 15 étapes pour arriver à 225, j'ai donc exploré 2+4+8+16...+2^15 nombres.
Dans le lot, il y avait pas mal de doublons. C'est assurément le plus court chemin de 147 à 225.
Un autre méthode, ce serait de parcourir l'arbre par les 2 extrémités :
Les 2 successeurs pssibles de 147 sont 73 et 442, et les 2 prédécesseurs possibles de 225 sont 450 et 451
Les 4 'petits-fils' possibles de 147 sont 36, 220, 221 et 1327, et les différents grands-parents possibles de 225 sont 150, 900, 901,902 et 903.
Et on s'arrête quand nos 2 arbres ont 1 élément en commun. Ainsi, au lieu de construire un arbre avec 2^16 éléments, on construit 2 arbres, avec 2^8 éléments pour l'un et un peu plus pour l'autre.... En gros 2 fois moins d'éléments analysés, mais un programme un peu plus compliqué à écrire.
Oui , on peut parler d'étalonnage. Mais pas d'étalonnage pour d'autres types de suite. Mais un étalonnage à partir d'autres types de suites.
Je te rappelle que l'objectif que tu t'es fixé, c'est d'analyser la suite de Syracuse.
Donc on part de suites connues, on regarde les graphes obtenus avec ces suites. Idéalement, il faudrait avoir plusieurs suites, qui donneraient des graphes très différents les uns des autres.
Puis on trace le graphe obtenu avec la suite de Syracuse, et on regarde si ce graphe se rapproche de tel graphe ou de tel autre.
Soyons honnête, l'espoir que ça mène quelque part est (à peu près) nul, mais ça occupe !
Et ça donne l'illusion d'avoir une méthode de travail.
Et donc, tu peux utiliser les suites que j'avais proposées. Ou d'autres de ton choix.
Et je ne m'appelle pas GerardO ("Mais pour le grand GerardO ...).
Même pas capable de différencier une lettre et un chiffre !
@ Wilfrid : Pour la suite à l'envers ( c'est bien ce qu'il faut faire ) si le nombre -1 n'est pas divisible par 3, on multiple par 2 et si nécessaire on ajoute 1, de manière à retrouver un nombre de la forme 3n+1.
225, 451, 150, 301, 100, 33, 67, 22, 7, 2, 4, 1.
J'ai bien dit que je "convertissais" les valeurs des impairs en couples $i(n),p(n)$ et que le graphe se faisait sur des sommets définis par ces couples.
Je pensais que cela piquerait un peu plus votre curiosité et déclencherait quelques critiques. Donc la question est : "Le graphe des couples $i(n),p(n)$ est-il aussi légitime que celui que l'on ferait avec les entiers impairs ? "
N'importe quel impair a une valeur $i(n),p(n)$. Le chemin de n'importe quel impair vers 1, donc la suite des étapes impaires jusqu'à 1 devient un ensemble de liaisons (arêtes) d'une certaine valeur $p(n)$ qui s'associe à la valeur $i(n)$ suivante. Donc pour les étapes $i(n)$ 12 à 1 un certain impair passera par des $p(n)$ tel que 0, 5, 6, 7, 10, 14, 16, 18, 22, 23, 24, 25. Toujours décroissant avec un mini de -1 mais pas mal de "sauts" aussi. Mais il y a plein de combinaisons possible comme montré ici : http://www.les-mathematiques.net/phorum/read.php?43,2058452,2109088#msg-2109088
Je suis sûr d'une chose : si une certaine valeur $i(n),p(n)$ va vers 1, tout entier passant par ce même couple ira vers 1 quelque soit la combinaison qu'il choisira. Il y a peut-être beaucoup de ces combinaisons mais pas une infinité car il y a une limite due à la décroissance obligée des $p(n)$.
Par exemple pour la serie $i(n)$ 12 à 1 la suite des $p(n)$ aurait pour limite 0, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25
Quelqu'un peut-il "démonter" ça ? Moi je conclus de ce raisonnement que l'on ne pourrait pas trouver un sommet plus "grand" que 002_015 en étape 2 dont le chemin passerai par 012_025...
j'ai choisi pour fabriquer un autre graphe la suite $U_{n+1}=U_n/2$ si $U_n$ est pair , et $U_n+1 $ sinon.
J'applique le même traitement que pour la suite de Syracuse : conversion des étapes impaires en couples $i(n),p(n)$ pour définir les sommets et les arêtes du réseau puis comptage de leurs occurrences
Par exemple pour l'entier 78593,
son cluster est : 12_17_3_30
son chemin (impairs) est : 3, 5, 39, 77, 615, 1229, 2457, 4913, 9825, 19649, 39297, 78593
et ses arêtes :
001_002<--002_001
002_001<--003_003
003_003<--004_001
004_001<--005_003
005_003<--006_001
006_001<--007_001
007_001<--008_001
008_001<--009_001
009_001<--010_001
010_001<--011_001
011_001<--012_001
J'ai aussi choisi de calculer dans un range 10^9 sur 10.000 tirages aléatoires
Le calcul est en cours...
Non ce n'est pas ça que Lourran veut faire. Il vaut avoir une possibilité d'étalonner un type de suite sur un type de graphe.
J'ai déjà fait des graphes sur les suites de Syracuse et je constate des structures. Lourran pense qu'une autre suite pas trop loin de celle de Syracuse aura aussi une structure. Si les graphes montrent des effets trop semblables pour des suites qui ne sont pas les mêmes, on pourra dire que ces structures sont "triviales" et n'apportent pas d'information décisive.
J'ai mis un peu de temps à me faire à cette idée mais je pense que lourran a raison sur ce coup-là. J'ai donc choisi la suite la plus proche de celle de Syracuse et qui est sure de converger vers 1 pour faire ce test
Je publie à suivre son graphe, le calcul vient de finir.
-1- tempérer l'enthousiasme qu'on peut voir dans ce message PMF ou les suivants.
Les graphes obtenus à partir des clusters laissent apparaître une structure ... cette structure serait 'propre' à Syracuse ? Non, je pense qu'à peu près n'importe quel arbre déséquilibré donne un graphe de ce type.
-2- donner du grain à moudre à PMF
PMF a du temps, il veut occuper ce temps en explorant la conjecture de Collatz, aidons-le à occuper son temps.
Est-ce qu'un début de piste pour la résolution de la conjecture sortira de ça ? Non, bien entendu.
voici "tout de même" le graphe de la suite $U_{n+1}=U_n/2$ si $U_n$ est pair , et $U_n+1$ sinon.
Ce graphe comporte 232 sommets et 1194 arêtes. Il est issu du calcul de 10.000 chemins d'impairs tirés aléatoirement entre 3 et 10^9
Cette suite convergeant vers 1 de manière évidente, on cherche à comparer son graphe à celui de la suite de Collatz qui elle converge "peut-être" vers 1.
Donc que voit-on ?
La structure est organisée en une série de convergence par i(n). Pour chaque sommet "target" d'une valeur i(n) donnée, on va trouver un certain nombres de sommets "source" de manière que cet ensemble d'arêtes fasse passer tous les chemins. Il faut jeter un œil au pdf joint où on voit que le premier couple avec le $p(n)$ le plus petit a le plus de passages, et que les passages décroissent avec les $p(n)$ plus grands.
Cette suite ne fait donc rien d'autre que de connecter un "cercle" $i(n)$ à un autre et de collecter dans chaque cercle des p(n) de valeurs décroissantes. Des ronds dans l'eau avec les vagues concentriques de force décroissante serait une bonne analogie.
Aucun chemin exotique n'est possible comme le fait la suite de Syracuse, et il n'y a pas cet effet de toron si particulier (comme des lianes entrelacées qui finiraient pas former un tronc)
J'attends donc vos avis.
Pour revenir sur la question du "tronçon commun", que penses-tu de ceci ?
c'est très bien, bien sûr.
Le graphe et les clusters tout ça c'est une façon de montrer comment les chemins se rejoignent en grands tronçons.
Ces deux parcours sont de véritables autoroutes pour les entiers :
5, 53, 35, 23, 61, 325, 433, 577, 3077, 2051, 1367, 911
ou sous la forme de $i(n),p(n)$
001_000<--002_005
002_005<--003_006
003_006<--004_007
004_007<--005_010
005_010<--006_014
006_014<--007_016
007_016<--008_018
008_018<--009_022
009_022<--010_023
010_023<--011_024
011_024<--012_025
Il y a une raison à ces "mots" ou à ces "phrases" si populaires dans le langage de Syracuse : c'est nettement plus organisé que chaotique comme structure !
J'ai extrait des données les liaisons entre les i(n)=2 et i(n)=3 pour mieux identifier ce qui se passe dans le graphe complet
Cette suite est de type 1x+1 si on veut la comparer au 3x+1 de Syracuse. On divise par deux tant que c'est pair et si c'est impair on "rend un point" pour redevenir pair à nouveau. Ce 1x+1 à chaque retour au pair est le chemin le plus rapide vers 1 pour n'importe quel entier. La convergence est tellement évidente que personne ne se demande ce qui se passe dans les grands nombres... Assez marrant que le passage de l'instruction 1x+1 à 3x+1 puisse changer tant de choses.
Donc les entiers convergent gentiment vers 1 si on leur donne une instruction simple pour le faire. Exactement comme pour 3x+1 il faut toujours passer d'un i(n) à un i(n)-1 pour aller vers 1. Ce qui est compliqué c'est le p(n) qui est associé au i(n). Dans le cas de 1x+1 il faut comprendre qu'un sommet $(i(n),p(n)$ va se raccorder à toutes les associations de sommets de i(n)-1 avec les p(n) possibles comme le montre le graphe et cette liste :
Source____________Target_____________Weight
003_001___________002_001___________2512
003_001___________002_002___________1263
003_001___________002_003___________658
003_001___________002_004___________329
003_001___________002_005___________173
003_001___________002_006___________61
003_001___________002_007___________33
003_001___________002_008___________19
003_001___________002_009___________9
003_001___________002_010___________4
003_001___________002_011___________5
003_001___________002_014___________1
C'est juste le nombre de divisions par 2 consécutives qui joue ici. Si la liaison 002_001<--003_001 est la plus fréquente c'est que la première division par 2 d'un pair donne un pair ou un impair. Donc on a une chance sur 2 de tomber sur un impair. Une chance sur 4 de tomber sur un impair après 2 divisions... Et on a forcément au final le type de données de la liste ci-dessus.
On peut donc dire qu'un entier pair a une probabilité 1/n de donner un nombre impair au bout de n divisions par 2. S'il est une puissance de 2 il file directement à 1. Ce que fait 1x+1 c'est simplement utiliser cet ordre possible des entiers.
L'ordre des entiers qui est a l'œuvre avec 3x+1 n'a jamais réussi à être expliqué... pourtant il repose sur un système de probabilités (un ordre comme en parle Serge Burckel) au même titre que 1x+1....
Donc on oublie le graphe publié hier et on recommence.
De manière à encore mieux "étalonner" la suite 3x+1 (Syracuse) par rapport à la suite x+1, voici le principe de la macro
1) Un entier impair est tiré au hasard entre 10^4 et 10^9 (10.000 tirages)
2) son chemin est calculé à la fois en 3x+1 et en x+1 en ne gardant que les étapes impaires
3) ces étapes impaires sont converties en $i(n),p(n)$
4) on ne garde que la liaison entre l'étape 3 et l'étape 2 et on compte toutes les occurrences que l'on trouve
Il se crée donc des liaisons spécifiques avec les deux types de suites. Le pdf joint donne les résultats complets pour les 10.000 tirages
La suite x+1 a un comportement régulier : les liaisons se font vers les sommets 002_003 à 002_013 avec 50% des cas pour liaisons vers 002_003 et 002_004. A partir de 002_005 les cas diminuent progressivement. Pour chaque sommet il se passe toujours la même chose : il y a une décroissance de moitié à partir de la première liaison dont le sommet "source" à le plus petit p(n).
La suite 3x+1 est nettement plus irrégulière. Deux liaisons concentrent 90% des cas :
002_005<--003_006 avec 4488 cas et 002_003<--003_005 avec 4621 cas.
Elle est aussi beaucoup plus sélective avec seulement 32 types de liaisons au lieu de 91 pour la suite x+1.
Contrairement à la suite x+1, 3x+1 peut se connecter avec les sommets 002_001 et 002_002 mais presque jamais avec le 002_004 (2 cas sur 10.000)
On peut voir ci-dessous les liaisons avec le sommet 002_003 pour les suites x+1 et 3x+1 :
Source____________Target_____________x+1________3x+1
003_001___________002_003______________________
003_002___________002_003______________________
003_003___________002_003______________________
003_004___________002_003___________1347_______
003_005___________002_003___________726________4621
003_006___________002_003___________337________1
003_007___________002_003___________157________
003_008___________002_003___________82_________
003_009___________002_003___________42_________55
003_010___________002_003___________25_________
003_011___________002_003___________17_________97
003_012___________002_003___________7__________
003_013___________002_003___________3__________
003_014___________002_003______________________
003_015___________002_003___________1__________8
003_016___________002_003___________1__________
003_017___________002_003______________________
003_018___________002_003______________________
La dernière étape impaire avant 1 ou $D(n)$ est très spécifique pour 3x+1. C'est toujours de type $\frac{2^m-1}{3}$ avec une énorme prédominance pour le 5 (93%)
Pour la suite x+1, on trouve des $D(n) : 3, 7,15,31,63,127,255...$ donc de forme 2^m-1
Sur 1000 tirages aléatoires on trouve :
D(n) x+1______nbr
3____________543
7____________272
15___________134
31___________30
63___________10
127__________7
255__________2
511__________2
Encore le coté très régulier de x+1: la fréquence des D(n) décroit de moitié au fur à mesure que m augmente
Pour info sur le même test de 1000 tirages, les D(n) de la suite 3x+1 sont :
D(n) 3x+1_____nbr
5____________925
85___________32
341__________42
5461_________1
C'est globalement une bonne idée de comparer 3x+1 à x+1. La règle qui en découle est évidente : tout ce qui est simple avec x+1 devient complexe avec 3x+1.
Avec x+1 c'est la répartition pair/impair des entiers qui fait le boulot. Il y a une chance sur 2 que la division par 2 d'un pair soit un impair, une chance sur 4 pour la division par 2^2, une sur 3 pour la division par 2^3, etc... Donc quand l'instruction x+1 travaille, elle ne fait que faire fonctionner ce très simple mécanisme de probabilité. Et la convergence vers 1 est évidente car le nombre d'impairs trouvés n'ajoute que très peu à la valeur à diviser.
3x+1 arrive à converger vers 1 de manière expérimentale mais on arrive pas comprendre comment. Il y a pourtant un "mécanisme de probabilité" qui est à l'œuvre comme pour x+1...
1) Tout entier impair s'écrit sous une forme $i(n),p(n)$
2) Tout entier impair passe par un chemin d'étapes impaires consécutives, elles-mêmes exprimables en $i(n),p(n)$, jusqu'à la dernière étape impaire $D(n)$
3) L'étape $D(n)$ est en relation avec une puissance de 2 : $D(n) = 2^m-1$ avec m>=2
4) La valeur de l'entier diminue en allant d'une étape impaire à l'autre : elle est au moins égale à $\frac{x}{2}+1$ mais elle peut être bien plus petite en fonction du nombre de divisions par 2
5) La valeur du $p(n)$ diminue d'au moins une unité d'une étape à l'autre.
6) Le graphe des relations $i(n);p(n)$ est entièrement connecté (aucun sommet "libre")
La suite 3x+1 converge (peut-être) vers 1. Donc toutes les affirmations suivantes sont (peut-être) vraies :
1) Tout entier impair s'écrit sous une forme $i(n),p(n)$
2) Tout entier impair passe par un chemin d'étapes impaires consécutives, elles-mêmes exprimables en $i(n),p(n)$, jusqu'à la dernière étape impaire $D(n)$
3) L'étape $D(n)$ est en relation avec une puissance de 2 : $D(n) = \frac{2^m-1}{3}$ avec m>=4 et toujours pair
4) Dans un cas sur deux, la valeur de l'entier ne diminue pas en allant d'une étape impaire à l'autre parce que le résultat de 3x+1 divisé par deux est impair. Dans tous les autres cas, la valeur de l'entier diminue en allant d'une étape impaire à l'autre
5) La valeur du $p(n)$ diminue d'au moins une unité d'une étape à l'autre.
6) Le graphe des relations $i(n);p(n)$ est entièrement connecté (aucun sommet "libre")
Il n'y a donc qu'une seule vraie grosse différence[/b] avec le point 4 (mais dans un seul cas) et expérimentalement les 6 points de la suite 3x+1 sont vrais. On constate bien sûr que les liaisons du graphe sont nettement plus irrégulières avec 3x+1 http://www.les-mathematiques.net/phorum/read.php?43,2058452,2110414#msg-2110414 mais le graphe est tout aussi connecté. C'est simplement un autre ordre.
On passe donc de quelque chose de très simple à quelque chose de très compliqué (voire inexplicable) pour la seule raison qu'il y a une chance sur deux que la valeur de l'impair de l'étape suivante soit plus grande que la valeur d'origine.
5, 53, 35, 23, 61, 325, 433, 577, 3077, 2051, 1367, 911
Rageant, non ?
5, 13, 17, 11, 7, 149, 99
il y a 3 cas où l'étape antérieure est plus petite : 149<--99, 11<--7 et 17<--11
dont on peut tirer une liste L1 des liaisons $i(n),p(n)$ :
003_005<--004_006
004_006<--005_007
006_013<--007_014
Et inversement on peut en déduire une autre liste L2 où l'étape antérieure est plus grande :
001_000<--002_003
002_003<--003_005
005_007<--006_013
En tirant tous les chemins des impairs de 3 à 99, on trouve deux listes d'arêtes L1 et L2 ne présentant aucun élément commun (tableau)
SI vous regardez bien L1, la différence des p(n) est toujours de -1 entre la source et la destination :
par exemple 007_015<--08_016
Donc on a une liste de "force divergente" L1 et une liste de "force convergente" L2. La force divergente présente ici plus de membres et plus d'occurrences : 48 membres vs 41 et 341 occurrences vs 289.
Le bilan des deux forces se finit toujours pour chaque chemin par la victoire de la force convergente. Si on est dans le cas de la force divergente, le p(n) ne diminue que de 1 au changement d'étape. Mais il diminue quand même. Donc dans cette optique, la force divergente ralentit la convergence mais ne peut pas l'empêcher.
Evidemment quand je dis ça je me place comme si ça convergeait toujours, ce qui n'est pas prouvé même si on le sait expérimentalement. Le chemin du 27, bien connu pour sa longueur (111) et son altitude maximale (101440) qui semblent disproportionnés par rapport à 27 n'est en fait qu'un chemin qui descend doucement comme le montre les valeurs successives de ses $p(n)$ :
0, , 5, 6, 7, 10, 14, 16, 18, 22, 23, 24, 25, 28, 29, 30, 31, 32, 33, 35, 36, 38, 39, 40, 43, 45, 46, 47, 48, 50, 51, 52, 54, 55, 57, 59, 60, 61, 62, 63, , 65, 66,
Imaginons qu'il existe un n n'atteignant pas 1. Dans cette expérience on l'a tiré par hasard et on lance l'algorithme pour constater que le calcul ne s'arrête pas. L'expérimentateur a un tableau de bord avec le nombre d'étapes parcourues et la valeur n de chacune. Il se dit qu'en toute logique, toutes ces valeurs d'étapes n'ont jamais été tirées dans aucun calcul précédant puisque tous les calculs faits par le passé ont toujours convergés. Donc si cet n existe parce son calcul n'aboutit pas, il va automatiquement s'accompagner d'une infinité des nombres qui sont ses interminables étapes intermédiaires.
Le seule problème est que cette expérience est infaisable. La seule chose que la réalité dit est que tant que c'est calculable ça converge. Tant que c'est calculable, au pire la descente des p(n) vers 0 est un peu lente.
Je peux d'ailleurs affirmer ceci pour finir. Ce chemin de décroissance de p(n) vers 0 est impossible à trouver expérimentalement.
0, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20
Je vous laisse deviner pourquoi.