Minimal Prime Tuplets and Nontrivial Bounds for A008407 Sequence

[CRGreathouse]

I was wondering if any nontrivial bounds for http://www.research.att.com/~njas/sequences/A008407 were known. This is the sequence of minimal width for k-tuplets of primes allowed by divisibility concerns. a(2) = 2 since n, n+2 could both be prime; n, n+1 isn't admissible since then either n or n+1 is even.

Clearly a(n+1) >= a(n) + 2, but practically speaking a(n) seems to grow superlinearly.

 

[CRGreathouse]

Ah, it just hit me: an appropriate reformulation of the sequence is superadditive. Even better, http://www.research.att.com/~njas/sequences/A023193 is subadditive, so I can just use the best ratio with some additive constant as an absolute bound.

OK, here's what I have: A023193(n) <= floor(n*331/2467+33.1). This comes from the fact that A023193(4934) = 662, so 4934 consecutive numbers can't contain more than 662 primes as long as the smallest number in the range > 4934. So clearly every 4934n numbers can't contain more than 662n primes, since each of the n subintervals must be legal as well. The additive constant 33.1 is such that this holds for 1 <= n <= 4934, and so must hold for all n >= 1. (Also, checking shows that this actually holds even if the smallest number is less than 4934.)

 

[CRGreathouse]

The purpose of the thread was to find an upper bound on the number of primes in a 'small' interval h, \pi(x)-\pi(x-h). Under the Riemann hypothesis we have

\left|\pi(x)-\pi(x-h)-(\operatorname{li}(x)-\operatorname{li}(x-h))\right|\le\frac{\ln x\sqrt x+\ln(x-h)\sqrt{x-h}}{8\pi}\approx\frac{\ln x\sqrt x}{4\pi}

for x-h > 3000, but we expect a large degree of cancellation. Using the above result we have

\pi(x)-\pi(x-h)\le\frac{331h}{2467}+33.1

which may be tighter for small h or large x and is not dependent on the RH or any other unproved hypothesis -- though the k-tuple conjecture would mean that A02319 is a maximum rather than 'just' an upper bound.

 

[CRGreathouse]

So equating the errors in the two methods, I get
\frac{331h}{2467}+33.1\approx\frac{\ln x\sqrt x}{4\pi}
which is
h\approx2.372\ln x\sqrt x-4.44

So for large x, this method can be useful. Still, I wonder if there is a sublinear bound for this, which could greatly increase the useful range of the approximation. Has anyone seen something like this? Is there a book or a paper I could read?