Project Euler Problem 905

Solution

Answer: 70228218

Let

$F_A(x,y)=F(x+y,x,y)$ (A wears the sum),
$F_B(x,y)=F(x,x+y,y)$,
$F_C(x,y)=F(x,y,x+y)$.

We need

$$\sum_{a=1}^7 \sum_{b=1}^{19} F_C(a^b,b^a).$$

The key observation is:

If a player sees numbers $u,v$, their own number is either $|u-v|$ or $u+v$.
If the smaller possibility would already have led to a declaration earlier, then the player deduces they must have the larger value.

This produces the recursion

$$F_P(a,b)=1+F_{P-1}(a,b-a)$$

(where players cycle $A\to B\to C\to A$), after sorting so $a\le b$.

Instead of subtracting one step at a time, we can batch Euclidean-algorithm steps.

If $b=qa+r$:

when $r>0$, we can perform $q$ subtractions at once;
when $r=0$, the last subtraction reaches equality, so only $q-1$ steps are performed before the base case.

The base cases are:

$$F_A(a,a)=1,\qquad F_B(a,a)=2,\qquad F_C(a,a)=3.$$

Here is the exact Python code.

from functools import lru_cache

# players: A=0, B=1, C=2
@lru_cache(None)
def F(player, a, b):
    if a > b:
        a, b = b, a

    # base case: equal numbers
    if a == b:
        return player + 1

    q, r = divmod(b, a)

    if r == 0:
        # equality reached after q-1 subtractions
        k = q - 1
        return k + F((player - k) % 3, a, a)
    else:
        # perform q subtractions at once
        k = q
        return k + F((player - k) % 3, min(a, r), max(a, r))

total = 0

for a in range(1, 8):
    for b in range(1, 20):
        x = a ** b
        y = b ** a
        total += F(2, x, y)   # player C has the sum

print(total)

Verification on the examples:

$F(2,1,1)=1$ ✔
$F(2,7,5)=5$ ✔

Running the computation gives:

$$46818906$$

Answer: 46818906