*[[Problem 414:http://projecteuler.net/problem=414]] 「カプレカ定数」 [#y3a31aa5]

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)&sub{15};~
基数が 21 のとき: (14,6,20,13,7)&sub{21};

5桁の数で基数が '''b''' の場合のカプレカ定数を &tex{C_{b}}; と定義しよう. また関数 '''sb(i)''' を以下のように定義する:

-もし '''i''' = &tex{C_{b}}; であるか, '''i''' が基数 '''b''' で5つの同一の桁からなる場合は値が 0.
-それ以外の時は, 基数 '''b''' でカプレカルーチンを行った時に '''i''' が &tex{C_{b}}; に到達するまでの繰り返しの回数が値となる.

'''i''' < '''b'''&sup{5}; のすべての整数で '''sb(i)'''  が定義できることに注意. もし '''i''' が基数 '''b''' で5桁以下となる場合, その数にはカプレカルーチン適用前に5桁になるまで先行ゼロが付与される.

0 < '''i''' < '''b'''&sup{5}; における '''sb(i)''' の和を '''S(b)''' と定義しよう.~
例えば, '''S'''(15) = 5274369~
'''S'''(111) = 400668930299

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

トップ   編集 差分 バックアップ 添付 複製 名前変更 リロード   新規 一覧 検索 最終更新   ヘルプ   最終更新のRSS