La conjecture de Syracuse, ou conjecture 3n+1

A l'origine, une constatation toute bête :
Prenez un nombre quelconque n, et :

S'il est pair, divisez le par deux
S'il est impair, multipliez le par trois et ajoutez un

Puis recommencez avec le nombre obtenu. Par exemple, en partant de 7 on obtient la suite :
7 22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1 4 2 1 4 2 1...

Il semble que l'on tombe toujours sur la suite 1 4 2 1... Et ce , quelque soit le nombre de départ ! Ça peut être très long : essayez en partant de 27... Il y a quelque chose de fascinant dans cette alternance de petits et de grands nombres. On croit parfois que la suite va croître indéfiniment, mais non, elle revient toujours vers 1...

Aussi étonnant que cela puisse paraître, et bien que cette suite soit connue depuis plus de cinquante ans et ait été étudiée très sérieusement par des mathématiciens professionnels renommés, personne n'a jamais pu prouver que la suite "retombait toujours sur 1 quel que soit le point de départ; Ce problème est connu sous le nom de problème de Syracuse ou (en anglais) the Collatz problem, the Syracuse problem, Kakutani's problem, Hasse's algorithm, and Ulam's problem,

Sous son air très simple, ce problème est extraordinairement difficile. Paul Erdös a affirmé que "les mathématiques ne sont pas prêtes pour de tels problèmes" !

On pourra trouver une étude sérieuse et très complète de ce sujet <ici>

Une recherche par ordinateur montre que la conjecture de Syracuse est vraie jusqu'à un million au moins. (et même jusqu'à 2^40). Mais y a-t'il un contre exemple ?

Ma modeste contribution a ce problème a été d'étudier la généralisation suivante :

Considérons toutes les fonctions telles que :
On se fixe un entier d >= 2 (dans le cas du problème "original" de Syracuse, ce serait 2), puis on se donne d nombres a₀...a_d-1 tous inférieurs à d; on définit alors une une fonction f de N dans N par :
- si n est divisible par d, f(n) = n * a_O / d (on dit que n est congru à 0 modulo d Ce que j'écrirais parfois a ~ 0 [d] )
- sinon si le reste de n dans la division par d est r, f(n) = a_r * n + r

Je dis qu'une telle fonction est syracusienne si pour tout n l'itération de f sur n conduit a 1.

J'ai recherché systématiquemment les fonctions syracusiennes, c'est à dire les a_i pour n donné (en vérifiant pour tous les diviseurs jusque 6, tous les n jusque 3000) et les a_i jusque 20) :

Remarque : du fait que je n'ai testé n que jusque 3000, certaines suites "syracusiennes" citées ci dessous ne le sont peut être pas en réalité. De plus j'ai considéré qu'une suite "divergeait" quand l'un des termes était supérieur à 100000000000000, certaines suites divergentes signalées ci dessous ne le sont donc peut être pas en réalité. Enfin j'ai considéré qu'une suite qui parcourait 5000 itérations sans retomber sur 1 bouclait, ce qui n'est pas une preuve..

On donne pour chaque diviseur toutes les fonctions syracusiennes 
et la suite obtenue en partant de 1
exemple : n~0 -> n*1/2 signifie : si n est congrus à zéro (modulo 2 ici) alors prendre n/2
------------diviseur 2--------------
------OK------------
  n~0 -> n*1/2
  n~1 -> n*1+1
 1 2 1 
------OK------------
** c'est le problème original de syracuse ** 
  n~0 -> n*1/2
  n~1 -> n*3+1
 1 4 2 1 
------------diviseur 3--------------
------------diviseur 4--------------
------OK------------
  n~0 -> n*1/4
  n~1 -> n*1+1
  n~2 -> n*1+2
  n~3 -> n*1+3
 1 2 4 1 
------OK------------
  n~0 -> n*1/4
  n~1 -> n*2+1
  n~2 -> n*1+2
  n~3 -> n*1+3
 1 3 6 8 2 4 1 
------OK------------
  n~0 -> n*1/4
  n~1 -> n*3+1
  n~2 -> n*1+2
  n~3 -> n*1+3
 1 4 1 
------OK------------
  n~0 -> n*1/4
  n~1 -> n*5+1
  n~2 -> n*1+2
  n~3 -> n*1+3
 1 6 8 2 4 1 
------OK------------
  n~0 -> n*1/4
  n~1 -> n*7+1
  n~2 -> n*1+2
  n~3 -> n*1+3
 1 8 2 4 1 
