Zum Collatz-Problem:  Permutation der Folge 2^i
   Die beantwortete 3n+1 Vermutung 


Eine Einleitung und Details zu dem Thema finden Sie unter:   Neues bei Collatz  
Ebenfalls neu ist:  
Die komprimierte Collatz-Folge    
Ergänzend zu diesen ausführlichen Seiten entschied ich mich für den folgenden Text. Er kann die gewonnenen Erkenntnisse konzentriert vermitteln. Es geht hier nochmals um das Ersetzen und Vertauschen von Divisionen und Multiplikationen bei Collatz-Folgen. In der Kombinatorik wird dafür der Begriff 'Permutation' verwendet. Wiederholungen bitte ich zu entschuldigen, sie dienen dem Verständnis.
   
       

       
Kurzfassung     
  • Jede 3n+1 Folge kann als 'komprimierte' Folge geschrieben werden. Dazu wird für ein beliebiges n gezielt ein späteres, ungerades Folgenglied n' berechnet. Die so gefundenen Stützpunkte werden hier als Coll-Punkte bezeichnet. Der neue Algorithmus ist absolut Collatz-kompatibel. Er zeigt, daß der 3n+1_Folgenverlauf für n nur abhängig ist von den Primfaktoren des endlichen Wertes  n+1. Ein Multiplikationenüberlauf ist daher unmöglich.
    Die Rekursionsformel lautet:

    n' = (((n+1) / 2^j ) * 3^j -1) / 2^e     
    j  und  e  sind die höchsten, im jeweiligen Zähler aufgehenden 2er Potenzen.
  • Aus der Collatz-Basisfolge 2^i entstehen durch gezielte Permutation alle gleichlangen Collatz-Folgen. Das ist der Grund für das sichere Folgenende bei EINS, denn genau dieses Ende der Basisfolge wird nicht permutiert.
        
    ••• Permutieren von Folgen soll hier nicht als 'Arbeitsverfahren' verstanden werden.
           Eine Angabe oder Abbildung permutierter Folgen zeigt den übergeordneter Folgenverlauf
           aller gleichlangen Folgen.    Treffender Name:  'Stammbaum aller Collatz-Folgen'

     
    Es läßt sich zeigen, daß im gesamten Zahlenverlauf bis abzählbar unendlich regelmäßige Häufungen gleichlanger Collatz-Folgen auftreten. Der Ort dieser Folgen wird bestimmt durch die Anzahl der Collatz-Multiplikationen.

    Man findet jeweils die obere Schranke s mit:
    s <= 2^i \ 6^m                         Bedingung:   2^i > 6^m
    i  Anzahl Glieder (Schritte)         m  Anzahl Collatz-Multiplikationen, kann nie überwiegen !
    (Untere Schranke bei ~4/5 der oberen Schranke.)
     
  • Daraus folgt:  Beweis
  

