Maths Olympiad Prep

Library / /101 of 128

Number theory Difficulty 6.3 National Olympiad Prove it Philippines

Problem:

The 2011th prime number is 1748317483, and the next prime is 1748917489.
Does there exist a sequence of 201120112011^{2011} consecutive positive integers that contains exactly 20112011 prime numbers? Prove your answer.

Solution

Solution:

Let N=20112011N = 2011^{2011}. Since N>17489N > 17489, there are more than 20112011 primes in the sequence 1,2,3,,N1, 2, 3, \ldots, N.

Claim. There exists a sequence of NN consecutive positive integers that are all composite.

Proof of the Claim. The sequence
(N+1)!+2, (N+1)!+3, (N+1)!+4, , (N+1)!+N, (N+1)!+(N+1) (N+1)! + 2,\ (N+1)! + 3,\ (N+1)! + 4,\ \ldots,\ (N+1)! + N,\ (N+1)! + (N+1)
consists of NN consecutive composite numbers, and so the claim follows.

Back to the solution of the problem, let
a, a+1, a+2, , a+N1 a,\ a+1,\ a+2,\ \ldots,\ a+N-1
be a sequence of NN consecutive positive integers with no prime. We do repeatedly the following operation to the numbers in ()(\star). Delete the far-right number a+N1a+N-1, and append to the far-left the number a1a-1. The resulting sequence
a1, a, a+1, , a+N2 a-1,\ a,\ a+1,\ \ldots,\ a+N-2
has at most one prime. Repeating this operation until we reach the sequence 1,2,3,,N1, 2, 3, \ldots, N, which has more than 20112011 primes.

Performing such operation either retains, increases by one, or decreases by one the number of primes of the previous sequence. Since the starting sequence has no prime at all, while the last sequence has more than 20112011 primes, there exists a sequence (after applying the operation a number of times) that contains exactly 20112011 primes.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.