2014 AMC 10A Problem 24

Every whole number is either listed or skipped. So the $500{,}000$th listed number equals $500{,}000$ plus the number of skipped numbers that come before it. The job is to count those skipped numbers.

1. What one round does. Round $n$ lists $n + 3$ numbers, then skips $n$.
2. Count the listed numbers after some rounds. After $n$ rounds, the number of listed numbers is
$$(1 + 3) + (2 + 3) + \cdots + (n + 3) = (1 + 2 + \cdots + n) + 3n = \frac{n(n+1)}{2} + 3n.$$
Check with the start: after $1$ round, $4$ listed; after $2$ rounds, $4 + 5 = 9$ listed. The formula gives $1 + 3 = 4$ and $3 + 6 = 9$.
3. Find the right round. We want this count to be close to $500{,}000$. It is roughly $\frac{n^2}{2}$, so $n^2 \approx 1{,}000{,}000$ and $n$ is a bit under $1000$. Try $n = 996$:
$$\frac{996 \cdot 997}{2} + 3 \cdot 996 = 496{,}506 + 2{,}988 = 499{,}494.$$
That is $506$ short of $500{,}000$. Round $997$ lists $997 + 3 = 1000$ numbers, which is more than $506$. So the $500{,}000$th number is listed during round $997$, before its skip.
4. Count the skipped numbers before it. The first $996$ rounds skipped $1 + 2 + \cdots + 996 = \frac{996 \cdot 997}{2} = 496{,}506$ numbers. Round $997$ has not skipped anything yet.
5. The answer. $500{,}000 + 496{,}506 = 996{,}506$.

Check with the given start: the $10$th listed number should be $13$. Before it, rounds $1$ and $2$ skipped $1 + 2 = 3$ numbers, and $10 + 3 = 13$.

The answer is $\boxed{\textbf{(A)}\ 996,506}$.

For a list that skips some numbers, "the $k$th number on the list" equals $k$ plus the number of skipped numbers before it. That turns the question into counting skips, which here is just $1 + 2 + \cdots + n$. The answer choices differ by $1$, so checking the method on the start of the list, as we did with the $10$th number, is worth the few seconds.

Track where each round starts. Round $n$ uses $2n + 3$ numbers ($n + 3$ listed and $n$ skipped). So after $n$ rounds we have gone through $5 + 7 + \cdots + (2n + 3) = n(n + 4)$ numbers. After $996$ rounds that is $996 \cdot 1000 = 996{,}000$, and $499{,}494$ numbers have been listed. Round $997$ lists $996{,}001$, $996{,}002$, and so on. We need the $500{,}000 - 499{,}494 = 506$th of these, which is $996{,}000 + 506 = 996{,}506$.

Track two running totals after $n$ complete rounds.

Numbers listed: $\sum_{k=1}^{n} (k + 3) = \frac{n(n+1)}{2} + 3n = \frac{n(n+7)}{2}$.

Integers passed (listed or skipped): $\sum_{k=1}^{n} (2k + 3) = n(n+1) + 3n = n(n+4)$. So round $n+1$ begins with the integer $n(n+4) + 1$.

Check: $n = 1$ gives $4$ listed and $5$ passed; $n = 2$ gives $9$ listed and $12$ passed, and the next term is $13$, matching the given start.

Now find the round containing the $500{,}000$th term. We need $\frac{n(n+7)}{2} \approx 500{,}000$, i.e. $n^2 + 7n \approx 1{,}000{,}000$, so $n \approx 996$. Indeed
$$\frac{996 \cdot 1003}{2} = 498 \cdot 1003 = 499{,}494 < 500{,}000,$$
and round $997$ lists $1000$ more, which is plenty. The integers passed after $996$ rounds total $996 \cdot 1000 = 996{,}000$.

Round $997$ lists $1000$ consecutive integers starting at $996{,}001$. The $500{,}000$th term is entry number $500{,}000 - 499{,}494 = 506$ of this block:
$$996{,}000 + 506 = 996{,}506.$$

The answer is $\boxed{\textbf{(A)}\ 996,506}$.