Recursivity of the primes

2012-01-03T18:43:20Z

As is well-known, with the finite set of the first $n$ primes $p_1,\dots ,p_n$ one can find all primes exactly (i.e. without false positives) with the Eratosthenes Sieve in the interval $[p_n+1;p_{n+1}^2]$. Of course, that requires computing $p_{n+1}$ first to know where $p_{n+1}^2$ is, but then one can sieve without further ado (I'm not looking at efficiency here, so Eratosthesnes is fine for the purpose of this discussion).

It is thus tempting to look at the recursive construction (in some sense, the maximal possible generation of primes):

$2$ produces $3,5,7$ in $[2+1;3^2]=[3;9]$ (that's 3 primes, i.e. $3=\pi(9)-\pi(3)$)

then $2,3,5,7$ produces $11,13\dots ,113$ in $[7+1;11^2]$ (that's 26 primes)

then $2,\dots ,113$ produces $127,\dots ,16127$ in $[113+1;127^2]$ (that's 1847 primes)

then $2,\dots ,16127$ produces $16139,\dots ,260 467 313$ in $[16127+1;16139^2]$ (that's 14 218 065 primes).

And so on...

I would be interested to know more about this recursive procedure, for instance obtain an asympotic equivalent if possible.

Notice that I'm not asking simply for an asymptotics of $\pi (p_{n+1}^2) - \pi (p_n+1)$, since I'm interested in only a certain subsequence of that, which grows much faster. One step forward would thus be e.g. a useful characterisation of that subsequence.

I have looked at the obvious places (the OEIS, and elementary texts like Conway & Guy's The Book of Numbers or Stein's lectures on Elementary Number Theory) but to no avail. In particular none of them, including the OEIS, seem to mention the relevant sequences:

a) growth of the number of primes produced: 1, 3, 26, 1847, 14 218 065, ...

b) accumulated growth: 1, 4, 30, 1877, 14 219 942, ...

c) first new prime produced: 2, 3, 11, 127, 16139, 260 467 367, 67 843 249 271 912 789, ...

d) last new prime produced: 7, 113, 16127, 260 467 313,...

I would be grateful for any help or useful reference (I do not have access to the Monthly, but wouldn't be surprised if this had been discussed there already).

Recursivity of the primes - MathOverflow

Recursivity of the primes