Studium, Ausbildung und Beruf

web uni-protokolle.de
 powered by
NachrichtenLexikonProtokolleBücherForenSamstag, 2. August 2014 

Collatz-Problem


Dieser Artikel von Wikipedia ist u.U. veraltet. Die neue Version gibt es hier.
Das Collatz-Problem gehört zu den ungelösten Problemen der Mathematik . Es wird gelegentlich auch 3n+1-Problem Syracuse Vermutung Kakutanis Problem Hasse Algorithmus Thwaites Vermutung oder Ulams Problem (Stanislaw Marcin Ulam) genannt.

Das Problem lautet:

Man beginne mit einer beliebigen natürlichen a 0 und bilde damit die rekursive Zahlenfolge

<math>{a_{n+1}} = T(n) = \left\{
\begin{matrix}
 \frac{1}{2}a_n & \mbox{für } a_n \mbox{ 3a_n + 1 & \mbox{für } a_n ungerade}  
\end{matrix} \right. </math>

Die Folge endet wenn sie den 1 erreicht.

Vermutung : Für jede natürliche Zahl a 0 erreicht die Folge nach endlich vielen den Wert 1.

Diese Vermutung konnte bisher weder bewiesen widerlegt werden.

Beispiel: Sei a 0 = 5. Dann erhält man die 5 16 8 4 2 1. Für 0 = 7 lautet die Folge 7 11 34 17 52 26 13 40 10 5 16 8 4 2 1.

Da auf jede ungerade Zahl n 2k+1 eine gerade Zahl folgt ( 3n+1 3*(2k+1) +1 = 6k + 4 ist betrachtet man oft auch das äquivalente Problem :

<math>{a_{n+1}} = T(n) = \left\{
\begin{matrix}
 \frac{1}{2}a_n & \mbox{für } a_n \mbox{ \frac{3a_n + 1}{2} & \mbox{für } a_n ungerade}  
\end{matrix} \right. </math>

Das Problem wurde 1937 von Lothar veröffentlicht. Seitdem haben sich viele Mathematiker mit Problem beschäftigt. Mehrfach wurden Preise für eine ausgelobt. 1970 bot H.S.M.Coxeter 50$ für einen der Vermutung und 100$ für ein Gegenbeispiel. hat 1996 1000 englische Pfund versprochen.

Prinzipiell kann die Zahlenfolge eine der folgenden Eigenschaften haben:

  • die Folge endet bei 1.
  • die Folge wächst über alle Grenzen.
  • die Folge gerät in einen Zyklus.

Computer haben alle Zahlen bis 3 2 53 (Stand 1999) durchprobiert; immer endet die mit 1 bestätigt also die Vermutung.

Falls die Folge in einen Zyklus dann besteht dieser aus mindestens 275.000 Zahlen J.C.Lagarias 1985 zeigte.

Man hat mit unterschiedlichen Methoden versucht Problem zu lösen.

Verallgemeinerungen des Problems

R.Terras gewinnt Teilerkenntnisse über Zyklen indem als Anfangswert auch negative Zahlen zulässt (1976
Marc Chamberland und Grinnell College definieren stetige Funktion welche die diskrete Collatz-Folge auf Bereich der reellen Zahlen erweitert.
Simon Letherman Dierk Schleicher und Reg betrachten Funktionen im Bereich der komplexen Zahlen Erweiterung.

Graphentheorie

Man untersucht den so genannten Collatz-Baum oder Collatz-Graphen . Dies ist ein Graph dessen Wurzelknoten 1 beginnt. Zu jedem Knoten gibt es oder zwei Vorgänger nämlich die Zahlen von aus durch Anwendung der Iterationsvorschrift der Knoten erreicht wird. 1 hat Vorgänger 2 (denn 2/2 = 1) 16 die Vorgänger 32 und 5 (denn 3*5+1 16).
Mit diesem Graphen beschäftigen sich u.a. Stefan Andrei Manfred Kudlek Raud Stefan Niculescu. gewinnen unendliche Teilmengen der natürlichen Zahlen für die Collatz-Folge bei 1 endet.




Bücher zum Thema Collatz-Problem

Dieser Artikel von Wikipedia unterliegt der GNU FDL.

ImpressumLesezeichen setzenSeite versendenSeite drucken

HTML-Code zum Verweis auf diese Seite:
<a href="http://www.uni-protokolle.de/Lexikon/Collatz-Folge.html">Collatz-Problem </a>