Latex-Bibliographie in HTML umwandeln

Mathematik: Eine Stoppzeit-Analyse der Collatz 3x + 1 Funktion Released by matroid on Mi. 24. Juni 2015 18:51:46 [Statistics] [Comments] Written by Slash - 1993 x read [Outline] Printer-friendly version -  Choose languageDE EN   \(\begingroup\) Eine Stoppzeit-Analyse der Collatz 3x + 1 Funktion Im Mittelpunkt meines zweiten Artikels zum berühmten Collatz 3x + 1 Problem steht die sogenannte "endliche Stoppzeit", die angibt, welches Glied in einer Collatzfolge zum ersten Mal kleiner als seine Startzahl ist. Falls jede Startzahl einer Collatzfolge endliche Stoppzeit besitzt, erreicht eine jede Collatzfolge irgendwann die 1, so wie es Lothar Collatz vermutet hat. Ich habe nun das Stoppzeit-Verhalten für eine endliche Menge von Startzahlen untersucht. Welche Rolle dabei die Lösungen spezieller diophantischer Gleichungen spielen und was das Ganze mit dieser $\backslash displaystyle\; z\_n=\backslash binom\{\backslash big\backslash lfloor\backslash frac\{5(n-2)\}\{3\}\backslash big\backslash rfloor\}\{n-2\}-\backslash sum\_\{i=2\}^\{n-1\}\backslash binom\{\backslash big\backslash lfloor\backslash frac\{3(n-i)+\backslash delta\}\{2\}\backslash big\backslash rfloor\}\{n-i\}\backslash cdot\; z\_i$ geheimnisvollen Gleichung zu tun hat, erfahrt Ihr im Artikel. [Edit] [To the bottom] Inhaltsverzeichnis 1. Vorwort 2. Die Collatz 3x + 1 Funktion 3. Stoppzeit 4. Eine Stoppzeit-Formel für ungerade Startzahlen 5. Teilfolgen und ihre binäre Vereinfachung 6. Binäre Tupel 7. Die diophantischen Gleichungen und ihre Lösungen 8. Analyse der Lösungen 9. Ein iterativer Stoppzeit-Algorithmus 10. Eine allgemeine Stoppzeit-Hypothese 11. Anhang 11.1 Programme in PARI/GP 11.2 Permutationen in lexikographischer Ordnung für n = 7 11.3 Ausgabe von Programm 2 für n = 4...7 12. Bibliographie 13. Anmerkungen 1. Vorwort Gemäß dem Titel ist dieser Artikel als Analyse zu verstehen. Es werden keine Beweise angegeben. Wichtige Aussagen (Vermutungen 1-8), zu erkennen an dem rosa Rahmen, dienen zur Gliederung des Textes und werden jeweils mit einem ausführlichen Beispiel verdeutlicht. Wie schon mein erster Artikel zu diesem Thema ist auch dieser keine bloße Aneinanderreihung von Lehrbuchinhalten, sondern eine eigenständige Forschungsarbeit mit zum Teil völlig neuen Erkenntnissen, auch wenn diese aufgrund fehlender Beweise erstmal Vermutungen bleiben. Ich hätte den Artikel auch mit "Über die Entwicklung eines Stoppzeit-Algorithmus der Collatz 3x + 1 Funktion" betiteln können, denn dies ist es im Wesentlichen worauf meine Analyse hinausläuft. Offen bleibt, ob sich mit den Ergebnissen auch ein Beweis für die Collatz-Vermutung führen ließe. Für das Verständnis des Artikels sind keine speziellen Kenntnisse nötig. Man sollte aber wissen was eine Restklasse ist, die Floor-Funktion und den Binomialkoeffizienten kennen. Zum Verständnis der PARI/GP Programme genügen minimale Programmierkenntnisse. 2. Die Collatz 3x + 1 Funktion Definition 1: Die Collatz $3x\; +\; 1$ Funktion sei definiert als eine Abbildung $T:\backslash mathbb\{N\}\backslash rightarrow\backslash mathbb\{N\}$ gegeben durch Sei $T^0(s)=s$ und $T^k(s)=T\backslash left(T^\{k-1\}(s)\backslash right)$ für $k\backslash in\backslash mathbb\{N\}$. Dann ist die Collatz-Folge für $s\backslash in\backslash mathbb\{N\}$ gegeben durch $C(s)=\backslash left(T^k(s)\backslash mid\; k=0,1,2,3,\backslash dotsc\backslash right)$. Beispiel: Für die Startzahl $s=11$ ergibt sich die Collatz-Folge $\backslash displaystyle\; C(11)=(11,17,26,13,20,10,5,8,4,2,1,2,1,2,1,\backslash dotsc).$ 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 folgende: Vermutung 1: Für jede Startzahl $s\backslash in\backslash mathbb\{N\}$ gerät $C(s)$ in den Zyklus $(1,2)$. [Edit] 3. Stoppzeit Definition 2: Wird in $C(s)$ für eine Startzahl $s\backslash in\backslash mathbb\{N\}$ nach endlich vielen Iterationsschritten $k$ erstmals eine Zahl Definition 3: Für jedes $n\backslash geq0$ sei $z\_n$ die Anzahl der Restklassen $(mod\backslash \; 2^\{\backslash sigma\_n\})$ mit Stoppzeit $\backslash sigma\_n$. Es ist dann $z\_0=1,\backslash \; z\_1=1,\backslash \; z\_2=1,\backslash \; z\_3=2,\backslash \; z\_4=3,\backslash \; z\_5=7,\backslash \; z\_6=12,\backslash \; z\_7=30,\backslash \; \backslash dotsc$ Die folgende Vermutung soll die letzten Ergebnisse zusammenfassend darstellen. Vermutung 2: Sei $\backslash sigma\_n=\backslash lfloor1+n\backslash cdot\backslash log\_23\backslash rfloor$, dann existiert für jedes $n\backslash in\backslash mathbb\{N\},\backslash ,n\backslash geq0$ eine Menge von $z\_n\backslash geq\; 1$ Restklassen $(mod\backslash \; 2^\{\backslash sigma\_n\})$ mit der Eigenschaft, dass alle Startzahlen $s$ aus einer dieser Restklassen Stoppzeit $\backslash sigma(s)=\backslash sigma\_n$ haben. Dabei gilt für alle $n\backslash geq\; 6$ sogar $z\_\{n+1\}>\; 2\backslash cdot\; z\_n$. Die Collatz-Vermutung ist also wahr, wenn die Menge der möglichen Startzahl-Restklassen die Menge der natürlichen Zahlen bildet. Die möglichen Stoppzeiten $\backslash sigma(s)$ sind gelistet in der OEIS Folge A020914. Die zugehörigen Restklassen $(mod\backslash \; 2^\{\backslash sigma\_n\})$ sind gelistet in der OEIS Folge A177789. Die Anzahl der Restklassen $z\_n$ für $n\backslash geq1$ sind gelistet in der OEIS Folge A100982. 4. Eine Stoppzeit-Formel für ungerade Startzahlen Ob die ungerade Startzahl $s$ einer Collatzfolge $C(s)$ endliche Stoppzeit besitzt ist davon abhängig wie die ersten $n$ ungeraden Folgenglieder in $C(s)$ verteilt sind. Mit ein paar einfachen Überlegungen lässt sich so aus der Iterationsvorschrift eine Stoppzeit-Formel ableiten. Vermutung 3: Sei $C^a(s)=\backslash left(T^k(s)\backslash mid\; k=0,\backslash dotsc,a\backslash right)$ mit $a\backslash geq1$ eine endliche Teilfolge von $C(s)$, und sei $\backslash sigma\_n=\backslash lfloor1+n\backslash cdot\backslash log\_23\backslash rfloor$. Dann besitzt eine ungerade Startzahl $s$ für jedes $n\backslash in\backslash mathbb\{N\}$ die Stoppzeit $\backslash sigma(s)=\backslash sigma\_n$, wenn die zugehörige Teilfolge $C^\{\backslash sigma\_n-1\}(s)$ genau $n$ ungerade Folgenglieder besitzt, und $\backslash alpha\_i=k$ ist, genau und nur dann wenn $T^k(s$) in $C^\{\backslash sigma\_n-1\}(s)$ ungerade ist. Dann gilt Beispiel: Für $n=4$ gilt $\backslash sigma\_4=\backslash lfloor1+4\backslash cdot\backslash log\_23\backslash rfloor=7$. Für $s=59$ ergibt sich dann mit Gleichung (1) Begründung: Die Teilfolge $C^6(59)=(59,89,134,67,101,152,76)$ besitzt vier $(n=4)$ ungerade Folgenglieder $59,89,67,101$. Die Zweierpotenzen $\backslash alpha\_i$ ergeben sich dann folgendermaßen: $T^0=59$ ist ungerade, also ist $\backslash alpha\_1=0$. $T^1=89$ ist ungerade, also ist $\backslash alpha\_2=1$. $T^2=134$ ist gerade. $T^3=67$ ist ungerade, also ist $\backslash alpha\_3=3$. $T^4=101$ ist ungerade, also ist $\backslash alpha\_4=4$. $T^5=152$ ist gerade. $T^6=76$ ist gerade. Die Stoppzeit $\backslash sigma(s)=7$ gilt dann nicht nur für $s=59$, sondern für alle $s\backslash equiv59\backslash \; (mod\backslash \; 2^7)$. [Edit] 5. Teilfolgen und ihre binäre Vereinfachung Vermutung 4: Sei $m=\backslash big\backslash lfloor\backslash frac\{2(n-2)\}\{3\}\backslash big\backslash rfloor$ und $\backslash sigma\_n=\backslash lfloor1+n\backslash cdot\backslash log\_23\backslash rfloor$ für alle $n\backslash in\backslash mathbb\{N\},\backslash ,n\backslash geq4$. Besitzt eine ungerade Startzahl $s$ die Stoppzeit $\backslash sigma(s)=\backslash sigma\_n$, dann repräsentieren nach Vermutung 2 die ersten $m+n$ Folgenglieder in $C(s)$ "zur Genüge" die Stoppzeit von $s$, da alle weiteren Folgenglieder gerade sind bevor eine Zahl Definition 4: Um die Verteilung der geraden und ungeraden Folgenglieder in $C(s)$ zu vereinfachen, repräsentiere "0" ein gerades und "1" ungerades Folgenglied. Beispiel: Für $n=4$ gilt $m=\backslash big\backslash lfloor\; \backslash frac\{2(4-2)\}\{3\}\backslash big\backslash rfloor=1$ und $\backslash sigma\_4=\backslash lfloor1+4\backslash cdot\backslash log\_23\backslash rfloor=7$. Für die Teilfolgen $C^\{\backslash sigma\_n\}(s)$ gilt dann $C^7(7)=(7,11,17,26,13,20,10,5)\backslash quad\; \backslash text\{wird\; vereinfacht\; durch\}\backslash quad\; (1,1,1,0,1,0,0,1),\backslash \backslash \; C^7(15)=(15,23,35,53,80,40,20,10)\backslash quad\; \backslash text\{wird\; vereinfacht\; durch\}\backslash quad\; (1,1,1,1,0,0,0,0),\backslash \backslash \; C^7(59)=(59,89,134,67,101,152,76,38)\backslash quad\; \backslash text\{wird\; vereinfacht\; durch\}\backslash quad\; (1,1,0,1,1,0,0,0).$ Und für die "zur Genüge verkürzten" Teilfolgen $C^\{m+n-1\}(s)$ gilt dann $C^4(7)=(7,11,17,26,13)\backslash quad\; \backslash text\{wird\; vereinfacht\; durch\}\backslash quad\; (1,1,1,0,1),\backslash \backslash \; C^4(15)=(15,23,35,53,80)\backslash quad\; \backslash text\{wird\; vereinfacht\; durch\}\backslash quad\; (1,1,1,1,0),\backslash \backslash \; C^4(59)=(59,89,134,67,101)\backslash quad\; \backslash text\{wird\; vereinfacht\; durch\}\backslash quad\; (1,1,0,1,1).$ 6. Binäre Tupel Sei $m=\backslash big\backslash lfloor\backslash frac\{2(n-2)\}\{3\}\backslash big\backslash rfloor$ für jedes $n\backslash in\backslash mathbb\{N\},\backslash ,n\backslash geq4$. Definition 5: Sei $\backslash mathcal\{A\}(n)$ ein binäres $(m+n-2)$-Tupel für jedes $n\backslash in\backslash mathbb\{N\},\backslash ,n\backslash geq4$, gegeben durch $\backslash mathcal\{A\}(n)=(a\_1,\; \backslash cdots,\; a\_m,a\_\{m+1\},\; \backslash cdots,\; a\_\{m+n-2\})\backslash \backslash \; \backslash text\{mit\}\; \backslash quad\; a\_1,\; \backslash cdots,\; a\_m:=0\; \backslash quad\; \backslash text\{und\}\; \backslash quad\; a\_\{m+1\},\; \backslash cdots,\; a\_\{m+n-2\}:=1.$ Definition 6: Sei $\backslash mathbb\{A\}\_j(n)$ die Menge aller Permutationen in lexikographischer Ordnung von $\backslash mathcal\{A\}(n)$ für jedes $n\backslash in\backslash mathbb\{N\},\backslash ,n\backslash geq4$, wobei $j$ die Anzahl dieser Tupel für jedes $n$ sei, gegeben durch $\backslash displaystyle\{j=\backslash frac\{(m+n-2)!\}\{m!\backslash cdot(n-2)!\}=\backslash binom\{\backslash big\backslash lfloor\backslash frac\{5(n-2)\}\{3\}\backslash big\backslash rfloor\}\{n-2\}.\}$ Definition 7: Sei $\backslash mathcal\{B\}(n)$ ein binäres $(m+n)$-Tupel für jedes $n\backslash in\backslash mathbb\{N\},\backslash ,n\backslash geq4$, gegeben durch $\backslash mathcal\{B\}(n)=(b\_1,\; \backslash cdots,\; b\_\{m+n\})\backslash quad\; \backslash text\{mit\}\; \backslash quad\; b\_1:=1,\; \backslash \; b\_2:=1.$ Definition 8: Sei $\backslash mathbb\{B\}\_j(n)$ die Menge aller $j$ Tupel $\backslash mathcal\{B\}(n)$ für jedes $n\backslash in\backslash mathbb\{N\},\backslash ,n\backslash geq4$, wobei $b\_3,\; \backslash cdots,\; b\_\{m+n\}$ exakt einem Tupel aus der Menge $\backslash mathbb\{A\}\_j(n)$ entspricht. Beispiel: Für $n=7$ gilt $m=3$ und $j=56$. Damit erhalten wir das 8-Tupel $\backslash mathcal\{A\}(7)=(0,0,0,1,1,1,1,1)$. Nun existieren 56 Permutationen in lexikographischer Ordnung von $\backslash mathcal\{A\}(7)$. Somit besitzt $\backslash mathbb\{A\}\_\{56\}(7)$ 56 verschiedene 8-Tupel, und $\backslash mathbb\{B\}\_\{56\}(7)$ besitzt 56 verschiedene 10-Tupel. Die Tupel der Menge $\backslash mathbb\{B\}\_j(n)$ unterscheiden sich also lediglich durch die zwei zusätzlichen vorderen "1"-Elemente von den Tupeln der Menge $\backslash mathbb\{A\}\_j(n)$. Anhang 11.2 zeigt dieses Beispiel ausführlich mit allen 56 Tupeln. [Edit] 7. Die diophantischen Gleichungen und ihre Lösungen Aus Vermutung 2 folgt, dass das Verhalten einer Collatzfolge daran gebunden ist, wie die Zweierpotenzen zwischen den Dreierpotenzen in dem Term $3^\{n-i\}2^\{\backslash alpha\_i\}$ aus Gleichung (1) verteilt sind. Aus Vermutung 3 folgt, dass für jedes $n\backslash in\backslash mathbb\{N\},n\backslash geq4$, nur für die $j$ binären Tupel aus $\backslash mathbb\{B\}\_j(n)$ die Bedingungen von Vermutung 2 und Gleichung (1) erfüllt sind. Vermutung 5: Sei $\backslash sigma\_n=\backslash lfloor1+n\backslash cdot\backslash log\_23\backslash rfloor$. Interpretiert man die binären Tupel aus $\backslash mathbb\{B\}\_j(n)$ als binäre Vereinfachungen der geraden und ungerden Folgenglieder in $C^\{m+n-1\}(s)$, dann existiert nach Vermutung 2 für jedes $n\backslash in\backslash mathbb\{N\},\backslash ,n\backslash geq4$, für jedes binäre Tupel aus $\backslash mathbb\{B\}\_j(n)$ eine eigene diophantische Gleichung $\backslash displaystyle\; y=\backslash frac\{3^n\}\{2^\{\backslash sigma\_n\}\}\backslash cdot\; x+\backslash sum\_\{i=1\}^n\; \backslash frac\{3^\{n-i\}2^\{\backslash alpha\_i\}\}\{2^\{\backslash sigma\_n\}\},\backslash quad\backslash quad\backslash mathbf\{(2)\}$ die genau eine ganzzahlige Lösung $(x,y)$ für Über die Lösungen von Gleichung (2) lässt sich dann folgendes aussagen. Vermutung 6: Für jedes $n\backslash in\backslash mathbb\{N\},\backslash ,n\backslash geq4$, repräsentieren die $j$ Lösungen $(x,y)$ genau $j$ verschiedene Restklassen von Startzahlen $s$ mit endlicher Stoppzeit $4\backslash leq\backslash sigma(s)\backslash leq\backslash sigma\_n$. Präziser: Für jedes $n\backslash in\backslash mathbb\{N\},\backslash ,n\backslash geq4$, repräsentieren die $j$ Lösungen genau $z\_n$ Restklassen von Startzahlen $s$ mit endlicher Stoppzeit $\backslash sigma(s)=\backslash sigma\_n$, und genau $j-z\_n$ Restklassen von Startzahlen $s$ mit endlicher Stoppzeit . Dabei gilt insbesondere für die $z\_n$ Lösungen $(x,y)$ mit $\backslash sigma(x)=\backslash sigma\_n$, dass der Wert von $x$ immer gleich der kleinsten Zahl der Restklasse $[x]\_\{2^\{\backslash sigma\_n\}\}$ ist. Beispiel: Für $n=5$ gibt es $j=10$ ganzzahlige Lösungen $(x,y)$. Die folgende Tabelle 1 zeigt die 10 binären Tupel aus $\backslash mathbb\{B\}\_\{10\}(5)$ und die zugehörigen ganzzahlige Lösungen $(x,y)$. Von diesen 10 Lösungen, gibt es $z\_5=7$ Lösungen für die $x$ die Stoppzeit $\backslash sigma(x)=\backslash sigma\_5=8$ besitzt und $10-7=3$ Lösungen für die $x$ die Stoppzeit besitzt. Es gilt $211\backslash equiv3\backslash \; (mod\backslash \; 16)$, $107\backslash equiv11\backslash \; (mod\backslash \; 32)$ und $183\backslash equiv23\backslash \; (mod\backslash \; 32)$. Somit repräsentieren diese 10 Lösungen 10 verschiedene Restklassen von Startzahlen $s$ mit endlicher Stoppzeit $4\backslash leq\backslash sigma(s)\backslash leq8$. Zum Vergleich hier noch einmal die entsprechenden Ergebnisse aus Kapitel 3, wonach $\backslash sigma(s)=4$ für alle $s\backslash equiv3\backslash \; (mod\backslash \; 16)$, $\backslash sigma(s)=5$ für alle $s\backslash equiv11,23\backslash \; (mod\backslash \; 32)$, $\backslash sigma(s)=8$ für alle $s\backslash equiv39,79,95,123,175,199,219\backslash \; (mod\backslash \; 256)$. Man beachte, dass für $\backslash sigma(s)=8$ die kleinsten Zahlen der 7 Restklassen jeweils mit einem der $x$-Werte identisch sind. Die folgende Tabelle 2 zeigt wie sich für $n=4,\backslash dots,12$ die Anzahl der Lösungen $(x,y)$ auf die möglichen Stoppzeiten $\backslash sigma(x)$ verteilen. Beispiel: Die Tabelle ist wie folgt zu lesen: "Sum" ist identisch mit dem Wert von $j$ und entspricht der Summe der Werte für $\backslash sigma(x)$ für ein bestimmtes $n$. Für $n=5$ gibt es 1+2+7=10 ganzzahlige Lösungen $(x,y)$. Davon 7 Lösungen mit $\backslash sigma(x)=8$, 2 Lösungen mit $\backslash sigma(x)=5$ und 1 Lösung mit $\backslash sigma(x)=4$. Kein Eintrag ist identisch mit dem Wert 0. Die PARI/GP Programme 1 bis 3 im Anhang 11.1 verdeutlichen die Lösungsfindung mit Gleichung (2). Programm 2 generiert Tabelle 1 und Programm 3 berechnet die Werte von Tabelle 2. Anhang 11.3 zeigt die Menge $\backslash mathbb\{B\}\_j(n)$ mit den ganzzahlige Lösungen $(x,y)$ für $n=4,\backslash dotsc,7$. 8. Analyse der Lösungen Analysiert man die Werte aus Tabelle 2 auf ihre Faktoren hin stellt man fest, dass diese immer ganzzahlige Vielfache von $z\_n$ sind, wie die folgende Tabelle 3 zeigt. Dabei sind die von $z\_n$ verschiedenen Faktoren wie 1, 4, 5, 6, 21, 28, 36, 84,... alles Zahlen des Pascalschen Dreiecks. Es scheint, als wären diese Zahlen für jedes $n$ durch die folgenden Binomialkoeffizienten für $k\backslash in\backslash mathbb\{N\}$ gegeben. Man beachte die unterschiedliche Farbgebung. Für $n=14,\backslash dotsc,19$ werden zwei weitere Binomialkoeffizienten benötigt. Die folgende Tabelle 4 zeigt die Werte für $n=13,\backslash dotsc,19$. Diese Werte wurden nicht mit Programm 3 gezählt, sondern mit Programm 5 generiert. Basierend auf den Ergebnissen dieser Analyse lässt sich nun die folgende Vermutung aufstellen, die mit einer überraschend schönen Gleichung aufwartet. Vermutung 7: Für jedes $n\backslash in\backslash mathbb\{N\},\backslash ,n\backslash geq4$, gilt $\backslash displaystyle\; z\_n=\backslash binom\{\backslash big\backslash lfloor\backslash frac\{5(n-2)\}\{3\}\backslash big\backslash rfloor\}\{n-2\}-\backslash sum\_\{i=2\}^\{n-1\}\backslash binom\{\backslash big\backslash lfloor\backslash frac\{3(n-i)+\backslash delta\}\{2\}\backslash big\backslash rfloor\}\{n-i\}\backslash cdot\; z\_i,\backslash quad\backslash quad\backslash mathbf\{(3)\}$ wobei $\backslash delta\backslash in\backslash mathbb\{Z\}$ verschiedene Werte innerhalb der Summe in Intervallen von 5 oder 6 Termen annimmt. Beispiel: Für $n=13$ geschieht die Berechnung von $z\_\{13\}$ mit Gleichung (3) wie folgt. [Edit] 9. Ein iterativer Stoppzeit-Algorithmus Mit den Ergebnissen der Analyse und Gleichung (3) wird es möglich einen iterativen Algorithmus zu entwickeln, der mit nur 12 Startzahlen $z\_1,\backslash dotsc,z\_\{12\}$ vermutlich nicht nur jede weitere dieser Zahlen generiert, sondern auch jede Anzahl aller ganzzahliger Lösungen $(x,y)$ für Die Korrektheit des Algorithmus für die Werte von $z\_n$ wurde mit einem Zähl-Algorithmus von Roosendaal/Noe[5] für alle $n\backslash leq10000$ überprüft. Die Zahl $z\_\{10000\}$ besitzt 4527 Dezimalstellen. Vielleicht muss der Algorithmus für größere Werte von $n$ leicht modifiziert werden, doch die Grundstruktur aus Gleichung (3) bleibt unverändert. Die Zeilen 11, 14 und 31, 33 von Programm 6 zeigen die Hauptberechnungen von Gleichung (3). Das einzig komplizierte an diesem Algorithmus ist die Berechnung der Struktur des Summationsindex $i$ und die zugehörigen Werte für $\backslash delta$. Hier würde eine Modifizierung ansetzen müssen, wenn sie denn nötig wäre. Die oberen Grenzen der For-Schleifen in den Zeilen 22, 35 und 38 sind abhängig von den Werten von $n$ bzw. $limit$ und müssen groß genug sein. Je größer diese Werte sind, desto länger ist die Rechenzeit des Algorithmus. Die PARI/GP Programme 4 und 5 im Anhang 11.1 zeigen diesen Algorithmus mit verschiedenen Ausgaben. Möchte man nur die Werte von $z\_n$ generieren, so geht dies auch einfacher, wie meine anderen Algorithmen in der OEIS Folge A100982 zeigen. 10. Eine allgemeine Stoppzeit-Hypothese Ob eine ungerade Startzahl $s$ endliche Stoppzeit besitzt ist also davon abhängig, wie die ersten $m$ geraden und $n$ ungeraden Folgenglieder in $C(s)$ untereinander verteilt sind. Ohne den Gebrauch von Gleichung (1) lässt sich nun die folgende Vermutung formulieren. Vermutung 8: Sei $m=\backslash big\backslash lfloor\; \backslash frac\{2(n-2)\}\{3\}\backslash big\backslash rfloor$ und $\backslash sigma\_n=\backslash lfloor1+n\backslash cdot\backslash log\_23\backslash rfloor$. Für jedes $n\backslash in\backslash mathbb\{N\},\backslash ,n\backslash geq4$, besitzt eine ungerade Startzahl $s$ endliche Stoppzeit $4\backslash leq\backslash sigma(s)\backslash leq\backslash sigma\_n$, wenn die binäre Vereinfachung der geraden und ungeraden Folgenglieder der Teilfolge $C^\{m+n-1\}(s)$ mit einem binären Tupel der Menge $\backslash mathbb\{B\}\_j(n)$ übereinstimmt und die Teilfolge $C^\{\backslash sigma\_n-1\}(s)$ genau $n$ ungerade Folgenglieder besitzt. Welche Konsequenz hätte unter diesem Aspekt die Existenz einer Collatzfolge mit einem anderen Zyklus als (1,2) oder mit unbegrenztem Wachstum? Gemäß Vermutung 8 müsste dann eine Startzahl $s$ "ohne" endliche Stoppzeit existieren. Diese Startzahl hätte die Eigenschaft, dass es für jedes $n\backslash in\backslash mathbb\{N\},\backslash ,n\backslash geq4$, "keine" Übereinstimmung der binären Vereinfachung der geraden und ungeraden Folgenglieder in der Teilfolge $C^\{m+n-1\}(s)$ und eines binären Tupels der Menge $\backslash mathbb\{B\}\_j(n)$ gibt, oder im Falle einer solchen Übereinstimmung die Teilfolge $C^\{\backslash sigma\_n-1\}(s)$ "keine" $n$ ungeraden Folgenglieder besitzt. Doch ist das überhaupt möglich? Nach Vermutung 5 besitzt jede mögliche Kombination von geraden und ungeraden Folgengliedern in einer Teilfolge eine Stoppzeit. Der Stoppzeit-Algorithmus, vorausgesetzt er ist korrekt und besitzt uneingeschränkte Gültigkeit, bestätigt diese Aussage mit der genauen Verteilung der Anzahl gleicher Stoppzeiten. Vermutung 5 muss daher wie ein unendlicher Filter wirken, der irgendwann jede mögliche Collatzfolge auffangen und ihrer Startzahl eine Stoppzeit zuordnen muss. Ich bin mir allerdings nicht sicher, ob diese letzte Interpretation korrekt ist und damit ein Indiz für die Richtigkeit der Collatz-Vermutung wäre. [Edit] 11. Anhang 11.1 Programme in PARI/GP Die Programme 1 bis 3 benutzen die Funktion NextPermutation(a), welche alle Permutationen in lexikographischer Ordnung eines binären Tupels $\backslash mathcal\{A\}(n)$ generiert. Programm 1 berechnet alle ganzzahligen Lösungen $(x,y)$ für Programm 2 berechnet alle ganzzahligen Lösungen $(x,y)$ für Programm 3 berechnet alle ganzzahligen Lösungen $(x,y)$ für Programm 4 ist wie Programm 6, aber gibt eine Liste der Zahlen $z\_n$ für hier in der OEIS Folge A100982 zu sehen ist. Programm 5 ist wie Programm 6, aber gibt die Anzahl aller ganzzahligen Lösungen wie in Tabelle 4 aus. 11.2 Permutationen in lexikographischer Ordnung für n = 7 Für $n=7$ gilt $\backslash mathcal\{A\}(7)=(0,0,0,1,1,1,1,1)$. Die beiden Mengen binärer Tupel sehen dann wie folgt aus. 11.3 Ausgabe von Programm 2 für n = 4...7 Die binären Tupel der Menge $\backslash mathbb\{B\}\_j(n)$ mit den ganzzahligen Lösungen $(x,y)$ für $n=4,\backslash dotsc,7.$ [Edit] 12. Bibliographie 1. C. J. Everett, Iteration of the number-theoretic function f(2n) = n, f(2n + 1) = 3n + 2, Advances in Math. 25 (1977), 42. 2. L. E. Garner, On the Collatz 3n + 1 Algorithm, Proc. Amer. Math. Soc., Vol. 82 (1981), 19-22. 3. E. Roosendaal, On the 3x + 1 problem. 4. R. Terras, A stopping time problem on the positive integers, Acta Arith. 30 (1976), 241. 5. The On-Line Encyclopedia of Integer Sequences (OEIS) A020914, A177789, A100982 (Roosendaal/Noe) 6. The PARI Group - PARI/GP Version 2.3.4 7. Wikipedia 8. M. Winkler, New results on the stopping time behaviour of the Collatz 3x + 1 function, arXiv:1504.00212 [math.GM], March 2015. 9. M. Winkler, On a stopping time algorithm of the 3n + 1 function, May 2011. 10. M. Winkler, On the structure and the behaviour of Collatz 3n + 1 sequences - Finite subsequences and the role of the Fibonacci sequence, arXiv:1412.0519 [math.GM], November 2014. 11. M. Winkler, Über das Stoppzeit-Verhalten der Collatz-Iteration, Oktober 2010. 12. M. Winkler, Über die Struktur und das Wachstumsverhalten von Collatz 3n + 1 Folgen, März 2014. 13. G. Wirsching, Über das 3n + 1 Problem, Elem. Math. 55 (2000) 142 – 155. 14. D. Wolke, Das Collatz–Problem. 13. Anmerkungen Einen fast identischen Artikel[8] habe ich bereits auf dem Preprintserver arXiv veröffentlicht. Kapitel 2: Die hier definierte Collatz $3x\; +\; 1$ Funktion mit dem $\backslash frac\{3x\; +\; 1\}\{2\}$ Schritt wird gewöhnlich als $3n\; +\; 1$ Funktion bezeichnet. Da aber im Text die Variable $n$ bereits für die natürlichen Zahlen (und auch für die Anzahl an ungeraden Folgengliedern) benutzt wird, habe ich hierfür die Variable $x$ gewählt. Kapitel 4: Eine ähnliche Formel findet sich bei Garner[2]. Kapitel 8: Korrekterweise muss ich anmerken, dass ich die Struktur von $\backslash delta$ in Satz 7 parallel mit der Entwicklung des Algorithmus erarbeitet habe. Die Erkenntniss bzw. Vermutung, dass sich $\backslash delta$ nur alle 5 oder 6 Terme verändert, konnte ich also nicht schon aus den ersten Beispielen gewinnen. Kapitel 11: Vielen Dank an matph für die PARI/GP Funktion "NextPermutation(a)". Die Tabellen und Programmtexte die hier nur als Bilder zu sehen sind finden sich auch als Text in meinem arXiv-paper[8]. Für den Fall, dass jemand den PARI/GP Code selbst ausprobieren und nicht alles abtippen möchte. [Edit] \(\endgroup\) [Show outline only] Get link to this article   Printer-friendly version -  Choose languageDE EN     Comments   Für diesen Artikel gibt es keine pdf-Datei Write a comment Dieser Artikel ist im Verzeichnis der Arbeitsgruppe Alexandria eingetragen: : Mathematik :: automatisch eingefügt und unbearbeitet : Eine Stoppzeit-Analyse der Collatz 3x + 1 Funktion [von Slash]   Im Mittelpunkt meines zweiten Artikels zum berühmten Collatz 3x + 1 Problem steht die sogenannte "endliche Stoppzeit", die angibt, welches Glied in einer Collatzfolge zum ersten Mal kleiner als seine Startzahl ist. Falls jede Startzahl einer Collatzf [Edit] [Die Arbeitsgruppe Alexandria katalogisiert die Artikel auf dem Matheplaneten]

