Aufgabe:
Sei π (N) die Anzahl der Primzahlen kleiner oder gleich N (Beispiel: π (100) = 25). Der berühmte Primzahlsatz (PNT) besagt dann (wobei ∼ asymptotisch gleich bedeutet):
$$ π (N) ∼ \frac{N}{log(N)} $$
Diesen Satz zu beweisen ist sehr schwer. Wir können jedoch eine statistische Form der Primzahlsatz ableiten. Dazu betrachten wir zufällige Primzahlen, die wie folgt erzeugt werden:
(i) Erstellen Sie eine Liste aufeinanderfolgender Ganzzahlen von 2 bis N.
(ii) Beginnen Sie mit 2 und markieren Sie jede Zahl > 2 mit einer Wahrscheinlichkeit von 1/2
(iii) Sei n die nächste nicht markierte Zahl. Markieren Sie jede Zahl> n mit einer Wahrscheinlichkeit von 1/n
(iv) Wiederholen Sie (iii), bis Sie N erreicht haben.
Alle nicht markierten Zahlen in der Liste werden als zufällige Primzahl bezeichnet.
(a) Sei qn die Wahrscheinlichkeit, dass n während dieses Algorithmus als zufällige Primzahl ausgewählt wird. Finden Sie einen Ausdruck für qn in Form von qn - 1.
(b) Beweisen Sie die folgende Ungleichung von qn und qn + 1:
$$ \frac{1}{q_n} + \frac{1}{n} < \frac{1}{q_{n+1}} < \frac{1}{q_n} + \frac{1}{n-1} $$
(c) Verwenden Sie das Ergebnis aus (b), um diese Ungleichung zu zeigen:
$$ \sum \limits_{k=1}^{\text{ N }} \frac{1}{k} < \frac{1}{q_N} < \sum \limits_{k=1}^{\text{ N }} \frac{1}{k} + 1 $$
(d) Leiten Sie mit diesem Ergebnis einen asymptotischen Ausdruck für qn in Form von n her.
(e) Sei ˜π (N) die Anzahl der zufälligen Primzahlen kleiner oder gleich N. Verwenden Sie das Ergebnis aus (d) , um einen asymptotischen Ausdruck für ˜π (N) abzuleiten, d. h. den Primzahlsatz für zufällige Primzahlen.
Problem/Ansatz:
Ehrlich gesagt verstehe ich bei dieser Aufgabe nur Bahnhof.
Es handelt sich um eine der fünf Uni Aufgaben , die ich Morgen abgeben muss.
Ihr seid meine letzte Hoffnung...
Bitte um dringende Hilfe.
