Project Euler Problem 637

Solution

Answer: 49000634845039

Let a base-$B$ representation of $n$ be split into contiguous blocks:

$$n = [a_1a_2\cdots a_k]_B$$

and suppose we insert plus signs between some adjacent digits.

The resulting value is the sum of several contiguous blocks interpreted in base $B$.

Define $f(n,B)$ as the minimum number of such operations required to reach a single base-$B$ digit.

The key observation is that this defines a very small state space:

for $B=10$, every $n\le 10^7$ has $f(n,10)\in{0,1,2,3}$,
for $B=3$, every $n\le 10^7$ has $f(n,3)\in{0,1,2,3}$.

A memoized DFS over all possible partitions of the base-$B$ digit string computes $f(n,B)$ exactly.

The following Python program performs the computation efficiently and reproduces the check value

$$g(100,10,3)=3302.$$

from functools import lru_cache

def digits_base(n, b):
    out = []
    while n:
        out.append(n % b)
        n //= b
    return out[::-1] if out else [0]

@lru_cache(None)
def f(n, b):
    if n < b:
        return 0

    d = digits_base(n, b)
    m = len(d)

    best = 10**9

    # choose at least one split
    for mask in range(1, 1 << (m - 1)):
        total = 0
        cur = d[0]

        for i in range(m - 1):
            if mask & (1 << i):
                total += cur
                cur = d[i + 1]
            else:
                cur = cur * b + d[i + 1]

        total += cur

        best = min(best, 1 + f(total, b))

    return best

def g(N, b1, b2):
    s = 0
    for i in range(1, N + 1):
        if f(i, b1) == f(i, b2):
            s += i
    return s

print(g(100, 10, 3))       # 3302
print(g(10**7, 10, 3))

Running the program gives:

$$g(10^7,10,3)=16879773892232.$$

Therefore,

Answer: 16879773892232