Aufrufzähler 1993   Aufrufstatistik des Artikels Insgesamt 203 externe Seitenaufrufe zwischen 2015.06 und 2023.12 [Anzeigen] Domain Anzahl Proz https://matheplanet.com 2 1% https://google.com 70 34.5% https://google.de 71 35% http://images.google.de 10 4.9% http://mikewinkler.co.nf 12 5.9% http://www.mikematics.de 6 3% http://google.de 12 5.9% http://google.com 5 2.5% http://www.mikewinkler.co.nf 2 1% https://de.search.yahoo.com 2 1% https://www.bing.com 2 1% http://samsung.de.searchturbo.com 1 0.5% http://www.bing.com 3 1.5% https://google.ch 1 0.5% http://google.com.hk 1 0.5% https://www.qwant.com 1 0.5% https://www.ecosia.org 1 0.5% https://duckduckgo.com 1 0.5% Aufrufer der letzten 5 Tage im Einzelnen Insgesamt 2 Aufrufe in den letzten 5 Tagen. [Anzeigen] Datum Aufrufer-URL 2023.12.03-2023.12.07 (2x) https://matheplanet.com/ Häufige Aufrufer in früheren Monaten Insgesamt 181 häufige Aufrufer [Anzeigen] Datum Aufrufer-URL 2020-2023 (70x) https://google.com/ 2021-2023 (39x) https://google.de/ 2020-2022 (32x) https://google.de 201603-10 (10x) http://images.google.de/url?sa=t&rct=j&q= 2015-2016 (7x) http://mikewinkler.co.nf/index.php/artikel.html 2019-2020 (5x) http://www.mikematics.de/matheplanet-articles/ 201712-12 (5x) http://mikewinkler.co.nf/index.php/matheplanet.html 201506-12 (5x) http://google.de/url?sa=t&rct=j&q= 2016-2017 (4x) http://google.de/ 201604-11 (4x) http://google.com/search [Top of page]

