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 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
2. [Bitfolge]1001 wird zu: [neue Bitfolge]1100
3. [Bitfolge]1101 wird zu: [neue Bitfolge]10100
4. 1[Bitfolge](01)01	wird zu: 1[neue Bitfolge](00)00 

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

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 (17, 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. Der Zusammenhang zwischen Fermat- und Mersenne-Zahlen ist, dass 2^k-1 abhängig davon, ob k gerade oder ungerade ist, die entstandene Zahl plus 1 durch 3 teilbar ist. In Collatz-Folgen tauchen allerdings ungerade Zahlen, die durch drei teilbar sind, nur als ungerade Startzahl auf.

Setzt man n = m * 2^k +/- 1 als ungeraden Startwert einer Collatz-Folge, wird 2^k sukzessive mit 3^k ausgetauscht:

Setzt man n = m * 2^k - 1 als ungeraden Startwert einer Collatz-Folge, laufen folgende Schritte ab:

In beiden Fällen bleibt m solange erhalten, bis alle 2en mit 3en ausgetauscht wurden. Damit erklärt sich das teils expotentiale Wachstum innerhalb von manchen Collatz-Reihen. In beiden Fällen, wenn das "Halt" erreicht ist (alle 2en "aufgebraucht" wurden), wird durch erneute Division durch 2 3^k eliminiert und die Primfaktoren von m durch neue ersetzt, wobei das "neue" m' kleiner ist als das m, mit dem gestartet wurde. Es gilt:

${\displaystyle m'<{\tfrac {m*2^{\;\!k}}{3^{\;\!k}}}}${\displaystyle m'<{\tfrac {m*2^{\;\!k}}{3^{\;\!k}}}}

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. Jede Zahl n, die nach den Collatz-Regeln in der Schleife 4-2-1 endet, landet auch bei 4-2-1, wenn n mit 2^k (k von 1 bis ∞) multipliziert 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 ist)
2. Jede ungerade Zahl mit n mod 3 = 2, die nach den Collatz-Regeln in der Schleife 4-2-1 endet, landet auch bei 4-2-1, wenn von n (n+1)/3 abgezogen wird; und weil das Ergebnis wieder eine ungerade Zahl ist, kann Regel Nr. 1 oder Nr. 2 angewandt werden, bzw. je nach dem, was mod 3 von dem Ergebnis ergibt, auch diese Regel oder Regel Nr. 4
3. Jede ungerade Zahl mit n mod 3 = 1, die nach den Collatz-Regeln in der Schleife 4-2-1 endet, landet auch bei 4-2-1, wenn zu n (n-1)/3 addiert wird; und weil das Ergebnis wieder eine ungerade Zahl ist, kann Regel Nr. 1 oder Nr. 2 angewandt werden, bzw. je nach dem, was mod 3 von dem Ergebnis ergibt, auch diese Regel oder Regel Nr. 3
4. Jede ungerade Zahl, die nach den Collatz-Regeln in der Schleife 4-2-1 endet, landet auch bei 4-2-1, wenn n mit (4^k - 1)/3 (Folge A002450 in OEIS) multipliziert wird (im Dualsystem das Anhängen von 01); und weil das Ergebnis wieder eine ungerade Zahl ist, kann diese Regel oder Regel Nr. 1 angewandt werden, bzw. je nach dem, was mod 3 von dem Ergebnis ergibt, auch Regel 2 oder 3