Shyan's intervals

First, note that the number of primes $<1000$ is $>25$ : one can calculate the first few primes, and note that the $26^{th}$ prime is $101$ , which is clearly $<1000$ , hence establishing our claim.

We now claim that all non-negative integers less than $25$ satisfy the given condition. Let $n$ be such an integer. Consider a larger positive integer $k$ . Let $m$ be the number of primes between $k-1$ and $k+1000$ (boundaries excluded). Note that if we increase $k$ by $1$ , $m$ will either not change at all, or will increase by $1$ , or will decrease by $1$ . This is obviously true, because in the process either we lose a prime or we gain one, or neither of these will happen.

Note that we can easily construct a sequence of $1000$ consecutive positive integers, none of which contain a prime. Let $p_1, p_2, ..., p_x$ be the set of primes from $1$ to $1001$ . Consider the sequence $p_1p_2...p_x + 2$ , $p_1p_2...p_x + 3$ , $\cdots$ , $p_1p_2...p_x + 1001$ . This sequence obviously satisfies the mentioned property.

Now suppose $a$ and $b$ are two positive integers for which $m$ assumes the values $c$ and $d$ respectively. From our previous observation, for all positive integers $n$ between $c$ and $d$ , we can find some $y$ satisfying the given property. Since there exists a sequence of consecutive positive integers for which $m$ takes the value $0$ , all non-negative integers between $1$ and $25$ satisfy the given property. In conclusion, our answer is $\boxed{26}$ .

Consider the function $f : \mathbb N \to \mathbb N$ that assigns to $n$ number of primes between $n$ and $n + 1000$ . The problem asks us to understand the range of this function. To that end notice that $f(n) - f(n-1)$ is always either $0, 1$ or $-1$ (because the number of primes in the adjacent intervals can't differ by more than one -- prove this!). Therefore the range of $f$ forms a set of consecutive integers.

The other part of the proof hangs on the existence of infinite gaps in primes. That is, there exist sets of consecutive integers of arbitrary length that contain no primes. It follows that in these regions our function $f$ equals $0$ . Finally, $f(1) > 25$ (since there are a lot of small primes). Putting these facts together with the observation of consecutive range from the first paragraph, the range of $f$ includes all the numbers $0 \leq n \leq 25$ and the answer is $26$ .

Case 1:

Consider the set of primes

$P$ = { 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97 }

And let $X$ be the set of consecutive integers from $1$ to $1000$ inclusive.

As $| P | = 25$ , and $P$ is a subset of $X$ , we have found a set of $1000$ consecutive integers containing exactly $n$ primes, for $1<=n<=25$ .

Case 2:

For $n = 0$ , consider the sequence of consecutive numbers

$a_i =$ { $1001! + i$ }, where $i$ goes from $2$ to $1001$ inclusive.

As $2 <= i <= 1001$ , $i$ is a common factor of $1001!$ and $i$ , thus the terms of $a_i$ are always composite and we have found $1000$ consecutive numbers containing $0$ primes.

From case 1 and case 2 we conclude that there are $26$ nonnegative integers $n <= 25$ containing exactly $n$ primes.