Competition problem — Number theory

Library / /245 of 860

Number theory Difficulty 5.0 AIME, harder Find the answer

A sequence of positive integers is given by $a_{1}=1$ and $a_{n}=\operatorname{gcd}\left(a_{n-1}, n\right)+1$ for $n>1$ . Calculate $a_{2002}$ .

Your answer

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

Solution

3. It is readily seen by induction that $a_{n} \leq n$ for all $n$ . On the other hand, $a_{1999}$ is one greater than a divisor of 1999. Since 1999 is prime, we have $a_{1999}=2$ or 2000; the latter is not possible since $2000>1999$ , so we have $a_{1999}=2$ . Now we straightforwardly compute $a_{2000}=3, a_{2001}=4$ , and $a_{2002}=3$ .

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.