Urbild-Mengen ungerader natürlicher Zahlen bezüglich der kompakten Collatz-Funktion

Vorbemerkungen

Rahmen der Betrachtung

Betrachtet wird die Collatz-Funktion ausschließlich für ungerade natürliche Zahlen, also die Menge

\[\mathbb{N}_u = \{n_u \in \mathbb{N} \mid n_u = 2n – 1,\; n \in \mathbb{N} \}\].

Definition: dyadische Bewertung

Die Funktion \(\nu_2(n)\) bezeichnet die dyadische Bewertung (auch: Zweier-Exponent oder 2-Adizität) einer natürlichen Zahl \(n\), also:

\[\boxed{\nu_2(n) := \max \left\{ k \in \mathbb{N}_0 \;\middle|\; 2^k \text{ teilt } n \right\}}\]

Mit anderen Worten:

• \(\nu_2(n)\) ist der größte Exponent \(k\), für den gilt: \[2^k \mid n, \quad \text{aber} \quad 2^{k+1} \nmid n\]

Man nennt \(\nu_2(n)\) auch die Anzahl der Faktoren 2 in der Primfaktorzerlegung von \(n\).

Beispielrechnungen

\(n\)	Primfaktorzerlegung	\(\nu_2(n)\)
12	\(2^2 \cdot 3\)	2
40	\(2^3 \cdot 5\)	3
21	\(3 \cdot 7\)	0
64	\(2^6\)	6
3c + 1 = 22	\(2 \cdot 11\)	1

Nicht-iterative Berechnungsvorschrift

Die dyadische Bewertung kann effizient ohne Schleife bestimmt werden, indem man die binäre Darstellung von nnn verwendet:

\[\boxed{\nu_2(n) = \text{Anzahl der abschließenden Nullen in der Binärdarstellung von } n}\]

Implementierungsidee (Bittrick)

Für \(n \in \mathbb{N}\): \[\nu_2(n) = \text{Anzahl der niedrigstwertigen Nullbits} = \text{Position des niedrigst gesetzten Einsbits von } n\]

Dies kann berechnet werden als:

\[\boxed{\nu_2(n) = \text{bit_length}((n \,\&\, -n)) – 1}\]

Erklärung:

• \(n \,\&\, -n\) isoliert das niedrigstwertige gesetzte Bit von \(n\)
• \(\text{bit_length}\) liefert die Position des höchsten gesetzten Bits
• Durch \(-1\) erhält man den Exponenten

Beispiel (Python-artig):

def nu2(n):
return (n & -n).bit_length() - 1

Beispiel:

Für \(n = 40\):

• \(40 = 2^3 \cdot 5\) ⇒ \(\nu_2(40) = 3\)
• Binär: \(40_{2} = 0b101000\)
• Drei abschließende Nullen ⇒ \(\nu_2(40) = 3\)

Definition: asymptotische obere Schranke \(\mathcal{O}(f(x))\)

Die Schreibweise \(\mathcal{O}(f(x))\) ist eine landausche Notation, auch bekannt als „Big-O-Notation“. Sie dient zur asymptotischen Abschätzung des Wachstumsverhaltens von Funktionen oder Mengen.

Die Aussage:

\[g(x) \in \mathcal{O}(f(x)) \quad \text{für } x \to \infty\]

bedeutet formal:

Es existieren Konstanten \(C > 0\) und \(x_0 \in \mathbb{R}\), sodass für alle \(x > x_0\)​ gilt:

\[|g(x)| \leq C \cdot |f(x)|\]

Mit anderen Worten: \(g(x)\) wächst asymptotisch höchstens so schnell wie \(f(x)\) (ab einer gewissen Schranke \(x_0\)​).

Kontext: Collatz-Funktion für ungerade Zahlen

Die Collatz-Funktion ist in der üblichen Definition:

\[f(n) = \begin{cases} n/2 & \text{wenn } n \text{ gerade} \\ 3n + 1 & \text{wenn } n \text{ ungerade} \end{cases}​\]

Da nur ungerade Zahlen interessieren, ist es sinnvoll, eine modifizierte Funktion zu betrachten, die von ungerader Zahl zu ungerader Zahl geht, wobei Zwischenschritte mit geraden Zahlen ausgelassen oder implizit „komprimiert“ werden.

Das bedeutet:

• Ausgehend von einer ungeraden Zahl \(c \in \mathbb{N}_u\)​ wird der Wert \(3c + 1\) berechnet,
• danach werden alle Zweierpotenzen herausdividiert, um zur nächsten ungeraden Zahl zu gelangen.

Kompakte Collatz-Funktion

Die kompakte Version der Collatz-Funktion \(C(c)\) für ungerade natürliche Zahlen lautet:

