Project Euler Problem 414

Project Euler Problem 414

Solution

Answer: 552506775824935461

Let the five digits (in base $b$) after sorting be

$$x_0 \le x_1 \le x_2 \le x_3 \le x_4.$$

The Kaprekar step replaces the number by

$$(x_4x_3x_2x_1x_0)_b-(x_0x_1x_2x_3x_4)_b.$$

A key simplification is that the result depends only on the two gaps

$$\alpha=x_4-x_0,\qquad \beta=x_3-x_1.$$

After carrying through the subtraction carefully, the resulting 5-digit number has digits

$$(\alpha,\ \beta-1,\ b-1,\ b-\beta-1,\ b-\alpha)_b,$$

so the entire process reduces to a deterministic map on the pair $(\alpha,\beta)$.

For bases $b=6t+3\neq 9$, the unique fixed point is the Kaprekar constant

$$C_b=(5t,\ 2t,\ 6t+2,\ 4t+1,\ 2t+1)_b.$$

The state graph is finite and every nontrivial state flows to this fixed point.

One can therefore compute:

1. the distance (number of Kaprekar iterations) from every state to the fixed point,
2. the number of actual 5-digit numbers corresponding to each state,
3. and finally sum all contributions.

Carrying this out for every base

$$b=6k+3,\qquad 2\le k\le 300,$$

and summing all corresponding $S(b)$, the required final value (modulo $10^{18}$) is

Answer: 552506775824935461