Problem 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 の場合のカプレカ定数を Cb と定義しよう. また関数 sb(i) を以下のように定義する:

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

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

0 < i < b5 における sb(i) の和を S(b) と定義しよう.
例えば, S(15) = 5274369
S(111) = 400668930299

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


トップ   編集 凍結 差分 バックアップ 添付 複製 名前変更 リロード   新規 一覧 単語検索 最終更新   ヘルプ   最終更新のRSS
Last-modified: 2013-02-11 (月) 00:50:44 (1649d)