Alice and Bob have enjoyed playing Nim every day. However, they finally got bored of playing ordinary three-heap Nim.
So, they added an extra rule:
- Must not make two heaps of the same size.
The triple $(a, b, c)$ indicates the size of three heaps.
Under this extra rule, $(2,4,5)$ is one of the losing positions for the next player.
To illustrate:
- Alice moves to $(2,4,3)$
- Bob moves to $(0,4,3)$
- Alice moves to $(0,2,3)$
- Bob moves to $(0,2,1)$
Unlike ordinary three-heap Nim, $(0,1,2)$ and its permutations are the end states of this game.
For an integer $N$, we define $F(N)$ as the sum of $a + b + c$ for all the losing positions for the next player, with $0 \lt a \lt b \lt c \lt N$.
For example, $F(8) = 42$, because there are $4$ losing positions for the next player, $(1,3,5)$, $(1,4,6)$, $(2,3,6)$ and $(2,4,5)$.
We can also verify that $F(128) = 496062$.
Find the last $9$ digits of $F(10^{18})$.
solutions/s488.md.