Die Mathe-Redaktion - 22.07.2017 18:30 - Registrieren/Login
Auswahl
Schwarzes Brett
Fragensteller hat Anwort gelesen, aber bisher nicht weiter reagiert2017-07-20 12:58 bb
Alte Mathematikbücher
Aktion im Forum
Suche
Stichwortsuche in Artikeln und Links von Matheplanet
Suchen im Forum
Suchtipps

Bücher
Englische Bücher
Software
Suchbegriffe:
Mathematik bei amazon
Naturwissenschaft & Technik
In Partnerschaft mit Amazon.de
Kontakt
Mail an Matroid
[Keine Übungsaufgaben!]
Impressum

Bitte beachten Sie unsere Nutzungsbedingungen, die Distanzierung, unsere Datenschutzerklärung und
die Forumregeln.

Sie können Mitglied werden oder den Newsletter bestellen.

Der Newsletter Apr. 2017

Für Mitglieder
Mathematisch für Anfänger
Wer ist Online
Aktuell sind 458 Gäste und 24 Mitglieder online.

Sie können Mitglied werden:
Klick hier.

Über Matheplanet
 
Mathematik: Eine Stoppzeit-Analyse der Collatz 3x + 1 Funktion
Freigegeben von matroid am Mi. 24. Juni 2015 18:51:46
Verfasst von Slash -   1557 x gelesen [Gliederung] [Statistik] Druckbare Version Druckerfreundliche Version
Mathematik

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
                                         <math>\displaystyle z_n=\binom{\big\lfloor\frac{5(n-2)}{3}\big\rfloor}{n-2}-\sum_{i=2}^{n-1}\binom{\big\lfloor\frac{3(n-i)+\delta}{2}\big\rfloor}{n-i}\cdot z_i</math>

