Über die Struktur und das Wachstumsverhalten von Collatz 3n + 1 Folgen.
Mein Artikel ist in erster Linie eine Analyse und zeigt ein paar neue Ergebnisse, Einsichten und Ideen zur Behandlung des Themas. Hier zunächst nur die ersten Seiten um sich einen Überblick verschaffen zu können. Der vollständige Artikel ist in LaTeX gesetzt und kann als PDF Version runtergeladen werden. Leider kann man den LaTeX-Code nicht 1 zu 1 auf dem MP posten.
Wer noch nie etwas von dem berühmten Collatz-Problem gehört hat, den bitte ich zuerst unter den folgenden Links nachzusehen (Wikipedia, Das Collatz–Problem). Für das mathematische Verständnis meines Artikels sind diese Einführungen jedoch nicht nötig.
Abstract
Die zahlentheoretische Funktion für gerade und für ungerade generiert für jede Startzahl eine Collatz-Folge . Eine kann nur zwei mögliche Formen annehmen. Entweder sie gerät in einen Zyklus oder sie wächst ins Unendliche. Das kleinste für das
1. Einleitung
2. Die Collatz 3n + 1 Funktion
3. Die Restklassen modulo
4. Endliche Teilfolgen
4.1 Die Teilfolgen der Restklassen
4.2 Die Teilfolgen der Restklasse
5. Anzahl der Folgenglieder
5.1 Die Anzahl der Folgenglieder der
5.2 Die Anzahl der Folgenglieder der
6. Stoppzeit
6.1 Die Stoppzeit
6.2 Eine Stoppzeit-Term-Formel für ungerade
6.3 Die Teilfolgen-Stoppzeit
7. Grenzwerte und asymptotische Dichten
7.1 Die Teilfolgen mit
7.2 Die Teilfolgen mit
8. Konsequenzen für unendliches Wachstum
8.1 Allgemeines zur Stoppzeit
8.2 Bedeutung der Grenzwerte
8.3 Wachstum und Zusammenbruch einer Collatz-Folge
8.4 Abschließende Beispiele
9. Quellenangaben
10. Erklärung der Selbstständigkeit
11. Anhänge
11.1 Die ersten Teilfolgen
11.2 Die ersten Teilfolgen
11.3 Die ersten Perioden und Teilperioden der
11.4 Die ersten Perioden und Teilperioden der
11.5 Die ersten Restklassen modulo
11.6 Die ersten Restklassen modulo für
11.7 Zwei Algorithmen zur Generierung der Zahlen
1. Einleitung
Schaut man sich die Entwicklung verschiedener Collatz-Folgen an, so gewinnt man schnell den Eindruck, dass hier pures Chaos am Werk ist. Ein Eindruck, der nicht täuscht. Günther Wirsching, ein internationaler Experte für dieses Thema, schreibt dazu: "Die mathematischen Schwierigkeiten bei der Untersuchung der Dynamik von 3n + 1 Iterationen scheinen damit zusammenzuhängen, dass wir es mit einem deterministischen Prozess zu tun haben, der stochastisches Verhalten simuliert. Das verbindet die Sache mit der mathematischen Behandlung des Chaos."[8]
Indem man eine Collatz-Folge in endliche Teilfolgen unterteilt kann man ein wenig Ordnung in ihr dynamisches Verhalten bringen.
Soll eine Collatz-Folge unendlich wachsen, muss sie irgendwann auf eine Zahl der Restklasse 3 mod 4 treffen. Von dort an besteht sie nur noch aus endlichen Teilfolgen mit Startzahlen der Restklassen 3,7 mod 12. Nimmt man jetzt eine Liste dieser Teilfolgen, dann muss die unendlich wachsende Collatz-Folge die Teilfolgen dieser Liste durchlaufen - nicht alle, aber jede nur einmal. Das geschieht in der Regel chaotisch, sie springt also mal vor und zurück. Doch tendenziell wird sie sich immer weiter nach oben durch die Liste entwickeln.
Nun lässt sich folgendes zeigen: Die Teilfolgen dieser Liste sind ihrer Länge (Gliederzahl) nach nicht chaotisch verteilt, sondern folgen einem strengen Muster basierend auf der Fibonacci-Folge. Statistisch besitzen zwei von drei dieser Teilfolgen endliche Stoppzeit (Stoppzeitfolgen). Dies führt dazu, dass jede Collatz-Folge irgendwann eine Serie dicht aufeinanderfolgender längerer Stoppzeitfolgen durchlaufen muss, was ihr Wachstum schließlich zusammenbrechen lässt.
Das eine Collatz-Folge nicht endlos wachsen kann ist jedoch noch kein Beleg dafür, dass sie immer in dem Zyklus (2,1) endet. Es besteht weiterhin die Möglichkeit der Existenz mindestens eines weiteren Zyklus, welcher nach heutigem Kenntnisstand aus vielen Milliarden Zahlen bestehen müsste.[5]
2. Die Collatz 3n + 1 Funktion
Die Collatz Funktion sei definiert als eine Abbildung gegeben durch
Sei und für . Dann ist die Collatz-Folge für gegeben durch .
Zum Beispiel ergibt die Startzahl die Collatz-Folge
Eine C(s) kann nur zwei mögliche Formen annehmen. Entweder sie gerät in einen Zyklus oder sie wächst ins Unendliche. Die bisher unbewiesene Vermutung zu diesem Problem ist die Aussage des folgenden Satzes.
Satz 1: Für jede Startzahl gerät in den Zyklus .
...um weiterzulesen, bitte den Artikel im PDF Format downloaden.
Nachtrag 01.01.2015: Den Artikel gibt es jetzt auch (noch ausführlicher) in Englisch unter: arXiv:1412.0519
Über die Struktur und das Wachstumsverhalten von Collatz 3n + 1 Folgen.
Mein Artikel ist in erster Linie eine Analyse und zeigt ein paar neue Ergebnisse, Einsichten und Ideen zur Behandlung des Themas. Hier zunächst nur die ersten Seiten um sich einen Überblick verschaffen zu können. Der vollständi
\(\begingroup\)Hallo Slash
Leider stimmt schon das erste Lemma nicht. Warum ist
$T^k(s)=2x$?
Gegenbeispiele findet man leicht.
$T^2(14)=11$ aber
$T^1(14)=7$.
mfG Moudi\(\endgroup\)
\(\begingroup\)Hi Moudi,
\
danke für den Hinweis. Die Voraussetzung sollte ein gerades Folgenglied sein. Es müsste dann wohl richtig: "Für alle T^k(s)==0 mod 2 gilt ..." heißen. Der Fehler zieht sich dann durch alle Lemmata.
Gruß, Slash
(07.03.2014) Fehler wurden korrigiert.\(\endgroup\)
\(\begingroup\)Noch eine Anmerkung für alle Leser aufgrund einer PM.
Dieser Artikel ist kein Beweisversuch der Collatz-Vermutung und war auch nicht als Beweisversuch der Collatz-Vermutung begonnen worden, sondern als eine Analyse. Der Schluss, dass es keine unendlich wachsenden Folgen geben kann (falls es denn stimmt) ist mehr ein Nebenprodukt.
Die Collatz-Vermutung wäre erst bewiesen, wenn gezeigt wird, dass es keine unendlich wachsende Folge "und" keine weiteren Zyklen außer 2,1,2,1 gibt.
Gruß, Slash\(\endgroup\)
\(\begingroup\)Hallo!
In Lemma 2 fehlt die Voraussetzung s > 1 (damit x > 0 gilt). Ansonsten sind die Lemmata 1-6 kleine Fingerübungen und damit korrekt.
---------
In Lemma 7 ist mir unklar, was du sagen willst: Wenn du n und s fest wählst (wie in der angegebenen Voraussetzung des Lemmas), dann sind deine Mengen jeweils leer (wenn dein s nicht die jeweils angegebene Bedingung erfüllt) oder bestehen aus genau dem einen Wert s. Ich denke nicht, dass du darauf hin wolltest.
Wolltest du vielleicht sagen, dass alle Zahlen s == 3 (mod 4) auch die Struktur s == 2^n - 1 (mod 2^{n+1}) für ein n >= 2 besitzen und umgekehrt?
Die Rückrichtung ist trivial, da ja 4 ein Teiler von 2^(n+1) ist und also s == 2^n - 1 == 3 (mod 4) ist, da n >= 2.
Zur Hinrichtung: Die zu erfüllende Bedingung s == 2^n - 1 (mod 2^{n+1}) heißt ja, dass es eine ganze Zahl x mit s = x * 2^{n+1} + 2^n - 1 = (2x+1) * 2^n - 1 gibt.
Umgekehrt heißt die Voraussetzung für diesen Fall s == 3 (mod 4), dass es eine genaze Zahl y gibt, sodass s = y*4 + 3 = (y+1) * 4 - 1 gibt. Nun können wir y+1 (eindeutig) in eine Zweierpotenz und einen ungeraden Faktor u zerlegen: (y+1)=2^m * u mit u == 1 (mod 2) und m >= 0.
Setzen wir nun x:=(u-1)/2 und n:=m+2, erhalten wir das gewünschte Ergebnis. \Box.
-----------
Edit: (hatte nicht gesehen, dass du für ungerade Zahlen gleich (3n+1)/2 definierst.
Lemma 8 ist also auch so ok.
Cyrix\(\endgroup\)
\(\begingroup\)Hi Cyrix,
\
in Lemma 7 will ich zeigen, dass die Vereinigung der Mengen {s==3 mod 8}, {s==7 mod 16}, {s==15 mod 32}, usw. gleich der Menge {s==3 mod 4} ist.
Wäre es so richtig(er)?
\forall \ s,n\el\ \IN, n>=2 gilt {s==(2^n-1) mod 2^n+1 } = {s==3 mod 4}
Bis auf Lemma 5 und 6 sind natürlich alle trivial und eben vorbereitend für den wichtigen Satz 2, welcher die Teilfolgen C^t(s) definiert und beschreibt.
Ich hätte auch alles voraussetzen können, doch dann hätte der nächste vielleicht schon nach einem Beweis für die Aussage aus Lemma 1 gefragt. Ich wollte es so genau wie möglich machen. Leider konnte/wollte ich diesen lückenlosen Stil nicht ganz durchziehen. Satz 3 ist dann schon ohne Beweis, da er nicht so wichtig ist wie Satz 2.
Gruß, Slash\(\endgroup\)
\(\begingroup\)Lemma 4 stimmt so nicht. Du setzt die Teilbarkeit von $T^k(s)$ durch $2^n$ voraus, führst aber dann den Beweis nur für den Fall der Gleichheit.
Sehr verwirrend auch gleich zu Beginn: C(s) bezeichnest du als Collatz-Folge, verwendest aber dann dafür die Schreibweise einer Menge bzw. Multimenge. Das sind natürlich zwei grundverschiedene Konzepte, die man auch in der Notation streng auseinanderhalten sollte.\(\endgroup\)
\(\begingroup\)Es sollte dann wohl \ Für alle T^k(s)=2^n ... schon zu Beginn heißen.
Die Einleitung in Garner's Text verwendet auch geschweifte Klammern. Das habe ich so übernommen. Dies sind halt Dinge die auf meinen Amateur-Status zurückzuführen sind. Ich denke aber, das jeder weiß was gemeint ist. Es ist meine Definition wie im folgenden Text eine Collatz-Folge geschrieben wird. Aber ich akzeptiere natürlich deinen Einwand von mathematischer Strenge in der Notation.
Gruß, Slash\(\endgroup\)
\(\begingroup\)@ Anonymous
Diese spezielle Seite nicht.
Doch es wurden schon etliche Versuche unternommen das Collatz-Problem mit anderen Start(Iterations)bedingungen hinsichtlich Zyklus-Bildung zu untersuchen. Lässt man im 3n + 1 Problem auch negative Zahlen zu, so finden sich sofort "drei" verschiedene Zyklen. Doch auch diese Zyklen unterliegen den Gesetzen der von mir beschriebenen Restklassen-Entwicklungen der Teilfolgen.
Ich bin in meinem Text zwar nicht auf Zyklen eingegangen, doch habe ich mir natürlich hinsichtlich der Teilfolgen auch dazu Gedanken gemacht. Meine Ergebnisse sind allerdings noch nicht so ausgereift, dass ich sie veröffentlichen wollte.
Gruß, Slash\(\endgroup\)
\(\begingroup\)@Slash:
Ich muß den genauen Moment verpaßt haben, aber mir ist aufgefallen, daß Dein Artikel nun (teilweise?) mit LaTeX komplett neu überarbeitet wurde - Glückwunsch!
\(\endgroup\)
\(\begingroup\)@cis
Danke! Die PDF Version ist komplett mit LaTeX gesetzt. Da man aber diese LaTeX-Version nicht 1 zu 1 hier als Artikel übertragen konnte, habe ich nur den hier zu lesenden Anfang umgeschrieben.
Auf jeden Fall sieht die PDF Version nun optisch sehr gelungen aus.
Gruß, Slash\(\endgroup\)
\(\begingroup\)Hallo Slash!
Der Satz "Jede Startzahl besitzt endliche Stoppzeit" wird hier nicht bewiesen. Du gibst maximal eine Heuristik an, dass für jede Startzahl mehr "Stoppzeitfolgen" als "Wachstumsfolgen" durchlaufen werden, und machst dies an einem Verteilungsargument (etwa 2/3 aller betrachteten olgen sind "Stoppzeitolgen") fest.
Zum Einen sagt diese Verteilung nichts über den konkreten Einzelfall für eine konkrete Startzahl, denn so lang diese Ausnahme genügend selten auftritt, strt diese Ausnahme nicht die Regel - jedenfalls nicht bei einer reinen Grenzwertbetrachtung, wo diese Ausnahme im Mittel der periodisch werdenden Collatz-olgen untergeht.
Zum Anderen sagst du nichts über das Wachstums- bzw. Schrumpfungsverhalten der jeweiligen Teilfolgen: Warum sollte nicht eine Collatz-Folge vielleicht zwar mehr "Stoppzeit-" als "Wachstumsfolgen" durchlaufen, während erste aber immer nur die Zahl um einen kleinen Faktor reduzieren, wärend zweitere sie mächtig aufplustern?!
Mit rein statistischen Mitteln wird man Collatz nicht erschlagen können...
Cyrix\(\endgroup\)
\(\begingroup\)Hi Cyrix,
korrekt, der Satz "Jede Startzahl besitzt endliche Stoppzeit" wird hier nicht bewiesen. Das steht auch nirgendwo geschrieben, denn dies wäre ja der Beweis der Vermutung.
Ich meine, und so steht es auch geschrieben, mit statistischen Mitteln zeigen zu können, dass ein unendliches Wachstum unmöglich ist. Die Vermutung wäre damit nicht bewiesen, da ja die Existenz mindestens eines größeren Zyklus möglich wäre.
Mit rein statistischen Methoden jeder Startzahl endliche Stoppzeit nachzuweisen dürfte wohl wirlich nicht möglich sein, aber ich setze die statistischen Methoden gegen ein unendliches Wachstum ein. Und das könnte funktionieren, da die Teilfolgen statistisch wohlgeordnet sind.
"Warum sollte nicht eine Collatz-Folge vielleicht zwar mehr "Stoppzeit-" als "Wachstumsfolgen" durchlaufen, während erste aber immer nur die Zahl um einen kleinen Faktor reduzieren, wärend zweitere sie mächtig aufplustern?!"
Das genau das bei einem "unendlichen" Wachstum nicht möglich sein kann versuche ich ja zu zeigen. Dagegen setze ich das Verteilungsmuster, wie im Abstract beschrieben. Es ist sozusagen die Unendlichkeit, die der Statistik unter die Arme greift.
Ich möchte aber nicht ausschließen, dass ich falsche Schlüsse ziehe.
Gruß, Slash\(\endgroup\)
\(\begingroup\)hi,
ich habe jz die pdf gelesen und scheitere am verständnis der teilfolgen-definition. für mich findet hier erstmal nur eine willkürliche teilung statt und keine, die iwie bezug zu relativen minima bzw 'maxima' hätte. dadurch entzieht sich mir natürlich auch komplett der zusammenhang zu den fibonacci-zahlen.
bye trunx\(\endgroup\)
\(\begingroup\)Hi trunx,
die Teilfolgen gliedern bzw. zerlegen eine jede Collatzfolge. Es wird genau das gezeigt/bewiesen, was im Abstract steht:
"Es wird gezeigt, dass jede $C(s)$ aus gleich strukturierten Teilfolgen $C^t(s)=\left(T^k(s)_{k=0}^t\right)$ für Startzahlen $s\equiv3,7\,mod\,12$ bzw. $C^h(s)=\left(T^k(s)_{k=0}^h\right)$ für Startzahlen $s\equiv9\,mod\,12$ zusammengesetzt ist."
Also von "Willkür" kann keine Rede sein. Schließlich kann man alles beweisen. Man könnte wohl auch andere Ein/Aufteilungen der Folgen vornehmen, aber meine gezeigte ist ja schon das Non plus Ultra. Und das sich darin die Fibonacci-Folge finden lässt bestätigt mir dieses Vorgehen.
Die Fibonacci-Folge findet sich in der Anzahl der Restklassen der Teilfolgen mit gleich vielen Gliedern wieder. Das wird nicht bewiesen. In der englischen Version ist das noch viel deutlicher dargestellt.
Die Teilfolgen haben natürlich erstmal keinen erkennbaren Nutzen um den Verlauf einer Collatz-Folge vorherzusagen, also auch deren Maxima und Minima. Dann hätte man ja schon die Lösung 😉 . Aber unter 8. "Konsequenzen für unendliches Wachstum" steht ja genau, wofür man sie gebrauchen kann. Und ich denke, da steckt noch jede Menge Potenzial drin.
Ich denke aber, du meinst genau das, was mir Cyrix schon geschrieben hat: "...Zum Einen sagt diese Verteilung nichts über den konkreten Einzelfall für eine konkrete Startzahl. ...Zum Anderen sagst du nichts über das Wachstums- bzw. Schrumpfungsverhalten der jeweiligen Teilfolgen." (siehe oben)
Gruß, Slash\(\endgroup\)
\(\begingroup\)hi slash, nein soweit wie cyrix bin ich noch nicht :)
es geht mir wirklich um die mir willkürlich erscheinende teilung der folgen. nehmen wir zb. c(27): diese teilst du zunächst nach der 62, man würde jz erwarten, dass der nächste schnitt nach 242 kommt, aber es wird nach der 182 geteilt. usw.\(\endgroup\)
\(\begingroup\)Ach so. Die Teilfolgen sind ja wohl definiert, nach der Restklassenstruktur. Diese folgt aus den anfänglichen Term-Lemmata. Da ist also nichts willkürlich, sondern alles streng gesetzlich. Das ist ja das tolle und erstaunliche, dass sich jede Collatzfolge so einteilen lässt. Meine Definition folgt also aus den Lemmata, vielleicht ist das verwirrend. Man kann die Definition auch als Konsequenz der Teilfolgen-Sätze sehen. Man könnte sie sogar weglassen. Wie gesagt, der englische Artikel ist der bessere. Dort habe ich das anders geschrieben. Der Begriff "Definition" ist wohl schon unangebracht. Also wichtig sind nur die Sätze mit Beweis. Dann wird auch klar, warum bei 31 erst nach 182 Schluss ist.
Ich werde die Definition wohl rausnehmen bzw. hinter die Beweise als zusätzliche Erklärung stellen. Das war mir nicht klar, dass das so verwirrend ist. Jetzt sehe ich es aber.\(\endgroup\)
\(\begingroup\)gut, ok, dann warte ich, bis du das aktualisiert hast, kannst mir ja dann gern ne pm schicken. achso und wenn du eh grad dabei bist, die verwirrenden teile zu entwirren, dann könntest du vllt noch ein wort zu den globalen minima und maxima sagen. für mich ist zb. das globale, ungerade maximum in c(27) 3077 und das ist in deinen teilfolgen nicht enthalten (weil du ja, wie gesagt aus irgendeinem unerfindlichen grund die folge schon vorher splittest). ein genau erläuterndes beispiel wäre nicht schlecht.\(\endgroup\)
\(\begingroup\)Du kannst jetzt schon weiterlesen. Die Definition überspringst du einfach. Die globalen Extremstellen sind schon vor der Definition genau erklärt. (Und in der Definition gibts dann noch ein paar Details.) Da muss nichts entwirrt werden. Auch Beispiele werden genannt. Zum Schluss gibts sogar zwei Seiten-Listen. Wie gesagt, schaue auch in den besseren englischen Artikel. Der ist einfach zu verstehen. Es ist ja keine Prosa. Du verstehst und liest doch auch die englische Physiker-Literatur.
"(weil du ja, wie gesagt aus irgendeinem unerfindlichen grund die folge schon vorher splittest)."
=> Die Teilfolgen sind so "definiert", dass sie mit dem Glied enden, auf das wieder eine Zahl der Restklasse 3,7 (mod 12) bzw 9 (mod 12) folgt. Lies doch erstmal weiter und zu ende.\(\endgroup\)
\(\begingroup\)eine durch drei teilbare zahl (wie 3 oder 9 mod 12) kann niemals auf eine andere zahl folgen. es bliebe nur 7 mod 12.
nehmen wir ein noch einfacheres beispiel, die folge c(7)={7,11,17,26,13,20,10,5}
auf 11 (einer 3 mod 4 zahl) folgt als globales ungerades maximum die 17 (eine 1 mod 4 zahl). danach sollte deiner meinung nach im kürzesten fall eine zahl 6 mod 8 als gerades maximum folgen und im längsten fall eine zahl der form 2 mod 6. 26 ist letzteres also der längste fall, direkt im anschluss? ich hätte das für kurz gehalten. aber egal, mir geht es ja darum wie die folge endet. du schreibst entweder mit dem geraden minimum in form einer 6 mod 8 zahl oder mit 1. aber weder die eine noch die andere zahl gibt es, dh. es gibt keine gültig def. grenze, also gibt es streng genommen für 7 auch keine teilfolge deiner art. und das sowohl auf deutsch und englisch.
sry, dass ich so hartnäckig bin. wenn du keinen bock zu antworten hast, ist das auch ok, dann ist das ganze als quatsch für mich erledigt.\(\endgroup\)
Home / Seite ohne Frame
Wie unterstütze ich den Matheplaneten mit Geld?
Printer-friendly version
Get link to this article
Comments
Dieser Artikel ist im Verzeichnis der 
