Primzahlen und O-Notation [Zahlentheorie]

11.11.2010, 15:40	phistoh	Auf diesen Beitrag antworten »
Primzahlen und O-Notation [Zahlentheorie] Puh, ich hoffe der Titel hat wenigstens ein bisschen Aussagekraft. Also, ich sitze gerade an meinem Zahlentheorieübungsblatt und soll folgende Sachen zeigen: ( $\begin{eqnarray} p_n \end{eqnarray}$ bezeichnet die n-te Primzahl) 1) $\begin{eqnarray} \frac{p_n}{log(p_n)} = \mathcal{O} (n) \end{eqnarray}$ 2) $\begin{eqnarray} p_n = \mathcal{O} (n^\alpha) \end{eqnarray}$ (für alle $\begin{eqnarray} \alpha > 1 \end{eqnarray}$ ) 3) $\begin{eqnarray} p_n = \mathcal{O} (nlog(n)) \end{eqnarray}$ So. Zur 1) Das kann man ja über Tschebyscheff zeigen, aber wäre folgender Weg auch richtig: Der Primzahlsatz besagt $\begin{eqnarray} \pi(p_n) \sim \frac{p_n}{log(p_n)} \end{eqnarray}$ . Da $\begin{eqnarray} p_n \end{eqnarray}$ die n-te Primzahl ist, ist $\begin{eqnarray} \pi(p_n) = n \end{eqnarray}$ . Also haben wir $\begin{eqnarray} n \sim \frac{p_n}{log(p_n)} \end{eqnarray}$ . Das heißt ja dann nichts anderes, als dass $\begin{eqnarray} \frac{p_n}{log(p_n)} = \mathcal{O} (n) \end{eqnarray}$ . Dann zur 2) Ich habe mir überlegt, da $\begin{eqnarray} p_n = \mathcal{O} (n^\alpha)\Leftrightarrow p_n < cn^\alpha \end{eqnarray}$ (mit c>0 und n groß genug) ist und aus der 1) folgt, dass $\begin{eqnarray} p_n < c' n * log(p_n) \end{eqnarray}$ (ebenso mit c'>0 und n groß genug) es reicht zu zeigen, dass die rechte Seite der Ungleichung, die aus 1) folgt kleiner oder gleich der rechten Seite der anderen Ungleichung sein muss, also: $\begin{eqnarray} c' * n * log(p_n) \leq cn^\alpha \end{eqnarray}$ Da $\begin{eqnarray} \alpha > 1 \end{eqnarray}$ kann man ja n kürzen und erhält (c' auf die andere Seite gebracht): $\begin{eqnarray} log(p_n) \leq \frac{c}{c'}n^{\alpha-1} \end{eqnarray*}$ Aber ich glaube, das bringt mich nicht sonderlich weiter. Wäre cool, wenn ihr vlt irgendeinen Tipp habt, wie man das anders angehen kann. (Die dritte Aufgabe habe ich mir noch nicht richtig angesehen, die könnt ihr auch erstmal ignorieren. )

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »