Recursivity of the primes - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-22T03:05:35Z http://mathoverflow.net/feeds/question/84823 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/84823/recursivity-of-the-primes Recursivity of the primes Thomas Sauvaget 2012-01-03T18:43:20Z 2012-01-03T18:43:20Z <p>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).</p> <p>It is thus tempting to look at the recursive construction (in some sense, the maximal possible generation of primes): </p> <p>$2$ produces $3,5,7$ in $[2+1;3^2]=[3;9]$ (that's 3 primes, i.e. $3=\pi(9)-\pi(3)$)</p> <p>then $2,3,5,7$ produces $11,13\dots ,113$ in $[7+1;11^2]$ (that's 26 primes)</p> <p>then $2,\dots ,113$ produces $127,\dots ,16127$ in $[113+1;127^2]$ (that's 1847 primes)</p> <p>then $2,\dots ,16127$ produces $16139,\dots ,260 467 313$ in $[16127+1;16139^2]$ (that's 14 218 065 primes).</p> <p>And so on...</p> <blockquote> <p>I would be interested to know more about this recursive procedure, for instance obtain an asympotic equivalent if possible.</p> </blockquote> <p>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.</p> <p>I have looked at the obvious places (the <a href="https://oeis.org/" rel="nofollow">OEIS</a>, and elementary texts like Conway &amp; Guy's <a href="http://books.google.fr/books?id=0--3rcO7dMYC" rel="nofollow">The Book of Numbers</a> or Stein's <a href="http://wstein.org/edu/2007/spring/ent/textbook.html" rel="nofollow">lectures on Elementary Number Theory</a>) but to no avail. In particular none of them, including the OEIS, seem to mention the relevant sequences: </p> <p>a) growth of the number of primes produced: 1, 3, 26, 1847, 14 218 065, ...</p> <p>b) accumulated growth: 1, 4, 30, 1877, 14 219 942, ...</p> <p>c) first new prime produced: 2, 3, 11, 127, 16139, 260 467 367, 67 843 249 271 912 789, ...</p> <p>d) last new prime produced: 7, 113, 16127, 260 467 313,...</p> <p>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).</p>