Prime Problem

Level pending

What is the smallest integer $k$ greater than $10$ such that there is some interval of $1000$ integers which contains exactly $k$ primes?

Credits: Thanks to randomusername on AoPS for this problem, I just wanted to share it with the rest of Brilliant as well

14 11 13 17

1 solution

Josh Speckman
Dec 26, 2013

Consider an interval of $1000$ integers which contains no primes. Now, decrease every term in that interval by $1$ . Notice that the only change we make is removing the largest integer and replacing it with an integer one smaller than that, so only $1$ term changes. It follows that the number of primes in the interval can only change by $1$ , $0$ , or $-1$ , since only one integer changes. Eventually, by repeating this process, we will find an interval with many more primes, for example, the interval from $1$ to $1000$ . This means that somewhere in between, we had an interval containing $11$ primes, so the answer is $\fbox{11}$

Sorry, I just realized this. When I said "...he only change we make is removing the largest integer and replacing it with an integer one smaller than that...", I meant that we replace the largest integer by an integer one less than the smallest integer in the interval.

Josh Speckman - 7 years, 5 months ago

Prime Problem

1 solution

0 pending reports