A combinatorial question about certain sequences

Question

Consider the sequence defined by the following algorithm:

Make a stack of tickets numbered from 1 to $n,n>1 \in N$ and arranged in reverse order with the ticket numbered 1 at the bottom and that with $n$ at the top. Now apply the following repeatedly until we are left with only one ticket: Throw aside the top ticket and put the next ticket at the bottom. Define the number on the ticket so obtained at the end of the process as $a_n$.Also,define $a_1$ to be 1. My question is:
Does the sequence $\langle a_n\rangle$ contain arbitrarily long monotonically increasing and arbitrarily long monotonically decreasing subsequences? Can we find a closed formula for $a_n?$
Mathematically I have absolutely no idea but the following plot for the first 20000 values makes me suspect it might be true.

On the x-axis is the value of $n$ and on the y -axis is the value of $a_n.$I will be highly obliged for any hints/suggestions

Answer 1

Inductively, $a_n$ tells us the index of the ticket selected from the reordered stack $n, 1, 2, \ldots, (n-1)$ to determine $a_{n+1}$. So $$a_n = \begin{cases} 1 & \textrm{if } n = 1 \\ n-1 & \textrm{if }a_{n-1} = 1 \\ a_{n-1} - 1 & \textrm{otherwise} \end{cases} \tag{1}$$

Then for $1 \le k \le 2^n$, $$a_{2^n + k} = 2^n + 1 - k \tag{2}$$

Proof of $(2)$ by induction on $n$: the base case is $n=0$ where the only value of $k$ is $1$ and we do indeed have $a_2 = 1$. For the inductive step, we assume it holds for $n-1$. Then $a_{2^n} = 1$, so $a_{2^n+1} = 2^n$ by $(1)$, and $(2)$ holds for $k=1$. Then by induction on $k$ using $(1)$, $(2)$ continues to hold until $k=2^n$, where we have $a_{2^{n+1}} = 1$.