New sequence : Primes for which SQRT(A000040(n)) < A001223(n)

[Dean Hickerson]

Mostly to David Wilson

> My intuition was that lim n->inf (p(n)/log(p(n))) / n = 1 would preclude an 
> infinitude of gaps p(n+1)-p(n) >= sqrt(n). Can someone give a function p 
> that would serve as a counterexample? If so, I will give my intuition a 
> sound boxing to the ears.

Let N(i) be a rapidly growing function of i.  Start with the set of primes
and delete any that are between  N(i)  and  N(i) + sqrt(N(i))  for some i.
Let p(n) be the n'th element of the resulting set.  The number of primes
that we're deleting near N(i) is less than sqrt(N(i)), which is much smaller
than the total number of primes less than N(i).  So as long as N(i) grows
fast enough, p(n) will still be asymptotic to  n log(n).  (I haven't
tried to figure out just how fast N(i) has to grow to make this work.)

Dean Hickerson
dean at math.ucdavis.edu