Kaprekarの操作
概要
Kaprekarの操作（Kaprekar routine）とは、$k$ 桁の数（先頭の $0$ も桁として残す）の数字を大きい順に並べた数から小さい順に並べた数を引き、結果を再び $k$ 桁の数として同じ操作をくり返すことである。差は $9$ の倍数で、3 桁では $99(a-c)$、4 桁では $999(a-d)+90(b-c)$（数字を $a\ge b\ge c\ge d$ と並べたとき）となるので、1 回目の結果は 3 桁で 9 個、4 桁で 54 個に限られる。これを使うと、すべての数字が同じではない 3 桁の数は高々 6 回で $495$ に、4 桁の数は高々 7 回で $6174$ になり、そこから動かないことが示せる。2 桁や 5 桁では、動かない数に着かず周期に入る数がある。
高校での出発点：並べ替えて引くと 6174 に着く
4 桁の数を 1 つ選び、その数字を大きい順に並べた数から、小さい順に並べた数を引く。出てきた数に同じことをくり返す。たとえば 2026 から始めてみる。
2026 の数字は $2,0,2,6$ である。大きい順に並べると $6220$、小さい順に並べると $0226$（先頭の $0$ も 1 桁として残す。数としては $226$）なので
$$
6220-0226=5994
$$
である。くり返すと
$$
\begin{aligned}
9954-4599&=5355\\
5553-3555&=1998\\
9981-1899&=8082\\
8820-0288&=8532\\
8532-2358&=6174\\
7641-1467&=6174
\end{aligned}
$$
となる。6 回目で $6174$ に着き、そこからは $6174$ のまま動かない。
352 から始めると
$$
532-235=297,\quad 972-279=693,\quad 963-369=594,\quad 954-459=495,\quad 954-459=495
$$
で、4 回目で $495$ に着き、そこから動かない。
別の数から始めても、4 桁なら $6174$、3 桁なら $495$ に着く。本当にどの数から始めてもそうなるのか。何回で着くのか。調べる数は 4 桁でも 1 万個しかないので、全部を計算機で試すことはできる。しかし、この記事では、手で追える個数まで場合を減らす論法を示し、残った有限個を表で全部確かめる。この記事では次の問いに答える。
- 「並べ替えて引く」操作を、先頭の $0$ の扱いまで含めてどう決めるか。→ def-kap-routine
- 並べ替えて引いた差には、どんな性質があるか。→ prop-kap-nine
- 3 桁の数は、必ず $495$ に着くか。何回で着くか。→ thm-kap-three
- 4 桁の数は、必ず $6174$ に着くか。何回で着くか。→ thm-kap-four
- 2 桁や 5 桁ではどうなるか。→ ex-kap-two、ex-kap-cx-five
高校の計算 この記事の言葉 大学の言葉 数字を並べ替えても各位の数字の和は同じ 差は $9$ の倍数 法 $9$ での不変量 $1000a+100b+10c+d$ と書く 差 $999(a-d)+90(b-c)$ 位取り記数法 起こりうる場合を書き出す 1 回目の結果は 54 通り 有限集合への帰着 同じ数がくり返し出てくる 動かない数・周期 写像の不動点・周期軌道
言葉の準備：先頭の 0 を残す約束
2026 の例では、小さい順に並べた $0226$ を 4 桁の数として扱った。この扱いを先に決めておかないと、操作の結果が変わってしまう（ex-kap-convention）。この記事では、次の約束で考える。
正の整数 $k$ を決める。$0$ 以上 $10^k-1$ 以下の整数 $n$ を、先頭に必要なだけ $0$ を付けて、ちょうど $k$ 桁の数字の列で書く（$k=4$ なら $226$ は $0226$、$5$ は $0005$）。この $k$ 桁の列を $k$ 桁の数 とよぶ。
$k$ 桁の数 $n$ の $k$ 個の数字（先頭の $0$ も含む）を、大きい順に並べた列が表す数を $n^{+}$、小さい順に並べた列が表す数を $n^{-}$ とし、
$$
K(n)=n^{+}-n^{-}
$$
とおく。$K(n)$ も $0$ 以上 $10^k-1$ 以下なので、再び先頭に $0$ を付けて $k$ 桁の数として書く。$n$ に $K$ を施して $K(n)$ を得る操作を Kaprekar の操作 という。
$k$ 個の数字がすべて同じ $k$ 桁の数（$333$、$7777$、$0000$ など）を ぞろ目 という。
$K(n)=n$ となる数を、$K$ の 動かない数 という。$K$ を何回か施して動かない数 $m$ に着けば、その後はずっと $m$ のままである。「$n$ は $r$ 回で $m$ になる」とは、$K$ を $r$ 回施して初めて $m$ になることとする（$n=m$ なら $0$ 回）。
- $k=4$、$n=2111$：$n^{+}=2111$、$n^{-}=1112$ で $K(n)=999$。これを $0999$ と書き、次は $n^{+}=9990$、$n^{-}=0999$ で $9990-0999=8991$ である。続けて $9981-1899=8082$、$8820-0288=8532$、$8532-2358=6174$ で、2111 は 5 回で $6174$ になる。
- $k=3$、$n=100$：数字は $1,0,0$ で、$n^{+}=100$、$n^{-}=001$ なので $K(n)=99$、つまり $099$ である。次は $990-099=891$ で、以後 $981-189=792$、$972-279=693$、$963-369=594$、$954-459=495$ となり、100 は 6 回で $495$ になる。
並べ替えた差は 9 の倍数
$n^{+}$ と $n^{-}$ は同じ数字を並べ替えたものなので、各位の数字の和が等しい。倍数の判定法 の定理「各位の数字の和による判定」は、正の整数を 9 で割った余りが各位の数字の和を 9 で割った余りに等しいことを述べている。だから $n^{+}$ と $n^{-}$ は 9 で割った余りが等しく、差 $K(n)$ は 9 の倍数である。桁数が小さいときは、差をもっとはっきり書ける。
$k$ 桁の数 $n$ について、$K(n)$ は $9$ の倍数である。さらに、$n$ の数字を大きい順に並べたものを次のように書くと、$K(n)$ は次の式で表せる。
- $k=2$、数字 $a\ge b$：$K(n)=9(a-b)$。
- $k=3$、数字 $a\ge b\ge c$：$K(n)=99(a-c)$。
- $k=4$、数字 $a\ge b\ge c\ge d$：$K(n)=999(a-d)+90(b-c)$。
9 の倍数であること：$n^{+}$ と $n^{-}$ の各位の数字の和は同じ値 $S$ である。倍数の判定法 の定理「各位の数字の和による判定」により $n^{+}\equiv S$、$n^{-}\equiv S\pmod9$ なので（$n^{-}$ や $n^{+}$ が $0$ のときも $0\equiv S=0$ で成り立つ）、$K(n)=n^{+}-n^{-}\equiv0\pmod9$ である。
式の形：位取りで書いて引き算する（n進法と記数法）。
- $n^{+}=10a+b$、$n^{-}=10b+a$ なので、$K(n)=9a-9b=9(a-b)$。
- $n^{+}=100a+10b+c$、$n^{-}=100c+10b+a$ なので、$K(n)=99a-99c=99(a-c)$。真ん中の $b$ は打ち消し合って消える。
- $n^{+}=1000a+100b+10c+d$、$n^{-}=1000d+100c+10b+a$ なので
$$ K(n)=(1000-1)a+(100-10)b+(10-100)c+(1-1000)d=999(a-d)+90(b-c) $$
である。$999$ と $90$ はどちらも 9 の倍数なので、ここからも $K(n)$ が 9 の倍数であることが分かる。$\square$
- 2026 の数字を大きい順に並べると $a=6$、$b=2$、$c=2$、$d=0$ で、$999\cdot6+90\cdot0=5994$。ex-kap-start-4 の 1 回目の結果と一致し、$5994=9\cdot666$ である。
- 352 の数字は $a=5$、$b=3$、$c=2$ で、$99\cdot(5-2)=297$。ex-kap-start-3 と一致する。
数字を並べ替えても 9 で割った余りが変わらないことは、チェックディジット では弱点だった。数字の和だけを検査に使うと、入れ替えの誤りを見逃してしまうからである。この記事では、同じ性質が逆に強みになる。prop-kap-nine の式は、$K(n)$ が数字そのものではなく、数字の 差 $a-c$ や $a-d$、$b-c$ だけで決まることを示している。差のとりうる値は少ないので、1 回目の結果のとりうる値も少なくなる。
$k=2$ で、ぞろ目でない数 $n$ を考える。prop-kap-nine の 1 より $K(n)=9(a-b)$ で、$a-b$ は $1$ から $9$ のどれかなので、1 回目の結果は $09,18,27,36,45,54,63,72,81$ の 9 個のどれかである。それぞれに $K$ を施すと
| $n$ | $09$ | $18$ | $27$ | $36$ | $45$ | $54$ | $63$ | $72$ | $81$ |
|---|---|---|---|---|---|---|---|---|---|
| $K(n)$ | $81$ | $63$ | $45$ | $27$ | $09$ | $09$ | $27$ | $45$ | $63$ |
となる。$09\to81\to63\to27\to45\to09$ と 5 個の数が輪になってくり返し、$18,36,54,72$ は 1 回でこの輪に入る。$K(n)=n$ となる数はこの 9 個の中になく、ぞろ目の $K$ は $00$ なので、2 桁では（$00$ を除いて）動かない数がない。どの数から始めても、最後はこの 5 個の輪を回り続ける。
主定理 1：3 桁の数は 495 に着く
$k=3$ とする。ぞろ目でない 3 桁の数は、$K$ を高々 6 回施すと $495$ になる。$495$ は動かない数である。さらに、ちょうど 6 回かかるのは、最大の数字と最小の数字の差が $1$ である数（$100$、$211$、$788$ など）に限る。
方針：1 回目の結果が $99p$（$p=1,\dots,9$）の 9 個に限られることを prop-kap-nine で示し、$99p$ の数字を調べて、次の結果が $99g(p)$ の形になることを示す。あとは $p$ の動きを追えばよい。
段 1（1 回目の結果）。ぞろ目でない 3 桁の数 $n$ の数字を $a\ge b\ge c$ とする。ぞろ目でないので $a> c$ であり、$p=a-c$ は $1$ 以上 $9$ 以下である。prop-kap-nine の 2 より $K(n)=99p$ である。
段 2（$99p$ の数字）。$p=1,\dots,9$ について
$$
99p=100p-p=100(p-1)+90+(10-p)
$$
で、$p-1$、$9$、$10-p$ はどれも $0$ 以上 $9$ 以下なので、$99p$ を 3 桁で書いたときの数字はこの 3 つである（$p=1$ なら $0,9,9$ で $099$）。最大の数字は $9$、最小の数字は $p-1$ と $10-p$ の小さい方である。
段 3（次の結果）。段 2 と prop-kap-nine の 2 から、$K(99p)=99\,g(p)$、ただし
$$
g(p)=9-\min(p-1,\ 10-p)=\max(10-p,\ p-1)
$$
である。$p\le5$ なら $10-p\ge p-1$（$2p\le11$ だから）で $g(p)=10-p$、$p\ge6$ なら $p-1>10-p$ で $g(p)=p-1$ である。
段 4（$p$ の動き）。段 3 から、$p$ は次のように動く。
$$
1\to9\to8\to7\to6\to5\to5,\qquad 2\to8,\quad 3\to7,\quad 4\to6
$$
$g(5)=\max(5,4)=5$ なので $K(495)=495$ で、$495$ は動かない数である。$99p$ から $495$ までの回数は、$p=5,6,7,8,9$ でそれぞれ $0,1,2,3,4$、$p=4,3,2$ でそれぞれ $2,3,4$（$6,7,8$ へ 1 回で移るから）、$p=1$ で $5$ である。最大は $p=1$ の $5$ 回である。
段 5（合わせる）。段 1 の 1 回目と段 4 を合わせると、$n$ から $495$ までは高々 $1+5=6$ 回である（$n$ 自身が $495$ なら $0$ 回）。ちょうど 6 回かかるのは、1 回目の結果が $099$（$p=1$）のとき、つまり $a-c=1$ のときに限る。逆に $a-c=1$ なら $n\ne495$ で、1 回目が $099$、そこから 5 回なので、ちょうど 6 回である。$\square$
段 4 の動きを、$99p$ の値で表にしておく（図 1）。
| $p=a-c$ | $1$ | $2$ | $3$ | $4$ | $5$ | $6$ | $7$ | $8$ | $9$ |
|---|---|---|---|---|---|---|---|---|---|
| 1 回目の結果 $99p$ | $099$ | $198$ | $297$ | $396$ | $495$ | $594$ | $693$ | $792$ | $891$ |
| その次 $99g(p)$ | $891$ | $792$ | $693$ | $594$ | $495$ | $495$ | $594$ | $693$ | $792$ |
| $495$ までの回数 | $5$ | $4$ | $3$ | $2$ | $0$ | $1$ | $2$ | $3$ | $4$ |
3 桁の数の 1 回目の結果になりうる 9 個の数と、K で移る先を矢印で結んだ図。どの数も 495 に着き、495 は動かない
- 352：$a-c=5-2=3$ なので 1 回目は $297$、表から残り 3 回で、合わせて 4 回である（ex-kap-start-3 と一致）。
- 211：$a-c=2-1=1$ なので 1 回目は $099$ で、合わせて 6 回かかる。実際 $211-112=099$、$990-099=891$、$981-189=792$、$972-279=693$、$963-369=594$、$954-459=495$ である。
- 910：$a-c=9-0=9$ なので 1 回目は $891$ で、合わせて 5 回である。
最大の数字と最小の数字の差が $1$ の 3 桁の数は、差が $1$ の 2 つの数字 $(0,1),(1,2),\dots,(8,9)$ の 9 組それぞれについて、3 桁にその 2 つの数字を両方使う並べ方が $2^3-2=6$ 通りずつあるので、$54$ 個ある（$001$ や $010$ のように先頭が $0$ のものも含む）。
主定理 2：4 桁の数は 6174 に着く
4 桁でも同じ考え方で場合を減らす。ただし今度は差が 2 つ（$a-d$ と $b-c$）あるので、1 回目の結果は 9 個ではなく 54 個になる。
$k=4$ とする。ぞろ目でない 4 桁の数は、$K$ を高々 7 回施すと $6174$ になる。$6174$ は動かない数である。
方針：1 回目の結果が 54 個に限られることを prop-kap-nine で示し（段 1・段 2）、その 54 個から $6174$ までの回数がどれも 6 以下であることを表で確かめる（段 3）。
段 1（1 回目の結果の形）。ぞろ目でない 4 桁の数 $n$ の数字を $a\ge b\ge c\ge d$ とし、$p=a-d$、$q=b-c$ とおく。prop-kap-nine の 3 より
$$
K(n)=999p+90q
$$
である。
段 2（$(p,q)$ の個数）。$a\ge b$ と $c\ge d$ から $p-q=(a-b)+(c-d)\ge0$ なので $q\le p$ である。$q\ge0$、$p\le9$ であり、ぞろ目でないので $a> d$、つまり $p\ge1$ である。よって $(p,q)$ は
$$
1\le p\le9,\qquad 0\le q\le p
$$
の範囲にあり、$p$ ごとに $q$ は $p+1$ 通りなので、全部で
$$
2+3+4+\cdots+10=\frac{(2+10)\cdot9}2=54
$$
通りである。したがって、1 回目の結果 $K(n)$ は、$999p+90q$ の形の 54 個の数のどれかである。
段 3（54 個から先）。54 個の数それぞれに $K$ をくり返し施した結果を、下の折りたたんだ表にすべて載せた。どの数も高々 6 回で $6174$ になる。また $7641-1467=6174$ なので $K(6174)=6174$ で、$6174$ は動かない数である。
段 4（合わせる）。段 2 の 1 回目と段 3 を合わせて、$n$ から $6174$ までは高々 $1+6=7$ 回である（$n$ 自身が $6174$ なら $0$ 回）。$\square$
54 個の行き先の表を開くと、段 3 を 1 行ずつ確かめられる。表の数はすべて先頭の $0$ を残した 4 桁で書いた（def-kap-routine）。
54 個の数の行き先の表を開く（段 3 の確かめ）
| p | q | 999p+90q | K をくり返した結果 | 6174 までの回数 |
|---|---|---|---|---|
| 1 | 0 | 0999 | 0999 → 8991 → 8082 → 8532 → 6174 | 4 |
| 1 | 1 | 1089 | 1089 → 9621 → 8352 → 6174 | 3 |
| 2 | 0 | 1998 | 1998 → 8082 → 8532 → 6174 | 3 |
| 2 | 1 | 2088 | 2088 → 8532 → 6174 | 2 |
| 2 | 2 | 2178 | 2178 → 7443 → 3996 → 6264 → 4176 → 6174 | 5 |
| 3 | 0 | 2997 | 2997 → 7173 → 6354 → 3087 → 8352 → 6174 | 5 |
| 3 | 1 | 3087 | 3087 → 8352 → 6174 | 2 |
| 3 | 2 | 3177 | 3177 → 6354 → 3087 → 8352 → 6174 | 4 |
| 3 | 3 | 3267 | 3267 → 5265 → 3996 → 6264 → 4176 → 6174 | 5 |
| 4 | 0 | 3996 | 3996 → 6264 → 4176 → 6174 | 3 |
| 4 | 1 | 4086 | 4086 → 8172 → 7443 → 3996 → 6264 → 4176 → 6174 | 6 |
| 4 | 2 | 4176 | 4176 → 6174 | 1 |
| 4 | 3 | 4266 | 4266 → 4176 → 6174 | 2 |
| 4 | 4 | 4356 | 4356 → 3087 → 8352 → 6174 | 3 |
| 5 | 0 | 4995 | 4995 → 5355 → 1998 → 8082 → 8532 → 6174 | 5 |
| 5 | 1 | 5085 | 5085 → 7992 → 7173 → 6354 → 3087 → 8352 → 6174 | 6 |
| 5 | 2 | 5175 | 5175 → 5994 → 5355 → 1998 → 8082 → 8532 → 6174 | 6 |
| 5 | 3 | 5265 | 5265 → 3996 → 6264 → 4176 → 6174 | 4 |
| 5 | 4 | 5355 | 5355 → 1998 → 8082 → 8532 → 6174 | 4 |
| 5 | 5 | 5445 | 5445 → 1089 → 9621 → 8352 → 6174 | 4 |
| 6 | 0 | 5994 | 5994 → 5355 → 1998 → 8082 → 8532 → 6174 | 5 |
| 6 | 1 | 6084 | 6084 → 8172 → 7443 → 3996 → 6264 → 4176 → 6174 | 6 |
| 6 | 2 | 6174 | 6174 | 0 |
| 6 | 3 | 6264 | 6264 → 4176 → 6174 | 2 |
| 6 | 4 | 6354 | 6354 → 3087 → 8352 → 6174 | 3 |
| 6 | 5 | 6444 | 6444 → 1998 → 8082 → 8532 → 6174 | 4 |
| 6 | 6 | 6534 | 6534 → 3087 → 8352 → 6174 | 3 |
| 7 | 0 | 6993 | 6993 → 6264 → 4176 → 6174 | 3 |
| 7 | 1 | 7083 | 7083 → 8352 → 6174 | 2 |
| 7 | 2 | 7173 | 7173 → 6354 → 3087 → 8352 → 6174 | 4 |
| 7 | 3 | 7263 | 7263 → 5265 → 3996 → 6264 → 4176 → 6174 | 5 |
| 7 | 4 | 7353 | 7353 → 4176 → 6174 | 2 |
| 7 | 5 | 7443 | 7443 → 3996 → 6264 → 4176 → 6174 | 4 |
| 7 | 6 | 7533 | 7533 → 4176 → 6174 | 2 |
| 7 | 7 | 7623 | 7623 → 5265 → 3996 → 6264 → 4176 → 6174 | 5 |
| 8 | 0 | 7992 | 7992 → 7173 → 6354 → 3087 → 8352 → 6174 | 5 |
| 8 | 1 | 8082 | 8082 → 8532 → 6174 | 2 |
| 8 | 2 | 8172 | 8172 → 7443 → 3996 → 6264 → 4176 → 6174 | 5 |
| 8 | 3 | 8262 | 8262 → 6354 → 3087 → 8352 → 6174 | 4 |
| 8 | 4 | 8352 | 8352 → 6174 | 1 |
| 8 | 5 | 8442 | 8442 → 5994 → 5355 → 1998 → 8082 → 8532 → 6174 | 6 |
| 8 | 6 | 8532 | 8532 → 6174 | 1 |
| 8 | 7 | 8622 | 8622 → 6354 → 3087 → 8352 → 6174 | 4 |
| 8 | 8 | 8712 | 8712 → 7443 → 3996 → 6264 → 4176 → 6174 | 5 |
| 9 | 0 | 8991 | 8991 → 8082 → 8532 → 6174 | 3 |
| 9 | 1 | 9081 | 9081 → 9621 → 8352 → 6174 | 3 |
| 9 | 2 | 9171 | 9171 → 8532 → 6174 | 2 |
| 9 | 3 | 9261 | 9261 → 8352 → 6174 | 2 |
| 9 | 4 | 9351 | 9351 → 8172 → 7443 → 3996 → 6264 → 4176 → 6174 | 6 |
| 9 | 5 | 9441 | 9441 → 7992 → 7173 → 6354 → 3087 → 8352 → 6174 | 6 |
| 9 | 6 | 9531 | 9531 → 8172 → 7443 → 3996 → 6264 → 4176 → 6174 | 6 |
| 9 | 7 | 9621 | 9621 → 8352 → 6174 | 2 |
| 9 | 8 | 9711 | 9711 → 8532 → 6174 | 2 |
| 9 | 9 | 9801 | 9801 → 9621 → 8352 → 6174 | 3 |
表の結果を、6174 までの回数ごとに数えると次のようになる。
| 6174 までの回数 | $0$ | $1$ | $2$ | $3$ | $4$ | $5$ | $6$ | 計 |
|---|---|---|---|---|---|---|---|---|
| 54 個のうちの個数 | $1$ | $3$ | $12$ | $10$ | $10$ | $10$ | $8$ | $54$ |
6 回かかるのは $4086$、$5085$、$5175$、$6084$、$8442$、$9351$、$9441$、$9531$ の 8 個である。図 2 は、54 個の数を「$6174$ まであと何回か」で段に分け、$K$ で移る先を線で結んだものである。どの道も、最後は $4176$、$8352$、$8532$ のどれかを通って $6174$ に着く。
4 桁の数の 1 回目の結果になりうる 54 個の数を、6174 まであと何回かで段に分けて並べ、K で移る先を線で結んだ図。一番上が 6174 で、一番下の段の 8 個は 6 回かかる
段 3 の表の数はすべて 54 個の中にある。54 個のどれに $K$ を施しても、それはある 4 桁の数の 1 回目の結果なので、段 1・段 2 から再び 54 個のどれかになるからである。だから、表は 54 個の数の中だけで閉じていて、表の外の数を調べる必要はない。
1004 の数字は $a=4$、$b=1$、$c=0$、$d=0$ で、$p=4$、$q=1$ なので、1 回目の結果は $999\cdot4+90\cdot1=4086$ である。表から $4086$ は 6 回かかる（$4086\to8172\to7443\to3996\to6264\to4176\to6174$）ので、1004 はちょうど 7 回かかる。thm-kap-four の「高々 7 回」の 7 は、これ以上小さくできない。
- 2026：$p=6-0=6$、$q=2-2=0$ で、1 回目は $5994$。表の $p=6$、$q=0$ の行から残り 5 回で、合わせて 6 回（ex-kap-start-4 と一致）。
- 2111：$p=2-1=1$、$q=1-1=0$ で、1 回目は $0999$。表の $p=1$、$q=0$ の行から残り 4 回で、合わせて 5 回（ex-kap-zeros と一致）。
0000 から 9999 までの 1 万個のうちぞろ目でない 9990 個について、6174 までの回数を数えると図 3 のようになる。これは計算機ですべての数を計算して数えた結果である（計算で確かめた）。thm-kap-four は 7 回以下であることを示しているが、それぞれの回数の個数までは示していない。
すべての数字が同じではない 9990 個の 4 桁の数字の列について、6174 になるまでの回数ごとの個数を表した棒グラフ。7 回かかる列が 2184 個ある
例と反例：どの仮定が効いているか
thm-kap-three と thm-kap-four には、「ぞろ目でない」と「桁数が 3 または 4」という仮定がある。どちらを外しても結論は崩れる。
| 外す条件 | 反例 | 成り立たなくなること |
|---|---|---|
| ぞろ目でない | $333$、$7777$（ex-kap-cx-repdigit） | 1 回で $000$・$0000$ になり、そこから動かない。$495$・$6174$ には着かない |
| 桁数が 3 または 4（2 桁にする） | $09\to81\to63\to27\to45\to09$（ex-kap-two） | ぞろ目でない数は動かない数に着かず、5 個の数の輪を回り続ける |
| 桁数が 3 または 4（5 桁にする） | $12345$（ex-kap-cx-five） | 動かない数に着かず、4 個の数の輪に入る |
$333$ では $n^{+}=n^{-}=333$ なので $K(333)=000$ である。$000$ もぞろ目で $K(000)=000$ なので、ずっと $000$ のままである。$7777$ も同じく $0000$ になって動かない。thm-kap-three の証明の段 1 で「ぞろ目でないので $a> c$」としたところが成り立たず、$p=a-c=0$ になって、1 回目の結果が $99p$（$p\ge1$）の 9 個に入らない。ぞろ目は、3 桁なら $000,111,\dots,999$ の 10 個、4 桁なら 10 個だけで、それ以外はすべて定理のとおりになる。
$k=5$、$n=12345$ から始めると
$$
\begin{aligned}
54321-12345&=41976\\
97641-14679&=82962\\
98622-22689&=75933\\
97533-33579&=63954\\
96543-34569&=61974\\
97641-14679&=82962
\end{aligned}
$$
となり、$82962\to75933\to63954\to61974\to82962$ の 4 個の輪に入る。この数は、動かない数にいつまでも着かない。5 桁で動かない数は $00000$ だけで、ぞろ目でない 5 桁の数は、どれも次の 3 つの輪のどれかに入る。
$$
(53955,\ 59994),\qquad(61974,\ 82962,\ 75933,\ 63954),\qquad(62964,\ 71973,\ 83952,\ 74943)
$$
この 3 つの輪と、5 桁で動かない数が $00000$ だけであることは、計算機で 10 万個の数をすべて調べて確かめたもので、この記事では証明しない（計算で確かめた。同じ 3 つの輪は Wei26 にも挙げられている）。$12345$ の輪は、上の 6 行の引き算で手で確かめられる。
定義の外の例：先頭の 0 を捨てる約束
def-kap-routine では先頭の $0$ を桁として残した。これは定理の仮定ではなく操作の定義の一部なので、別の約束をとると、定理の主張そのものが別のものになる。
$K(n)$ を計算するたびに先頭の $0$ を捨て、桁数の減った数として次の計算をする約束を考える。
(1) $100$：$100-001=99$ である。$99$ を 2 桁の数とみなすと、次は $99-99=0$ になる。先頭の $0$ を残す約束（ex-kap-zeros の (2)）では、$099$ として続けて 6 回で $495$ に着いた。
(2) $2111$：$2111-1112=999$ で、$999$ を 3 桁の数とみなすと $999-999=0$ になる。先頭の $0$ を残す約束では、$0999\to8991\to\cdots$ と続いて $6174$ に着いた。
この約束では、ぞろ目でない数でも $0$ になるものがある。100 から 999 までの 3 桁の数のうち $0$ になるのは 60 個（ぞろ目の 9 個を含む）、1000 から 9999 までの 4 桁の数のうち $0$ になるのは 77 個（ぞろ目の 9 個を含む）である（計算で確かめた。個数は Wei26 にも書かれている）。どちらの約束で考えているかで答えが変わるので、回数や個数を比べるときは約束をそろえる必要がある。
大学数学で見る：有限の世界で写像をくり返す
$k$ 桁の数は $10^k$ 個しかないので、$K$ は有限個の数の集まりから自分自身への写像である。このような写像をくり返すと、必ずどこかで同じ数が 2 回目に出てくる（鳩の巣原理：$10^k+1$ 個の数 $n,K(n),K(K(n)),\dots$ のうち 2 つは等しい）。同じ数が出てきた後は、同じ計算がくり返されるので、どの数から始めても、最後は動かない数か、いくつかの数の輪（周期）に入る。累乗の余りがくり返す理由（冪の余りの周期と元の位数）も同じ考え方である。
thm-kap-three と thm-kap-four は、3 桁・4 桁ではその行き先がただ 1 つの動かない数（$495$、$6174$）だと述べている。2 桁・5 桁では、行き先は動かない数ではなく輪だった（ex-kap-two、ex-kap-cx-five）。
桁数や底を変えたときについて開く
Wei26 によれば、この操作は 1949 年に D. R. Kaprekar が 4 桁の数について見つけたもので、$k$ 桁の数に一般化できる。10 進法で $K(n)=n$ となる数として $495$、$6174$、$549945$、$631764$ などが挙げられ、底（10 進法の 10）を変えると、行き先は $0$、動かない数、輪のどれかになり、その様子は底によって大きく変わる。6 桁の $549945$ と $631764$ が動かない数であることは、$995544-445599=549945$、$766431-134667=631764$ と、それぞれの数字を並べ替えて引けば確かめられる。
この記事の証明の要点は、「$K(n)$ が数字そのものではなく数字の差だけで決まる」ことで場合を減らし、残った有限個を全部調べることだった。桁数が増えると、差の組の個数も、そこから先を追う手間も増える。$k$ 桁の行き先を一般の $k$ について決める方法は、この記事では扱わない。
演習
ぞろ目でない 2 桁の数から始めると、高々 5 回で $09$ になることを示せ。ちょうど 5 回かかる数の例を 1 つ挙げよ。
解答を開く
ex-kap-two より、1 回目の結果は $09,18,\dots,81$ のどれかである。表をたどると、$09$ までの回数は $09$ が $0$、$45$ が $1$、$54$ が $1$、$27$ が $2$、$72$ が $2$（$72\to45\to09$）、$63$ が $3$、$36$ が $3$（$36\to27\to45\to09$）、$81$ が $4$、$18$ が $4$（$18\to63\to27\to45\to09$）である。最大は $4$ なので、1 回目と合わせて高々 $5$ 回である。ちょうど 5 回かかるのは、1 回目の結果が $81$ か $18$ になる数、つまり 2 つの数字の差が $9$ か $2$ の数である。たとえば $90$：$90-09=81$、$81-18=63$、$63-36=27$、$72-27=45$、$54-45=09$ で 5 回。
$495$ 以外の 3 桁の数で、$K$ を 1 回施すと $495$ になるのはどんな数か。
解答を開く
prop-kap-nine の 2 より、数字を $a\ge b\ge c$ とすると $K(n)=99(a-c)$ である。$99(a-c)=495$ となるのは $a-c=5$ のときに限る。よって、最大の数字と最小の数字の差がちょうど $5$ の数である（$105$、$549$、$594$、$950$ など。$495$ 自身も差は $5$ だが、すでに $495$ なので除いた）。差が $6$ の数（$106$、$600$ など）は 1 回目が $594$ で、2 回目に $495$ になる。
さらに先へ
- 数字の並べ替えで 9 で割った余りが変わらないことは 倍数の判定法 で示した。同じ性質は、数字の和だけで誤りを調べる方式が入れ替えを見逃す理由でもある（チェックディジット）。
- 有限個の値をくり返しとる操作が必ず周期に入るという構造は、冪の余りの周期と元の位数 で累乗の余りについて詳しく扱う。
- 計算で見つけた規則を証明するという流れは、数列の一般項の推定と帰納法 でも扱う。
- 位取りで数を式に書く方法は n進法と記数法 と 整数の筆算の仕組み で扱う。
関連項目
- 前提: 倍数の判定法, n進法と記数法
- 前に読む: チェックディジット, 倍数の判定法, n進法と記数法
- 次に読む: 冪の余りの周期と元の位数
- 関連（高校数学）: 曜日の計算, 数列の一般項の推定と帰納法, 整数の筆算の仕組み
参考文献
Mathpediaは寄付と、参考文献の書籍リンク（Amazonアソシエイト）の紹介料で運営されています。 支援について ／ 寄付する
