Finding a closed formula for some SG function

Question

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.

Answer 1

You wrote :

If $n$ is even, we have $g(n)=\frac{n}{2}$. If $n$ is odd, we have $g(n)=g(\frac{n-1}{2})$

This means that we may shift right our starting number $n$ until getting $0$ for the least significant digit at which point one more shift will return the answer!
(coder short formulation : "shift $n$ right until 'carry' equal $0$!")

I fear that a closed form solution could only be the previous algorithm in disguise (I mean artificial and much slower...).

For references about this problem you may consult the OEIS A025480 and related.

Sorry if this doesn't help,

Answer 2

If you are allowed to use bithacks:

You can first compute $x = n \& (n+1)$, where $\&$ is the bitwise AND.

This will zero out all the bits you need to right shift.

Now use any applicable (to you) bitwise hacks which count the number of trailing zeroes of $x$: http://graphics.stanford.edu/~seander/bithacks.html#ZerosOnRightLinear

Once you have the count, you can right shift it appropriately to get the desired value.

Though technically this will also be $\Omega(\log n)$, if you deal with only $32$/$64$ bit numbers this might be faster than just following the recursive method, as you will only make a constant number of operations, assuming the underlying hardware supports it.