Ausflug ins Dualsystem

Für welche ungerade Zahlen gilt nun `bb "P"_H(n)=1`?
Um diese Frage zu beantworten, empfiehlt sich ein Ausflug ins Dualsystem.

Angenommen, wir haben die Aufgabe, aus 2 einfachen Registern (A und B) eine Rechenmaschine zu bauen, die die Collatz-Folgen nach der `bb "H"`-Funktion berechnen soll. Die Register rechnen mit Dualzahlen und kennen weder Multiplikation oder Division. Sie beherrschen nur Addition, Subtraktion, Kopieren, Verdoppeln und Halbieren (also Shift) und Test auf gesetzte Bits. Wie gehen wir vor?

Zuerst formulieren wir die  `bb "H"`-Funktion ein wenig anders:

` bb "H"_S: NN rarr NN,   n mod 2 -= 1,    bb "H"_S(n)=  bb "S"(4n-(n-1)) `
Die `bb "H"_S`-Funktion ist die Subtraktions-Variante der `bb "H"`-Funktion.
Sie benötigt im Dualsystem weder Addition, Multiplikation noch Division, sondern nur Subtraktion und die Shift-Funktionen

Im Register A befinde sich die Zahl n. Eine Iteration nach der `bb "H"_S`-Funktion besteht nun aus folgenden 5 Schritten:

  1. Kopiere A nach B
  2. Subtrahiere 1 von B
  3. Schiebe A um 2 Stellen nach links (das entspricht der Multiplikation mit 4)
  4. Subtrahiere B von A
  5. Schiebe nun A so lange nach rechts, bis Bit 0 eine 1 enthält (das entspricht der Anwendung der `bb "S"`-Funktion)

Als Abbruchbedingung muss lediglich getestet werden ob A den Wert 1 enthält.

Nun können wir auch die Frage beantworten, für welche Zahlen `bb "P"_H(n)=1` gilt.
Es sind unendlich viele ungerade Zahlen, die im Dualsystem aus einer alternierenden Folge von 1 und 0 bestehen und mit einer 1 enden.

Mit diesem Wissen ist die Beantwortung der Quizfrage "Für wie viele ungerade Zahlen im Bereich zwischen `2^999` und `2^1009` gilt `bb "P"_H(n)=1`?" trivial:
Die korrekte Lösung lautet 5.

Beispiel: Iteration am Beispiel der Dualzahl 101010101 (also Dezimalzahl 341), Änderungen zum vorhergehenden Zustand jeweils in rot:
Schritt   Inhalt Register A   Inhalt Register B
Start 101010101 beliebig
Kopiere A nach B 101010101 101010101
Subtrahiere 1 von B 101010101 101010100
Schiebe A um 2 Stellen nach links 10101010100 101010100
Subtrahiere B von A 10000000000 101010100
Schiebe A nach rechts, bis Bit 0 = 1 1 101010100

Eine weitere Möglichkeit

Für unsere einfache Rechenmaschine können wir die  `bb "H"`-Funktion natürlich auch noch anders formulieren:

` bb "H"_A: NN rarr NN,   n mod 2 -= 1,    bb "H"_A(n)=  bb "S"(2n+n+1) `
Die `bb "H"_A`-Funktion ist die Additions-Variante der `bb "H"`-Funktion.
Sie benötigt im Dualsystem weder Subtraktion, Multiplikation noch Division, sondern nur Addition und die Shift-Funktionen

Im Register A befinde sich die Zahl n. Eine Iteration nach der `bb "H"_A`-Funktion besteht aus folgenden 5 Schritten:

  1. Kopiere A nach B
  2. Addiere 1 zu B
  3. Schiebe A um 1 Stelle nach links (das entspricht der Multiplikation mit 2)
  4. Addiere B zu A
  5. Schiebe nun A so lange nach rechts, bis Bit 0 eine 1 enthält (das entspricht der Anwendung der `bb "S"`-Funktion)

Als Abbruchbedingung muss lediglich getestet werden ob A den Wert 1 enthält.

Die 3 `bb "H"`-Funktionen machen rechnerisch ja alle das Gleiche, aber für das einfache Verstehen der Zusammenhänge im Dualsystem empfiehlt es sich, die `bb "H"_S`-Funktion zu verwenden, wenn die Dualzahl mehr Ziffern 1 als Ziffern 0 aufweist, und die `bb "H"_A`-Funktion, wenn es umgekehrt ist.

Nun können wir die Collatz-Vermutung auch mal völlig anders formulieren:

Lemma 3

Es ist nicht möglich, eine Zahl anzugeben, die bei wiederholter Anwendung der `bb "H"`-Funktion NICHT in eine Zahl übergeht, die im Dualsystem aus einer alternierenden Folge von 1 und 0 besteht.

Da alle möglichen Kombinationen mit bis zu 68 Stellen im Dualsystem bereits getestet wurden, fällt es schwer sich vorzustellen, dass eine größere Zahl ein anderes Verhalten zeigen kann. Zumal es dann unendlich viele solcher Zahlen geben müsste. Aber dazu später mehr.

Vielleicht findet sich ja jemand, der diese Variante der Collatz-Vermutung beweisen möchte.