Project Euler Problem 961

Solution

Answer: 166666666689036288

The game state depends only on which digits are zero/nonzero, not on the actual values of the nonzero digits.

Represent a number by a binary string:

1 = nonzero digit
0 = zero digit

For example:

10501 → 10101
7008 → 1001

Every binary pattern with $k$ ones corresponds to exactly $9^k$ actual integers (each nonzero digit has 9 choices).

A move deletes one position from the binary string and then strips leading zeros.

We can therefore solve the game recursively on binary strings.

from functools import lru_cache

@lru_cache(None)
def winning(pattern):
    # "0" means there are no nonzero digits left,
    # so the previous player already won.
    if pattern == "0":
        return False

    n = len(pattern)

    # Try every possible digit deletion
    for i in range(n):
        nxt = (pattern[:i] + pattern[i+1:]).lstrip('0')

        if nxt == "":
            nxt = "0"

        # If any move reaches a losing position,
        # current position is winning.
        if not winning(nxt):
            return True

    return False

answer = 0

# Numbers below 10^18 have length 1..18
for length in range(1, 19):

    # First digit must be nonzero => leading bit is 1
    for mask in range(1 << (length - 1), 1 << length):

        pattern = bin(mask)[2:]

        if winning(pattern):
            answer += 9 ** pattern.count('1')

print(answer)

Running this code gives:

166666666689036288

Checks:

$W(100)=18$ ✔
$W(10^4)=1656$ ✔

So the required value is

Answer: 166666666689036288