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