Das Collatz-Problem - Beweis der Vermutung 


Die Devise dieser Homepage lautet: "Kleine Primzahlen... Was nicht im Lehrbuch steht."
Es war notwendig, die Collatz-Frage aus neuer Sicht zu untersuchen. Denn auch in 2010 ist das Collatz-Problem - die 3n+1 Folge - von Interesse und wird immer noch als unbeantwortete Vermutung angesehen. Mit hohem Computeraufwand wurde und wird weltweit nach einem Gegenbeispiel gesucht, bis in hohe Bereiche. Vergeblich! Lediglich etwas hat sich geändert: Angesprochene Mathematiker distanzieren sich heute gerne von der ungelösten Frage, sie sei ja nur eine Spielerei von Collatz gewesen. Man verweist auf die anderen großen Verdienste dieses Mathematikers - oder man formuliert es vorsichtig so:

"Die Frage hat sich bislang als sehr anspruchsvoll erwiesen. Trotz zahlreicher (mehr als 100) Untersuchungen aus der Feder hochkarätiger Mathematiker scheint noch keine Lösung in Sicht zu sein. Es ist daher nicht überraschend, dass man an der Existenz eines nur schulmathematisch begründeten, raschen Lösungsweges Zweifel hegt."      
                                                                ... Einverstanden, bitte lesen Sie den Schlußsatz.
Das Konstrukt von Lothar Collatz - seit fast 80 Jahren bekannt - läßt sich knapp anschreiben.
Für jede natürliche Zahl n>0  (n = Startzahl einer Folge)  gilt:
        n' = 3*n+1  falls n ungerade     ... gleichwertig ist   n' = (3*n+1)/2   ... gekürzte Folge
        n' = n/2       falls n gerade        
Unbewiesen war bis 2009, daß nach endlich vielen Schritten immer der Endwert 1 erreicht wird.
 
Es sind zwei Säulen, die einen Beweis der 'Collatz EINS' stützen. Streng genommen, genügen schon die Erkenntnisse nach Punkt 1 :

1. Neuer Algorithmus zu allen  3n+1 Folgen
    Eine Rekursionsformel wurde gefunden - absolut kompatibel zu der bekannten Collatz-Folge.
    Details unter:   Kompression der Collatz-Folge    
 

Die spezielle Rekursionsformel liefert in der Regel nicht die nächste Collatz-Folgenzahl, sondern meist ein späteres, immer ungerades Folgenglied n', das hier Coll-Punkt benannt werden soll. Es entsteht eine komprimierte Collatz-Folge, die ebenfalls zur 1 führt.
    Der Collatz-Folgenverlauf für jede natürliche (ungerade) Zahl n wird
    eindeutig bestimmt durch die Primfaktoren von n+1.
   
Die Rekursion, geschrieben als eine Art Kettenbruchentwicklung, lautet:

              (n+1)                                        (n+1) / 2^j  ... ist das Produkt der  ungeraden
             --------  * 3^j   -1                                               Primfaktoren von  ( n+1)                 
                2^j    
    n' = -----------------------        oder       n'   = ( ( (n+1) / 2^j ) * 3^j -1) / 2^e
                        2^e                                 _____________________________________
  
Die Nenner 2^j und 2^e sind die größte im jeweiligen Zähler aufgehende Zweierpotenz.
Eine Ableitung finden Sie unten im gelben Kasten.

Eine Diskussion der obigen Rekursionsformel zeigt, daß eine maximale, örtliche Anhäufung von Collatz-Multiplikationen unter bestimmten Bedingungen auftritt, z.B. bei den Mersenne-Zahlen  2^i -1 oder wenn n+1 ein Vielfaches einer hohen Zweier-Potenz ist.
Dazu speziell auch   Extreme Collatz-Folgen zu Mersenne-Zahlen

Allgemein gilt für 3n+1 Folgen: Im Mittel werden die Glieder jeder Folge kleiner. Das ist korrekt und wird in der Literatur auch ausführlich behandelt. Der mittlere Verkleinerungsfaktor liegt bei ca 3/4 . Diese Tatsache der Verkleinerung von n bis zum Wert 1 kann alleine nicht als Beweis gelten, denn ein 'Überwiegen' der Collatz-Multiplikationen war bisher nicht auszuschließen.
Siehe dazu insbesondere  Dr. Wolke, collatz problem.pdf   Zu dieser wichtigen Frage ist ...
 
NEU und von Bedeutung :        
Es läßt sich berechnen/abschätzen, wieviel Collatz-Multiplikationen m in einer Folge auftreten können und wo diese möglichen Folgen mit i Gliedern im Zahlenraum verteilt sind.
Dargestellt in einer speziellen Grafik   Totale zu Collatz
Die Abschätzung der oberen Schranke s für normale Collatz-Folgen mit m Collatz-Multiplikationen wird gefunden mit:

Obere Schranke       i, k  Anzahl Glieder (Schritte)      m  Anzahl Multilpikationen
s = 2^i \ 6^m  ...  normale Folge mit Multiplikationsschritten  (3*n+1)
s = 2^k \ 3^m ...  spezielle Folge mit Multiplikationsschritten (3*n+1)/2                                                                           \ ... Ganzzahl-Division
 ... beide Folgen mit der Bedingung:   s >1   oder   2^i > 6^m   bzw.  2^k > 3^m    

Untere Schranke   s' ~ s * 4/5     ... alles gültig für mögliche Folgen                                  
      Wenn Sie nur etwas Zeit haben, bitte studieren Sie die weiteren Collatz-Seiten unter home.
      Gewisse Überschneidungen sind dabei unvermeidbar.
    