Konkret auf dieser Seite:
Permutation einer beliebigen Collatz-Folge
  und  Nichtkommutative Collatz-Operationen


       Die offene, sehr einfache Kernfrage lautet:

              " Endet die Collatz-Folge für jede Eingabe bei der Eins? "
             
        Die Antwort ist ein klares  Ja !

  • Trivial und doch von entscheidender Bedeutung ist:
    Es gibt 'abzählbar unendlich' viele Collatz-Folgen, deren Verlauf bis zur 1 direkt gegeben ist. Die betreffenden Startzahlen sind reine 2er Potenzen  n=2^i, mit  i>1 . Diese Folgen werden hier Collatz-Basisfolgen genannt. Jede hat i Schritte (Divisionen) und ist selbstverständlich nicht zyklisch (keine Schleife). Der letzte Schritt führt zwingend zu der vorgegebenen EINS. Keine dieser Folgen hat eine Collatz-Multiplikation.
  • Es ist leicht nachprüfbar, daß zu jeder Collatz-Basisfolge eine große, bis sehr große Menge von Collatz-Folgen gehört, die alle die gleiche Länge i haben. Jede dieser Folgen hat  eine bestimmte Anzahl m von Multiplikationen. Bei obigem Link 'Neues bei Collatz' wird im Detail gezeigt: 
    Aus der Collatz-Basisfolge entstehen durch gezielte Permutation (Ersatz und Tausch von Division u. Multiplikation) alle gleichlangen Collatz-Folgen.
    Je größer die Zahl der Multiplikationen, desto kleiner wird die Startzahl n der Collatz-Folge.
    Die Anwendung/Durchführung der Permutation ist in verschiedener Weise möglich, z.B.
    bei einem Folgenaufbau von rechts nach links, also beginnend bei dem Wert 1 .
      •
     In der Literatur wird ein solches Vorgehen beschrieben unter: Collatz-Graph.
      • Denkbar ist auch, gezielt nur wenige Glieder einer (Basis-) Folge zu permutieren.
      • Allg.: Immer wird der linke Teil einer Folge verändert, also ähnlich zu Collatz-Graph.
     
  • Die beste Permutation ist der Normalfall, nach Collatz. Es ist die Folgenentwicklung von links nach rechts, nach gegebener Startzahl. Der sehr einfache Collatz-Algorithmus ist eine perfekte Anweisung zur Permutation der vorgegebenen Basisfolge. Vorgegeben bedeutet jedoch nicht, die Folgenlänge sei vorgegeben oder vorhersagbar!
    Das normale Verfahren 'ab Startzahl' hat den Vorteil, daß während des Folgenaufbaues die zunächst unbekannte Folgenlänge unbegrenzt verlängert wird. Dies geschieht ohne Einwirkung auf das konstante Folgenende mit  "
    ...16,8,4,2,1". Die letzten 4 Schritte werden niemals permutiert, denn das iterative Verfahren bzw. die Permutation bricht ab, wenn die Collatz-Folge in reine 2er Potenzen übergeht, das ist spätestens mit der Zahl 16 der Fall... 16 mod 3=1. Insgesamt werden i Schritte ausgeführt. Damit steht am Ende fest, zu welcher Basisfolge n=2^i die aktuelle Folge gehört. Für die endliche Gliederzahl i existiert keine Obergrenze. 
     
  • Die korrekte Form eines Beweises ist schwierig. Mir ist nicht bekannt, wie in der Kombinatorik vorzugehen wäre. Ich gehe davon aus, daß die unten gegebene Darstellung der Permutationan einer Basisfolge  i=2^10=1024  den Anforderungen genügtEin Übergang auf  2^i, in der Art einer vollständigen Induktion, sollte dem Fachmann möglich sein. Klar beantwortet ist:  
    Jede Collatz-Folge endet mit dem trivialen Ende aller Collatz-Basisfolgen  n=2^i. Dieses Ende ist die EINS, auch dann, wenn die Anzahl der endlichen Schritte i gegen 'abzählbar unendlich' geht.
      
  • Plausibilität
    Unter Die komprimierte Collatz-Folge wird gezeigt, daß jede Collatz-Folge für eine  gegebene Zahl n eindeutig ist, da ihr Verlauf durch die Primfaktoren von n+1, n'+1 ... bestimmt wird. Das bedeutet aber auch: Der Folgenverlauf ist ohne fortgesetzte Primfaktorenanalyse von n+1 nicht vorhersagbar !!!
    Es bestätigte sich der mittlere Verkleinerungsfaktor pro Folgenschritt von ~3/4. 
    Es ist richtig, daß dieses Merkmal alleine nicht als Beweis für die EINS dienen kann, wegen der alten Befürchtung: 
    "Es kann nicht ausgeschlossen werden , daß die Multiplikationen die Divisionen überwiegen." 
    Das ist eindeutig widerlegt, denn nur die Primfaktoren von n+1 bestimmen den Folgenverlauf. Damit ist bekannt, bei welchen Folgen die maximale, endliche Anzahl von Collatz- Multiplikationen auftritt. Es sind die Folgen der Mersenne-Zahlen, mit i Multiplikationen nach Collatz. Siehe nächsten Punkt. Örtlich können die Folgenwerte durch Multiplikationen deutlich steigen. Es wäre aber falsch, daraus abzuleiten, daß sie endlos ansteigen können. Eine Folge kann eventuell sehr lang werden. Mit steigendem i und jedem neuen Glied n bestimmen neue Primfaktoren von n+1 den weiteren Verlauf. Nach bestätigter Theorie - mittlerer Faktor ~3/4 - werden die Werte jeder Folge im Mittel fortlaufend kleiner...
    und gehen über zu kleineren 2er Potenzen und letztlich zu 2^0 = 1. 
     
  • Zu Mersenne-Zahlen:
    Die Collatz-Folge jeder Mersenne-Zahl   2^i -1   beginnt mit einer endlichen Maximalzahl von i Collatz-Multiplikationen, an die sich sofort eine Vielzahl wechselnder Operationen anschließt. Damit kann man gezielt  z.B. 6000 Collatz-Multiplikationen erzeugen, ohne daß es zu einem Überlauf kommt. Natürlich ergibt das eine neue, sehr lange Folge, doch diese endet wieder - über weitere Permutationen - bei der gegebenen EINS aller Basisfolgen !!!
    Siehe:  
    Extreme Collatz-Folge zu n= 2^6000 -1  
      
  • Allgemein gilt ein Beweis als erbracht, wenn es zu einer Vermutung kein Gegenbeispiel gibt, bzw. nicht geben kann. Ein solcher Beweis ist leicht zu führen:
     
    Ein konkretes Gegenbeispiel wäre eine 'unendlich' lange, beliebig aufgebaute Collatz-Folge, die nicht bei 1 endet. Die Folge hätte dann eine zugehörige, ebenfalls 'unendlich' lange Basisfolge. Diese kann es aber im Bereich der natürlichen Zahlen definitionsgemäß nicht geben. Basisfolge und Normalfolge (nach Collatz) bedingen sich gegenseitig. Zu jeder endlichen Basisfolge 2^i (i bis 'abzählbar unendlich') gibt es gleichlange, durch Permutation ableitbare Collatz-Folgen. Sie haben eine Startzahl <2^i und sie haben das durch die Basisfolge vorgegebene, nicht permutierte Ende bei 1.
     
   

