Benutzer:Iovialis/Collatz-Problem

Im Dualsystem erkennt man am letzten Bit, ob eine Zahl gerade oder ungerade ist. Ist dieses 0, ist die Zahl gerade; ist dieses 1, ist die Zahl ungerade. Deshalb kann die Collatz-Funktion auch als eine abstrakte Maschine verstanden werden, die Zeichenketten von Bits verarbeitet.

Ist eine Zahl gerade, wird diese solange durch 2 dividiert, bis das Ergebnis ungerade wird. Dazu sind k Schritte notwendig. Im Binärsystem werden k endende Nullen „gestrichen". Dabei gibt es zwei Fälle, die mit dem Modulo (n mod 4) der Zahl unterschieden werden können:

1.) [Bitfolge 1]0 n mod 4 = 2
2.) [Bitfolge 1](0)0 n mod 4 = 0 mit beliebiger Anzahl an in Klammer gesetzten Nullen

Bei einer geraden Zahl n mod 4 = 2 werden die Folgezahlen nach einer Iteration ungerade und das nächste Glied der Reihe ist kleiner, wird aber danach mit der Vorschrift 3n+1 "verarbeitet". Das nächste Glied der Reihe ist deshalb größer. Aus diesem Grund wird das Collatz-Problem auch teilweise mit der verkürzten Form (3n+1)/2-Problem benannt.

Bei einer geraden Zahl n mod 4 = 0 werden die Folgezahlen nach mindestens zwei Iterationen ungerade und damit ist das nächste ungerade Glied der Folge kleiner als der Startwert der Folge.

Ist eine Zahl ungerade, werden zwei Teilrechnungen durchgeführt. Im Binärsystem wird für eine Verdopplung der Zahl einfach eine Null angehängt. Die Addition sieht deshalb wie folgt aus:

 A = 1[Bitfolge X]1 n
 B = 1[Bitfolge X]0 (2n)
 C = 1 (+1)
 Merker = 1[abhängig von Bitfolge 1]1 
 ————————————————————————————
Ergebnis = 1[neue Bitfolge Y]10 (3n+1)
 ̳ ̳ ̳ ̳ ̳ ̳ ̳ ̳ ̳ ̳ ̳ ̳ ̳ ̳ ̳ ̳ ̳ ̳ ̳ ̳ ̳ ̳ ̳ ̳ ̳ ̳ ̳ ̳

Das X ist ein Bit, das je nach dem ob gesetzt oder ungesetzt Y beeinflusst. Bei der Betrachtung der letzten 4 Bits gibt es 5 Möglichkeiten, die von n mod 4 abhängen:

Mit n mod 4 = 1 werden die Folgezahlen zu n‘ mod 4 = 0 – das nächste ungerade Folgenglied ist kleiner:

1. [Bitfolge]0001 wird zu: [neue Bitfolge]0100 mod 4 = 1
2. [Bitfolge]1001 wird zu: [neue Bitfolge]1100 mod 4 = 3
3. [Bitfolge]1101 wird zu: [neue Bitfolge]10100 mod 4 = 1
4. 1[Bitfolge](01)01	wird zu: 1[neue Bitfolge](00)00 mod 4 = 1 oder 3

Zu Fall 4 ist zu erklären, dass beliebig viele der in Klammern gesetzten 01 zu 00 werden.

Mit n mod 4 = 3 werden die Folgezahlen zu n‘ mod 4 = 2 – das nächste ungerade Folgenglied ist größer:

5. [Bitfolge]0(1)11 wird zu [neue Bitfolge]0(1)10 mod 4 = 1 oder 3

Zu Fall 5 ist zu erklären, dass beliebig viele der in Klammern gesetzten 1 erhalten bleiben.

Fermat-Zahlen haben die Form : ${\displaystyle F_{n}=2^{\;\!2k}+1}${\displaystyle F_{n}=2^{\;\!2k}+1}, was binär wie folgt aussieht (in Klammern die Dezimalzahl und k):

1[k-1 Nullen]1 - Beispiel: 11 (3, k=1), 101 (5, k=2), 10001 (17, k=4), 1000001 (65, k=6), 100000001 (257, k=8)

Mersenne-Zahlen haben folgende Form: ${\displaystyle M_{n}=2^{\;\!k}-1}${\displaystyle M_{n}=2^{\;\!k}-1}, was binär wie folgt aussieht (in Klammern die Dezimalzahl und k):

[k Einsen]1 - Beispiel: 1, (1, k=0), 11 (3, k=1), 111 (7, k=2), 1111 (11, k=3), 11111 (19, k=4), 111111 (31, k=5)

Zieht man von einer Fermat-Zahl 2 ab, erhält man eine der Mersenne-Zahlen mit der Form 2^2k - 1 = 4^k - 1 (Folge A002450 in OEIS). Diese sind durch 3 teilbar, weshalb ${\displaystyle {\tfrac {4^{\;\!k}-1}{3}}}${\displaystyle {\tfrac {4^{\;\!k}-1}{3}}} eine ganze ungerade Zahl ergibt. Dies folgt aus der Tatsache, dass das Teilen einer ungeraden Zahl durch eine ungerade Zahl eine ungerade Zahl ergibt, wenn die Teilung ganzzahlig ist.