------OK------------
  n~0 -> n*1/4
  n~1 -> n*9+1
  n~2 -> n*1+2
  n~3 -> n*1+3
 1 10 12 3 6 8 2 4 1 
------OK------------
  n~0 -> n*1/4
  n~1 -> n*10+1
  n~2 -> n*1+2
  n~3 -> n*1+3
 1 11 14 16 4 1 
------OK------------
  n~0 -> n*1/4
  n~1 -> n*11+1
  n~2 -> n*1+2
  n~3 -> n*1+3
 1 12 3 6 8 2 4 1 
<<< échec pour n=21845>>>:
  n~0 -> n*1/4
  n~1 -> n*13+1
  n~2 -> n*1+2
  n~3 -> n*1+3
divergence
------OK------------
  n~0 -> n*1/4
  n~1 -> n*1+1
  n~2 -> n*1+2
  n~3 -> n*5+3
 1 2 4 1 
<<< échec pour n=2041>>>:
  n~0 -> n*1/4
  n~1 -> n*11+1
  n~2 -> n*1+2
  n~3 -> n*5+3
divergence
<<< échec pour n=2307>>>:
  n~0 -> n*1/4
  n~1 -> n*13+1
  n~2 -> n*1+2
  n~3 -> n*5+3
divergence
<<< échec pour n=421>>>:
  n~0 -> n*1/4
  n~1 -> n*14+1
  n~2 -> n*1+2
  n~3 -> n*5+3
divergence
------OK------------
  n~0 -> n*1/4
  n~1 -> n*1+1
  n~2 -> n*1+2
  n~3 -> n*6+3
 1 2 4 1 
------OK------------
  n~0 -> n*1/4
  n~1 -> n*1+1
  n~2 -> n*1+2
  n~3 -> n*7+3
 1 2 4 1 
<<< échec pour n=21453>>>:
  n~0 -> n*1/4
  n~1 -> n*7+1
  n~2 -> n*1+2
  n~3 -> n*7+3
divergence
------OK------------
  n~0 -> n*1/4
  n~1 -> n*1+1
  n~2 -> n*1+2
  n~3 -> n*9+3
 1 2 4 1 
------OK------------
  n~0 -> n*1/4
  n~1 -> n*3+1
  n~2 -> n*1+2
  n~3 -> n*9+3
 1 4 1 
<<< échec pour n=327>>>:
  n~0 -> n*1/4
  n~1 -> n*13+1
  n~2 -> n*1+2
  n~3 -> n*9+3
divergence
<<< échec pour n=1563>>>:
  n~0 -> n*1/4
  n~1 -> n*3+1
  n~2 -> n*1+2
  n~3 -> n*13+3
divergence
<<< échec pour n=443>>>:
  n~0 -> n*1/4
  n~1 -> n*5+1
  n~2 -> n*1+2
  n~3 -> n*13+3
boucle
<<< échec pour n=6135>>>:
  n~0 -> n*1/4
  n~1 -> n*3+1
  n~2 -> n*1+2
  n~3 -> n*14+3
divergence
------------diviseur 5--------------
------------diviseur 6--------------
------OK------------
  n~0 -> n*1/6
  n~1 -> n*2+1
  n~2 -> n*8+2
  n~3 -> n*1+3
  n~4 -> n*1+4
  n~5 -> n*1+5
 1 3 6 1 
<<< échec pour n=929>>>:
  n~0 -> n*1/6
  n~1 -> n*1+1
  n~2 -> n*11+2
  n~3 -> n*1+3
  n~4 -> n*1+4
  n~5 -> n*1+5
divergence
<<< échec pour n=8339>>>:
  n~0 -> n*1/6
  n~1 -> n*2+1
  n~2 -> n*11+2
  n~3 -> n*1+3
  n~4 -> n*1+4
  n~5 -> n*1+5
divergence
<<< échec pour n=737>>>:
  n~0 -> n*1/6
  n~1 -> n*9+1
  n~2 -> n*14+2
  n~3 -> n*1+3
  n~4 -> n*1+4
  n~5 -> n*1+5
boucle
etc... Je ne cite pas toutes les suites syracusiennes pour d = 6, il 
y en a trop.

Ce qui est intéressant c'est que apparemment il n'y a pas de suite syracusiènne pour les diviseurs impairs. De plus lorsque n ~ 0, on doit toujours diviser par d ; par exemple il n'y a pas de suite syracusienne telle que
si n ~ 0 [d] alors f(n) = 2n/d ...

Enfin le grand nombre se suite syracusiennes trouvées est intéressant. Je ne m'attendais pas à un si grand nombre...