BrainDen.com - Brain Teasers
• 0

# Exactly 150 primes

## Question

Show that there is a set of 2002 consecutive positive integers containing exactly 150 primes. (You may use the fact that there are
168 primes less than 1000)

(original source: from a training set for IMO).

## Recommended Posts

• 0

Let P(n) denote the number of primes in set {n, n+1, ..., n+2001}

(the set of 2002 consecutive positive integers starting with n).
We are given that P(1)>=168.
First observe that P(2003!+2) = 0. Indeed k | (2003!+k) for k=2, 3, ..., 2003,
so each number in set {2003!+2, 2003!+3, ..., 2003!+2003} is composite.
Now observe that |P(n+1) - P(n)| <= 1. Indeed, shifting the set by one to the right
cannot change the number of primes in the set more then by 1.
Therefore P(n) takes all intermediate values between P(1)(>=168) and P(2003!+2) (=0),
so the value of 150 is also taken for some 1<n<(2003!+2) in particular.

## Join the conversation

You can post now and register later. If you have an account, sign in now to post with your account.

×   Pasted as rich text.   Paste as plain text instead

Only 75 emoji are allowed.

×   Your previous content has been restored.   Clear editor

×   You cannot paste images directly. Upload or insert images from URL.