\[C(c) = \frac{3c + 1}{ \nu_2(n)}\]

Beispiel:

• \(c = 7\)
• \(3 \cdot 7 + 1 = 22\)
• \(22/2=11 \rightarrow ungerade \Rightarrow C(7)=11\)

Urbildmengen von \(c \in\mathbb{N}_u\) unter \(C(c)\)

Empirisch lässt sich feststellen, dass es Mengen von Collatzzahlen gibt, die mit einer Anwendung der kompakten Collatzfunktion auf einen gemeinsamen Collatz-Nachfolger abgebildet werden.

Das Ziel ist, diese Urbildmengen formal zu beschreiben. Es handelt sich um die Mengen \[\mathcal{C}^{-1}(c‘) := \{ c \in \mathbb{N}_u \mid \mathcal{C}(c) = c‘ \}\]

Prüfung:

• Die kompakte Collatz-Funktion für ungerade \(c\) ist definiert als:

\[\mathcal{C}(c) = \frac{3c + 1}{2^{\nu_2(3c + 1)}}​\]

• Rückwärts: Wenn \(\mathcal{C}(c) = c’\), dann muss gelten:

\[3c + 1 = 2^k \cdot c‘ \Rightarrow c = \frac{2^k \cdot c‘ – 1}{3}\]

• Damit der Ausdruck \(c\) ganzzahlig ist, muss \(2^k \cdot c‘ \equiv 1 \mod 3\) gelten.
• Da auf ungerade \(c\) beschränkt wurde, gilt zusätzlich: \(c \equiv 1 \mod 2\)

Ziel: Beschreibung aller \(c \in\mathbb{N}_u\), für die die \(C(c)\) denselben Wert ergibt

Gegeben \(c’\), suche alle \(\mathbb{N}_u\)​, für die gilt:

\[\frac{3c + 1}{2^k} = c‘ \quad \Rightarrow \quad 3c + 1 = 2^k \cdot c’\]

Daraus ergibt sich:

\[c = \frac{2^k \cdot c‘ – 1}{3}​\]

Nebenbedingung: \(c \ in \mathbb(N)_u\)

Damit \(c\) natürlich und ungerade ist, müssen gelten:

1. \(2^k \cdot c‘ – 1 \equiv 0 \mod 3\)
2. \(\frac{2^k \cdot c‘ – 1}{3} \in \mathbb{N}_u\)​

Formel zur Konstruktion aller Urbild-Elemente

\[\mathcal{C}^{-1}(c‘) = \left\{ \frac{2^k \cdot c‘ – 1}{3} \;\middle|\; k \in \mathbb{N},\; 2^k \cdot c‘ \equiv 1 \mod 3,\; \text{und } \text{Ergebnis ungerade} \right\}\]

Diese Formel beschreibt alle \(c \in \mathbb{N}_u\)​, die auf ein gegebenes \(c’\) abgebildet werden. Die Bedingung \(2^k \cdot c‘ \equiv 1 \mod 3\) sichert die Ganzzahligkeit.

Beispiel: c′=1

Gesucht: Alle \(c\) mit \(C(c) = 1\)

Setze in die Formel ein:

\[c = \frac{2^k \cdot 1 – 1}{3} = \frac{2^k – 1}{3}\]​

Nun suche alle \(k\), sodass \(2^k \equiv 1 \mod 3\)

Da \(2^1 = 2 \mod 3\), \(2^2 = 4 \equiv 1 \mod 3\), \(2^4 = 16 \equiv 1 \mod 3\), usw.

⇒ \(k \equiv 2 \mod 2\), also gerade Exponenten.

Also:

• \(k = 2 \Rightarrow c = (4 – 1)/3 = 1\)
• \(k = 4 \Rightarrow c = (16 – 1)/3 = 5\)
• \(k = 6 \Rightarrow c = (64 – 1)/3 = 21\)
• usw.

Dies ergibt die Urbildmenge: \(\mathcal{C}^{-1}(1) = \left\{ \frac{2^{2n} – 1}{3} \;\middle|\; n \in \mathbb{N} \right\}\)

Verallgemeinerte iterative Formel

Für gegebenes \(c’\), kann die Urbildfolge rekursiv beschrieben werden durch:

\[c_n = \frac{2^{k_n} \cdot c‘ – 1}{3}\]​

wobei die \(k_n\)​ die kleinsten natürlichen Zahlen sind mit:

• \(2^{k_n} \cdot c‘ \equiv 1 \mod 3\)
• \(c_n\)​ ungerade und ganzzahlig

Zusammenfassung

Formale Beschreibung der Urbildmengen:

\[\mathcal{C}^{-1}(c‘) = \left\{ c \mathbb{N}_u \;\middle|\; \exists k \in \mathbb{N}: c = \frac{2^k c‘ – 1}{3},\; 2^k c‘ \equiv 1 \mod 3,\; c \text{ ungerade} \right\}\]

Kompakte Formel bei bestimmten \(c’\):

Wenn \(c‘ = 1\), ergibt sich: \(c_n = \frac{2^{2n} – 1}{3},\; n \in \mathbb{N}\)

Diese ergibt eine explizite und wachsende Folge ungerader Zahlen, die alle auf 1 abgebildet werden.

Unvollständigkeit der Urbildmengen für alle ungeraden natürlichen Zahlen

Nicht jede ungerade natürliche Zahl \(c‘ \mathbb{N}_u\)​ besitzt ein Urbild unter der kompakten Collatzfunktion. Ein Urbild \(c \mathbb{N}_u\)​ existiert genau dann, wenn sich für ein \(k \in \mathbb{N}\) die Gleichung

\[c = \frac{2^k \cdot c‘ – 1}{3}\]​

mit ganzzahligem und ungeradem Ergebnis lösen lässt. Damit der Ausdruck ganzzahlig ist, muss der Zähler \(2^k \cdot c‘ – 1\) durch 3 teilbar sein. Dies ist äquivalent zur Kongruenz: \(2^k \cdot c‘ \equiv 1 \mod 3.\)

Ob eine Zahl \(c’\) diese Bedingung erfüllt, hängt ausschließlich von ihrem Rest bei Division durch 3 ab:

• Ist \(c‘ \equiv 0 \mod 3\), dann gilt \(2^k \cdot c‘ \equiv 0 \mod 3\) für alle \(k\), sodass die Bedingung nicht erfüllt ist. In diesem Fall besitzt \(c’\) kein Urbild.
• Ist \(c‘ \equiv 1 \mod 3\) oder \(c‘ \equiv 2 \mod 3\), dann existiert stets mindestens ein \(k \in \mathbb{N}\), das die Bedingung erfüllt. In diesen Fällen besitzt \(c’\) eine unendliche Urbildmenge.

\(c‘ \mod 3\)	Verhalten von \(2^k \cdot c‘ \mod 3\)	Wann gilt \(2^k \cdot c‘ \equiv 1 \mod 3\)?
0	Immer 0	Nie ⇒ \(\mathcal{C}^{-1}(c‘) = \emptyset\)
1	Zyklus: \(2^1 \cdot 1 = 2,\; 2^2 = 4 \equiv 1\)	\(k \equiv 2 \mod 2\) ⇒ gerade \(k\)
2	Zyklus: \(2^1 \cdot 2 = 4 \equiv 1\)	\(k \equiv 1 \mod 2\) ⇒ ungerade \(k\)

Fazit

Genau die ungeraden natürlichen Zahlen, die nicht durch 3 teilbar sind, besitzen eine Urbildmenge unter der kompakten Collatzfunktion. Die Urbildmenge ist dann gegeben durch:

\[\mathcal{C}^{-1}(c‘) = \left\{ \frac{2^k \cdot c‘ – 1}{3} \;\middle|\; k \in \mathbb{N},\; 2^k \cdot c‘ \equiv 1 \mod 3 \right\}\]

Diese Menge enthält unendlich viele ungerade natürliche Zahlen. Hingegen ist \(\mathcal{C}^{-1}(c‘) = \emptyset\) genau dann, wenn \(c‘ \equiv 0 \mod 3\).

Kleinstes Element der Urbildmenge

Hinweis:
Im weiteren werden nur die Fälle betrachtet, in denen \(\mathcal{C}^{-1}(c‘)\neq\emptyset\).

Für jede Urbildmenge \(\mathcal{C}^{-1}(c‘)\) mit \(c‘ \not\equiv 0 \mod 3\) lässt sich aus dem kleinsten Element \(c_0\)​ eine unendliche Folge \(\{ c_i \}_{i \in \mathbb{N}_0}\)​​ konstruieren, in der jedes Element ein Urbild von \(c’\) unter der kompakten Collatzfunktion ist. Diese Folge lässt sich durch eine rekursive Formel der Gestalt \(c_{i+1} = f(c_i)\) beschreiben, wobei sich \(f\) auf einfache Weise aus der Struktur der zugrundeliegenden Exponenten \(k_i\)​ ergibt.

Aufbau der Urbildfolge

Jedes Element der Urbildmenge hat die Form: \(c_i = \frac{2^{k_i} \cdot c‘ – 1}{3}\).​

