projecteuler.net

Unbalanced Nim

Published on Sunday, 9th November 2014, 01:00 am; Solved by 190;
Difficulty rating: 80%

Problem 488

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 < a < b < c < 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(1018).