Die Collatz Vermutung – einfach zu verstehen, (fast) unmöglich zu meistern
Letzte Woche hatte ich die Ehre, einem Vortrag des Fields Medaillen Gewinners Terry Tao zu lauschen. Dies an der Universität Basel. Die Fields Medaille entspricht dem Nobelpreis, ist die höchste Auszeichnung der Mathematik und wird nur Personen unter 40 Jahren verliehen. Tao berichtete über eine alte Vermutung der Mathematik, die wirklich einfach zu verstehen ist, aber bisher noch nicht bewiesen oder widerlegt wurde. Es handelt sich dabei um die Collatz Vermutung.
Die Collatz Funktion
Eine Collatz Funktion nimmt eine natürliche Zahl, also n=1, 2, 3, 4 und so weiter und bildet sie auf eine andere natürliche Zahl ab. Die Regel dabei lautet wie folgt: Ist n eine gerade Zahl, so dividiert man sie einfach durch zwei. Mathematisch ausgedrückt liest sich das als Col(n)=n/2. Ist n hingegen ungerade, so multipliziert man sie mit drei und zählt eins dazu, also Col(n)=3n+1. Das Resultat dieser Funktion dürfen wir wieder in die Collatz Funktion einfügen, so dass wir eine Folge von Zahlen generieren.
Ein Beispiel der Collatz Funktion
Betrachten wir einmal ein Beispiel und starten mit der Zahl fünf. Die Zahl fünf ist ungerade, also ist Col(5)=3*5 + 1 = 16. Fügen wir diese neu generierte Zahl, also 16 wieder in die Collatz Funktion ein, so ergibt sich Col(16)=16/2=8, da 16 gerade ist. Auch acht ist gerade, also ist Col(8)=8/2=4. Weiter geht es mit Col(4)=4/2=2 und Col(2)=2/2=1. Nun sind wir bei eins angekommen, was ungerade ist, also ist Col(1)=3*1+1=4, doch diese Zahl hatten wir schon einmal. Was passiert nun? Aus vier wird zwei, aus zwei wird eins und aus eins wieder vier. Wir enden also in einer Schlaufe, welche sich ewigs wiederholt.
Die Collatz Vermutung
Hier kommt der Knackpunkt, der Mathematiker*Innen in den Wahnsinn treibt. Die Frage lautet: enden alle natürliche Zahlen in dieser 4-2-1-4 Schleife, wenn man eine solche Folge von Collatz Funktionen bildet?
Jetzt kann man sich natürlich die grundsätzliche Frage stellen, warum uns die Lösung dieses Problem überhaupt interessiert. Terry Tao hat dafür ein paar gute Gründe genannt.
Ich persönlich mag den letzten Punkt besonders: das Recht zu Prahlen. Aber der wohl wichtigste wissenschaftliche Punkt ist natürlich, dass dieser Beweis (oder die Widerlegung der Vermutung) ein Test unseres mathematischen Verständnis darstellt. Denn die Collatz Funktion ist denkbar einfach, also sollte es doch ein Klacks sein, diese Vermutung zu lösen. Dem ist aber nicht so.
Brute Force – wenn man nicht weiter weiss, probiert man einfach aus
Ein Ansatz, der mithilfe von Computern verfolgt wurde war, Zahlen einfach der Reihe nach zu testen. Dies wurde mit Hilfe von PCs, die Leute in ihrer Freizeit zur Verfügung gestellt haben, ausprobiert (im englischen nennt man dies Citizen Science). Das ist der wohl simpelste Ansatz, aber natürlich kann man nicht unendlich viele Zahlen testen. Aber immerhin, für die ersten 10 hoch 20 Zahlen, das sind hundert Trillionen oder 100’000’000’000’000’000’000 ausgeschrieben fand man keine Abweichung. Jede einzelne dieser Zahlen endete schlussendlich in der 4-2-1-4 Schleife, ganz so, wie es die Collatz Vermutung vermutet. Aber um die Collatz Vermutung zu widerlegen, genügt ein einziges Gegenbeispiel, welches nicht in dieser Schleife endet. Und obwohl hundert Trillionen eine ganze Menge Zahlen darstellt, gibt es noch unendlich weitere Zahlen, die nicht getestet wurden.
Hilfe aus der Statistik
Ein anderen Ansatz eines (Teil-)Beweises kommt aus der Statistik. Darin betrachtet man sich, welche Zahlen man generell erwartet, wenn man die Collatz Funktion genügend oft anwendet. Das Argument lautet wie folgt. Ist die Zahl gerade, dann wird ihr Funktionswert kleiner, man teilt ja durch zwei. Und das ist genau dass, was man will: die Folge muss so klein werden, dass sie in die 4-2-1-4 Schleife abdriftet. Nun sind aber die Hälfte der Zahlen nicht gerade, sondern ungerade. Was passiert bei denen? Die werden ja mit 3n+1 grösser. Dabei besteht aber eine 50 Prozent Chance, dass das Resultat gerade wird. Ein Beispiel: Die Zahl n=13 wird Col(13)=3*13+1=40. Diese wird dann durch zwei geteilt, also hat man (3n+1)/2=20. Auch hier gibt es wieder ein 50 Prozent Chance, dass das Resultat gerade wird, also gibt das (3n+1)/4=10.
Statistisch gesehen ist die Wahrscheinlichkeit gross, dass die Zahl nach einer gewissen Zeit kleiner wird, als sie ursprünglich war. Man kann zeigen, dass dies für fast alle Zahlen gilt. Das Problem ist dabei wieder, dass fast alle Zahlen eben nicht alle Zahlen sind, und somit durchaus Ausnahmefälle exisitieren können.
Eine Problem ohne Aussicht auf Lösung
Tao selbst hat einen Ansatz gewählt, der aus der Differenzialrechnung kommt. Nachzulesen ist dies in einem kürzlich erschienen Artikel im Spektrum. Aber auch dieser Ansatz gilt eben nicht für alle Zahlen. Tao kommentierte sein Ergebnis während seines Vortrags zwar als interessant, aber er selbst denke nicht, dass es den Weg zur Lösung der Collatz Vermutung darstellt. Auch Paul Erdös, eine Ikone der Mathematik, bezeichnete die Collatz Vermutung als fast unlösbar.
Während des Vortrages stellte Tao noch eine Verschwörungstheorie in den Raum. Nachdem der japanische Mathematiker Shizuo Kakutani an der Yale University und der University of Chicago über die Collatz Vermutung einen Vortrag hielt, verschwendeten amerikanische Mathematiker*Innen monatelang ihre Zeit an dem Problem… Ohne Erfolg. Und dieses Phänomen wiederholt sich ständig. Deshalb steht die Verschwörung im Raum, dass die Collatz Vermutung in die USA eingeführt wurde, damit der Fortschritt in der amerikanischen Mathematik gebremst wird. Und dank Tao wurde die Collatz Verschwörung nun in Europa eingeführt.
Ich denke, die Formel für ungerade Zahlen kann durchaus erweitert werden:
Col(n) = (2k+1)n +1,
wobei k und n natürliche Zahlen sind. D.h., es darf nicht nur ungerade Zahl “3” sein, sondern beliebige ungerade Zahlen.
Ich habe mit Phython versucht … Doch geht nicht. Die Zahl “3” ist schon die Grenze.
Die Collatz-Vermutung ist auch als Ulam-Folge bekannt, nach dem Mathematiker Stanislaw Ulam (*1909 Lemberg, +1984 USA). Man kann zeigen, dass der Algorithmus notwendig mit 1 endet, sofern er nicht in einen unendlichen Zyklus läuft. Letzteres bliebe noch zu beweisen. Ein Profi könnte das schaffen.
Übrigens, die Variante 3n-1 würde nicht funktionieren.
Hast du eine Quelle, in der gezeigt wird, dass es keinen Startwert gibt, für den die Folge bestimmt gegen unendlich divergiert?
Das ist der einfache Teil
– Die Quadratzahlen sind die Ausstiegsstelle, von dort landet man direkt bei 1, 2, 4
– Alle ungeraden Startzahlen landen nach Anwendung des ersten Schrittes bei einem geraden Zwischenergebnis, somit genügt es alle geraden Startzahlen zu betrachten.
– Alle Startzahlen/Zwischenergebnisse die Vielfache von 4 sind, lassen sich mindestens zweimal durch 2 teilen und man landet dann bei einem Zwischenergebnis, welches niedriger als der Start/Zwischenwert davor ist.
Startwerte die Vielfache von 4 sind kann man also ausschließen.
– Alle geraden Startwerte der Reihe 2 hoch a mal b + (2 hoch a-1) -2) für b von 0
bis Unendlich führen nach Anwendung von 2 mal a -4 Schritten zu einem Zwischenergebnis welches durch 4 teilbar ist.
Beispiele:
– für a = 3 (8*b+2) ist die Reihe (2), 10, 18, 26, 34, … führt nach 2 Anwendungen zu einem Vielfachen von 4
– für a = 4 (16*b+6) ist die Reihe 6, 22, 38, 54, 70, … führt nach 4 Anwendungen zu einem Vielfachen von 4
– für a = 5 (32*b+14) ist die Reihe 14, 46, 78, 110, 142, … führt nach 6 Anwendungen zu einem Vielfachen von 4
– für a = 6 (64*b+30) ist die Reihe 30, 94, 158, 222, 286, … führt nach 8 Anwendungen zu einem Vielfachen von 4
…
– damit halbiert man nach jeder Reihe die Zahl der noch zu betrachtenden geraden Startwerte, dass macht man einfach unendlich oft und weiß damit, dass die alle bei Vielfachen von 4 ankommen und damit wieder kleiner werden.
– Blöderweise springen die dann anschließend folgenden Zwischenergebnisse aber munter zwischen diesen Reihen hin und her, so dass zu zeigen, dass es da keinen unendlichen Zirkel geben kann, der doch auf etwas anderes als auf 1, 2, 4 hinausläuft, dann nicht so einfach ist.
„Die Collatz-Vermutung ist auch als Ulam-Folge bekannt“
Komisch, zur Ulam-Folge finde ich im Internet nur something complete different.
Mit etwas Geduld habe ich nun sogar noch mehr veraltete Namen für das gleiche Problem gefunden.
Wahrscheinlich ist die Collatz Funktion gar kein algebraisches Problem.
Es geht um die Struktur des Zahlenraumes.
Genau so sind die Sudokus nicht nur eine algebraisches Aufgabe, weil ja die Zahlen durch Farben, Buchstaben oder Sonstiges ersetzt werden können.
Also, das Verständnis der Collatz Funktion erfordert ein Umdenken .
Als “normaler Mensch” würde ich sagen, dass es nur zwei Arten von Zahlen gibt: gerade und ungerade, und die verhalten sich immer gleich: ungerade Zahl x ungerade Zahl ergibt immer ungerade Zahl, ungerade Zahl +1 ergibt immer gerade Zahl. 1 ist die kleinste ungerade Zahl, 4 ist die kleinste (gerade) Zahl, die man mit 3 x ungerade Zahl + 1 erhalten kann.
Ja, es gibt einen Konsensus unter Mathematikern, dass das Collatz-Problem mit heutigen Mitteln nicht gelöst werden kann – wie viele andere zahlentheoretische Probleme übrigens.
friesenjung,
Die collatz Folge ist nicht normal.
bei einer Startzahl von 26 erreicht man nach 10 Zahlen wieder die 1.
26,13,40,20,10,5,16,8,4,2,1. Die höchste Zahl ist dabei 40. Es sind 7 gerade Zahlen dabei !
Nimmt man aber stattdessen 27 als Startzahl, dann benötigt man 111 Schritte und die höchste Zahl ist dabei 9332,
27, 82, 41, 124, 62, 31, 94, ………………….
Bei 28 als Startzahl braucht man 18 Schritte und die höchste Zahl dabei ist 52. Es sind 13 gerade Zahlen dabei.
28, 14, 7, 22, 11,34, 17, 52, 26, 13, 40, 20, 10 ,5 , 16, 8, 4, 2, 1
Die Verteilung von gerade und ungerade ist das Seltsame dabei.
die höchste “exakt” überprüfte Zahl ist wohl 1 152 921 504 606 846 976 vom Apr2019
„vom Apr2019“
Anfang April?
Vor etlichen Jahren habe ich mich schon damit beschäftigt und dabei eine kleine Spielerei ausgedacht:
3n +1 = 2n + 1 + n
In der binären Darstellung hängt man also an n eine 1 hinten (rechtes Ende) dran und addiert n dazu. Dann streicht man von hinten alle Nullen weg bis zu einer 1, entsprechend der Division durch 2ⁱ. Dann macht man mit dem erhaltenen n weiter.
Das dekadische Zahlensystem ist kein orthodoxer Zwang. Man könnte es in diesem Fall auch mit dem trinären System versuchen. Allerdings führt die Methode im Beweisverfahren sehr wahrscheinlich nicht weiter.
Das Collatz-Problem ist nur eines von vielen zahlentheoretischen Problemen, deren Lösung Mathematik voraussetzt, die über alles schon vorhandene, bekannte hinausgeht. Andere Beispiele finden sich bei den Primzahlen, also den Grundelementen der Zahlen, sind Primzahlen doch der Kern des Fundamentalsatzes der Algebra (Existenz der Primfaktorzerlegung für jede natürliche Zahl und deren Eindeutigkeit).
Gerade wurde auf Quantamagazine der Artikel Mathematicians Discover Prime Conspiracy veröffentlicht, der sich mit der Entdeckung beschäftigt, dass aufeinanderfolgende Primzahlen “verschworen” sind, denn die letzte Ziffer der zweiten Primzahl des Folgepaares ist nicht zufällig verteilt, sondern es gilt beispielsweise, dass eine Primzahl, die mit der Ziffer 3 endet bevorzugt von einer Primzahl gefolgt wird, deren letzte Ziffer in 9 endet – dabei würde man doch erwarten, dass jede der Ziffern 1,3,7 und 9 gleich wahrscheinlich sein sollte.
Für mich stellt sich die Frage: Kann sich die Mathematik so weiterentwickeln, dass irgendwann alle zahlentheoretischen Probleme gelöst werden. Und als Nachfolgefrage kommt dann: Ist auch in der Mathematik eine grosse Vereinheitlichung möglich? Gibt es also irgendwann ein mathematisches Objekt, das alle Fragen der Zahlentheorie löst?
Ein ja, würde für mich bedeuten, dass diese Welt vollkommen “entschlüsselt” werden kann, ein Nein aber bedeutet für mich, dass Mathematik für alle Ewigkeit eine Herausforderung sein wird an der die meisten scheitern – selbst die allergrössten Geister . Ist Scheitern also (nur) menschlich oder ist es unabwendbar (so unabwendbar wie der Tod (doch ist dieser unabwendbar?)).
@H.Wied
Danke für den Hinweis!
A.Reutlinger,
wenn man nicht unterscheidet zwischen gerade und ungerade, dann erkennt man, dass mit den Beiden Operatoren x 3 + 1 und : 2 alle Zahlen abgedeckt werden.
Dazu betrachten wir die Zahlen isoliert, also nicht in einer Kollatz Folge.
Aus 1 wird ( 0 / 2 ) weil 0 x 3 + 1 = 1 und 2 : 2 = 1
Aus 4 wird (1 / 8) weil 1 x 3 +1 = 4 und 8 : 2 = 4
Damit ergibt sich ein Baum, ein B – Tree, der alle Zahlen beinhaltet , ohne die Reihenfolge von Kollatz zu beachten. Es geht ja um die Struktur des Zahlenraumes.
Aus der 5 folgt die 10 oder die 32,
Aus der 10 folgt die 3 oder die 20
Aus der 32 folgt die 16 oder die 97
Dieser Zahlenbaum (Tree) enthält alle Zahlen ohne Lücken und er gabelt sich bei jeder Zahl in zwei Möglickeiten.
Nur mal als Anregung !
Gute Anregung! Dahinter steht ein Gesetz: Der Algorithmus der Collatz-Vermutung verwandelt jede natürliche Zahl in ein Produkt einer Potenz von 2 und einer natürlichen Zahl. Das heißt doch, dass dieser Algorithmus lediglich allen natürlichen Zahlen eine andere Reihenfolge aufdrängt, aber die Wohlordnung der natürlichen Zahlen natürlich nicht ändert. Da nun die andere Reihenfolge an diese Wohlordnung gebunden ist, enthält ihre Logik die Rückführung jeder natürlichen Zahl zu der 1. Somit ist der Beweis gegeben.
@anton reutlinger
Alles endet in einer Schleife, history repeats itself, hier ist der Beweis.
Collatz, das Halteproblem und Fragen der Entscheidbarkeit
Wenn die Collatz-Vermutung , dass die Funktion
bei wiederholter Anwendung immer irgendwann 1 als Resultat zurückgibt, dann hält der folgende Algorithmus:
, im anderen Fall (wenn die Collatz-Vermutung nicht stimmt) bleiben wir für immer in der Schleife und der Algorithmus hält nicht. Nun könnte man meinen – und Hilbert glaubte noch daran – dass die Collatz-Vermutung entweder gilt oder aber, dass sie nicht gilt. Doch heute wissen wir, dass es noch eine dritte Möglichkeit gibt: es könnte auch sein, dass die Collatz-Vermutung weder beweisbar noch widerlegbar ist.
Nehmen wir einmal an, die Collatz-Vermutung treffe zu. Das würde bedeuten, dass der oben angegebene Algorithmus immer anhalten und ein Resultat zurückgeben würde. In der Terminologie der Informatik würde man in diesem Falle sagen, das Collatz-Problem sei entscheidbar. Im ungekehrten Falle wäre das Collatz-Problem nicht entscheidbar.
Interessanterweise können gewisse zahlentheoretische Probleme algorithmisch entschieden werden (es kommt immer ein Resultat zurück) obwohl sie nicht gelöst wurden, also nicht bewiesen wurden. Dazu gehört das Goldbach-Problem, also die unbewiesene Vermutung, dass jede gerade Zahl als Summe von 2 Primzahlen angegeben werden kann. Diese unbewiesene Behauptung ist mit folgendem Algorithmus entscheidbar:
Die Goldbach-Vermutung ist also algorithmisch für eine bestimmte Eingabe entscheidbar, nicht aber die Collatz-Vermutung. Unbewiesen sind beide.
MH,
Der Knackpunkt bei der Collatz Folge sind die Begriffe gerade und ungerade. Obwohl jeder versteht, was gemeint ist, sind diese Begriffe im Zahlenraum nicht definiert. Ein Programmierer muss sich schon Tricks einfallen lassen, um dem Programm klar zu machen, was der Unterschied ist.
Ersetzen wir doch einmal die Zahlen durch Buchstaben. z. B. 11 = Elf. Woran erkennen wir bei der Buchstabenschreibweise, ob die Zahl gerade oder ungerade ist. ?
Da liegt der Hund begraben.
@H.Wied
Eine Zahl n ist gerade wenn gilt: n mod 2 = 0.
Oder im Binärformat: wenn die letzte Ziffer eine 0 ist.
“Nun sind aber die Hälfte der Zahlen nicht gerade, sondern ungerade. Was passiert bei denen? Die werden ja mit 3n+1 grösser. Dabei besteht aber eine 50 Prozent Chance, dass das Resultat gerade wird. ”
Nein, die Chance in diesem Schritt ist 100% – wenn n ungerade ist, ist 3n auch ungerade, also 3n+1 gerade. Es kommt also nach jeder ungeraden Zahl mindestens eine gerade Zahl.
Man könnte die Collatzfunktion für ungerades n somit auch als Col(n)=(3n+1)/2 definieren, indem man zwei Schritte zu einem zusammenfasst. Erst für (3n+1)/2 (was immer noch größer als n ist) ist es nicht a priori klar, ob dies gerade oder ungerade ist, und heuristisch würde man von einer 50%-Chance für beides ausgehen.