geheimnisvollen Gleichung zu tun hat, erfahrt Ihr im Artikel.

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 <math>3x + 1</math> Funktion sei definiert als eine Abbildung <math>T:\mathbb{N}\rightarrow\mathbb{N}</math> gegeben durch

                              <math>T(x):=\left\{\begin{array}{lcr}T_0:=\displaystyle{\frac{x}{2}} & \mbox{für gerade} & x,\\ \\T_1:=\displaystyle{\frac{3x+1}{2}} & \mbox{für ungerade} & x.\end{array}\right.</math>

Sei <math>T^0(s)=s</math> und <math>T^k(s)=T\left(T^{k-1}(s)\right)</math> für <math>k\in\mathbb{N}</math>. Dann ist die Collatz-Folge für <math>s\in\mathbb{N}</math> gegeben durch <math>C(s)=\left(T^k(s)\mid k=0,1,2,3,\dotsc\right)</math>.

Beispiel: Für die Startzahl <math>s=11</math> ergibt sich die Collatz-Folge

                              <math>\displaystyle C(11)=(11,17,26,13,20,10,5,8,4,2,1,2,1,2,1,\dotsc).</math>

Eine <math>C(s)</math> 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 <math>s\in\mathbb{N}</math> gerät <math>C(s)</math> in den Zyklus <math>(1,2)</math>.


3. Stoppzeit

Definition 2: Wird in <math>C(s)</math> für eine Startzahl <math>s\in\mathbb{N}</math> nach endlich vielen Iterationsschritten <math>k</math> erstmals eine Zahl <math>T^k(s)<s</math> erreicht, so nennt man dieses <math>k</math> die Stoppzeit von <math>s</math> und bezeichnet sie mit <math>\sigma(s)</math>. Man spricht in diesem Fall auch von "endlicher" Stoppzeit.

Vermutung 1 ist nun äquivalent zu der Aussage, dass alle Startzahlen <math>s>1</math> endliche Stoppzeit besitzen. Dass "fast alle" Startzahlen endliche Stoppzeit besitzen wurde bereits 1979 von Everett[1] und Terras[4] bewiesen.

Für bestimmte Restklassen von Startzahlen sind dabei immer nur ganz bestimmte Stoppzeiten möglich, die durch die reelle Zahl <math>\log_23</math> bestimmt werden. Mit <math>\sigma_n=\lfloor1+n\cdot\log_23\rfloor</math> gilt für alle <math>n\in\mathbb{N},\,n\geq0</math>, dass <math>\sigma(s)=\sigma_n</math> für alle <math>s\equiv x_1,x_2,x_3,\dotsc,x_z\ (mod\ 2^{\sigma_n})</math> ist. Für die ersten <math>n</math> ist dann

          <math>\sigma(s)=1</math>  für alle  <math>s\equiv0\ (mod\ 2)</math>,
          <math>\sigma(s)=2</math>  für alle  <math>s\equiv1\ (mod\ 4)</math>,
          <math>\sigma(s)=4</math>  für alle  <math>s\equiv3\ (mod\ 16)</math>,
          <math>\sigma(s)=5</math>  für alle  <math>s\equiv11,23\ (mod\ 32)</math>,
          <math>\sigma(s)=7</math>  für alle  <math>s\equiv7,15,59\ (mod\ 128)</math>,
          <math>\sigma(s)=8</math>  für alle  <math>s\equiv39,79,95,123,175,199,219\ (mod\ 256)</math>,
          <math>\sigma(s)=10</math>  für alle  <math>s\equiv287,347,367,423,507,575,583,735,815,923,975,999\ (mod\ 1024)</math>,
          usw.

Definition 3:  Für jedes <math>n\geq0</math> sei <math>z_n</math> die Anzahl der Restklassen <math>(mod\ 2^{\sigma_n})</math> mit Stoppzeit <math>\sigma_n</math>. Es ist dann

                    <math>z_0=1,\ z_1=1,\ z_2=1,\ z_3=2,\ z_4=3,\ z_5=7,\ z_6=12,\ z_7=30,\ \dotsc</math>

Die folgende Vermutung soll die letzten Ergebnisse zusammenfassend darstellen.
Vermutung 2: Sei <math>\sigma_n=\lfloor1+n\cdot\log_23\rfloor</math>, dann existiert für jedes <math>n\in\mathbb{N},\,n\geq0</math> eine Menge von <math>z_n\geq 1</math> Restklassen <math>(mod\ 2^{\sigma_n})</math> mit der Eigenschaft, dass alle Startzahlen <math>s</math> aus einer dieser Restklassen Stoppzeit <math>\sigma(s)=\sigma_n</math> haben. Dabei gilt für alle <math>n\geq 6</math> sogar <math>z_{n+1}> 2\cdot z_n</math>.

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 <math>\sigma(s)</math> sind gelistet in der OEIS Folge A020914. Die zugehörigen Restklassen <math>(mod\ 2^{\sigma_n})</math> sind gelistet in der OEIS Folge A177789. Die Anzahl der Restklassen <math>z_n</math> für <math>n\geq1</math> sind gelistet in der OEIS Folge A100982.


4. Eine Stoppzeit-Formel für ungerade Startzahlen

Ob die ungerade Startzahl <math>s</math> einer Collatzfolge <math>C(s)</math> endliche Stoppzeit besitzt ist davon abhängig wie die ersten <math>n</math> ungeraden Folgenglieder in <math>C(s)</math> verteilt sind. Mit ein paar einfachen Überlegungen lässt sich so aus der Iterationsvorschrift eine Stoppzeit-Formel ableiten.
Vermutung 3: Sei <math>C^a(s)=\left(T^k(s)\mid k=0,\dotsc,a\right)</math> mit <math>a\geq1</math> eine endliche Teilfolge von <math>C(s)</math>, und sei <math>\sigma_n=\lfloor1+n\cdot\log_23\rfloor</math>. Dann besitzt eine ungerade Startzahl <math>s</math> für jedes <math>n\in\mathbb{N}</math> die Stoppzeit <math>\sigma(s)=\sigma_n</math>, wenn die zugehörige Teilfolge <math>C^{\sigma_n-1}(s)</math> genau <math>n</math> ungerade Folgenglieder besitzt, und <math>\alpha_i=k</math> ist, genau und nur dann wenn <math>T^k(s</math>) in <math>C^{\sigma_n-1}(s)</math> ungerade ist. Dann gilt

                                        <math>\displaystyle T^{\sigma_n}(s)=\frac{3^n}{2^{\sigma_n}}\cdot s+\sum_{i=1}^n \frac{3^{n-i}2^{\alpha_i}}{2^{\sigma_n}}<T^0(s).\quad\quad\mathbf{(1)}</math>

Beispiel: Für <math>n=4</math> gilt <math>\sigma_4=\lfloor1+4\cdot\log_23\rfloor=7</math>. Für <math>s=59</math> ergibt sich dann mit Gleichung (1)

                              <math>\displaystyle T^{7}(59)=\frac{3^4}{2^7}\cdot59+ \frac{3^3 2^0+3^2 2^1+3^1 2^3+3^0 2^4}{2^7}=38<59.</math>

Begründung: Die Teilfolge <math>C^6(59)=(59,89,134,67,101,152,76)</math> besitzt vier <math>(n=4)</math> ungerade Folgenglieder <math>59,89,67,101</math>. Die Zweierpotenzen <math>\alpha_i</math> ergeben sich dann folgendermaßen: <math>T^0=59</math> ist ungerade, also ist <math>\alpha_1=0</math>. <math>T^1=89</math> ist ungerade, also ist <math>\alpha_2=1</math>. <math>T^2=134</math> ist gerade. <math>T^3=67</math> ist ungerade, also ist <math>\alpha_3=3</math>. <math>T^4=101</math> ist ungerade, also ist <math>\alpha_4=4</math>. <math>T^5=152</math> ist gerade. <math>T^6=76</math> ist gerade.

Die Stoppzeit <math>\sigma(s)=7</math> gilt dann nicht nur für <math>s=59</math>, sondern für alle <math>s\equiv59\ (mod\ 2^7)</math>.


5. Teilfolgen und ihre binäre Vereinfachung

Vermutung 4: Sei <math>m=\big\lfloor\frac{2(n-2)}{3}\big\rfloor</math> und <math>\sigma_n=\lfloor1+n\cdot\log_23\rfloor</math> für alle <math>n\in\mathbb{N},\,n\geq4</math>. Besitzt eine ungerade Startzahl <math>s</math> die Stoppzeit <math>\sigma(s)=\sigma_n</math>, dann repräsentieren nach Vermutung 2 die ersten <math>m+n</math> Folgenglieder in <math>C(s)</math> "zur Genüge" die Stoppzeit von <math>s</math>, da alle weiteren Folgenglieder gerade sind bevor eine Zahl <math>T^{\sigma_n}(s)<s</math> erreicht ist.

Definition 4: Um die Verteilung der geraden und ungeraden Folgenglieder in <math>C(s)</math> zu vereinfachen, repräsentiere "0" ein gerades und "1" ungerades Folgenglied.

Beispiel: Für <math>n=4</math> gilt <math>m=\big\lfloor \frac{2(4-2)}{3}\big\rfloor=1</math> und <math>\sigma_4=\lfloor1+4\cdot\log_23\rfloor=7</math>.

Für die Teilfolgen <math>C^{\sigma_n}(s)</math> gilt dann

          <math>C^7(7)=(7,11,17,26,13,20,10,5)\quad \text{wird vereinfacht durch}\quad (1,1,1,0,1,0,0,1),\\
          C^7(15)=(15,23,35,53,80,40,20,10)\quad \text{wird vereinfacht durch}\quad (1,1,1,1,0,0,0,0),\\
          C^7(59)=(59,89,134,67,101,152,76,38)\quad \text{wird vereinfacht durch}\quad (1,1,0,1,1,0,0,0).</math>

Und für die "zur Genüge verkürzten" Teilfolgen <math>C^{m+n-1}(s)</math> gilt dann

          <math>C^4(7)=(7,11,17,26,13)\quad \text{wird vereinfacht durch}\quad (1,1,1,0,1),\\
          C^4(15)=(15,23,35,53,80)\quad \text{wird vereinfacht durch}\quad (1,1,1,1,0),\\
          C^4(59)=(59,89,134,67,101)\quad \text{wird vereinfacht durch}\quad (1,1,0,1,1).</math>


6. Binäre Tupel

Sei <math>m=\big\lfloor\frac{2(n-2)}{3}\big\rfloor</math> für jedes <math>n\in\mathbb{N},\,n\geq4</math>.

Definition 5: Sei <math>\mathcal{A}(n)</math> ein binäres <math>(m+n-2)</math>-Tupel für jedes <math>n\in\mathbb{N},\,n\geq4</math>, gegeben durch

                                   <math>\mathcal{A}(n)=(a_1, \cdots, a_m,a_{m+1}, \cdots, a_{m+n-2})\\

                                   \text{mit} \quad a_1, \cdots, a_m:=0 \quad \text{und} \quad a_{m+1}, \cdots, a_{m+n-2}:=1.</math>

Definition 6: Sei <math>\mathbb{A}_j(n)</math> die Menge aller Permutationen in lexikographischer Ordnung von <math>\mathcal{A}(n)</math> für jedes <math>n\in\mathbb{N},\,n\geq4</math>, wobei <math>j</math> die Anzahl dieser Tupel für jedes <math>n</math> sei, gegeben durch

                                             <math>\displaystyle{j=\frac{(m+n-2)!}{m!\cdot(n-2)!}=\binom{\big\lfloor\frac{5(n-2)}{3}\big\rfloor}{n-2}.}</math>

Definition 7: Sei <math>\mathcal{B}(n)</math> ein binäres <math>(m+n)</math>-Tupel für jedes <math>n\in\mathbb{N},\,n\geq4</math>, gegeben durch

                                   <math>\mathcal{B}(n)=(b_1, \cdots, b_{m+n})\quad \text{mit} \quad b_1:=1, \ b_2:=1.</math>

Definition 8: Sei <math>\mathbb{B}_j(n)</math> die Menge aller <math>j</math> Tupel <math>\mathcal{B}(n)</math> für jedes <math>n\in\mathbb{N},\,n\geq4</math>, wobei <math>b_3, \cdots, b_{m+n}</math> exakt einem Tupel aus der Menge <math>\mathbb{A}_j(n)</math> entspricht.

Beispiel: Für <math>n=7</math> gilt <math>m=3</math> und <math>j=56</math>. Damit erhalten wir das 8-Tupel <math>\mathcal{A}(7)=(0,0,0,1,1,1,1,1)</math>. Nun existieren 56 Permutationen in lexikographischer Ordnung von <math>\mathcal{A}(7)</math>. Somit besitzt <math>\mathbb{A}_{56}(7)</math> 56 verschiedene 8-Tupel, und <math>\mathbb{B}_{56}(7)</math> besitzt 56 verschiedene 10-Tupel.

Die Tupel der Menge <math>\mathbb{B}_j(n)</math> unterscheiden sich also lediglich durch die zwei zusätzlichen vorderen "1"-Elemente von den Tupeln der Menge <math>\mathbb{A}_j(n)</math>. Anhang 11.2 zeigt dieses Beispiel ausführlich mit allen 56 Tupeln.


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 <math>3^{n-i}2^{\alpha_i}</math> aus Gleichung (1) verteilt sind.

Aus Vermutung 3 folgt, dass für jedes <math>n\in\mathbb{N},n\geq4</math>, nur für die <math>j</math> binären Tupel aus <math>\mathbb{B}_j(n)</math> die Bedingungen von Vermutung 2 und Gleichung (1) erfüllt sind.
Vermutung 5: Sei <math>\sigma_n=\lfloor1+n\cdot\log_23\rfloor</math>. Interpretiert man die binären Tupel aus <math>\mathbb{B}_j(n)</math> als binäre Vereinfachungen der geraden und ungerden Folgenglieder in <math>C^{m+n-1}(s)</math>, dann existiert nach Vermutung 2 für jedes <math>n\in\mathbb{N},\,n\geq4</math>, für jedes binäre Tupel aus <math>\mathbb{B}_j(n)</math> eine eigene diophantische Gleichung

                                                      <math>\displaystyle y=\frac{3^n}{2^{\sigma_n}}\cdot x+\sum_{i=1}^n \frac{3^{n-i}2^{\alpha_i}}{2^{\sigma_n}},\quad\quad\mathbf{(2)}</math>

die genau eine ganzzahlige Lösung <math>(x,y)</math> für <math>0<x<2^{\sigma_n}</math> besitzt, so dass <math>y=T^{\sigma_n}(x)<x</math> in <math>C(x)</math>.

Über die Lösungen von Gleichung (2) lässt sich dann folgendes aussagen.
Vermutung 6: Für jedes <math>n\in\mathbb{N},\,n\geq4</math>, repräsentieren die <math>j</math> Lösungen <math>(x,y)</math> genau <math>j</math> verschiedene Restklassen von Startzahlen <math>s</math> mit endlicher Stoppzeit <math>4\leq\sigma(s)\leq\sigma_n</math>.

Präziser: Für jedes <math>n\in\mathbb{N},\,n\geq4</math>, repräsentieren die <math>j</math> Lösungen genau <math>z_n</math> Restklassen von Startzahlen <math>s</math>  mit endlicher Stoppzeit <math>\sigma(s)=\sigma_n</math>, und genau <math>j-z_n</math> Restklassen von Startzahlen <math>s</math> mit endlicher Stoppzeit <math>4\leq\sigma(s)<\sigma_n</math>. Dabei gilt insbesondere für die <math>z_n</math> Lösungen <math>(x,y)</math> mit <math>\sigma(x)=\sigma_n</math>, dass der Wert von <math>x</math> immer gleich der kleinsten Zahl der Restklasse <math>[x]_{2^{\sigma_n}}</math> ist.

Beispiel: Für <math>n=5</math> gibt es <math>j=10</math> ganzzahlige Lösungen <math>(x,y)</math>. Die folgende Tabelle 1 zeigt die 10 binären Tupel aus <math>\mathbb{B}_{10}(5)</math> und die zugehörigen ganzzahlige Lösungen <math>(x,y)</math>.

Von diesen 10 Lösungen, gibt es <math>z_5=7</math> Lösungen für die <math>x</math> die Stoppzeit <math>\sigma(x)=\sigma_5=8</math> besitzt und <math>10-7=3</math> Lösungen für die <math>x</math> die Stoppzeit <math>4\leq\sigma(x)<8</math> besitzt.

Es gilt <math>211\equiv3\ (mod\ 16)</math>, <math>107\equiv11\ (mod\ 32)</math> und <math>183\equiv23\ (mod\ 32)</math>. Somit repräsentieren diese 10 Lösungen 10 verschiedene Restklassen von Startzahlen <math>s</math> mit endlicher Stoppzeit <math>4\leq\sigma(s)\leq8</math>. Zum Vergleich hier noch einmal die entsprechenden Ergebnisse aus Kapitel 3, wonach

                              <math>\sigma(s)=4</math>  für alle  <math>s\equiv3\ (mod\ 16)</math>,
                              <math>\sigma(s)=5</math>  für alle  <math>s\equiv11,23\ (mod\ 32)</math>,
                              <math>\sigma(s)=8</math>  für alle  <math>s\equiv39,79,95,123,175,199,219\ (mod\ 256)</math>.

Man beachte, dass für <math>\sigma(s)=8</math> die kleinsten Zahlen der 7 Restklassen jeweils mit einem der <math>x</math>-Werte identisch sind.

Die folgende Tabelle 2 zeigt wie sich für <math>n=4,\dots,12</math> die Anzahl der Lösungen <math>(x,y)</math> auf die möglichen Stoppzeiten <math>\sigma(x)</math> verteilen.

Beispiel: Die Tabelle ist wie folgt zu lesen: "Sum" ist identisch mit dem Wert von <math>j</math> und entspricht der Summe der Werte für <math>\sigma(x)</math> für ein bestimmtes <math>n</math>. Für <math>n=5</math> gibt es 1+2+7=10 ganzzahlige Lösungen <math>(x,y)</math>. Davon 7 Lösungen mit <math>\sigma(x)=8</math>, 2 Lösungen mit <math>\sigma(x)=5</math> und 1 Lösung mit <math>\sigma(x)=4</math>. 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 <math>\mathbb{B}_j(n)</math> mit den ganzzahlige Lösungen <math>(x,y)</math> für <math>n=4,\dotsc,7</math>.


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 <math>z_n</math> sind, wie die folgende Tabelle 3 zeigt.

Dabei sind die von <math>z_n</math> 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 <math>n</math> durch die folgenden Binomialkoeffizienten für <math>k\in\mathbb{N}</math> gegeben. Man beachte die unterschiedliche Farbgebung.

Für <math>n=14,\dotsc,19</math> werden zwei weitere Binomialkoeffizienten benötigt.

Die folgende Tabelle 4 zeigt die Werte für <math>n=13,\dotsc,19</math>. 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 <math>n\in\mathbb{N},\,n\geq4</math>, gilt

                                        <math>\displaystyle z_n=\binom{\big\lfloor\frac{5(n-2)}{3}\big\rfloor}{n-2}-\sum_{i=2}^{n-1}\binom{\big\lfloor\frac{3(n-i)+\delta}{2}\big\rfloor}{n-i}\cdot z_i,\quad\quad\mathbf{(3)}</math>

wobei <math>\delta\in\mathbb{Z}</math> verschiedene Werte innerhalb der Summe in Intervallen von 5 oder 6 Termen annimmt.

Beispiel: Für <math>n=13</math> geschieht die Berechnung von <math>z_{13}</math> mit Gleichung (3) wie folgt.



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 <math>z_1,\dotsc,z_{12}</math> vermutlich nicht nur jede weitere dieser Zahlen generiert, sondern auch jede Anzahl aller ganzzahliger Lösungen <math>(x,y)</math> für <math>0<x<2^{\sigma_n}</math> der diophantischen Gleichung (2) mit gleicher Stoppzeit <math>\sigma(x)</math> berechnet. So wie man es in den Tabellen 2 bis 4 sieht.

Das folgende PARI/GP Pogramm 6 zeigt diesen Algorithmus, welcher spaltenweise die Werte von Tabelle 2 für <math>12<n\leq limit</math> ausgibt. Eine Besonderheit dieses Algorithmus ist, dass er ohne die reelle Zahl <math>\log_23</math> auskommt, was für sich allein schon erstaunlich ist. Wolke[14] schreibt hierzu: "Diese Zahl mit ihren großenteils schwer durchschaubaren Eigenschaften tritt in zahlreichen Untersuchungen zum Collatz–Problem auf, und scheint hier von ganz entscheidender Bedeutung zu sein." Sie spielt also eine ganz zentrale Rolle für das dynamische Verhalten der Collatz-Funktion. Der Algorithmus bringt sozusagen Struktur und Ordnung ins Chaos.


Die Korrektheit des Algorithmus für die Werte von <math>z_n</math> wurde mit einem Zähl-Algorithmus von Roosendaal/Noe[5] für alle <math>n\leq10000</math> überprüft. Die Zahl <math>z_{10000}</math> besitzt 4527 Dezimalstellen. Vielleicht muss der Algorithmus für größere Werte von <math>n</math> 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 <math>i</math> und die zugehörigen Werte für <math>\delta</math>. 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 <math>n</math> bzw. <math>limit</math> 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 <math>z_n</math> generieren, so geht dies auch einfacher, wie meine anderen Algorithmen in der OEIS Folge A100982 zeigen. Die einfachste und schnellste Methode beruht auf einer Idee von Hubert Schaetzel, welche allerdings den Ausdruck <math>\log_23</math> benötigt.



10. Eine allgemeine Stoppzeit-Hypothese

Ob eine ungerade Startzahl <math>s</math> endliche Stoppzeit besitzt ist also davon abhängig, wie die ersten <math>m</math> geraden und <math>n</math> ungeraden Folgenglieder in <math>C(s)</math> untereinander verteilt sind. Ohne den Gebrauch von Gleichung (1) lässt sich nun die folgende Vermutung formulieren.
Vermutung 8: Sei <math>m=\big\lfloor \frac{2(n-2)}{3}\big\rfloor</math> und <math>\sigma_n=\lfloor1+n\cdot\log_23\rfloor</math>. Für jedes <math>n\in\mathbb{N},\,n\geq4</math>, besitzt eine ungerade Startzahl <math>s</math> endliche Stoppzeit <math>4\leq\sigma(s)\leq\sigma_n</math>, wenn die binäre Vereinfachung der geraden und ungeraden Folgenglieder der Teilfolge <math>C^{m+n-1}(s)</math> mit einem binären Tupel der Menge <math>\mathbb{B}_j(n)</math> übereinstimmt und die Teilfolge <math>C^{\sigma_n-1}(s)</math> genau <math>n</math> 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 <math>s</math> "ohne" endliche Stoppzeit existieren. Diese Startzahl hätte die Eigenschaft, dass es für jedes <math>n\in\mathbb{N},\,n\geq4</math>, "keine" Übereinstimmung der binären Vereinfachung der geraden und ungeraden Folgenglieder in der Teilfolge <math>C^{m+n-1}(s)</math> und eines binären Tupels der Menge <math>\mathbb{B}_j(n)</math> gibt, oder im Falle einer solchen Übereinstimmung die Teilfolge <math>C^{\sigma_n-1}(s)</math> "keine" <math>n</math> 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.

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 <math>\mathcal{A}(n)</math> generiert.

Programm 1 berechnet alle ganzzahligen Lösungen <math>(x,y)</math> für <math>0<x<2^{\sigma_n}</math> der diophantischen Gleichung (2) für <math>n=7</math>.


Programm 2 berechnet alle ganzzahligen Lösungen <math>(x,y)</math> für <math>0<x<2^{\sigma_n}</math> der diophantischen Gleichung (2) für <math>2\leq n\leq limit</math>.



Programm 3 berechnet alle ganzzahligen Lösungen <math>(x,y)</math> für <math>0<x<2^{\sigma_n}</math> der diophantischen Gleichung (2) für <math>2\leq n\leq10</math> und zählt die Lösungen mit gleicher Stoppzeit <math>\sigma(x)</math>.



Programm 4 ist wie Programm 6, aber gibt eine Liste der Zahlen <math>z_n</math> für <math>12<n\leq limit</math> aus, so wie sie 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 <math>n=7</math> gilt <math>\mathcal{A}(7)=(0,0,0,1,1,1,1,1)</math>. 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 <math>\mathbb{B}_j(n)</math> mit den ganzzahligen Lösungen <math>(x,y)</math> für <math>n=4,\dotsc,7.</math>



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 <math>3x + 1</math> Funktion mit dem <math>\frac{3x + 1}{2}</math> Schritt wird gewöhnlich als <math>3n + 1</math> Funktion bezeichnet. Da aber im Text die Variable <math>n</math> bereits für die natürlichen Zahlen (und auch für die Anzahl an ungeraden Folgengliedern) benutzt wird, habe ich hierfür die Variable <math>x</math> gewählt.

Kapitel 4: Eine ähnliche Formel findet sich bei Garner[2].

Kapitel 8: Korrekterweise muss ich anmerken, dass ich die Struktur von <math>\delta</math> in Satz 7 parallel mit der Entwicklung des Algorithmus erarbeitet habe. Die Erkenntniss bzw. Vermutung, dass sich <math>\delta</math> 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.


Link auf diesen Artikel Link auf diesen Artikel  Druckbare Version Druckerfreundliche Version  Einen Freund auf diesen Artikel aufmerksam machen Weitersagen Kommentare zeigen Kommentare  
pdfFür diesen Artikel gibt es keine pdf-Datei


Arbeitsgruppe Alexandria 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
[Die Arbeitsgruppe Alexandria katalogisiert die Artikel auf dem Matheplaneten]

 
Verwandte Links
 
Besucherzähler 1557
 
Aufrufstatistik des Artikels
Insgesamt 38 externe Besuche zwischen 2017.07 und 2017.07 [Anzeigen]
DomainAnzahlProz
http://matheplanet.com410.5%10.5 %
http://images.google.de1026.3%26.3 %
http://mikewinkler.co.nf718.4%18.4 %
http://google.de821.1%21.1 %
http://google.com410.5%10.5 %
http://google.com.hk12.6%2.6 %
http://www.bing.com37.9%7.9 %
http://samsung.de.searchturbo.com12.6%2.6 %

Aufrufer der letzten 5 Tage im Einzelnen
Insgesamt 3 Aufrufe in den letzten 5 Tagen. [Anzeigen]
DatumAufrufer-URL
2017.07.19-2017.07.20 (3x)https://www.google.de/

Häufige Aufrufer in früheren Monaten
Insgesamt 26 häufige Aufrufer [Anzeigen]
DatumAufrufer-URL
201603-10 (10x)http://images.google.de/url?sa=t&rct=j&q=
2015-2016 (7x)http://mikewinkler.co.nf/index.php/artikel.html
201506-12 (5x)http://google.de/url?sa=t&rct=j&q=
201604-11 (4x)http://google.com/search

[Seitenanfang]

" Mathematik: Eine Stoppzeit-Analyse der Collatz 3x + 1 Funktion" | 5 Kommentare
 
Für den Inhalt der Kommentare sind die Verfasser verantwortlich.

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


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.

 [Bearbeiten]

Re: Eine Stoppzeit-Analyse der Collatz 3x + 1 Funktion
von Slash am Do. 25. Juni 2015 17:02:02


"Entschuldigung" angenommen! wink Ich habe das mit den "Sätzen" geändert. Ob du weiterlesen möchtest bleibt natürlich dir selbst überlassen.

Gruß, Slash

 [Bearbeiten]

Re: Eine Stoppzeit-Analyse der Collatz 3x + 1 Funktion
von ehochipi am Do. 25. Juni 2015 17:23:27


Du schreibst:
Vermutung 1 ist nun äquivalent zu der Aussage, dass alle Startzahlen endliche Stoppzeit besitzen.

Es muss heißen: ...., dass alle Startzahlen s>1 endliche Stoppzeit besitzen. s=1 hat nämlich keine endliche Stoppzeit.

 [Bearbeiten]

Re: Eine Stoppzeit-Analyse der Collatz 3x + 1 Funktion
von Slash am Sa. 11. Juli 2015 19:07:41


@ ehochipi: Ja, danke für den Hinweis.

 [Bearbeiten]

Re: Eine Stoppzeit-Analyse der Collatz 3x + 1 Funktion
von Ex_Mitglied_40174 am Fr. 14. August 2015 14:45:48



 [Bearbeiten]

 
All logos and trademarks in this site are property of their respective owner. The comments are property of their posters, all the rest © 2001-2017 by Matroids Matheplanet
This web site was made with PHP-Nuke, a web portal system written in PHP. PHP-Nuke is Free Software released under the GNU/GPL license.
Ich distanziere mich von rechtswidrigen oder anstößigen Inhalten, die sich trotz aufmerksamer Prüfung hinter hier verwendeten Links verbergen mögen.
Lesen Sie die Nutzungsbedingungen, die Distanzierung, die Datenschutzerklärung und das Impressum.
[Seitenanfang]