2. Collatz-gerechte Permutation aller Collatz-Folgen beginnend bei der Basisfolge 2^i
 
3. Beweisführung   (Widerspruchsbeweis)  
Allgemein gilt ein Beweis als erbracht, wenn es zu einer Vermutung kein Gegenbeispiel gibt,
bzw. nicht geben kann. Ein solcher Beweis kann nach 1.) und 2.) geführt werden, dazu
 
Lemma:
Jede vorgelegte 3n+1 Zahlenfolge nach Collatz (mit i Gliedern) geht auf eine Basisfolge 2^i zurück und zu jedem 2^i  (i bis 'abzählbar unendlich') gibt es gleich lange, durch gezielte, Collatz-gerechte Permutation ableitbare Collatz-Folgen. Diese haben Startzahlen n<2^i und das schleifenfreie Profil der Collatz-Basisfolge mit dem vorgegebenen, nicht permutierten Ende bei EINS.

Beweis:
Wir treffen die Annahme, es gäbe zu einer natürlichen (Start-) Zahl n eine 'unendlich' lange, beliebig aufgebaute Collatz-Folge, die nicht bei 1 endet. Die Anzahl der Glieder i wäre unendlich. Die Folge hätte dann eine zugehörige, ebenfalls unendlich lange Basisfolge mit einer unendlich großen Startzahl n=2^∞. Diese Zahl stände im Widerspruch zu der ursprünglich gewählten, natürlichen Startzahl n, mit der Konsequenz: Die getroffene Annahme enthält einen Fehler, sie ist falsch. - Eine unendlich lange Collatz-Folge '3n+1' zu einer natürlichen (Start-) Zahl n ist nicht möglich, da diese angenommene Folge keiner endlichen Basisfolge 2^i zuzuordnen ist.  *)    
Die Anzahl i der Folgenglieder kann jedoch beliebig groß werden, bis 'abzählbar unendlich'.

zu *)   Außerhalb des Beweises: Mit hohem Computeraufwand wurden alle Startzahlen  bis  
n ~ 5.76 * 10^18  untersucht (Stand 2009). Ergebnis: Die Längen aller geprüften Collatz-Folgen sind endlich. Es wurde keine Schleifenbildung für 3*n+1 gefunden. Jede Folge kann damit eindeutig einer endlichen Basisfolge 2^i zugeordnet werden.
 
NEU, Aug. 2011, lesen Sie bitte die letzten Erkenntnisse zu  Dezimalfolgen y*n(±1) !!


Ableitung der Rekursion    für bestimmte, ungerade Collatz-Punkte

Jede gerade Zahl kann auf eine ungerade Zahl zurückgeführt werden (2er Division).  
Jede ungerade Zahl läßt sich schreiben            n = k * 2^j -1    
Die nächstgrößere gerade Zahl ist dann       n+1 = k * 2^j
k ist ungerade und >=1           (Mit k=1 und j>1 ist n eine Mersenne-Zahl.)  

Die Rekursion findet man aus                                       n  = k*2^j -1      
und aus der Collatz-Vorschrift für die gekürzte Folge     n' = n*3/2 +1/2
      n' = (k * 2^j -1) * 3/2 +1/2  = (k *2^j *3 -3 +1) / 2 =  k *2^(j-1) *3^1 -1
Für j=1 ist  2^(j-1)=2^0=1  und statt  3^1 wird für  j=1 ... 3^j    
Führt man die Entwicklung weiter für j>1 bestätigt sich diese Beziehung !!
Man erhält den geraden Wert       n' = k*3^j -1 ,   ... aus  n=k*2^j -1 
und mit 2^e als Teiler von n'        n' = k' * 2^e      
damit ist der ungerade, reduzierte Wert     n' = (k *3^j-1) / 2^e
                                                                
    n' = ( ( (n+1) / 2^j ) * 3^j -1) / 2^e    wobei gilt ...
    
    2^j   ist die größte in n+1 aufgehende Zweierpotenz    und            
    2^e  ist die größte in ( (n+1) / 2^j ) * 3^j  -1 aufgehende Zweierpotenz   

 
Bitte klicken Sie auch die knappe Seite an:  Die vier Collatz-Folgen
 
Link:    
An dieser Stelle danke ich Herrn Reinhold Kiebart für die enge Zusammenarbeit in den letzten Jahren. Insbesondere geht die Verknüpfung von 'Collatz und Dualzahlen' direkt auf ihn zurück. Er schrieb das Windowsprogramm, mit dem man den 'Collatz-Stammbaum' studieren kann:  http://www.euroware.de/primzahlen/   Titel: 'Primzahlen oder die Magie der Zahlen' 
     
Über jede Zuschrift freue ich mich - auch über sachliche Kritik.               Danke!
Vielleicht schreibt jemand eine Ergänzung in heute üblicher Notation. 
Noch besser, es würde eine entsprechende Arbeit an einer Universität vergeben.  
Kaum verständlich ist, daß Mathematiker meine Folgerungen /noch/ ignorieren.
Es ist richtig, die obigen Ausführungen fallen aus dem Rahmen bisheriger Untersuchungen.
Aber das 3n+1 Problem hat nun mal einen numerischen Hintergrund, und die Numerik
sollte heute nicht mehr als ein Stiefkind der Mathematik angesehen werden.

21.9.2010   erste Veröffentlichung im April 2009     Willi Jeschke    Copyright © 2009-12
17.8.2011   Siehe:  Extrem viele Dezimal-Folgen - einschließlich der Collatz-Folge