Given $k, n > 0$, how many ordered lists $a_1, a_2, \dots, a_k$ are there such that $a_i \geq 0$ for all $i$, such that $\sum_i a_i = n$ and $\oplus_i a_i = 0$, where the latter operation denotes bitwise xor (i.e. $15 \oplus 3 = 12$).

It is likely there is no closed-form expression, in that case a reasonably fast algorithm would also be interesting.

EDIT: Context: this is the number of losing starting positions in a game of Nim with $k$ initial piles containing a total of $n$ stones.

  • 2
    $\begingroup$ See section 5 of Tanya Khovanova and Joshua Xiong, "Nim Fractals", arxiv.org/abs/1405.5942, in particular Theorem 27. $\endgroup$ – Michael Lugo Jan 10 at 20:22
  • $\begingroup$ @MichaelLugo Thanks, that's pretty good. It only gives $n$ even though. $\endgroup$ – Timon Knigge Jan 10 at 21:32
  • 1
    $\begingroup$ Aha, but if $n \equiv 1 \mod 2$ then there is an odd number of odd sized piles and the nim sum is never $0$. $\endgroup$ – Timon Knigge Jan 10 at 21:36

Let $F(n,k,x)$ denote the amount of ordered lists $a_1,...,a_k$ such that $a_i\geq0$, $\sum a_i=n$ and $\oplus a_i=x$. Then considering all possible values of $a_k$ we find the recursive formula $$F(n,k,x)=\sum_{i=0}^nF(n-i,k-1,x\oplus i).$$ This gives us an $\mathcal{O}(n^3k)$ time algorithm. Not very fast, but at least polynomial in $n$ and $k$.

  • 1
    $\begingroup$ One can use binary doubling (as in squaring by exponentiation) to get this to $O(n^3 \log k)$. Still very slow though. $\endgroup$ – Timon Knigge Jan 10 at 20:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.