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 Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle (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 Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle X(n_1, n_2, n_3) = n_1 \oplus n_2 \oplus n_3}
  • The given condition Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle X(n, 2n, 3n)=0} translates to Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle n \oplus 2n \oplus 3n = 0}

• XOR/Bitwise operations:
  • Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle 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