This is related to an [older question](https://mathoverflow.net/questions/17597/prime-numbers-with-given-difference) about [prime k-tuples and constellations](http://en.wikipedia.org/wiki/Prime_k-tuple), but takes a slightly different direction.


Given an integer k, we want to find n such that the interval {n+1, ..., n+k} contains as many primes as possible. (We consider only n ≥ k to eliminate certain exceptional cases, such as {3,5,7}, which is irregular since for k=5 there can be at most 2 primes in the interval if n>2.)


There is an obvious upper bound ak on the number of primes in this interval, given by considering the numbers modulo p for all primes p ≤ k. More precisely, ak is the largest possible cardinality of a set A ⊂ {1, ..., k} such that for some n, the set n+A does not contain any numbers divisible by any prime p ≤ k.


For example, a3=2 since out of 3 consecutive numbers at least one is even, and a7=3 since out of seven consecutive numbers at least three are even, and at least one of the odd numbers is divisible by 3. Similarly, a9=4 and a13=5.


The four bounds listed so far can be achieved by taking n=4, n=10, n=10, n=36, respectively. The natural question to ask is whether for every k there is a value of n such that the interval {n+1, ..., n+k} contains ak primes, but the comments on the [older question](https://mathoverflow.net/questions/17597/prime-numbers-with-given-difference) make me suspect that this may be open. (Another natural question is whether there are infinitely many such n, but since for k=3 this is the twin prime conjecture, that's definitely out of reach at present.)


Since the natural question to ask seems very hard, my question instead is this: Is anything about the asymptotics of this problem? More precisely, I'd like to know if something like the following statement is true: "For every ε>0, there exist infinitely many pairs (k,n) such that the interval {n+1, ..., n+k} contains at least (1-ε)ak prime numbers."


There are a few different ways to tweak that statement -- for example, we could ask for infinitely many n for a fixed k, or we could let both k and n become arbitrarily large. (Of course k will need to become arbitrarily large as ε becomes small.) I'd be happy with any of them -- I'm asking this question out of curiosity rather than out of a need for a specific result.



Intervals with large numbers of primes
For fixed $k$ this is definitely hopeless, since it would imply that for some $b$ there are infinitely many primes $p$ such that $p + b$ is prime, and this is a well-known open problem that seems out of reach of the latest techniques for finding small gaps between primes (see this survey article of Soundararajan for example: <http://www.ams.org/journals/bull/2007-44-01/S0273-0979-06-01142-6/S0273-0979-06-01142-6.pdf>)


For similar reasons this will also be hopeless if $k$ is too small depending on $n$. 


If $k$ is huge compared with $n$ then the existence of many such pairs would follow immediately from the prime number theorem if only one knew that $a\_k \leq (1 + o(1))\pi(k)$. However, I do not believe this is known and in fact I'm nigh-on certain that nothing better than $a\_k \leq 2\pi(k)$ is known. This is a result of Montgomery and Vaughan; the slightly weaker bound of $a\_k \leq (2 + o(1))\pi(k)$ follows rather easily from the Selberg upper bound sieve. Incidentally, the presence of the factor $2$ here reflects something called the parity problem in sieve theory: breaking it, even by a tiny amount, is generally very problematic.


In the previous discussion referenced above, the result of Hensley and Richards was mentioned. This is an example to show that it is \emph{not} true that $a\_k \leq \pi(k)$. As you hint in the question, one might then conjecture that there is $n$ such that $\{n+1,\dots, n+k\}$ contains $a\_k > \pi(k)$ primes, in which case one would have a violation of the triangle inequality $\pi(x+y) \leq \pi(x) + \pi(y)$. Such a conjecture would follow from the Hardy-Littlewood $k$-tuple conjecture which is, of course, hopelessly out of reach.


