Autor:in
Das Collatz-Problem
Dieses doch Recht einfache erklärende Problem der Mathematik, ist weitaus komplexer als manche es sich vorstellen können.
Einleitung
Das Problem ist unter verschiedenen Namen bekannt, wie dem \(3x+1\)—Problem.
Die Vermutung über dieses Problem hat Lothar Collatz 1937 gestellt.
Neben der Zahlentheorie hat es einei Enge Verbindung zur Theorie der Berechenbarkeit in der Informatik.
Aber was sagt dieses Problem überhaupt aus? Ganz einfach!
Formulierung der Vermutung
Mathematisch
Es Sei \(n \in \mathbb{N}\) und \(C \colon \mathbb{N} \to \mathbb{N}\) eine Funktion. Wir definieren:
\[C(n) \colon = \begin{cases} \frac{n}{2} &, \text{ wenn } n \text{ gerade }\\ 3n+1 &, \text{ sonst} \end{cases}\]Außerdem definieren wir weiter rekursiv:
\[C^k(n) \colon = \begin{cases} n &, k=0 \\ C(n) &, k=1 \\ C(C^{k-1}(n)) &, k>1 \end{cases}\]Die Vermutung lautet dann: \(\forall n \in \mathbb{N} \exists t \in \mathbb{N}: C^t(n) = 1\).
Umgangssprachlich
Man wähle eine beliebige natürliche Zahl und teile diese durch zwei falls sie gerade ist und multipliziere sie mit 3 und addiere 1 hinzu, falls die Zahl ungerade ist. Wiederhole dies solange bis, man im Zyklus 4,2,1 landet. Man überlege sich kurz ein Beispiel:
\[32, 16, 8, 4, 2, 1, 4, 2, 1 \dots\]Oder ein nicht triviales Beispiel:
\[7, 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1\]