Dabei sind alle \(k_i \in \mathbb{N}\) genau diejenigen Exponenten, für die \(2^{k_i} \cdot c‘ \equiv 1 \mod 3\) gilt. Diese Bedingung ist notwendig, damit der Bruch ganzzahlig ist. Für ein gegebenes \(c‘ \not\equiv 0 \mod 3\) ergibt sich daraus eine unendliche Folge von Exponenten \(k_i\)​, die eine arithmetische Folge mit Differenz 2 bilden: \(k_i = k_0 + 2i\)

Die Struktur der \(k_i\)​ wird durch die Restklasse von \(c‘ \mod 3\) bestimmt:

• Für \(c‘ \equiv 1 \mod 3\) sind alle gültigen \(k_i\)​ gerade.
• Für \(c‘ \equiv 2 \mod 3\) sind alle gültigen \(k_i\)​ ungerade.

Die Differenz zwischen den Exponenten aufeinanderfolgender Urbilder beträgt in beiden Fällen \(k_{i+1} – k_i = 2\).

Rekursive Formel für \(c_{i+1}\)​

Die allgemeine Rekursionsformel ergibt sich direkt durch Einsetzen der Urbilddefinition:

\[3c_i + 1 = 2^{k_i} \cdot c‘ \quad \Rightarrow \quad 3c_{i+1} + 1 = 2^{k_{i+1}} \cdot c‘ = 4 \cdot 2^{k_i} \cdot c‘ = 4 \cdot (3c_i + 1)\]

Daraus folgt: \(c_{i+1} = \frac{4 \cdot (3c_i + 1) – 1}{3} = 4c_i + 1\)

Diese einfache lineare Rekursionsformel gilt daher für alle Urbildmengen, unabhängig davon, ob die zugrundeliegenden \(k_i\)​ gerade oder ungerade sind.

Fazit

Für jede Urbildmenge \(\mathcal{C}^{-1}(c‘)\) mit \(c‘ \not\equiv 0 \mod 3\) gilt:

• Die Urbildfolge \({ c_i }\) lässt sich durch \(k_i = k_0 + 2i\) beschreiben.
• Die Restklasse von \(c‘ \mod 3\) bestimmt, ob die \(k_i\)​ gerade oder ungerade sind.
• Die Folge der Urbilder ist durch die lineare Rekursion \[\boxed{c_{i+1} = 4c_i + 1}\] vollständig beschreibbar.

Diese Formel erzeugt aus dem kleinsten Urbildelement \(c_0\)​ alle weiteren Urbilder von \(c’\).

Restklassen-Betrachtungen für die Urbildmenge

Die Analyse der Urbildmengen \(\mathcal{C}^{-1}(c‘)\) unter der kompakten Collatzfunktion gewinnt erheblich an Tiefe durch eine Betrachtung der Restklassen modulo geeigneter Zahlen. Solche Restklassen erlauben Aussagen über die Existenz, Struktur, Periodizität und das Verhalten der Folgeglieder \(c_i\)​, welche die Urbildmenge bilden.

Besonders relevant sind dabei die Moduli \(3, 2, 4, 8\) und allgemein \(2^k\).

Restklasse modulo 3 – Existenzbedingung

Die Urbildformel \[c = \frac{2^k \cdot c‘ – 1}{3}\] setzt voraus, dass der Zähler durch 3 teilbar ist, also \(2^k \cdot c‘ \equiv 1 \mod 3\).

Daraus folgt:

• Für \(c‘ \equiv 0 \mod 3\): keine Lösung, die Urbildmenge ist leer.
• Für \(c‘ \equiv 1 \mod 3\): gültige Exponenten \(k\) sind alle gerade.
• Für \(c‘ \equiv 2 \mod 3\): gültige Exponenten \(k\) sind alle ungerade.

Prüfung:

• mod 3: Die Bedingung \(2^k \cdot c‘ \equiv 1 \mod 3\) ist nur lösbar, wenn \(c‘ \not\equiv 0 \mod 3\).
  Die Ordnung von 2 modulo 3 ist 2, also:
  • Wenn \(c‘ \equiv 1 \mod 3\): \(2^k \equiv 1 \Rightarrow k\) gerade
  • Wenn \(c‘ \equiv 2 \mod 3\): \(2^k \equiv 2 \Rightarrow k\) ungerade
• mod 8: Die Rekursion \(c_{i+1} = 4c_i + 1\) ⇒
  Wenn \(c_i \equiv r \mod 8\), dann \(4c_i \equiv 4r \mod 8\), und \(c_{i+1} \equiv 4r + 1 \mod 8\).
  Für beliebige ungerade Startwerte \(c_0 \in \{1,3,5,7\}\), ergibt sich ab \(i = 1\) immer \(c_i \equiv 5 \mod 8\)

Diese Bedingung steuert sowohl die Existenz als auch die Struktur der Urbildmengen.

Restklasse modulo 2 – Sicherstellung ungerader Urbilder

