Minimal prime tuplets

CRGreathouse

I was wondering if any nontrivial bounds for 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, 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, [itex]\pi(x)-\pi(x-h)[/itex]. Under the Riemann hypothesis we have

[tex]\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}[/tex]

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

[tex]\pi(x)-\pi(x-h)\le\frac{331h}{2467}+33.1[/tex]

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
[tex]\frac{331h}{2467}+33.1\approx\frac{\ln x\sqrt x}{4\pi}[/tex]
which is
[tex]h\approx2.372\ln x\sqrt x-4.44[/tex]

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?