解説:カプレカ数の条件
\[ K(n)=D(n)-A(n),\qquad K(n)=n>0 \] 同じ数をこの操作に入れると、その数自身が返るので固定点と呼ぶ。任意の数から操作を繰り返す過程や、複数の数を巡回する周期の探索は行わない。
最小値を作るとき、先頭に0が来てもよい。たとえば、97508421では次のようになる。
\[ 98754210-01245789=97508421 \] 整数として表示すると先頭の0は消えるが、計算結果は同じである。すべての桁が同じ数から得られる0は、今回は出力しない。
なお、2乗した数を左右に分け、その和が元の数になる数も「カプレカ数」と呼ばれる。本記事は495や6174を含む固定点の定義に統一する。
カプレカ数の判定フロー
目次
サンプル・プログラム
| KaprekarNumber.exe | 実行プログラム本体(CUI版) |
| KaprekarNumber.cpp | ソース・プログラム |
| makefile | ビルドファイル |
| README.md | ビルド方法と使い方 |
| バージョン | 更新日 | 内容 |
|---|---|---|
| 1.0.1 | 2026/10/31 | 最大16桁に対応 |
| 1.0.0 | 2026/10/31 | 初版 |
使用ライブラリ
計算には標準の64ビット符号なし整数型 uint64_t を使う。16桁までの最大値と最小値、その差はこの型の範囲に収まるので、任意精度演算ライブラリGMPは不要である。
ライブラリの導入方法は「C++ 開発環境の準備 -MSYS2編-」をご覧いただきたい。
ビルド
makeソースの文字コードはCP932、改行はCRLFである。makefile では、C++11以降の機能を有効にし、ソースと実行時の日本語文字列の文字コードを指定している。
g++ を直接呼び出す場合は、次のようにする。
g++ -std=c++11 -Wall -Wextra -O3 -finput-charset=CP932 -fexec-charset=CP932 -s -static -o KaprekarNumber.exe KaprekarNumber.cpp -lboost_program_options-mt -lstdc++ -lgcc -lpthread
実行方法
KaprekarNumber.exe -n8実行結果は、通し番号、カプレカ数、最大値から最小値を引く計算式の順に表示する。
1: 495 = 954 - 459計算時間を表示するときは time を追加する。en はヘルプ、バージョン情報、計算時間のメッセージを英語に切り替える。
2: 6174 = 7641 - 1467
3: 549945 = 995544 - 445599
4: 631764 = 766431 - 134667
5: 63317664 = 76664331 - 13346667
6: 97508421 = 98754210 - 1245789
KaprekarNumber.exe -n16 -t1桁または2桁までを指定した場合、該当する正のカプレカ数がないので結果行は表示されない。範囲外の桁数や不正なオプションはエラーになる。
KaprekarNumber.exe -e --help
解説:数字の組合せから候補を作る
たとえば、数字1、4、6、7から作れる並べ替えは複数あるが、最大値と最小値は常に7641と1467である。その差6174が同じ数字で構成されていれば、6174自身を並べ替えても同じ引き算になる。
そこで、昇順の文字列 "1467" を代表として1回だけ調べる。一般に、文字列 \(s\) から最大値 \(D_s\) と最小値 \(A_s\) を作り、候補 \(x\) を次のように定める。
\[ x=D_s-A_s \] 候補が正であり、その数字を昇順に並べた文字列が \(s\) と一致すれば、\(D(x)=D_s\)、\(A(x)=A_s\) なので \(K(x)=x\) が成立する。逆に、どのカプレカ数も昇順に並べた数字の組合せを持つため、すべての組合せを列挙すれば漏れなく見つかる。
解説:結果を保存する構造体
KaprekarNumber.cpp
144: typedef uint64_t Integer;
145:
146: struct KaprekarNumber {
147: Integer number;
148: Integer maximum;
149: Integer minimum;
150: };
数値だけでなく両端の値を残すことで、最後に確認用の引き算もまとめて出力できる。結果の保存先には、要素数を増やせる vector を使う。
解説:最大値と最小値の差を判定する
KaprekarNumber.cpp
152: /**
153: * 昇順の数字列から最大値と最小値を作り,差が同じ桁の組合せか調べる.
154: * 最小値の先頭の0も桁として扱うが,差の先頭に0を補うことはしない.
155: * @param string digits 昇順に並んだ数字列
156: * @param KaprekarNumber& answer 判定結果
157: * @return bool true:正のカプレカ数 / false:それ以外
158: */
159: bool isKaprekarNumber(const string& digits, KaprekarNumber& answer) {
160: Integer minimum = 0;
161: Integer maximum = 0;
162: for (size_t i = 0; i < digits.size(); ++i) {
163: minimum = minimum * 10 + (digits[i] - '0');
164: maximum = maximum * 10 + (digits[digits.size() - 1 - i] - '0');
165: }
166: const Integer number = maximum - minimum;
167: if (number == 0) return false;
168: string sorted = to_string(number);
169: if (sorted.size() != digits.size()) return false;
170: sort(sorted.begin(), sorted.end());
171: if (sorted != digits) return false;
172: answer = KaprekarNumber{number, maximum, minimum};
173: return true;
174: }
1桁を付け足す処理は、現在の値を10倍して次の数字を加えるだけである。たとえば、1、4、6、7を順に読むと、値は1、14、146、1467となる。
\[ v_{i+1}=10v_i+d_i,\qquad v_0=0 \] digits[i] - '0' は、数字の文字を整数値へ変換する処理である。昇順に並んでいるため最大値は最小値以上であり、符号なし整数の引き算でも負の値にはならない。
残った候補の数字を sort で昇順に並べ、元の digits と比較する。文字列全体を比較するので、数字の種類だけでなく各数字の個数も一致しなければならない。
一致したときは、候補と最大値・最小値を参照引数 answer に書き込み、true を返す。この関数の引数は判定対象の整数ではなく、探索用の昇順の数字列である。
解説:重複組合せを再帰で列挙する
KaprekarNumber.cpp
176: /**
177: * 重複を避けるため,数字を昇順に追加して全ての桁の組合せを調べる.
178: * 同じ桁の組合せでは最大値・最小値・差が一意なので,全整数の走査は不要.
179: */
180: void searchKaprekarNumbers(unsigned int remaining, char first, string& digits,
181: vector<KaprekarNumber>& answers) {
182: if (remaining == 0) {
183: KaprekarNumber answer;
184: if (isKaprekarNumber(digits, answer)) answers.push_back(answer);
185: return;
186: }
187: for (char digit = first; digit <= '9'; ++digit) {
188: digits.push_back(digit);
189: searchKaprekarNumbers(remaining - 1, digit, digits, answers);
190: digits.pop_back();
191: }
192: }
remaining は残りの桁数、first は次に選べる最小の数字、digits は作成中の文字列である。同じ数字を繰り返し選べるよう、再帰呼び出しには選んだ digit 自身を次の下限として渡す。
たとえば1を選んだ後は0を選べず、1~9だけを追加できる。このため、0146とその並べ替えを重複して調べることはない。
残りの桁数が0になったら文字列が完成しているため、isKaprekarNumber で判定する。該当した場合だけ answers に追加する。
文字列の先頭に0を含む組合せも列挙する。これにより、97508421のように最小値の先頭が0になるケースも探索できる。
解説:指定した桁数まで探索する
KaprekarNumber.cpp
194: /**
195: * 指定した最大桁数までの正のカプレカ数と,確認用の引き算を昇順に出力する.
196: */
197: void putKaprekarNumber(unsigned int num) {
198: vector<KaprekarNumber> answers;
199: string digits;
200: for (unsigned int length = 1; length <= num; ++length) {
201: searchKaprekarNumbers(length, '0', digits, answers);
202: }
203: sort(answers.begin(), answers.end(),
204: [](const KaprekarNumber& left, const KaprekarNumber& right) {
205: return left.number < right.number;
206: });
207: for (size_t i = 0; i < answers.size(); ++i) {
208: const KaprekarNumber& answer = answers[i];
209: cout << i + 1 << ": " << answer.number << " = "
210: << answer.maximum << " - " << answer.minimum << endl;
211: }
212: }
数字列を昇順に列挙した順序と、カプレカ数の大小の順序は必ずしも一致しない。そこで、見つかった結果を最後に number の昇順に並べ直す。sort に渡している [] から始まる部分は、2つの構造体を比較するラムダ式である。
同じカプレカ数に対応する昇順の数字列は1つだけで、桁数も一致するものだけを採用する。そのため、別途重複を取り除く必要はない。
解説:コマンドラインオプション
KaprekarNumber.cpp
219: // コマンドライン・オプションの定義
220: options_description options("コマンドライン・オプション");
221: options.add_options()
222: ("number,n", value<unsigned int>(), "最大桁数")
223: ("time,t", "計算時間表示")
224: ("en,e", "英語表示")
225: ("help,h", "ヘルプ")
226: ("version,v", "バージョン情報")
227: ;
228: // コマンドライン・オプションの取得
229: variables_map vm;
230: try {
231: store(parse_command_line(argc, argv, options), vm);
232: notify(vm);
parse_command_line で引数を解析し、store と notify を通して variables_map に格納する。最大桁数は vm["number"].as<unsigned int>() で取り出し、1~16の範囲かを確認する。
解析に失敗した場合はBoostの例外を捕捉してエラーを出力する。範囲外の場合も終了コード1を返す。計算時間は探索前後の clock の差から求めるCPU時間であり、実際の待ち時間を測るものではない。
探索範囲と計算量
\[ N_d=\binom{d+9}{9} \] 16桁までに調べる組合せの総数は、次の5311734通りである。
\[ \sum_{d=1}^{16}\binom{d+9}{9}=\binom{26}{10}-1=5311734 \] これは、1から9999999999999999までを順に調べる方法よりはるかに少ない。各候補では最大値と最小値の組み立てに \(O(d)\)、差の文字列を並べ替えるのに \(O(d\log d)\) の処理を行う。ほかに、最後の結果の並べ替えが必要になる。
64ビット符号なし整数の最大値は \(2^{64}-1\) であり、16桁の最大値 \(10^{16}-1\) は十分に収まる。ただし、桁数を増やす場合は演算範囲と組合せ数の両方を再検討する必要がある。
実行結果の検証
\[ \begin{gathered} 495,\ 6174,\ 549945,\ 631764,\\ 63317664,\ 97508421,\ 554999445,\ 864197532,\\ 6333176664,\ 9753086421,\ 9975084201 \end{gathered} \] この結果は OEIS A099009 の10桁以下の項から0を除いたものと一致する。1桁、2桁、5桁、7桁には該当する正の整数がない。
プログラムの確認では、別方式として100万未満の全整数を1つずつ並べ替えて判定し、6桁以下の結果が495、6174、549945、631764の4個になることも照合した。
最大16桁までの実行結果は34個であり、OEIS A099009の16桁以下の項から0を除いたものと一致する。16桁の最大の解は \(9999975084200001\) である。
参考サイト
- A099009: Fixed points of the Kaprekar mapping:The On-Line Encyclopedia of Integer Sequences
- Boost.Program_options Tutorial:Boost C++ Libraries
- Boost Format Library:Boost C++ Libraries
- C++ 開発環境の準備 -MSYS2編-:ぱふぅ家のホームページ

たとえば、495は \(954-459=495\)、6174は \(7641-1467=6174\) となる。C++で数字の組合せを調べ、16桁までのカプレカ数を探索するプログラムを作る。