Da nur ungerade natürliche Zahlen \(c \in \mathbb{N}_u\)​ betrachtet werden, ist stets zu prüfen, ob der Ausdruck \(\frac{2^k \cdot c‘ – 1}{3}\) selbst ungerade ist. Dies ergibt sich direkt aus den Eigenschaften von \(2^k \cdot c’\) und stellt sicher, dass das Ergebnis innerhalb von \(\mathbb{N}_u\) liegt. Tatsächlich ist für gültige \(c‘ \not\equiv 0 \mod 3\) jedes so erzeugte \(c\) ungerade.

Restklasse modulo 4 – Rekursionsstruktur

Die rekursive Bildung der Urbildfolge folgt: \(c_{i+1} = 4c_i + 1\).

Da \(4c_i \equiv 0 \mod 4\), ergibt sich: \(c_{i+1} \equiv 1 \mod 4 \quad \text{für alle } i \ge 1\).

Sobald \(c_0\)​ gegeben ist, sind alle weiteren Folgenglieder in der Restklasse 1 modulo 4.

Restklasse modulo 8 – Stabilität der Folgenglieder

Die Betrachtung der Urbildfolge \(c_i\)​ modulo 8 zeigt eine besonders konvergente Struktur. Für beliebiges \(c_0 \in \mathbb{N}_u\)​, also \(c_0 \equiv r \mod 8\) mit \(r \in \{1, 3, 5, 7\}\), ergibt sich:

\[c_1 = 4c_0 + 1 \equiv 5 \mod 8\].

In allen Fällen ist: \(c_i \equiv 5 \mod 8 \quad \text{für alle } i \ge 1\).

Die Folge stabilisiert sich ab dem ersten Folgenglied auf die Restklasse 5 modulo 8. Diese Eigenschaft ist unabhängig vom Startwert \(c_0\)​, solange dieser ungerade ist.

Restklassen der Zweierpotenzstruktur

Die Potenzstruktur in \(3c + 1\) führt zur Betrachtung der dyadischen Bewertung \(\nu_2(3c + 1)\). Diese ist direkt durch \(c \mod 2^m\) beeinflusst. Gewisse Restklassen erzeugen höhere \(\nu_2\)​-Werte, also tiefere Reduktionen in der kompakten Collatzfunktion. Damit lässt sich die „Tiefe“ der Abbildung aus dem Wertbereich der Urbildfolge ableiten.

Fazit

Für die Analyse und Konstruktion von Urbildmengen unter der kompakten Collatzfunktion sind insbesondere folgende Restklassenmoduli von Bedeutung:

Modul	Bedeutung
\(\mod 3\)	Existenz der Urbildmenge, Steuerung der gültigen Exponenten \(k\)
\(\mod 2\)	Sicherung der Zugehörigkeit zu \(mathbb{N}_u\)
\(\mod 4\)	Ab dem zweiten Glied stets \(\equiv 1 \mod 4\)
\(\mod 8\)	Ab dem ersten Schritt stets \(\equiv 5 \mod 8\)
\(\mod 2^k\)	Beeinflusst den Wert von \(\nu_2(3c + 1)\)

Diese Restklassen strukturieren die Urbildmengen, erklären auftretende Muster und liefern Kriterien für rekursive Bildung, Zyklizität und Klassifikation.

Partitionierung der ungeraden natürlichen Zahlen durch die Urbildmengen

Die Urbildmengen \(\mathcal{C}^{-1}(c‘)\) der kompakten Collatzfunktion bilden keine vollständige Partitionierung der Menge der ungeraden natürlichen Zahlen \(\mathbb{N}_u = \{1, 3, 5, 7, \dots\}\).

Das bedeutet:
Es gibt ungerade natürliche Zahlen, die in keiner Urbildmenge vorkommen, also für kein \(c’\) ein Urbild sind.

Begründung im Detail

Die kompakte Collatzfunktion:

\[\mathcal{C}(c) = \frac{3c + 1}{2^{\nu_2(3c + 1)}}\]​

ist definiert für \(c \in \mathbb{N}_u\)​, also ungerade natürliche Zahlen. Sie bildet stets auf eine ungerade natürliche Zahl ab. Man könnte also vermuten, dass sich die Urbildmengen \(\mathcal{C}^{-1}(c‘)\) zu einer vollständigen Zerlegung von \(\mathbb{N}_u\)​ zusammensetzen.

Doch das ist nicht der Fall, denn:

Nicht jede ungerade natürliche Zahl​ ist das Urbild einer anderen ungeraden natürlichen Zahl

• Sei \(c \in \mathbb{N}_u\)​ gegeben.
• Prüfen wir, ob es ein \(c‘ \in \mathbb{N}_u\) gibt mit \(\mathcal{C}(c‘) = c\).
• Dazu müsste gelten:

