Project Euler/301

Problem statement

The problem asks for the number of positive integers $n\leq 2^{30}$ such that the Nim game position (n, 2n, 3n) is a losing position for the player whose turn it is, assuming perfect play.

The function X(n1, n2, n3) determines this: X=0 for a losing position and X!=0 for a winning position

Notes

Key mathematical topics:

• Game theory (impartial game, available moves only depend on the state of the game and not on which player is moving)
  • P-positions (previous player winning, current player will lose if opponent plays optimally) and N-positions (next player winning)
  • Problem statement says, X(a,b,c)=0 corresponds to a P-position

• Bouton's Theorem (fundamental to solving Nim)
  • States that a Nmim position $(n_{1},n_{2},...,n_{k})$ is a P-position iif and only if the nim-sum of the heap sizes is zero
  • The Nim-sum is calculated using the bitwise XOR operation
  • The given 3-heap problem has a Nim-sum $X(n_{1},n_{2},n_{3})=n_{1}\oplus n_{2}\oplus n_{3}$
  • The given condition $X(n,2n,3n)=0$ translates to $n\oplus 2n\oplus 3n=0$

• XOR/Bitwise operations:
  • $a\oplus b=0\quad {\mbox{iff}}\quad a=b,a\oplus a=0$
  • XOR is associative and commutative

Solution in 0.4 seconds using Firefox