# Game of Nim (Find winning states in large range)

If I want to solve a game of nim with 3 piles containing (x, 2x, 3x) respectively

I know that the solution of (winning) iff x^2x^3x != 0

but if x can be in the range from 1 to 2^61 so How many winning states in this range?

I want to solve this problem ... I tried to find a pattern but I think there is no pattern for that

• Try understanding first when $a\oplus b = a+b$. – Yuval Filmus Nov 28 '17 at 19:29
• Because a xor b xor c ≠ 0 iff a xor b ≠ c. And x xor 2x xor 3x ≠ 0 iff x xor 2x ≠ 3x. – gnasher729 Dec 28 '17 at 23:05

Let $a=a_{n-1} \cdots a_0$ and $b=b_{n-1} \cdots b_0$ be two positive integers with given binary expansion. Since $z+w = 2(z \land w) + (z \oplus w)$, we have $$a + b = a \oplus b + 2(a \land b),$$ where $a \oplus b$ and $a \land b$ are bitwise XOR and AND. In particular, $a + b = a \oplus b$ iff $a \land b = 0$.
Consider now the equation $x \oplus 2x \oplus 3x = 0$. We can rewrite it as $x \oplus 2x = 3x = x + 2x$. Above we have seen that this is equivalent to $x \land 2x = 0$. If $x = x_{n-1} \ldots x_0$ then $$x \land 2x = 0 (x_{n-1} \land x_{n-2}) \ldots (x_1 \land x_0) 0.$$ Thus $x \oplus 2x \oplus 3x = 0$ if the binary expansion of $x$ doesn't contain two adjacent 1s.
It remains to count how many binary strings of length $n$ (in your case, $n = 61$) satisfy this condition. It is a standard exercise to show that the answer is the Fibonacci number $F_{n+2}$.