\[c = \frac{3c‘ + 1}{2^{\nu_2(3c‘ + 1)}} \Rightarrow 3c‘ + 1 = 2^k \cdot c \Rightarrow c‘ = \frac{2^k \cdot c – 1}{3}\]​

• Diese Rückrechnung führt nicht immer auf ein ganzzahliges Ergebnis.
• Es existieren also Werte \(c \in \mathbb{N}_u\), für die keine Zahl \(c‘ \in \mathbb{N}_u\)​ existiert, deren kompakte Collatzabbildung \(c\) ergibt.

Beispiel

• Setze \(c = 3\), frage: Gibt es ein \(c‘ \in \mathbb{N}_u\)​ mit \(\mathcal{C}(c‘) = 3\)?
• Rückrechnungsformel: \[c‘ = \frac{2^k \cdot 3 – 1}{3}\] → \(2^k \cdot 3 \equiv 1 \mod 3 \Rightarrow 0 \equiv 1 \mod 3\)
• Für alle \(k\) gilt: \(2^k \cdot 3 \equiv 0 \mod 3\) ⇒ nie ganzzahlig

⇒ \(c = 3\) hat kein Urbild ⇒ gehört zu keiner Urbildmenge

Mathematisch präzise:

Die Menge der Urbilder aller \(c‘ \in \mathbb{N}_u \setminus 3\mathbb{N}\) ist:

\[U = \bigcup_{c‘ \not\equiv 0 \mod 3} \mathcal{C}^{-1}(c‘) \subsetneq \mathbb{N}_u\]​

Diese Vereinigung ist eine echte Teilmenge:
Es gilt:

\[∅N_u \setminus U \ne \emptyset\]

Die Menge der ungeraden natürlichen Zahlen wird also nicht vollständig durch die Urbildmengen überdeckt.

Struktur der Lücken

Die Ergänzungsmenge \(\mathbb{N}_u \setminus U\) besteht aus jenen ungeraden Zahlen \(c\), für die kein \(c‘ \in \mathbb{N}_u\)​ mit \(\mathcal{C}(c‘) = c\) existiert.

Diese Menge ist:

• nicht leer
• unendlich, denn:
  • Für jedes \(c \equiv 0 \mod 3\) ergibt die Rückrechnung \(\frac{2^k \cdot c – 1}{3}\) keine natürliche Zahl

Fazit

Die Urbildmengen \(\mathcal{C}^{-1}(c‘)\) mit \(c‘ \not\equiv 0 \mod 3\) bilden eine echte Teilpartition der ungeraden natürlichen Zahlen.
Es gibt ungerade Zahlen, die in keiner Urbildmenge enthalten sind.
Insbesondere gilt:

\[\boxed{\bigcup_{c‘ \not\equiv 0 \mod 3} \mathcal{C}^{-1}(c‘) \subsetneq \mathbb{N}_u}\]​​

Position eines Elementes in seiner Urbildmenge

Für jede ungerade natürliche Zahl \(c \in \mathbb{N}_u\)​ mit \(c \not\equiv 0 \mod 3\) lässt sich ihre Position innerhalb der Urbildmenge \(\mathcal{C}^{-1}(c‘)\) eindeutig bestimmen, sofern sie überhaupt ein Urbild von \(c’\) ist. Die Bestimmung erfolgt über die dyadische Struktur des Ausdrucks \(3c + 1\) und basiert auf der Umkehrformel der kompakten Collatzfunktion.

Ausgangspunkt: Kompakte Collatzfunktion

Für ungerades \(c \in \mathbb{N}_u\)​ liefert die kompakte Collatzfunktion:

\[\mathcal{C}(c) = \frac{3c + 1}{2^{\nu_2(3c + 1)}} =: c’\]

Dabei ist \(\nu_2(n)\) die dyadische Bewertung (größte Potenz von 2, die \(n\) teilt).
Der Funktionswert \(c’\) ist immer ungerade. Die Zahl \(c\) ist damit ein Element der Urbildmenge \(\mathcal{C}^{-1}(c‘)\).

Methode zur Positionsbestimmung

Wir nutzen die explizite Darstellung der Urbildfolge:

\[\boxed{c_i = \frac{4^i \cdot (3c_0 + 1) – 1}{3}} \quad \text{mit } c_0 = \frac{2^{k_0} \cdot c‘ – 1}{3}\]​

Da \(\mathcal{C}(c_i) = c’\) für alle \(i\), liegt jede solche Zahl \(c\) eindeutig in dieser Folge.

Ziel: Bestimme \(i\), sodass \(c = c_i\)​.

Vorgehensweise (algorithmisch):

Gegeben: \(c \in \mathbb{N}_u\)​​, \(c‘ := \mathcal{C}(c)\)

1. Berechne \(k := \nu_2(3c + 1)\)
2. Setze \(c‘ = \dfrac{3c + 1}{2^k}\)​
3. Finde das kleinste \(k_0\)​ mit \(\frac{2^{k_0} \cdot c‘ – 1}{3} =: c_0 \in \mathbb{N}_u\)​ \) → Dies ist das erste Glied der Urbildfolge
4. Jetzt gilt: \[3c + 1 = 2^k \cdot c‘ \quad \text{und} \quad 3c_0 + 1 = 2^{k_0} \cdot c’\] ⇒ \[\frac{3c + 1}{3c_0 + 1} = 2^{k – k_0} \Rightarrow k – k_0 = 2i \Rightarrow \boxed{i = \frac{k – k_0}{2}}\]​​​

Voraussetzung: \(k – k_0\) ist gerade ⇒ folgt automatisch aus der Struktur der Folge.

Interpretation

• Die Position \(i\) innerhalb der Urbildfolge \(c_i\)​ zu einem festen \(c’\) ist eindeutig bestimmbar über den dyadischen Abstand der Werte \(\nu_2(3c + 1)\) und \(\nu_2(3c_0 + 1)\).
• Diese Position ist: \[\boxed{i = \frac{\nu_2(3c + 1) – \nu_2(3c_0 + 1)}{2}}\]​​
• \(c_0\)​ ist das kleinste Urbild zu \(c’\), berechnet über: \[c_0 = \frac{2^{k_0} \cdot c‘ – 1}{3}, \quad \text{mit kleinstem } k_0 \text{ s.d. } 2^{k_0} \cdot c‘ \equiv 1 \mod 3\]

Fazit

Für jede ungerade Zahl \(c \in \mathbb{N}_u\)​​, die zu einem \(c‘ \in \mathbb{N}_u\)​\)​ mit \(c‘ \not\equiv 0 \mod 3\) führt, lässt sich eindeutig ihre Position iii innerhalb der Urbildfolge \(c_i = 4^i c_0 + \dots\) ermitteln.

Diese Position ergibt sich aus der Differenz der dyadischen Bewertungen \(\nu_2(3c_0 + 1)\), geteilt durch 2:\[\boxed{i = \frac{\nu_2(3c + 1) – \nu_2(3c_0 + 1)}{2}}\]​​

:

• Für alle Folgeglieder \(c_i\)​ mit \(i \geq 1\) gilt: \(c_i \equiv 5 \mod 8\)
• Nur der Startwert \(c_0\)​ kann eine andere Restklasse haben.
• Durch explizites Prüfen zeigt sich: \[\mathcal{C}^{-1}(c‘) = \{ c_0, 4c_0 + 1, 4^2c_0 + \dots \}\], wobei \[c_0 \mod 8 \in \{1, 3, 7\} \quad \text{ aber } \boxed{\not\in \{5\}}\]

Begründung:
Ist \(c_0 \equiv 5 \mod 8\), dann: \[c_0 + 1 \equiv 4 \cdot 5 + 1 = 21 \equiv 5 \mod 8\]

⇒ \(c_1 \equiv 5 \mod 8\), aber \(c_0 \equiv 5 \mod 8\) widerspricht der Annahme, dass es der kleinste Wert der Folge ist (denn dann wäre er Folgeglied einer früheren Urbildfolge mit kleinerem \(c_0\)​).

Statistische Folgerung: \(3/4–1/4\)-Verteilung