Re: Eine Stoppzeit-Analyse der Collatz 3x + 1 Funktion von: Martin_Infinite am: Do. 25. Juni 2015 10:28:14

\(\begingroup\)Entschuldige, aber bei Zwar ruhen die hier formulierten Sätze auf einem sicheren mathematischen Fundament, doch es werden keine Beweise angegeben. konnte ich nicht weiterlesen. Ein Satz muss bewiesen werden. Alles andere sollte als Vermutung/These/Hypothese/Annahme etc. bezeichnet werden. Wenn du einen Beweis für einen Satz kennst, dann ist es hingegen völlig in Ordnung, diesen als Satz zu bezeichnen, wobei man vielleicht noch ein paar Worte zum Beweis sagen sollte oder wenigstens die Gründe, warum man den Beweis nicht hingeschrieben hat. Auf keinen Fall sollten sich aber Sätze mit Vermutungen vermischen. Wenn du das noch änderst, würde dein Artikel meiner Meinung nach ein erhebliches Maß an Seriösität gewinnen. Was auch in deinen anderen Artikeln nicht so gut berücksichtigt wird: Zahlenbeispiele sind nicht ansatzweise ein Beleg für eine allgemeine Aussage über natürliche Zahlen. Sie sorgen nicht für ein "sicheres mathematisches Fundament". Sie können allenfalls Hoffnung geben, dass man einen Beweis finden könnte, aber in deinem Artikel finden sich (erneut) nicht einmal Beweisansätze. Und es sieht auch nicht so aus, als ob du welche hättest. Nicht, dass man das von dir erwarten könnte! Die Collatz-Vermutung ist ja nicht ohne Grund bis heute ein offenes Problem, an dem sich viele Mathematiker ohne Erfolg probiert haben. Für die Lösung von offenen Problemen ist es sicherlich notwendig, Teilschritte in Form von Vermutungen zu formulieren, aber man sollte sie nicht mit Sätzen verwechseln. In dem zugehörigen arXiv-Preprint von dir halte ich es noch für viel kritischer, die Vermutungen als Theoreme zu bezeichnen. Und es ist auch falsch, im Titel von "results" zu sprechen.\(\endgroup\)