Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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

share|improve this question
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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.