An inversive algorithm. (Q563464): Difference between revisions

Verf. gibt eine Verallgemeinerung eines von \textit{Brun} (1931; JFM 57.0185.*) herrührenden Algorithmus zur Berechnung der \(n\)-ten Primzahl aus der Funktion \(\pi (x)\), welche die Anzahl der Primzahlen unterhalb \(x\) angibt. Sei nämlich \(C\) irgendeine Menge ganzer Zahlen, \(\vartheta (x)\) die zugehörige Anzahlfunktion, welche angibt, wieviel Zahlen von \(C\leqq x\) sind; um die \(n\)-te Zahl von \(C\) zu bestimmen, bilde man der Reihe nach: \[ \begin{aligned} n_0 &=n,\\ n_1 &=n-\vartheta (n_0),\\ n_2 &= n-\vartheta (n_0+n_1),\\ \cdots &\cdots \cdots \cdots \cdots \cdots \end{aligned} \] Die \(n_0, n_1, n_2,\ldots \) bilden eine monoton nicht zunehmende Folge, welche von einem Glied an lauter Nullen enthält. Ist \(n_{k-1}\) das letzte von 0 verschiedene Glied dieser Folge, so ist \(n_0+n_1+\cdots +n_{k-1}\) die gesuchte \(n\)-te Zahl der Folge \(C\).