Consider the following sequence, defined by recursion:
$g(0)=g(1)=0$. If $n>1$, let $g(n)$ be the mex of the $g(k)$ with $\frac{n}{2} \leq k < n$.
The first values of $g(n)$ with $0 \leq n \leq 30$ are:
$0, 0, 1, 0, 2, 1, 3, 0, 4, 2, 5, 1, 6, 3, 7, 0, 8, 4, 9, 2, 10, 5, 11, 1, 12, 6, 13, 3, 14, 7, 15$
Question. What is a closed formula for $g(n)$?
I have already found a more simple recursion for $g(n)$: The initial values are $0,0,1,0$. If $n$ is even, we have $g(n)=\frac{n}{2}$. If $n$ is odd, we have $g(n)=g(\frac{n-1}{2})$. Of course this will implement an easy computation of $g(n)$ if we have given the binary representation of $n$.
Background: $g$ is the SG function for the subtraction game, where a player has to remove at most the half of the counters, but at least one.