From $\{1,2,\ldots,2002\}$, remove numbers at positions congruent to $1\bmod 3$, repeating the process until one number remains. 
We have a list of natural numbers $\{1,2,3,...,2002\}$. In each step, we remove the numbers whose positions are congruent to $1\bmod 3$. (The initial element is in position $1$.) Which is the last number remaining?

For example, in the list $\{1,2,3,\ldots,10\}$, the different steps are
$$\{\color{red}{1},2,3,\color{red}{4},5,6,\color{red}{7},8,9,\color{red}{10}\} \rightarrow 
\{\color{red}{2},3,5,\color{red}{6},8,9\} \rightarrow 
\{\color{red}{3},5,8,\color{red}{9}\} \rightarrow 
\{\color{red}{5},8\} \rightarrow 
\{8\}$$
So the last number remaining is $8$.
I prove that every element $n$, each step moves to position $n-\lceil n/3\rceil$. With Rstudio, I achieve the last number must be $1598$ and the number of steps must be $17$.
How can I prove it?
 A: Here's a sketch (omitting some details):  This process can be thought of as a map $f:\mathbb{N}\rightarrow \mathbb{N}$ sending $x\mapsto 0$ if $x\equiv 1$ mod 3 and $x\mapsto$ (new position) otherwise.  So e.g. $5\mapsto 3$, $3\mapsto 2$, $2\mapsto 1$, etc.
Now think of it in reverse.  Suppose it takes $k$ steps to get to just one number.  We know the last non-zero number (at step $k$) must be 1.  If we run the process in reverse, where does 1 go?  At step $k-1$, the numbers left are $\{1,2\}$, and 1 went to 2.  At the next step, 2 goes to 3, and then 3 goes to 5, etc.
In general, let's consider what happens at step $j$ to a list of numbers $\{1,2,\dots,n\}$.  To go backwards to step $j-1$, we insert a new number before the list and after every two successive numbers, giving something like this:
$$\{*,1,2,*,3,4,*,5,6,*,\dots\}$$
If $n$ is even, then there are $n/2$ new numbers inserted before it, so $n\mapsto 3n/2$ under this reverse process.  If $n$ is odd, then you can convince yourself that $n\mapsto (3n+1)/2$.  These two cases can be stated concisely as $$n\mapsto \lceil 3n/2\rceil$$
This gives a recursive formula for the last number standing.  The values are easy to compute: $$1,2,3,5,8,12,18,27,41,62,93,140,210,315,473,710,1065,1598,2397$$
The last number in this list that is less that 2002 is 1598, and it takes 17 steps for it to get to 1.
