Project Euler Problem 893

Project Euler Problem 893

Solution

Answer: 26688208

Let

• $L(n)$ = matchstick cost of writing $n$ directly in decimal,
• $P(n)$ = minimum cost using only multiplication,
• $M(n)$ = true minimum cost allowing both $+$ and $\times$.

The digit costs are:

$$(0,1,2,3,4,5,6,7,8,9)\mapsto(6,2,5,5,4,5,6,3,7,6)$$

and each operator costs $2$ matchsticks.

The dynamic programming recurrences are:

$$P(n)=\min\Bigl(L(n),\ P(a)+P(b)+2\Bigr)\qquad(ab=n)$$

and

$$M(n)=\min\Bigl(P(n),\ M(a)+P(n-a)+2\Bigr).$$

A fast implementation computes:

1. all literal costs $L(n)$,
2. multiplicative relaxations for all products $ab\le 10^6$,
3. additive relaxations using only low-cost summands (which stabilizes completely by cost $15$).

The implementation reproduces the check value:

$$T(100)=916.$$

For $N=10^6$, the computation gives:

$$T(10^6)=26688208.$$

Answer: 26688208