65 lines
2.9 KiB
Markdown
65 lines
2.9 KiB
Markdown
---
|
|
id: 5900f50b1000cf542c51001d
|
|
title: '問題 414: カプレカ定数'
|
|
challengeType: 5
|
|
forumTopicId: 302083
|
|
dashedName: problem-414-kaprekar-constant
|
|
---
|
|
|
|
# --description--
|
|
|
|
6174 は驚くべき数です。その各位を降順に並べ替えた数から昇順に並べ替えた数を引くと、$7641 - 1467 = 6174$ となるのです。
|
|
|
|
さらに驚くべきことに、いずれの 4 桁の数から始めても、並べ替えと減算を繰り返すと最終的に 6174 になるか、または、すべての桁の数字が同じである場合は即座に 0 になります。
|
|
|
|
4 桁より少ない桁の数についても、4 桁になるまで先行ゼロを付けることで上と同様のことが起こります。
|
|
|
|
例えば、 数 0837 から始めると次のようになります。
|
|
|
|
$$\begin{align} & 8730 - 0378 = 8352 \\\\
|
|
& 8532 - 2358 = 6174 \end{align}$$
|
|
|
|
6174 はカプレカ定数と呼ばれます。 0 かカプレカ定数になるまでこのように並べ替えと減算を繰り返すプロセスは、カプレカ操作と呼ばれます。
|
|
|
|
基数や桁数が異なる数に対するカプレカ操作を考えることができます。 残念ながら、すべてのケースに必ずカプレカ定数があるわけではありません。一部の入力値が最終的に循環に入るか、または入力値ごとに定数が異なるかのいずれかが起こります。 しかし、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 である。
|
|
- それ以外のときの値は、$C_b$ に到達するまでに基数 $b$ でカプレカ操作を繰り返す必要のある回数である。
|
|
|
|
なお、すべての整数 $i < b^5$ に対して $sb(i)$ を定義することができます。 $b$ を基数として表される $i$ が 5 桁未満の数である場合、カプレカ操作を行う前にその数が 5 桁になるまで先行ゼロを付けます。
|
|
|
|
$0 < i < b^5$ のとき、$sb(i)$ の和を $S(b)$ と定義します。 例: $S(15) = 5\\,274\\,369$ $S(111) = 400\\,668\\,930\\,299$
|
|
|
|
$2 ≤ k ≤ 300$ のとき、$S(6k + 3)$ の和を求めなさい。 回答は、下位 18 桁とすること。
|
|
|
|
# --hints--
|
|
|
|
`kaprekarConstant()` は `552506775824935500` を返す必要があります。
|
|
|
|
```js
|
|
assert.strictEqual(kaprekarConstant(), 552506775824935500);
|
|
```
|
|
|
|
# --seed--
|
|
|
|
## --seed-contents--
|
|
|
|
```js
|
|
function kaprekarConstant() {
|
|
|
|
return true;
|
|
}
|
|
|
|
kaprekarConstant();
|
|
```
|
|
|
|
# --solutions--
|
|
|
|
```js
|
|
// solution required
|
|
```
|