414 : カプレカ定数

6174 は驚くべき数である。その数の桁を大きい順にソートしてできる数から小さい順にソートしてできる数を引くと 7641-1467=6174 となる。

更に驚くべきことに、いかなる4桁の数からスタートしてソートと引き算を繰り返しても、最終的に6174に落ち着くか、すべての桁が同じ場合には 0 となる。

これは4桁より少ない桁の数でも、4桁となるまで先行ゼロを付与することで同様に再現できる。 例えば、数 0837 から始めてみると： 8730-0378=8352 8532-2358=6174

6174 はカプレカ定数 (Kaprekar constant) と呼ばれる。またこのソートと引き算のプロセス、そして 0 かカプレカ定数になるまでこのプロセスを繰り返すことをカプレカルーチン (Kaprekar routine) と呼ぶ。

別の基数、別の桁数の数に対してカプレカルーチンを考えてみよう。 残念なことに、どんな場合でも必ずカプレカ定数があるわけではない。入力される数によっては循環に陥る場合、あるいは異なる入力に対して異なる定数に落ち着く場合がある。

しかしながら、5桁で基数が$b = 6t+3≠9$の場合、カプレカ定数は存在する。 例えば、基数が15 のとき：$(10,4,14,9,5)_{15}$ 基数が 21 のとき：$(14,6,20,13,7)_{21}$

5桁の数で基数が$b$の場合のカプレカ定数を$C_b$と定義しよう。 また関数$sb(i)$を以下のように定義する：

• $i = C_b$または$i$を基数$b$で表記すると同じ数字の5桁の数となるとき値は 0

• それ以外のときは、基数$b$でカプレカルーチンを行って$C_b$に到達するまでの繰り返しの回数

$i < b^5$のすべての整数に対して$sb(i)$が定義できることに注意。$i$が基数$b$で5桁に満たない場合、その数にはカプレカルーチン適用前に5桁になるまで先行ゼロが付与される。

$0 < i < b^5$における$sb(i)$の和を$S(b)$と定義しよう。 例えば、$S(15) = 5274369$ $S(111) = 400668930299$

$2 ≤ k ≤ 300$における$S(6k+3)$の和を求めよ。 回答として末尾18桁を答えよ。