facebook   Besuchen Sie uns bitte auf facebook

Die "(3n+1)-Vermutung"

Auf den deutschen Mathematiker Lothar Collatz (1910 - 1990) (siehe auch Seite "Jahreszahl 2010") geht folgendes Problem zurück:

Neu (Juni 2011): Berechnung von Folgen mit ci+1 = 3 · ci + m, wenn ci ungerade ist.
Eine Folge natürlicher Zahlen wird gestartet mit einer beliebigen natürlichen Zahl c0. Ein beliebiges Element ci+1 der Folge errechnet sich aus seinem Vorgänger nach
  • ci+1 = c/2, wenn ci gerade ist bzw.
  • ci+1 = 3 · ci + 1, wenn ci ungerade ist.
Collatzsche Vermutung: Diese Folgen enden bei beliebigem Startwert mit der Sequenz   ..., 4, 2, 1 (und diese Sequenz würde sich bei weiterer Rechnung natürlich immer wiederholen).

Beispiel: Mit dem Startwert c0 = 11 erhält man die Folge

11,  34,  17,  52,  26,  13,  40,  20,  10,  5,  16,  8,  4,  2,  1.

Es ist nicht ganz klar, wann L. Collatz diese Vermutung erstmals ausgesprochen hat, mit ziemlicher Sicherheit war es in den 30er Jahren des vorigen Jahrhunderts. Sie ist bisher weder bewiesen noch widerlegt. Umso erstaunlicher ist die Formulierung dieser Vermutung zu einer Zeit, als man das nicht mal eben mit einem kleinen Script für einige Millionen Startwerte ausprobieren konnte. Für die Handrechnung artet ein Test sehr schnell in Arbeit aus (für den Startwert 27 z. B. hat die Folge 112 Glieder, für den Startwert 626331 sind es 509 Glieder, man kann das alles mit dem folgenden Script probieren).

Natürlich hat dieses Problem viele Programmierer gereizt, und man findet im Web weltweit verteilte Gruppen (siehe "Delay Records"), die mit dezentraler Rechnerleistung alles ausloten, was an diesem Problem interessant sein kann. Je mehr Startzahlen probiert wurden, desto eher darf man annehmen, dass die Collatzsche Vermutung richtig ist, aber ein Beweis ist auf diesem Wege natürlich nicht zu führen.

Erzeugen einer Collatz-Folge

zur "(3n+1)-Vermutung"

Bitte Anfangswert (positive ganze Zahl) eingeben, danach OK anklicken:

   
Ergebnisausgabe ... kompakt in das weiße Feld
... ohne Collatz-Folge (nur Eigenschaften der Folge)
... erweitert (Zusatzinformationen und jedes Element in eine neue Zeile)
 
 

Reaktionen von Besuchern dieser Seite

Diese Seite wurde im Januar 2010 erstmals veröffentlicht und hat zu sehr vielen (ausschließlich freundlichen) Reaktionen von Besuchern geführt. Besonders nach einer Erwähnung in einem Artikel auf "Heise online" anlässlich des 100. Geburtstages von Lothar Collatz und noch einmal nach einem Bericht in Spiegel "online" über einen Beweis zur Collatzschen Vermutung haben sich zahlreiche Besucher dieser Seite gemeldet. Den Autor der Seite hat es besonders gefreut, dass viele Besucher geschrieben haben, dass sie keine Mathematiker sind und dass ihnen trotzdem die Beschäftigung mit diesem Problem viel Spaß gemacht hat. Deshalb werden nachfolgend exemplarisch einige Reaktion publiziert:

"Delay Records"

Die Rekordjäger nach den so genannten "Delay Records" (die gibt es tatsächlich und nicht nur einmal, siehe zum Beispiel 3x+1 Delay Records oder das BOINC-Projekt Collatz Conjecture) haben den Rekord-Begriff schärfer definiert: Als Rekord-Startzahl wird nur anerkannt, wenn bewiesen ist, dass alle kleineren Startzahlen kürzere Folgen liefern. Das BOINC-Projekt meldete im Dezember 2010 die Startzahl 2367363789863971985761, die in diesem Sinne eine Rekordzahl ist. Das oben angegebene Script liefert damit eine Folge mit 2652 Elementen.

Und nach dieser Definition scheiden auch alle Zweierpotenzen als Startzahlen aus der Konkurrenz aus, denn eine einfache Überlegung ergibt, dass es zu jeder Startzahl 2n eine kleinere Startzahl gibt, die eine um mindestens ein Element längere Folge liefert:

Weil 2n garantiert nicht durch 3 teilbar ist, muss entweder eine der beiden ungeraden Zahlen 2n−1 oder 2n+1 durch 3 teilbar sein. Wenn es 2n−1 ist, dann gibt es eine (ungerade) Startzahl m1=(2n−1)/3, für die mit der Collatz-Vorschrift 3m1+1=2n entsteht und somit eine Collatzfolge liefert, die um ein Element länger ist.

Wenn dagegen 2n+1 durch 3 teilbar ist, dann ist auch der doppelte Wert (2n+1)·2 = 2n+1+2 durch 3 teilbar. Weil dann 2n+1+1 und 2n+1 ohnehin nicht durch 3 teilbar sind, muss 2n+1−1 durch 3 teilbar sein, und es gibt mit m2=(2n+1−1)/3 wieder eine Startzahl, die im ersten Collatz-Schritt auf 2n+1 und im zweiten Schritt auf 2n führt. Weil m2=(2n+1−1)/3 = 2n·2/3−1/3 < 2n gilt, gibt es also in jedem Fall zu einer Zweierpotenz 2n eine kleinere Startzahl, die eine längere Collatz-Folge liefert.

Beweis gefunden?

Am 5. Juni 2011 meldete Spiegel online: "Die Collatz-Vermutung ist etwa 60 Jahre alt - ein Hamburger Mathematiker könnte sie nun bewiesen haben. Prof. Gerhard Opfer hat den von ihm gefundenen Beweis beim Fachblatt 'Mathematics of Computation' eingereicht. Ein Preprint ist online verfügbar." Mit der üblichen Vorsicht des seriösen Wissenschaftlers wurde Gerhard Opfer mit den Worten zitiert: "Ich würde erst sagen, dass es stimmt, wenn es begutachtet ist."

Der Autor dieser Seite schrieb seinerzeit dazu: "Die Sensation steckt schon in den letzten fünf Worten des Abstracts: '... the Collatz conjecture is true'. Das Collatz-Problem ist so populär, dass man wohl davon ausgehen kann, dass die besten Mathematiker der Welt sich daran machen werden, das Haar in der (Beweis-)Suppe zu finden."

Das Haar scheint gefunden zu sein. Im Preprint steht seit dem 17. Juni 2011 jetzt eine "Author's note": "… the statement 'that the collatz conjecture is true' has to be withdrawn, at least temporarily." (siehe auch: Spiegel online).

Schade, aber als Trost mag gelten, womit Gerhard Opfer selbst in "Spiegel online" vom 5. Juni 2011 zitiert wird: "Die Collatz-Vermutung hat eine Vielzahl von Arbeiten ausgelöst. Es wäre eigentlich schade, wenn sie jetzt bewiesen ist, denn dann wäre es damit ja vorbei."



Modifikationen des Collatz-Problems

"(3n−1)-Folge"

Es gibt einige sehr interessante Modifikationen des Collatz-Problems, z. B. die Erweiterung auf negative Startzahlen. Dann entstehen natürlich nur negative Zahlen, aber ganz andere Folgen, weil sich das Addieren der 1 nach der Verdreifachung entsprechend anders auswirkt. Praktisch gleichwertig damit ist die folgende kleine Änderung, die dafür sorgt, dass nach wie vor positive Zahlen entstehen:

Eine Folge natürlicher Zahlen wird gestartet mit einer beliebigen natürlichen Zahl c0. Ein beliebiges Element ci+1 der Folge errechnet sich aus seinem Vorgänger nach
  • ci+1 = c/2, wenn ci gerade ist bzw.
  • ci+1 = 3 · ci − 1, wenn ci ungerade ist.
Diese Folgen enden bei beliebigem Startwert in einer der drei folgenden Sequenzen:
  • 2, 1  oder
  • 5, 14, 7,  20,  10  oder
  • 17, 50, 25, 74, 37, 110, 55, 164, 82, 41, 122, 61, 182, 91, 272, 136, 
    68, 34.

Es ist leicht einzusehen, dass nach Erreichen einer dieser Sequenzen bei weiterer Rechnung eine ständige Wiederholung entsteht, weil die erste Zahl der Sequenz der halbe Wert der jeweils letzten (geraden) Zahl ist. Das nebenstehende Script berechnet solche Folgen.

Erzeugen einer "(3n−1)-Folge"

Bitte Anfangswert (positive ganze Zahl) eingeben, danach OK anklicken:

   

Die zugehörige modifizierte Collatzfolge hat

Elemente und endet mit der Sequenz:

Dies ist die Folge:

Man probiere zum Beispiel als Anfangswerte die 6 oder die 13 oder die 31, die jeweils zu unterschiedlichen Sequenzen am Ende der Folge führen.