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 =
ci /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:
- Länge der Folge:
Dass größere Startzahlen längere Folgen liefern, stimmt nur
bedingt. Aber für den Versuch, Startzahlen für lange
Folgen zu finden, bietet das Script natürlich die ideale
Spielweise (siehe
"Reaktionen von Besuchern dieser Seite").
Als "Delay Record" (Startzahl, die eine besonders lange Collatz-Folge
liefert) gilt gegenwärtig (Juni 2011) wohl die Startzahl
2367363789863971985761, die eine Collatz-Folge mit 2652 Elementen liefert
(kann mit dem Script schnell nachgeprüft werden).
Der Begriff
"Rekord" bedarf allerdings einer genaueren Definition, siehe
"Delay Records", und die nachfolgend
zusammengestellten interessanten Startzahlen von Besuchern
dieser Seite sind in diesem
Sinne keine "Rekorde".
- Größtes Element der Folge:
Mit größeren Startzahlen ergeben sich in der Regel
auch größere Elemente der Folge. Interessant ist deshalb
das Verhältnis des größten Elements zum
Startelement (wie weit entfernt sich die Folge "nach oben"
vom Startelement?). Die Startzahl c0 = 27 bringt
es mit c77 = 9232 immerhin
auf fast das 342-fache. Für die auf
3x+1 Delay Records zu
findende Startzahl c0 = 1980976057694848447
zeigt das oben zu sehende Script als c690 ein Element,
das den Startwert um mehr als das 1019-fache übersteigt.
- Lange Folge bei kleiner Startzahl:
Die Länge der Folge kann auch dann sehr groß werden, wenn
sich das größte Element nicht sehr weit vom Startelement
entfernt. Solche Folgen "treten in weiten Bereichen auf der Stelle".
Deshalb ist auch das Verhältnis der Anzahl der Elemente der Folge
zur Anzahl der Ziffern der Startzahl interessant. Die
zweiziffrige Startzahl 27
bringt es hier bei 112 Elementen der Collatz-Folge
auf den beachtlichen Wert 56, die 22-ziffrige Startzahl
7219136416377236271195 (Quelle:
"On the 3x + 1 problem")
sogar auf den Wert 135.
Noch etwas aussagekräftiger
wird diese Eigenschaft dargestellt, wenn man die Länge der
Folge durch den dekadischen Logarithmus der Startzahl dividiert,
der neben der Stellenanzahl auch die Größe der
Zahl berücksichtigt. Das oben zu sehende Script weist
im erweiterten Ausgabemodus beide Werte aus.
- Vorhersage der Folgenlänge:
Weil bei beliebiger Startzahl alle Folgen bei 1 enden, muss
"im Mittel" von Element zu Element eine Abnahme eintreten,
die allerdings von der Startzahl abhängt.
Deren Kenntnis würde die Vorhersage der Länge der Folge
ermöglichen. Eine einfache Formel zur Schätzung der
stochastisch zu erwartenden Elementanzahl ist
En = 3·log4/3c0 (mit dem Logarithmus zur Basis 4/3 von der Startzahl),
die bei großen Startzahlen in der Regel erstaunlich
gute Voraussagen der Länge der Folge liefert. Aber auch diese
schöne Formel weicht bei einigen speziellen Startwerten
doch erheblich von der tatsächlichen Länge
der Folge ab, wie zum Beispiel für
7219136416377236271195.
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:
- Natürlich lassen sich mit einfachen Strategien Startzahlen
finden, die Collatz-Folgen mit beliebig vielen Elementen liefern.
Karl Hovekamp
lieferte den
Hinweis, dass natürlich alle Zweier-Potenzen 2n
als Startzahlen
Collatz-Folgen mit n+1 Elementen und damit beliebig lange
Folgen liefern (siehe dazu die Betrachtung unter
"Delay Records").
- Prof. Dr. Gerhard Opfer
von der Universität Hamburg schrieb im Juli 2010: "Durch einen
Zufall (Heise online berichtete) habe ich Ihre sehr schöne Seite,
die bei Heise zitiert wurde, gesehen. Ich habe selbst schon mal
vor längerer Zeit für etliche größere Zahlen
(etwa 22-stellig)
die Länge der Collatz-Folge bestimmt und habe dabei festgestellt,
dass sich die berechneten Längen auf wenige Zahlen
konzentrieren und dass man eine gewisse
Häufigkeitsverteilung feststellen kann.
Nachdem ich selbst mit etlichen
größeren Zahlen
experimentiert habe, bin ich mittlerweile der Meinung, dass man dabei
wenig gewinnen kann.
Erstaunlich ist nur, dass man auch bei großen Zahlen immer schnell zu
einem Ergebnis kommt.
Das sieht man ja auch an Ihrem Programm. Auch lange Zahlen bringen es
nicht in
Verlegenheit."
- Andreas Welzien lieferte mit
4678569684640115198788879879891134694131654641135698443131649876871351354984987413213
eine Riesen-Startzahl, mit der das Script eine Collatz-Folge
mit 2216 Elementen liefert.
- Mario Palestini
lieferte die Information, dass die ersten 100 Nachkommastellen
von π als Startzahl eine Folge mit 2533 Elementen liefert.
Es stimmt, wie man leicht nachprüfen kann, wenn man die
Startzahl
1415926535897932384626433832795028841971693993751058209749445923078164062862089986280348253421170679
mit "Cut and paste" in das Eingabefeld des Scripts überträgt.
- Marius Deutschmann hat die Nachkommastellen
von π
systematisch untersucht und die Sequenz
2384626433832795028841971693993751058209749445923078164062862089986280348253421170679821480865
gefunden, die als Startzahl eine Collatz-Folge mit
3098 Elementen liefert.
- Offensichtlich sind die Ziffernfolgen transzendenter Zahlen
interessante Objekte für Versuche. Mario Palestini
liefert die Information, dass die ersten 285 Nachkommastellen
der Eulerschen Zahl e
71828182845904523536028747135266249775724709369995957496696762772407663035354759457138217852516
64274274663919320030599218174135966290435729003342952605956307381323286279434907632338298807531
95251019011573834187930702154089149934884167509244761460668082264800168477411853742345442437107
eine Collatzfolge mit 7210 Elementen liefert.
- Sam Jongman macht darauf aufmerksam, dass auch das so genannte
"196-er Problem"
interessante Startzahlen liefert, zum Beispiel entsteht nach
300 Inversionen der Zahl 196:
1750793305108461108296695255897595811480440836557620422289738445555
545534946981225126744738044974228585887562506602702253911502307957
Diese Startzahl liefert eine Collatz-Folge mit
2979 Elementen.
- Auch Ralf Tyburski liefert mit
88888888888888888888888888888888888888888888888888888888888888888888888888888888888
888888888888888888888888888888888888888888888888888888888888888888888888888888888888
eine schöne Startzahl, die auf eine Collatz-Folge mit
4234 Elementen führt.
- Arnold Thielmann aus Asunción (Paraguay), der sich ausrücklich
als "absoluter Laie in mathematischen Angelegenheiten" vorstellte,
lieferte die hübsche Zahl
17171717171717171717171717171717171717171717171717171717171717171717171717
mit dem Hinweis, dass sie zwar eine nicht ganz so lange Collatz-Folge
liefert wie andere hier aufgeführte Startzahlen, aber dafür
deutlich weniger Ziffern habe. Rekordverdächtig in dieser
Hinsicht ist diese Zahl allerdings nicht. Schon die Startzahl 27
hat ein deutlich gößeres Verhältnis von
Folgenlänge zu Ziffernanzahl der Startzahl. Der Hinweis von
Herrn Thielmann hat immerhin dazu geführt, dass der Autor dieser
Seite diesen Wert in der erweiterten Ausgabe des Scripts
ergänzt hat.
- Prof. Dr. Ingo Althöfer von der Universität Jena
schrieb: "Durch einen Beitrag im Spiegel-Online-Forum bin ich auf Ihre
sehr schöne interaktive Webseite zum Collatz-Problem gestossen.
Aus Spass habe ich im Eingabefenster mal eine Folge aus ganz vielen Einsen
eingegeben (111111111111111111....1111111111111). Ihr Collatz-Berechner
spuckte dann eine Länge von 4829 aus. Leider konnte ich im Fenster
dann nicht mehr ermitteln, wieviele Einsen die Zahl genau hatte.
Dies war der Anlass für den Einbau der Informationen über
die Ziffernanzahl. Neben vielen anderen Informationen lieferte
Prof. Althöfer die gewissermaßen als Nebenprodukt angefallene
Startzahl 1111...111 mit 997 Ziffern, die eine Collatz-Folge
mit 25202 Elementen liefert.
- Beeindruckende (teilweise einfach "schöne")
Startzahlen und sehr wirksame Möglichkeiten,
die korrekte Arbeit des Scripts zu überprüfen, allerdings
natürlich keine Rekorde im Sinne der nachfolgend definierten
"Delay Records"!
"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 = ci /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:
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.