9. Die Anzahl der Primfaktoren
Die Primfaktorzerlegung erlaubt es, die Komplexität einer natürlichen Zahl über die Anzahl ihrer Primfaktoren zu messen. Dabei können wir mehrfach auftretende Faktoren ignorieren oder auch nicht, beide Möglichkeiten sind je nach Kontext sinnvoll. Wir definieren entsprechend zwei Funktionen:
Definition (Primfaktorzählfunktionen)
Wir definieren die Primfaktorzählfunktionen ω : ℕ* → ℕ und Ω : ℕ* → ℕ für alle n ≥ 1 durch
ω(n) = k, Ω(n) = e1 + … + ek, wobei n = p1e1 · … · pkek
die kanonische Primfaktorzerlegung von n ist (mit k = 0 für n = 1).
Mit Hilfe der p-Exponenten formuliert gilt für alle n ≥ 1:
ω(n) = |{ p prim | exp(n) > 0 }|, Ω(n) = ∑p prim exp(n).
Weiter gilt
ω(n) = ∑p|n 1, Ω(n) = ∑pk|n 1 für alle n ≥ 1,
wobei ein „p“ in den Summen wieder stets eine Primzahl bezeichnet.
Leicht zu zeigen ist:
Satz (elementare Eigenschaften von ω und Ω)
Für alle n, m ≥ 1 gilt:
(a) | ω(n) ≤ Ω(n). |
(b) | ω(n) = Ω(n) = 0 genau dann, wenn n = 1. |
(c) | ω(n) = 1 genau dann, wenn n eine Primzahlpotenz ist. |
(d) | Ω(n) = 1 genau dann, wenn n eine Primzahl ist. |
(e) | ω(nm) ≤ ω(n) ω(m). |
(f) | ω(nm) = ω(n) ω(m) genau dann, wenn n und m teilerfremd. |
(g) | Ω(n m) = Ω(n) Ω(m). |
Die folgenden Diagramme geben einen Eindruck vom Verlauf der beiden Funktionen.
Die ω-Funktion bis 300
Die Ω-Funktion bis 300
Wir können die beiden Funktionen auch in der Ebene visualisieren. Hierzu zählen wir die natürlichen Zahlen 1, 2, 3, … wie in der Ulam-Spirale auf, tragen nun aber anstelle der Zahlen die Werte der ω- bzw. Ω-Funktion ein.
Die ω-Spirale (oben) und Ω-Spirale (unten) bis 625
Das folgende Diagramm zeigt eine größere Spirale für die Ω-Funktion, wobei nur die Zahlen mit den Ω-Werten kleinergleich 2 markiert sind. Der Leser vergleiche die Strukturen des Diagramms mit den Punkt-Diagrammen im Essay über Ulam-Spiralen.
Die Werte 0, 1 und 2 der Ω-Spirale bis 10201 (Primzahlen rot)