Project Euler 692 - Siegbert and Jo

Siegbert and Jo take turns playing a game with a heap of N pebbles:

1. Siegbert is the first to take some pebbles. He can take as many pebbles as he wants. (Between 1 and N inclusive.)

2. In each of the following turns the current player must take at least one pebble and at most twice the amount of pebbles taken by the previous player.

3. The player who takes the last pebble wins.

Although Siegbert can always win by taking all the pebbles on his first turn, to make the game more interesting he chooses to take the smallest number of pebbles that guarantees he will still win (assuming both Siegbert and Jo play optimally for the rest of the game).

Let H(N) be that minimal amount for a heap of N pebbles.

H(1)=1, H(4)=1, H(17)=1, H(8)=8 and H(18)=5

Let G(n) be ∑k from 1 to n of H(k), G(13)=43

Find G(23416728348467685)

Official link: https://projecteuler.net/problem=692

Thought Process

This game is called Fibonnaci Nim you can read about it here

Things to know to solve this question:

let F(n) denote the nth fibonnaci number

(1) H(N) is the smallest number in the Zeckendorf Expansion of a number

(2) H(F(n) + i) = H(i) where F(n) + I < F(n+1) - You can find this from producing the first few H(i)

Here are the first 20: [1, 2, 3, 1, 5, 1, 2, 8, 1, 2, 3, 1, 13, 1, 2, 3, 1, 5, 1]

(3) This means that:

G(F(n)) = G(F(n-1)) + G(F(n-2) - 1) + F(n)

Note: G(F(n-2) - 1) = G(F(n-2)) - F(n-2)

Therefore G(F(n)) = G(F(n-1)) + G(F(n-2)) + F(n) - F(n-2)

(4) F(80) = 23416728348467685 (This can be a hint because they use fibonnaci numbers for a reason!)

So we can quickly make a code which iteratively calculates G(F(80)) by starting with

F(1)=F(2) = 1 and G(F(1)) = G(F(2)) = 1