In Collatz-Folgen tauchen allerdings Zahlen, die durch drei teilbar sind, entweder nur solange auf, bis sie durch die Rechenvorschriften ungerade werden oder selbst ungerade Startzahl sind.

Setzt man ${\displaystyle n=m*{\tfrac {4^{\;\!k}-1}{3}}}${\displaystyle n=m*{\tfrac {4^{\;\!k}-1}{3}}} als Startzahl für die Collatz-Vorschrift gilt:

1. Das Ergebnis von ${\displaystyle n=m*{\tfrac {4^{\;\!k}-1}{3}}}${\displaystyle n=m*{\tfrac {4^{\;\!k}-1}{3}}} kann nur gerade sein, wenn m gerade ist.
2. Ist das Ergebnis von ${\displaystyle n=m*{\tfrac {4^{\;\!k}-1}{3}}}${\displaystyle n=m*{\tfrac {4^{\;\!k}-1}{3}}} ungerade gibt es zwei für die Collatz-Regel "3n+1" zu betrachtende Fälle, wenn k=0:

   a) Zum einen kann man Fälle der Form 2^x+1 untersuchen (x>0) (entspricht n mod 4 = 1 und bei geradem x einer Fermat-Zahl und bei ungeradem x einer durch drei teilbaren Zahl)

   b) Zum andern kann man Fälle der Form 2^x-1 untersuchen (x>0) (entspricht n mod 4 = 3 und einer Mersenne-Zahl, die bei geradem x durch drei teilbar ist)

3. Ein Sonderfall ist, wenn man eine ungerade Zahl der Form ${\displaystyle n=m*4^{\;\!k}+{\tfrac {4^{\;\!k}-1}{3}}}${\displaystyle n=m*4^{\;\!k}+{\tfrac {4^{\;\!k}-1}{3}}} untersucht (entspricht n mod 4 = 1), die nach der ersten Itteration zu n₁ = 3 * m * 4^k + 4^k wird, damit gerade ist und bis n_3+k = 3 * m + 1 immer wieder halbiert werden kann.

Setzt man n = m * 2^k + 1 (m>1, k>1) als ungeraden Startwert der Collatz-Funktion, wird der Wert bis zur nächsten ungeraden Zahl kleiner:

Setzt man n = m * 2^k - 1 (m>1, k>0) als ungeraden Startwert der Collatz-Funktion, wird 2^k sukzessive mit 3^k ausgetauscht. In diesem Fall bleibt m solange erhalten, bis alle 2en mit 3en ausgetauscht wurden. Damit erklärt sich das teils exponentielle Wachstum innerhalb mancher Collatz-Reihen:

Abhägig von 3^k und m ist die Zahl p weiter durch 2 teilbar und wird mit der nächsten Iteration entweder größer oder kleiner als m.

Die Umkehr der Collatz-Funktion ist vergleichbar mit einer Retrograden Analyse beim Schach, die als Technik eingesetzt wird, um festzustellen, welche Züge zuvor gespielt wurden, um eine bestimmte Stellung zu erreichen. Für die Collatz-Funktion heißt dies, dass analysiert wird, ob und welche möglichen Vorgänger für einen Startwert existieren sowie ob und welche alternativen Startwerte ab wann zu einer gleichen Zahlenfolge führen, die nach wiederholter Anwendung der jeweiligen Rechenvorschriften immer den Zyklus 4-2-1 erreichen.

Dabei gibt es vier Möglichkeiten, zu einem Vorgänger zu kommen:

1. Jeder Vorgänger der Zahl n, die durch die Collatz-Funktion in der Schleife 4-2-1 endet, landet auch bei 4-2-1, wenn der Vorgänger n' mit 2^k (k von 1 bis ∞) berechnet wird; da das Ergebnis gerade wird, kann entweder diese Regel wiederholt werden, oder, wenn das Ergebnis mod 6 = 4 ist, kann 1 abgezogen und das Ergebnis durch 3 geteilt werden (was zu einer ungeraden Zahl führt und Regel 2, 3 oder 4 anwendbar macht).
2. Ein Vorgänger der Zahl n mod 3 = 2, die durch die Collatz-Funktion in der Schleife 4-2-1 endet, landet auch bei 4-2-1, wenn von n der Wert (n+1)/3 abgezogen wird; da das Ergebnis wieder eine ungerade Zahl ist, kann eine der vier Regeln angewandt werden, um einen Vorgänger des Vorgängers zu berechnen.
3. Ein Vorgänger der Zahl n mod 3 = 1, die durch Collatz-Funktion in der Schleife 4-2-1 endet, landet auch bei 4-2-1, wenn zu n der Wert (n-1)/3 addiert wird; da das Ergebnis wieder eine ungerade Zahl ist, kann eine der vier Regeln angewandt werden, um einen Vorgänger des Vorgängers zu berechnen.
4. Ein "Alias" jeder ungeraden Zahl n, die durch die Collatz-Funktion in der Schleife 4-2-1 endet, landet auch bei 4-2-1, wenn n mit 4 multipliziert und dann eins hinzuaddiert wird (im Dualsystem das Anhängen von 01) - die ursprüngliche ungerade Zahl n wird durch das "Alias" ersetzt, aber die nachfolgende ungerade Zahl ist die gleiche wie die des "Alias" von n; da das Ergebnis wieder eine ungerade Zahl ist, kann eine der vier Regeln angewandt werden, um ein "Alias" des "Alias" zu berechnen.