yaworsw/euler-manager

---
:id: 400
:name: Fibonacci tree game
:url: https://projecteuler.net/problem=400
:content: "A **Fibonacci tree** is a binary tree recursively defined as:\n\n- T(0)
  is the empty tree.\n- T(1) is the binary tree with only one node.\n- T(<var>k</var>)
  consists of a root node that has T(<var>k</var>-1) and T(<var>k</var>-2) as children.\n\nOn
  such a tree two players play a take-away game. On each turn a player selects a node
  and removes that node along with the subtree rooted at that node.  \nThe player
  who is forced to take the root node of the entire tree loses.\n\nHere are the winning
  moves of the first player on the first turn for T(<var>k</var>) from <var>k</var>=1
  to <var>k</var>=6.\n\n![p400_winning.png]({{ images_dir }}/p400_winning.png)\n\nLet
  <var>f</var>(<var>k</var>) be the number of winning moves of the first player (i.e.
  the moves for which the second player has no winning strategy) on the first turn
  of the game when this game is played on T(<var>k</var>).\n\nFor example, <var>f</var>(5)
  = 1 and <var>f</var>(10) = 17.\n\nFind <var>f</var>(10000). Give the last 18 digits
  of your answer.\n\n"