Arbre de Collatz
La suite de Syracuse, autrement connue sous le nom de suite de Collatz, est définie de la façon suivante :
- on choisit comme valeur de départ un entier strictement positif,
- à chaque étape on calcule une nouvelle valeur en appliquant les règles suivantes :
- si la valeur actuelle est paire, la nouvelle valeur est égale à sa moitié,
- sinon, la nouvelle valeur est égale à son triple augmenté de 1.
Exprimé en termes mathématiques, on a donc \(u_0\) un entier strictement positif et pour tout \(n\) entier naturel :
En prenant comme valeur initiale \(u_0=3\) on obtient la succession suivante :
graph LR
Q(3) --> R(10)
R --> A(5)
A --> B(16)
B --> C(8)
C --> D(4)
D --> E(2)
E --> F(1)
F --> DComme on peut le voir, lorsque l'on a atteint la valeur \(1\), on rentre dans un cycle \(1\rightarrow 4\rightarrow 2\rightarrow 1\rightarrow \dots\).
Partant de \(3\), il faut calculer sept termes avant d'obtenir \(1\).
Une célèbre conjecture suppose que la suite de Syracuse de n'importe quel entier strictement positif atteint \(1\). Si cette conjecture est vraie, il est possible de construire un arbre enraciné, appelé arbre de Collatz, représentant les trajectoires de différents entiers jusqu'à ce qu'ils atteignent la valeur \(1\).
graph LR
R(1)
A(2)
B(4)
C(8)
D(16)
subgraph sg1 ["h=5"]
E(5)
F(32)
end
H(64)
G(10)
subgraph sg2 ["h=7"]
K(21)
L(128)
J(20)
I(3)
end
A --- R
B --- A
C --- B
D --- C
F --- D
H --- F
E --- D
G --- E
J --- G
I --- G
L --- H
K --- HL'arbre représenté ci-dessus est de hauteur \(7\), ses feuilles ont pour valeurs \(\left[3;20;21;128\right]\).
La racine de l'arbre a pour valeur \(1\). Les autres nœuds sont obtenus de la façon suivante. Soit \(n\) la valeur d'un nœud :
- dans tous les cas, ce nœud a pour enfant un nouveau nœud de valeur \(2n\),
- si de plus, \(n\) est strictement supérieur à \(6\) et si la division euclidienne de \(n\) par \(6\) donne un reste de \(4\), on ajoute un autre enfant de valeur \(\dfrac{n - 1}{3}\).
On demande d'écrire la fonction feuilles qui prend en argument la hauteur de l'arbre souhaité et renvoie la liste triée des valeurs des feuilles de cet arbre.
Les hauteurs passées en argument seront toujours des entiers compris entre \(0\) et \(30\).
Trier une liste
On rappelle qu'il est possible de trier une liste nombres en faisant nombres.sort() (tri en place) ou sorted(nombres) (qui renvoie une nouvelle liste triée contenant les mêmes éléments).
>>> nombres = [2, 0, 1]
>>> nombres.sort()
>>> nombres
[0, 1, 2]
>>> nombres = [2, 0, 1]
>>> sorted(nombres)
[0, 1, 2]
>>> nombres
[2, 0, 1]
Exemples
>>> feuilles(0)
[1]
>>> feuilles(1)
[2]
>>> feuilles(5)
[5, 32]
>>> feuilles(7)
[3, 20, 21, 128]
>>> feuilles(14)
[11, 68, 69, 70, 75, 384, 416, 424, 426, 452, 453, 454, 2560, 2688, 2720, 2728, 2730, 16384]
Aide
Chaque niveau d'indice supérieur ou égal à \(1\) peut être déterminé à partir du niveau précédent.
# Tests(insensible à la casse)(Ctrl+I)
(Alt+: ; Ctrl pour inverser les colonnes)
(Esc)