Problem #121
The Game of Fibonacci and Powers of Two
You are given a pile of stones. Two people play this game turn by turn. In any turn, a player can remove a number of stones from the pile, say X, such that X can be either a non zero Fibonacci number or a power of 2.
The person that empties the pile wins the game. Both the persons play optimally, i.e they try to make the best possible move that will help them win. If the number of stones in the pile varies between 1 and 10^6, in how many cases will the first player lose?