euler/961.py

#!/usr/bin/env pypy3

# Generated by GPT-5 on 2025-11-05. Tested on Ubuntu 25.04, pypy3 3.11.11. Runtime on Lenovo ThinkPad P14s: 0m1.512s

from functools import lru_cache
from itertools import product

# --- Utility functions ---

def normalize(s):
    """Remove leading zeros. If empty, return '0'."""
    s = s.lstrip('0')
    return s if s != '' else '0'

def is_terminal(s):
    """Return True if the string has no nonzero digits."""
    return all(ch == '0' for ch in s)

# --- Recursive solver for arbitrary strings ---
@lru_cache(maxsize=None)
def first_player_wins(s):
    """
    Return True if the player to move has a forced win from string s.
    s: decimal string representing current number (no leading zeros except '0').
    """
    if is_terminal(s):
        return False  # game already ended, previous player won
    
    n = len(s)
    for i in range(n):
        new_s = s[:i] + s[i+1:]
        # if removing this digit removes the last nonzero digit, current player wins
        if not any(ch != '0' for ch in new_s):
            return True
        new_s_norm = normalize(new_s)
        # If opponent loses from this position, we win
        if not first_player_wins(new_s_norm):
            return True
    return False

# --- Pattern-based solver (zeros/nonzeros) ---
@lru_cache(None)
def wins_for_pattern(pattern):
    """
    pattern: tuple of 0/1 (1=nonzero digit, 0=zero)
    Returns True if the player to move can force a win.
    """
    s = ''.join('1' if b else '0' for b in pattern)
    return first_player_wins(s)

# --- Compute W(10^18) ---

def W_digits_weighted(d):
    """
    Compute the number of winning integers with exactly d digits.
    Uses the fact that each nonzero digit can be 1..9.
    """
    total = 0
    for bits in product([0,1], repeat=d):
        if bits[0] == 0:  # skip patterns with leading zero
            continue
        if wins_for_pattern(bits):
            k = sum(bits)  # number of nonzero digits
            total += 9**k
    return total

# Sum over lengths 1..18
W_by_d = {}
for d in range(1, 19):
    val = W_digits_weighted(d)
    W_by_d[d] = val
    print(f"d={d}, W(d) = {val}")

W_10_18 = sum(W_by_d[d] for d in range(1, 19))
print("\nFinal answer: W(10^18) =", W_10_18)