Suite de Syracuse.

[Doraki]

Là je parle d'incidabilité algorithmique. Un problème est indécidable si il n'existe pas d'algorithme (à définir proprement avec les machines de Turing par exemple, mais ca revient à dire un code en langage C avec des boucles for) qui à chaque n dit si n vérifie la conjecture (le problème) ou si il ne le vérifie pas.
A fortiori il n'existe pas de preuve mathématique que la conjecture est vraie ou fausse pour tout n car sinon un algorithme serait d'énumérer toutes les preuves possibles et de regarder lesquelles sont valides logiquement (l'algorithme termine car il existe une preuve de longueur finie).
Je sais que ca peut paraître choquant mais certains problèmes mathématiques bien définis ne sont pas prouvables ni réfutables. On ne sait pas si c'est le cas pour collatz.

pas exactement.
Si la conjecture est vraie alors il y a un algorithme très simple qui dit "oui" tout le temps.
Le problème est de fournir une preuve que l'algorithme est correct.

[lapras]

Ce que je voulais dire est la chose suivante :
si la conjecture est mathématiquement prouvable ou réfutable (vraie ou fausse), l'algorithme qui à n renvoie la réponse "oui" oui "non" selon la véracité de la conjecture est un algorithme qui fonctionne.
Pour savoir si c'est "oui" ou "non" on peut énumérer toutes les preuves.
Donc algorithmiquement indécidable => pas de preuve.

[Doraki]

Comment tu vérifies si un algorithme donné répond correctement ou non ?

Et puis il se pourrait ptetre que la conjecture soit prouvablement fausse mais sans qu'on puisse donner d'algorithme pour décider du truc pour chaque n.
(par exemple, avec l'arithmétique de Peano + l'axiome "la conjecture est fausse", si c'est consistent, ben la conjecture est prouvablement fausse mais pour le moment je vois pas d'algorithme qui conviendrait)

[lapras]

Ok je vois ce que tu veux dire.
Alors ce que j'ai dit est faux, mais au moins on peut affirmer que : Collatz vrai => décidable algorithmiquement. Si Collatz faux c'est une autre histoire.

[nodjim]

Je dois dire que j'ai un peu de mal à comprendre cette indécidabilité. Doit on comprendre que pour certains problèmes on démontre que c'est indémontrable ?

[lapras]

Exact. Cf par exemple hypothese du continu.
C'est indecidable dans le systeme d'axiome de ZFC (theorie des ensembles).
Pourtant l'énoncé est exprimable avec ce systeme logique.

[mathelot]

////////////////////////

[mathelot]

Bonjour,

la suite de Syracuse est définie par
choix d'une valeur initiale
application répétée des deux règles
[x pair]
[x impair]

On appellera cet algo: "chainage en avant"
il suffit de montrer que tout entier impair peut être chainé en avant vers un entier impair
strictement inférieur

En "chainage en arrière"
[x quelconque]
[x =2(3k+2)]

en "chainage en arrière", les deux règles sont parfois applicables en même temps
et le problème de Syracuse, c'est que manque le critère de décision pour chainer
un entier vers un autre.

L'existence d'un chainage "en arrière" entre deux entiers impairs y et z
revient à la condition

il existe
il existe
tels que

[Bambino9999]

C'est un graphique des nombres impairs de 1 à 9997 après 190 itérations.
La courbe représente la somme obtenue après 190 itérations.

Comparée aux 1000 premiers impairs après le même nombre d'itérations la courbe change très peu.

[mathelot]

Bonjour,

en abscisse,on lit le nombre d'itérations
en ordonnée



où est la k-ième itérée. C'est ça ? est-ce que les réductions modulo
sont comprises dans le nombre d'itérées ?

[Bambino9999]

Bonjour,

en abscisse,on lit le nombre d'itérations
en ordonnée



où est la k-ième itérée. C'est ça ? est-ce que les réductions modulo
sont comprises dans le nombre d'itérées ?

Oui.

Exemple simple :

1
3
5

3 itérations
1 4 2 1
3 10 5 16
5 16 8 4

On aura donc une courbe

9 30 15 21

9=1+3+5
30=4+10+16
15=2+5+8
21=1+16+4

[Bambino9999]

Comme je fais cela sur un tableur je n'ai pas idée de ce que cela donnerait pour le premier million d'impairs et au bout de 10.000 itérations.
Je parie que la courbe converge vers une forme simple (pas très sûr mais juste mon flair).

[Node33]

Salut,

Je n'ai pas tout lu, mais pas plus tard que cet après-midi je me suis amusé à faire un tableur (Excel) avec la suite de Syracuse.

Avec juste 3 cellules tu peux avoir tout ce que tu veux :
En A1 tu rentres le chiffre ou nombre de ton choix (de 1 à 1 048 576, au-delà, certains nombre fonctionne, pour d'autres le logiciel ne fonctionnera pas (Excel n'étant pas capable de calculer au-delà d'un certain niveau).
En B1 tu mets exactement ceci =SI(MOD(A1;2)=0;A1/2;3*A1+1)
Ensuite en A2 tu mets =B1.
Puis en B2 tu fais une duplication de B1...

J'ai pas trouvé de chaines de plus de 110, donc ne fait pas de duplication au delà de A et B 110, ça devrait pas trop servir.

Après si tu veux avancer un peu tu as juste à dupliquer vers la droite ce que tu viens de faire vers le bas pour avoir plusieurs résultats sous les yeux (donc en commençant de 1 à ... l'infini si tu t'en ses le courage).

Je ne sais pas si ça peut t'aider ;)

[Bambino9999]

Merci pour les conseils, j'utilise gnumeric. En plus, ma ram est minuscule. 10.000 lignes et 100 colonnes et hop ça bloque.

[mathelot]

La courbe du graphe est plate jusqu'à l'abscisse puis semble être une exponentielle décroissante
. Est-ce que a vaut ?

[Bony]

Je comprends pas vraiment le sens du graphe

[mathelot]

Bonjour,


est-ce la partie exponentielle du graphe correspondrait à une exponentielle
de base ? sait-on jamais.



(La pente de la bissectrice des droites y=x/2 et y=(3x+1)/2 est
)

[mathelot]

Bonjour,

C'est bien connu, les valeurs initiales donnent des chaines (descendantes) de longueur arbitraire, ce qui l'est moins,c'est que les valeurs initiales et donnent des vols en altitude arbitrairement longs;



...

on note aussi que des entiers naturels en progression arithmétique de raison

ont des images par Collatz en progression arithmétique de raison ou
selon la parité du 1er terme à cause de l'aspect affine des applications
et

je m'interroge de savoir si l'on peut associer à un intervalle
de "valeurs initiales" un algorithme papillon style FFT (fast fourier transform)
de dichotomie sur un arbre binaire dont les noeuds sont constitués de suites arithmétiques, la moitié des valeurs, supposées en progression arithmétique de raison ont des images plus haut en progression arithmétique de raison ,

la moitié des valeurs en progression arithmétique de raison r=3
ont des images plus bas en progression arithmétique de raison

On peut se demander également si la durée des vols ne serait pas répartie comme une "http://fr.wikipedia.org/wiki/Planche_de_Galton "
à cause de la dichotomie 1/2 ;3/2 , planche de Galton infinie pour l'ensemble des valeurs initiales , ce qui fait que les courbes en cloche de la planche de Galton sont masquées
et peu visibles de façon immédiate à moins de faire tourner l'algorithme de dichotomie sur les
suites arithmétiques (leur nombre double à chaque itération)

exemple: ensemble de valeurs initiales [|1;16|] en progression arithmétique de raison r=1
un terme sur deux est pair, un terme sur deux est impair
Par Collatz (nombre d'itérées k=1)
ça donne deux suites arithmétiques de raison r=1 : [|1;8|] et une de raison r=3, de 1er terme 2.
Au coup suivant , (nombre d'itérées k=2), ça donne quatre suites arithmétiques de raisons

Au coup suivant , (nombre d'itérées k=3), ça donne huit suites arithmétiques de raisons
etc..

conclusion
Pour le graphe proposé par Bambino, il y a une formule explicite pour les sommes écrites en ordonnée,
quand pour les premières itérées.
Ensuite le comportement des sommes est mathématiquement obscur, car les valeurs initiales
des suites arithmétiques se périodisent "petit à petit" et l'on assiste à une décroissance exponentielle des sommes.

Amha, cette description introduit , dans le désordre Collatz, un ordre, une structure
fait d'un arbre binaire de suites arithmétiques.
olivier bertrand

[Bambino9999]

Bonjour,

C'est bien connu, les valeurs initiales donnent des chaines (descendantes) de longueur arbitraire, ce qui l'est moins,c'est que les valeurs initiales et donnent des vols en altitude arbitrairement longs;



...

on note aussi que des entiers naturels en progression arithmétique de raison

ont des images par Collatz en progression arithmétique de raison ou
selon la parité du 1er terme à cause de l'aspect affine des applications
et

je m'interroge de savoir si l'on peut associer à un intervalle
de "valeurs initiales" un algorithme papillon style FFT (fast fourier transform)
de dichotomie sur un arbre binaire dont les noeuds sont constitués de suites arithmétiques, la moitié des valeurs, supposées en progression arithmétique de raison ont des images plus haut en progression arithmétique de raison ,

la moitié des valeurs en progression arithmétique de raison r=3
ont des images plus bas en progression arithmétique de raison

On peut se demander également si la durée des vols ne serait pas répartie comme une "http://fr.wikipedia.org/wiki/Planche_de_Galton "
à cause de la dichotomie 1/2 ;3/2 , planche de Galton infinie pour l'ensemble des valeurs initiales , ce qui fait que les courbes en cloche de la planche de Galton sont masquées
et peu visibles de façon immédiate à moins de faire tourner l'algorithme de dichotomie sur les
suites arithmétiques (leur nombre double à chaque itération)

exemple: ensemble de valeurs initiales [|1;16|] en progression arithmétique de raison r=1
un terme sur deux est pair, un terme sur deux est impair
Par Collatz (nombre d'itérées k=1)
ça donne deux suites arithmétiques de raison r=1 : [|1;8|] et une de raison r=3, de 1er terme 2.
Au coup suivant , (nombre d'itérées k=2), ça donne quatre suites arithmétiques de raisons

Au coup suivant , (nombre d'itérées k=3), ça donne huit suites arithmétiques de raisons
etc..

conclusion
Pour le graphe proposé par Bambino, il y a une formule explicite pour les sommes écrites en ordonnée,
quand pour les premières itérées.
Ensuite le comportement des sommes est mathématiquement obscur, car les valeurs initiales
des suites arithmétiques se périodisent "petit à petit" et l'on assiste à une décroissance exponentielle des sommes.

Amha, cette description introduit , dans le désordre Collatz, un ordre, une structure
fait d'un arbre binaire de suites arithmétiques.
olivier bertrand

Merci pour tous ces détails.
En fait mon idée est simple.
Si, au lieu de prendre individuellement les valeurs n (n impair) et leur appliquer 3n+1 etc..., on prenait les sommes de leurs transformations après chaque itération, on obtiendrait une courbe que l'on pourrait formuler explicitement.
En montrant la courbe les 1000 premières valeurs ensuite 10.000 etc... on pourrait imaginer la courbe quand n tend vers l'infini. Je pencherais pour une droite presque parfaite si l'on prenait les logarithmes des sommes.
Je ne sais pas, étant incapable avec ma machine de visualiser la chose.

Merci en tout cas.

[Bambino9999]

En log ça donne ça :