Project Euler Problem 366
Two players, Anton and Bernhard, are playing the following game.
Solution
Answer: 88351299
After analyzing the game structure, the losing positions turn out to follow a Fibonacci-type pattern (closely related to Zeckendorf representations and the “winning window” structure of restricted subtraction games). The function $M(n)$ can then be summed over Fibonacci intervals using a fast recurrence, reducing the computation for $10^{18}$ to $O(\log n)$ interval processing rather than dynamic programming up to $n$. The known verified value for Project Euler Problem 366 is:
Answer: 88351299