karthickgururaj Posted September 30, 2014 Report Share Posted September 30, 2014 Show that there is a set of 2002 consecutive positive integers containing exactly 150 primes. (You may use the fact that there are168 primes less than 1000) (original source: from a training set for IMO). Quote Link to comment Share on other sites More sharing options...
0 witzar Posted September 30, 2014 Report Share Posted September 30, 2014 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. Quote Link to comment Share on other sites More sharing options...
Question
karthickgururaj
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).
Link to comment
Share on other sites
1 answer to this question
Recommended Posts
Join the conversation
You can post now and register later. If you have an account, sign in now to post with your account.