Project Euler Problem 692

Solution

Answer: 842043391019219959

Let the Fibonacci numbers be defined by

$$F_1=1,\qquad F_2=2,\qquad F_n=F_{n-1}+F_{n-2}.$$

So:

$$1,2,3,5,8,13,21,\dots$$

The key fact behind this game is that it is exactly Fibonacci Nim.

1. Mathematical analysis

Step 1: Losing positions are Fibonacci numbers

A classical result for Fibonacci Nim states:

A position with $N$ pebbles is losing iff $N$ is a Fibonacci number $F_k$.

This explains the examples:

$H(8)=8$ because $8$ is Fibonacci, so Siegbert must take all pebbles immediately.
$H(18)=5$ because

$$18 = 13+5,$$

and removing $5$ leaves $13$, a losing Fibonacci position.

Step 2: Zeckendorf representation

Every positive integer has a unique representation as a sum of non-consecutive Fibonacci numbers:

$$N = F_{a_1}+F_{a_2}+\cdots$$

This is the Zeckendorf decomposition.

For Fibonacci Nim:

The minimal winning move $H(N)$ equals the smallest Fibonacci summand in the Zeckendorf decomposition of $N$.

Examples:

$$4=3+1 \Rightarrow H(4)=1$$

$$17=13+3+1 \Rightarrow H(17)=1$$

$$18=13+5 \Rightarrow H(18)=5$$

This perfectly matches the problem statement.

Step 3: Interval structure

For numbers in the interval

$$F_m \le n < F_{m+1},$$

every number can be written uniquely as

$$n = F_m + r, \qquad 0\le r < F_{m-1}.$$

If $r>0$, the smallest Zeckendorf term of $n$ is exactly the smallest term of $r$. Hence

$$H(F_m+r)=H(r) \quad (r>0),$$

while

$$H(F_m)=F_m.$$

Therefore the interval sum is

$$B_m = \sum_{n=F_m}^{F_{m+1}-1}H(n) = F_m + G(F_{m-1}-1).$$

Let

$$S_m = G(F_m).$$

Then one obtains the recurrence

$$S_m = S_{m-1}+S_{m-2}+F_{m-1},$$

with initial values

$$S_1=1,\qquad S_2=3.$$

Check:

$$S_6 = S_5+S_4+F_5 = 23+12+8 = 43,$$

and since $F_6=13$,

$$G(13)=43,$$

matching the problem statement.

Step 4: The target value

We are given

$$N=23416728348467685.$$

This is exactly the Fibonacci number

$$F_{79}.$$

So we compute $S_{79}=G(F_{79})$ using the recurrence.

2. Python implementation

# Fibonacci numbers with F1 = 1, F2 = 2
F = [1, 2]

TARGET = 23416728348467685

# Build Fibonacci sequence until target
while F[-1] < TARGET:
    F.append(F[-1] + F[-2])

m = len(F)  # target is F_m

# S[m] = G(F_m)
S = [0] * (m + 1)

S[1] = 1  # G(1)
S[2] = 3  # G(2)

# Recurrence:
# S_m = S_(m-1) + S_(m-2) + F_(m-1)
for i in range(3, m + 1):
    S[i] = S[i - 1] + S[i - 2] + F[i - 2]

print(S[m])

3. Code walkthrough

Generate Fibonacci numbers using:

F.append(F[-1] + F[-2])

until reaching the target. 2. Since the target is exactly $F_{79}$, we want $S_{79}$. 3. Use the recurrence:

S[i] = S[i - 1] + S[i - 2] + F[i - 2]

which corresponds to

$$S_m=S_{m-1}+S_{m-2}+F_{m-1}.$$ 4. The program reproduces the sample:

$$G(13)=43.$$

4. Final verification

The target is exactly a Fibonacci number, so the recurrence applies directly.
The growth rate is roughly Fibonacci-like, so a $10^{18}$-scale answer is expected.
The recurrence reproduces the provided check value $G(13)=43$.

Answer: 842043391019219959