Die ungeraden natürlichen Zahlen modulo 8 haben die 4 möglichen Restklassen: {\(\{1, 3, 5, 7\}\).

Alle sind gleichverteilt ⇒ je 25% Anteil.

• Startwerte \(c_0\)​ einer Urbildfolge: nur 1, 3, 7 ⇒ 3 von 4 ⇒ 75 %
• Folgeglieder (c_i)​ mit \(i \ge 1\): immer \(\equiv 5 \mod 8\) ⇒ 25 %

Folgerung:

• 75 % aller ungeraden Zahlen sind Startwerte \(c_0\)​ von Urbildfolgen.
• Die übrigen 25 % sind Folgeglieder dieser Urbildfolgen (niemals Startwerte).
• Da jede Urbildfolge unendlich viele Glieder hat (durch \(c_{i+1} = 4c_i + 1\)), wird jeder \(c_i \equiv 5 \mod 8c\) genau einmal von einem \(c_0 \equiv 1, 3, 7 \mod 8\) erzeugt.

Asymptotische Dichte der Urbildfolgen

Für jede Urbildfolge \[\mathcal{C}^{-1}(c‘) = \{ c_0, c_1, c_2, \dots \} \quad \text{mit} \quad c_{i+1} = 4c_i + 1\] lässt sich ein asymptotischer Dichtegrenzwert im Raum der ungeraden natürlichen Zahlen angeben. Diese Dichte beschreibt den Anteil der Zahlen in der Folge innerhalb der gesamten ungeraden Zahlenmenge bis zu einem gegebenen Grenzwert.

Definition: Dichte im asymptotischen Sinn

Für eine unendliche Menge \(A \subset \mathbb{N}\) ist die (asymptotische) natürliche Dichte definiert als: \[\delta(A) = \lim_{n \to \infty} \frac{\#(A \cap \{1, 2, \dots, n\})}{n} \quad \text{(sofern der Grenzwert existiert)}\]

Für Urbildfolgen betrachten wir die relative Dichte unter den ungeraden Zahlen: \[\delta^*(\mathcal{C}^{-1}(c‘)) = \lim_{N \to \infty} \frac{\#(\mathcal{C}^{-1}(c‘) \cap \{1, 3, \dots, 2N-1\})}{N}\]

Struktur der Urbildfolge

Die Folge:

\[c_0,\; c_1 = 4c_0 + 1,\; c_2 = 4^2c_0 + 4 \cdot 1 + 1,\; \dots\]

besitzt die geschlossene Darstellung:

\[c_i = \frac{4^i \cdot (3c_0 + 1) – 1}{3} \quad \text{mit } c_0 \in \mathbb{N}_u\]​

Da \(4^i\) exponentiell wächst, ist das Wachstum der Folge exponentiell.

Anzahl Elemente \(\leq x\)

Sei \(x \in \mathbb{N}\) eine große Zahl. Wie viele Folgenglieder \(c_i\)​ liegen unterhalb von \(x\)?
Man löst:

\[c_i \le x \quad \Rightarrow \quad \frac{4^i \cdot (3c_0 + 1) – 1}{3} \le x\]

Daraus folgt:

\[4^i \le \frac{3x + 1}{3c_0 + 1} \quad \Rightarrow \quad i \le \log_4\left( \frac{3x + 1}{3c_0 + 1} \right)\]

Somit wächst die Anzahl der Folgeglieder \(c_i \le x\) nur wie:

\[\#(\mathcal{C}^{-1}(c‘) \cap [1,x]) = \mathcal{O}(\log x)\]

Da ungerade Zahlen bis \(x\) ≈ \(2x/2\), ist relative Dichte \(\frac{\log x}{x} \to 0\)
Herleitung:

Gegebenen die explizite Darstellung: \(c_i = \frac{4^i(3c_0 + 1) – 1}{3}\)​

Da \(4^i\) exponentiell wächst, liegt \(c_i = O(4^i)\)

Umgekehrt:\(i = \log_4(\frac{3x + 1}{3c_0 + 1}) \Rightarrow i = O(\log x)\)

Also: Anzahl \(i\) mit \(c_i \le x\) ist \(O(\log x)\)

Dichteberechnung

Die Zahl ungerader Zahlen ≤ \(x\) beträgt:

\[\#(\mathbb{N}_u \cap [1,x]) \approx \frac{x}{2}\]

Die relative Dichte der Urbildfolge beträgt daher:

\[\delta^*(\mathcal{C}^{-1}(c‘)) = \lim_{x \to \infty} \frac{\mathcal{O}(\log x)}{x/2} = 0\]

Fazit

Genau 3/4 aller ungeraden natürlichen Zahlen sind Startwerte neuer Urbildfolgen \(\mathcal{C}^{-1}(c‘)\), und 1/4 sind Folgeglieder dieser Urbildfolgen.

Diese Verteilung ergibt sich aus der Restklassenanalyse modulo 8:

• Startwerte: \(c_0 \equiv 1, 3, 7 \mod 8\)
• Folgeglieder: \(c_i \equiv 5 \mod 8\) für \(i \ge 1\)

Jede einzelne Urbildfolge zur kompakten Collatzfunktion besitzt asymptotisch Dichte Null im Raum der ungeraden natürlichen Zahlen:

\[\boxed{\delta^*(\mathcal{C}^{-1}(c‘)) = 0}\]

Die Anzahl ihrer Folgenglieder wächst nur logarithmisch, während die Menge aller ungeraden Zahlen bis zu einer Schranke linear wächst.
Auch die Vereinigung aller Urbildfolgen, d. h. der Mengen \(\mathcal{C}^{-1}(c‘)\) für alle \(c‘ \not\equiv 0 \mod 3\), deckt den Raum der ungeraden Zahlen nicht vollständig ab:

\[\bigcup_{c‘} \mathcal{C}^{-1}(c‘) \;\subsetneq\; \mathbb{N}_u\]​