C++ でカプレカ数を求める

(1/1)
KaprekarNumber.exeで8桁以下のカプレカ数6個を探索した実行画面
8桁以下の正のカプレカ数を探索した結果
カプレカ数は、各桁を大きい順に並べた最大値から、小さい順に並べた最小値を引くと元に戻る数である。本記事では、この操作の固定点となる正の整数を対象にする。
たとえば、495は \(954-459=495\)、6174は \(7641-1467=6174\) となる。C++で数字の組合せを調べ、16桁までのカプレカ数を探索するプログラムを作る。

解説:カプレカ数の条件

正の整数 \(n\) の各桁を降順に並べた値を \(D(n)\)、昇順に並べた値を \(A(n)\) とすると、今回求める条件は次の式である。
\[ 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ビルド方法と使い方
KaprekarNumber.cpp 更新履歴
バージョン 更新日 内容
1.0.1 2026/10/31 最大16桁に対応
1.0.0 2026/10/31 初版

使用ライブラリ

コマンドライン・オプションの解析には Boost Program Options Library、ヘルプやバージョン情報の組み立てには Boost Format Library を利用する。
計算には標準の64ビット符号なし整数型 uint64_t を使う。16桁までの最大値と最小値、その差はこの型の範囲に収まるので、任意精度演算ライブラリGMPは不要である。
ライブラリの導入方法は「C++ 開発環境の準備 -MSYS2編-」をご覧いただきたい。

ビルド

同梱の makefile を利用する。MSYS2 MinGW 64-bit のシェルで、展開したフォルダへ移動し、次のコマンドを実行する。
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

実行方法

オプション number に探索する最大桁数を指定する。省略時は4桁、指定できる範囲は1~16桁である。次の例では8桁以下を探索する。
KaprekarNumber.exe -n8
実行結果は、通し番号、カプレカ数、最大値から最小値を引く計算式の順に表示する。
1: 495 = 954 - 459
2: 6174 = 7641 - 1467
3: 549945 = 995544 - 445599
4: 631764 = 766431 - 134667
5: 63317664 = 76664331 - 13346667
6: 97508421 = 98754210 - 1245789
計算時間を表示するときは time を追加する。en はヘルプ、バージョン情報、計算時間のメッセージを英語に切り替える。
KaprekarNumber.exe -n16 -t
KaprekarNumber.exe -e --help
1桁または2桁までを指定した場合、該当する正のカプレカ数がないので結果行は表示されない。範囲外の桁数や不正なオプションはエラーになる。

解説:数字の組合せから候補を作る

1から順に整数を調べる方法では、16桁までに約1京回の判定が必要になる。しかし、同じ数字を同じ個数だけ含む数なら、元の並び順によらず最大値と最小値は同じである。
たとえば、数字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: };

Integer は uint64_t に付けた別名である。KaprekarNumber 構造体には、見つかったカプレカ数 number、最大値 maximum、最小値 minimum を保存する。
数値だけでなく両端の値を残すことで、最後に確認用の引き算もまとめて出力できる。結果の保存先には、要素数を増やせる 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: }

ユーザー定義関数 isKaprekarNumber は、昇順の数字列 digits を受け取る。左から読んで最小値を、右から読んで最大値を組み立てる。
1桁を付け足す処理は、現在の値を10倍して次の数字を加えるだけである。たとえば、1、4、6、7を順に読むと、値は1、14、146、1467となる。
\[ v_{i+1}=10v_i+d_i,\qquad v_0=0 \] digits[i] - '0' は、数字の文字を整数値へ変換する処理である。昇順に並んでいるため最大値は最小値以上であり、符号なし整数の引き算でも負の値にはならない。
差が0なら対象外とする。次に to_string で差を文字列に変換し、元の文字列と桁数が違えば除外する。候補の先頭に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: }

ユーザー定義関数 searchKaprekarNumbers は、0~9から数字を重複して選ぶ重複組合せを再帰で列挙する。
remaining は残りの桁数、first は次に選べる最小の数字、digits は作成中の文字列である。同じ数字を繰り返し選べるよう、再帰呼び出しには選んだ digit 自身を次の下限として渡す。
たとえば1を選んだ後は0を選べず、1~9だけを追加できる。このため、0146とその並べ替えを重複して調べることはない。
push_back で数字を1つ追加し、残りの桁数を1減らして再帰呼び出しする。呼び出しから戻ったら pop_back で追加した数字を取り除き、次の数字を試す。このように状態を戻しながら探索する方法をバックトラックと呼ぶ。
残りの桁数が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: }

ユーザー定義関数 putKaprekarNumber は、1桁から指定した最大桁数までを順に探索する。各桁数では、次に選ぶ最小の数字を0として searchKaprekarNumbers を呼ぶ。
数字列を昇順に列挙した順序と、カプレカ数の大小の順序は必ずしも一致しない。そこで、見つかった結果を最後に 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);

Boost Program Options Library の options_description で、桁数、計算時間、言語、ヘルプ、バージョンの各オプションを定義する。
parse_command_line で引数を解析し、store と notify を通して variables_map に格納する。最大桁数は vm["number"].as<unsigned int>() で取り出し、1~16の範囲かを確認する。
解析に失敗した場合はBoostの例外を捕捉してエラーを出力する。範囲外の場合も終了コード1を返す。計算時間は探索前後の clock の差から求めるCPU時間であり、実際の待ち時間を測るものではない。

探索範囲と計算量

数字を \(d\) 桁選ぶとき、0~9の10種類から重複を許して選ぶ組合せの数は次のようになる。
\[ 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\) は十分に収まる。ただし、桁数を増やす場合は演算範囲と組合せ数の両方を再検討する必要がある。

実行結果の検証

10桁以下では、次の11個の正のカプレカ数が得られる。
\[ \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\) である。

参考サイト

(この項おわり)
header