# Recursivity of the primes

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).

-
As you remarked, the sequences in (a) and (b) can be obtained from (c) or (d) using the prime-counting function $\pi(\cdot)$. For asymptotics, I think it is more reasonable to look at the logarithms of the values. The logarithms of the values in the sequences (c) and (d) more or less double in every step. – Goldstern Jan 4 '12 at 0:02
Thanks for the comment. Yes, following your suggestion, the logarithm of sequence (c) is well-fitted, up to small errors, by the sequence $0.3023191518585 e^{0.6933439751085 n}$, while the logarithm of sequence (d) is less accurately fitted by $0.592994983 e^{0.696248232024512 n}$. This is certainly helpful, but unfortunately Plouffe's inverter doesn't seem to recognize either of these four constants, while I was hoping for something known and explicit. – Thomas Sauvaget Jan 4 '12 at 10:04

Just to close off this old question, noting $(q_n)$ the sequence of first primes produced (2, 3, 11, 127, 16139, 260 467 367, 67 843 249 271 912 789, ...) I'll make the guess that $\ln(\ln(q_n))$ is asymptotic to $n\ln(2)$.

Supporting data:

n   q_n                 ln(l(q_n))   ln(ln(q_n))-ln(ln(q_{n-1}))
1   2                   -0.36651292  ---
2   3                   0.09404783   0.46056075
3   11                  0.84759138   0.78054356
4   127                 1.57777945   0.70318806
5   16139               2.27099060   0.69321115
6   260467367           2.96413779   0.69314719
7   67843249271912789   3.65728497   0.69314718


while $\ln(2)=0.693147180559945...$

-
This can almost certainly be proved: you're jumping from $p_n$ to $p_{n+1}$, the first prime beyond $p_n^2$, at each stage; and $p_{n+1}$ isn't going to be that much larger than $p_n^2$. Therefore you're essentially squaring at each step, which is what the relationship $\log\log q_n \sim n\log 2$ is saying. – Greg Martin Nov 17 '14 at 7:41
Thank you. Probably a silly question, but: couldn't it be possible, with bad luck, that those gaps between the square and the next prime actually grow larger and larger at some point? I agree that if this can be brushed off then the guess is proved. – Thomas Sauvaget Nov 17 '14 at 11:17
The question of how close to a given integer the next prime must be is certainly an area of active research (so not silly at all!). It's known that the next prime after $N$ is at most $N + CN^{0.525}$ (for some fixed constant $C$); and it's conjectured that it's at most $N + C(\log N)^2$. Anyway, the known result is enough to prove the recursive $\log\log q_n = \log\log q_{n-1} + \log 2 + O(1/q_{n-1}^{0.9})$ say, which is enough to imply $\log\log q_n = n\log 2 + O(1)$. – Greg Martin Nov 17 '14 at 19:21
Great, thank you for the explanation. – Thomas Sauvaget Nov 18 '14 at 6:49