Demo   Permutation einer beliebigen Folge              (hier i=10)   
       =  Stammbaum aller Collatz-Folgen mit  i=10  Gliedern (Schritten)    

Das kleine Bild zeigt:  6  ungekürzte, gleich lange Collatz-Folgen    mit  i=10
Die erste der Folgen ist die hier so benannte 
Collatz-Basisfolge mit der
Startzahl  2^i=2^10=1024  ... 10 Divisionen, keine Multiplikation !
( 1024  im dualen Zahlensystem:  10000000000   oder eine 1 mit 10 Nullen )
Symbole im Bild:  
Punkte sind Divisionen, der letzte Punkt ist die Division   2/2=1 .   
Ein Doppelpunkt ist die erste Division nach einer Multiplikation (in Richtung der Folge).
Rufzeichen sind Collatz-Multiplikationen.
 
Collatz 2^10 dual

  10   9   8   7   6   5   4  3  2  1  0    i = Potenz von 2
1024 512 256 128  64  32  16  8  4  2  1      = Collatz-Basisfolge
--->   1   2   3   4   5   6  7  8  9 10      = Zahl der Schritte


Doppelpunkte, bzw. unterstrichene Zahlen >4 haben mod 3 den Rest 1.
Das sind bei Basisfolgen gerade 2er Potenzen, 16 ist die kleinste dieser Zahlen (>4). Trivial: Nur Rest_1_Zahlen folgen auf eine Collatz-Multiplikation!
        
Die Basisfolge 1024 = 
.......... = ..:.:.:... kann alternativ an 3 Stellen permutiert werden, zu
170 = .!:.......    oder  168 = ...!:.....    oder  160 = .:.:.!:... 

Die Collatz-Folge 160 =
.:.:.!:... kann 2x alternierend permutiert werden,  zu
26 = .!:..!:...    oder    24 = ...!:!:...


Weitere
Collatz-gerechte Permutationen sind für 2^10 nicht möglich. 

Theoretisch könnte man 2^30= "..:.:.:.:.:.:.:.:.:.:.:.:.:..." mit Papier und Bleistift so verändern (permutieren), daß alle Folgen mit 30 Gliedern erhalten werden. Man wird bereits bei einigen Multiplikationen scheitern, erst recht bei höheren 2er Potenzen. Völlig anders ist es bei einer Bearbeitung per Programm. 

Noch einfacher - sogar ohne ein Programm - schafft es der gegebene Collatz-Algorithmus. Er ist die denkbar einfachste Permutationsvorschrift. Bei allen Untersuchungen und Beweisüberlegungen hat man übersehen, was dieses Prozedere eigentlich beinhaltet.



Ergänzende Anmerkungen:

         
          Was sind "Nichtkommutative" Collatz-Operationen ?
  • Die ungekürzte Folge der Zahl 27  hat 111 Schritte, davon 41 Multiplikationen.
    Und so sieht die Folge aus, mit Symbolen       ! = Multiplikation    . = Division
         27  !.!..!.!.!.!.!..!..!.!..!.!.!..!.!.!.!..!...!.!.!..!.!..!.!.!.!.!.!...!.!.!.!....!..!..!....!...!.!.!.....!.... 
        Die Folge ist eindeutig. Es gibt nur eine Lösung mit m=41 Multiplikationen.
  • Permutieren wir die ersten 6 Glieder der Folge, erhalten wir 3 neue Lösungen mit
        i=111 und m=40    und 
    n=166  .!.!...!.!.!.!..!..!.!..!.!.!..!.!.!.!..!...!.!.!..!.!..!.!.!.!.!.!...!.!.!.!....!..!..!....!...!.!.!.....!....   111.40
         165  !....!.!.!.!.!..!..!.!..!.!.!..!.!.!.!..!...!.!.!..!.!..!.!.!.!.!.!...!.!.!.!....!..!..!....!...!.!.!.....!....
      111.40    
         164  ..!..!.!.!.!.!..!..!.!..!.!.!..!.!.!.!..!...!.!.!..!.!..!.!.!.!.!.!...!.!.!.!....!..!..!....!...!.!.!.....!....
      111.40
        ( 27  !.!..!.!.!.!.!..!..!.!..!.!.!..!.!.!.!..!...!.!.!..!.!..!.!.!.!.!.!...!.!.!.!....!..!..!....!...!.!.!.....!....   111.41 )
       Nur als Demo - vergrößert dargestellt, in der Regel abwärts permutiert -
                   die ersten 6 Operationen   mit den ersten 6 Gliedern bis n=94:
      166  .!.!..       83  250  125  376  188   94   ...   unterstrichen:  mod 3 = 1
      165  !....!    
    496  248  124    62     31   94   ...    
      164  ..!..!  
       
    82    41  124    62     31   94   ...                   
        27  !.!..!  
         82    41  124    62     31   94   ...   eine Multiplikation mehr !!!

    Nichtkommutativ:   Die Reihenfolge von Division und Multiplikation ist bestimmend.


Zum Abschluß zwei Bilder, die weitere Permutationen zeigen.
Grafik: ungekürzte Folgen     ... gezielt, ungek. Länge  i=33     Multipl.  m= 0 bis 10
••• Jeder Startwert ist etwa ~1/6 des Wertes der Vorzeile  •••    zu: 
( s ~ 2^i / 6^m )
gezielte Permutation

Grafik, Random: gekürzte Folgen       ungekürzte Folgenlänge i=161     Multipliplikationen m= 56
collatz - random

Geschrieben, am 23.6.2009     Willi Jeschke     Copyright © 2012
+ Redigiert in 2009/10