Maths Olympiad Prep

Library / /496 of 860

Number theory Difficulty 5.2 AIME, harder Find the answer

Let A11A_{11} denote the answer to problem 11. Determine the smallest prime pp such that the arithmetic sequence p,p+A11,p+2A11,p, p+A_{11}, p+2 A_{11}, \ldots begins with the largest possible number of primes.

A number or a short expression. Fractions can be typed as 3/2, and spacing doesn't matter.

Solution

First, note that the maximal number of initial primes is bounded above by the smallest prime not dividing A11A_{11}, with equality possible only if pp is this prime. For, if qq is the smallest prime not dividing A11A_{11}, then the first qq terms of the arithmetic sequence determine a complete residue class modulo qq, and the multiple of qq is nonprime unless it equals qq. If q<A11q<A_{11}, then qq must appear first in the sequence, and thus divide the (q+1)(q+1) st term. If q>A11q>A_{11}, then A11=2A_{11}=2 and q=3q=3 by Bertrand's postulate, so qq must appear first by inspection. Now since A11=30A_{11}=30, the bound is 7. In fact, 7,37,67,97,1277,37,67,97,127, and 157 are prime, but 187 is not. Then on the one hand, our bound of seven initial primes is not realizable. On the other hand, this implies an upper bound of six, and this bound is achieved by p=7p=7. Smaller primes pp yield only one initial prime, so 7 is the answer.

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: Omni-MATH, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.