## 2014 AMC 10A Problem 24

2014 AMC 10A 24. A sequence of natural numbers is constructed by listing the first 4, then skipping one, listing the next 5, skipping 2, listing 6, skipping 3, and, on the $n$th iteration, listing $n+3$ and skipping $n$. The sequence begins 1, 2, 3, 4, 6, 7, 8, 9, 10, 13. What is the 500,000th number in the sequence?

(A) 996,506   (B) 996,507   (C) 996,508   (D) 996,509   (E) 996,510

This problem is not a difficult one, but we must be very careful not to make any mistakes in working out the pattern. See if you can follow the logic in the next few paragraphs. (Ideally the working in the next few paragraphs should be presented in a table, but as I haven’t figured out a good way to do that in WordPress yet, I will list them out.)

1st Iteration
Numbers added to sequence in this iteration: 4 = 1 + 3
Length of sequence after this iteration: 4 = 1 + 3
1st number listed: 1
Numbers listed: 1, 2, 3, 4
Numbers skipped: 5

2nd Iteration
Numbers added to sequence in this iteration: 5 = 2 + 3
Length of sequence after this iteration: (2 + 3) + (1 + 3) = 9
1st number listed: [(1+3) + 1] + 1 = 6
Numbers listed: 6, 7, 8, 9, 10
Numbers skipped: 11, 12

n-th Iteration
Numbers added to sequence in this iteration: $n + 3$
Length of sequence after this iteration:
\begin{aligned} (1 + 3) + (2 + 3) + \dots + (n + 3) &= (1 + 2 + \dots + n) + 3n \\ &= \frac{n(n+1)}{2} + 3n \end{aligned}
1st number listed:
\begin{aligned} &[(1+3) + 1] + [(2+3) + 2] + \dots + [(n-1 + 3) + n-1] + 1 \\ &= 2 \times [1 + 2 + \dots + (n-1)] + 3(n-1) + 1 \\ &= (n-1)n + 3(n-1) + 1 \\ &= (n-1)(n+3) + 1 \end{aligned}
Numbers listed: $(n-1)(n+3) + 1$ to $(n-1)(n+3) + n + 3$ (included)
Numbers skipped: $(n-1)(n+3) + n + 3 + 1$ to $(n-1)(n+3) + n + 3 + n$ (included)

Once we have worked out the general formulas for the n-th iteration, it’s always a good idea to check the general formulas against small cases to make sure they are correct. Convince yourself that the formulas work for the 1st, 2nd and even the 3rd iteration.

The last step is to figure out which iteration the 500,000th number lies in. The relevant formula here is the “Length of sequence after this iteration”: to find a value of $n$ such that

$\frac{(n-1)[(n-1)+1]}{2} + 3(n-1) < 500,000 \leq \frac{n(n+1)}{2} + 3n.$

Even though calculators are not allowed on the AMC 10, it’s not hard to guess roughly how big $n$ should be. When $n = 1000$, $1 + 2 + \dots n = \frac{n(n+1)}{2} = 500,500$, so the value of $n$ which satisfies the inequality above should be in that region. A bit of trial and error shows that $n = 997$:

$\frac{(997-1)(997)}{2} + 3(997-1) = 499,494 < 500,000 < 500,494 = \frac{(997)(998)}{2} + 3(997).$

After the 996th iteration, there are 499,494 numbers in the sequence. Hence, the 997th iteration begins with the 499,495th number in the sequence which is $(997-1) \times (997+3) + 1 = 996,001$. As 500,000 = 499,494 + 506, the 500,000th number in the sequence is

$(997-1) \times (997+3) + 506 = 996,506$. The answer is (A).