Take the 2-minute tour ×

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.

share|improve this question
add comment

2 Answers

up vote 1 down vote accepted

You wrote :


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,

share|improve this answer
Yes I knew this algorithm, it follows directly from this recursion. But I was too ignorant to just enter it to OEIS. Thanks for this hint. –  Martin Brandenburg Apr 9 '12 at 18:01
add comment

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.

share|improve this answer
So, in a way, this is "closed form" and can be rewritten that way. Only, it would be too ugly and cumbersome to write. I presume the reason for asking a closed form is to get a "fast" algorithm... –  Aryabhata Apr 9 '12 at 19:37
add comment

Your Answer


