フリードマン数の判定フロー
目次
サンプル・プログラム
| FriedmanNumber.exe | 実行プログラム本体（CUI版） |
| FriedmanNumber.cpp | ソース・プログラム |
| makefile | ビルドファイル |
| バージョン | 更新日 | 内容 |
|---|---|---|
| 1.0.0 | 2026/09/06 | 初版 |
使用ライブラリ
コマンドライン・オプションの解析には Boost Program Options Library、メッセージの組み立てには Boost Format Library を利用する。
各ライブラリの導入方法は「C++ 開発環境の準備 -MSYS2編-」をご覧いただきたい。
ビルド
makeg++ を直接呼び出す場合は、次のようにする。
g++ -Wall -O3 -o FriedmanNumber.exe FriedmanNumber.cpp -lboost_program_options-mt -lgmpxx -lgmp
実行方法
FriedmanNumber.exe -n3実行結果は、通し番号、フリードマン数、成立した計算式の順に表示する。数字の並び順を変えずに表せた場合は "【ナイス】" を付ける。
1: 25 = (5^2)4桁以下を探索すると、フリードマン数の提唱者であるエリック・フリードマンが掲載している既知の72個と一致する。
2: 121 = (11^2)
3: 125 = (5^(1+2))
4: 126 = (21*6)
5: 127 = ((-1)+(2^7)) 【ナイス】
6: 128 = (2^(8-1))
7: 153 = (51*3)
8: 216 = (6^(2+1))
9: 289 = ((8+9)^2)
10: 343 = ((3+4)^3) 【ナイス】
11: 347 = (4+(7^3))
12: 625 = (5^(6-2))
13: 688 = (86*8)
14: 736 = (7+(3^6)) 【ナイス】
解説：フリードマン数の条件
- 元の数を構成する数字を、重複も不足もなく1回ずつ使う。
- 加算、減算、乗算、除算、累乗、単項マイナス、括弧、数字の連結を使える。
- 複数の数字を連結するとき、先頭に0を置かない。
- 数字を並べただけではなく、少なくとも1つの演算子を使う。
解説：式と値を保存する
FriedmanNumber.cpp
142: struct Formula {
143: string expression;
144: bool usedOperator;
145: };
146:
147: typedef map<mpq_class, Formula> FormulaMap;
148:
149: // 探索中に保持する値の上限．巨大な中間値によるメモリー消費を抑える．
150: static mpz_class ValueLimit;
FormulaMap は、有理数の値をキー、その値を作る式を値とする map である。同じ値になる式を何通りも保存せず、演算子を使った式と短い式を優先することで、メモリー消費を抑え、結果を読みやすくする。
ValueLimit は、途中で巨大な数や分数が増え続けることを防ぐための上限である。
FriedmanNumber.cpp
152: /**
153: * 値が探索範囲内かどうかを判定する．
154: * @param mpq_class value 判定する値
155: * @return bool TRUE:探索範囲内 / FALSE:探索範囲外
156: */
157: bool isWithinLimit(const mpq_class& value) {
158: mpz_class numerator = value.get_num();
159: if (numerator < 0) numerator = -numerator;
160: return numerator <= ValueLimit && value.get_den() <= ValueLimit;
161: }
FriedmanNumber.cpp
163: /**
164: * 式を表へ登録する．同じ値では演算子を使った式を優先する．
165: */
166: void addFormula(FormulaMap& table, const mpq_class& value,
167: const string& expression, bool usedOperator) {
168: if (!isWithinLimit(value)) return;
169: FormulaMap::iterator it = table.find(value);
170: if (it == table.end()) {
171: table[value] = Formula{expression, usedOperator};
172: } else if (usedOperator && !it->second.usedOperator) {
173: it->second = Formula{expression, true};
174: } else if (usedOperator == it->second.usedOperator
175: && expression.size() < it->second.expression.size()) {
176: // 同じ値なら，結果表示が読みやすい短い式を残す．
177: it->second = Formula{expression, usedOperator};
178: }
179: }
ユーザー定義関数 addFormula は上限内の値だけを表へ追加する。同じ値がすでにある場合、連結しただけの式より演算子を含む式を優先し、条件が同じなら文字数が短い式へ置き換える。
解説：数字を連結する
FriedmanNumber.cpp
181: /**
182: * maskで指定した数字を並べ替えて作れる整数を登録する．
183: * 先頭ゼロは認めない．数字の連結だけでは非自明な式とはしない．
184: */
185: void addConcatenations(FormulaMap& table, const vector<int>& digits,
186: unsigned int mask) {
187: vector<int> selected;
188: for (unsigned int i = 0; i < digits.size(); ++i) {
189: if (mask & (1U << i)) selected.push_back(digits[i]);
190: }
191: sort(selected.begin(), selected.end());
192: do {
193: if (selected.size() > 1 && selected[0] == 0) continue;
194: mpz_class value = 0;
195: string expression;
196: for (size_t i = 0; i < selected.size(); ++i) {
197: value *= 10;
198: value += selected[i];
199: expression += static_cast<char>('0' + selected[i]);
200: }
201: addFormula(table, mpq_class(value), expression, false);
202: if (value != 0) {
203: addFormula(table, mpq_class(-value), "(-" + expression + ")", true);
204: }
205: } while (next_permutation(selected.begin(), selected.end()));
206: }
たとえば 347 の数字から3と7を選んだ部分集合なら、連結した37と73を候補として登録する。0を含むときは、複数桁の先頭が0になる並びを除外する。
単項マイナスも使えるよう、0以外の候補については負数の式も登録する。ただし、数字を連結しただけの式は非自明な式ではないため、usedOperator を false とする。
解説：有理数の累乗
FriedmanNumber.cpp
208: /**
209: * 整数の累乗を正確に計算する．
210: * @param mpq_class base 底
211: * @param long exponent 指数
212: * @param mpq_class& answer 計算結果
213: * @return bool TRUE:計算可能 / FALSE:定義外または探索範囲外
214: */
215: bool rationalPower(const mpq_class& base, long exponent, mpq_class& answer) {
216: if (exponent < -16 || exponent > 16) return false;
217: if (exponent == 0) {
218: if (base == 0) return false;
219: answer = 1;
220: return true;
221: }
222: if (base == 0 && exponent < 0) return false;
223:
224: unsigned long power = static_cast<unsigned long>(exponent < 0 ? -exponent : exponent);
225: mpz_class numerator;
226: mpz_class denominator;
227: mpz_pow_ui(numerator.get_mpz_t(), base.get_num().get_mpz_t(), power);
228: mpz_pow_ui(denominator.get_mpz_t(), base.get_den().get_mpz_t(), power);
229: if (exponent < 0) swap(numerator, denominator);
230: answer = mpq_class(numerator, denominator);
231: answer.canonicalize();
232: return isWithinLimit(answer);
233: }
ユーザー定義関数 rationalPower は、底の分子と分母をそれぞれ mpz_pow_ui で累乗する。負の指数では分子と分母を交換し、canonicalize で約分された標準形に直す。\(0^0\) と0の負数乗は定義しない。
解説：部分式を組み合わせる
FriedmanNumber.cpp
235: /**
236: * 2つの部分式を演算で結合する．
237: */
238: void combineFormula(FormulaMap& destination, const mpq_class& leftValue,
239: const Formula& left, const mpq_class& rightValue, const Formula& right) {
240: const string le = "(" + left.expression;
241: const string re = right.expression + ")";
242: addFormula(destination, leftValue + rightValue, le + "+" + re, true);
243: addFormula(destination, leftValue - rightValue, le + "-" + re, true);
244: addFormula(destination, leftValue * rightValue, le + "*" + re, true);
245: if (rightValue != 0) {
246: addFormula(destination, leftValue / rightValue, le + "/" + re, true);
247: }
248: if (rightValue.get_den() == 1 && rightValue.get_num().fits_slong_p()) {
249: mpq_class powered;
250: if (rationalPower(leftValue, rightValue.get_num().get_si(), powered)) {
251: addFormula(destination, powered, le + "^" + re, true);
252: }
253: }
254: }
すべての式を括弧で囲んで保存するため、演算子の優先順位に左右されず、プログラムが計算した順序をそのまま結果に表示できる。
解説：動的計画法で判定する
FriedmanNumber.cpp
256: /**
257: * フリードマン数かどうかを判定する．
258: * @param unsigned long n 判定する値
259: * @param string& expression 成立する式
260: * @return bool TRUE:フリードマン数である / FALSE:フリードマン数ではない
261: */
262: bool isFriedmanNumber(unsigned long n, string& expression) {
263: string source = to_string(n);
264: vector<int> digits;
265: for (size_t i = 0; i < source.size(); ++i) {
266: digits.push_back(source[i] - '0');
267: }
268: const unsigned int fullMask = (1U << digits.size()) - 1;
269: vector<FormulaMap> formulas(fullMask + 1);
270:
271: ValueLimit = mpz_class(n);
272: ValueLimit *= ValueLimit;
273: if (ValueLimit < 1000000) ValueLimit = 1000000;
274:
275: for (unsigned int mask = 1; mask <= fullMask; ++mask) {
276: addConcatenations(formulas[mask], digits, mask);
277: for (unsigned int leftMask = (mask - 1) & mask; leftMask != 0;
278: leftMask = (leftMask - 1) & mask) {
279: unsigned int rightMask = mask ^ leftMask;
280: if (rightMask == 0 || leftMask > rightMask) continue;
281: for (FormulaMap::const_iterator left = formulas[leftMask].begin();
282: left != formulas[leftMask].end(); ++left) {
283: for (FormulaMap::const_iterator right = formulas[rightMask].begin();
284: right != formulas[rightMask].end(); ++right) {
285: combineFormula(formulas[mask], left->first, left->second,
286: right->first, right->second);
287: // 減算，除算，累乗は交換法則がないので逆順も調べる．
288: combineFormula(formulas[mask], right->first, right->second,
289: left->first, left->second);
290: }
291: }
292: }
293: }
294:
295: FormulaMap::const_iterator found = formulas[fullMask].find(mpq_class(n));
296: if (found != formulas[fullMask].end() && found->second.usedOperator) {
297: expression = found->second.expression;
298: return true;
299: }
300: return false;
301: }
まず、各ビットマスクについて数字を連結した候補を作る。次に、そのマスクを重ならない左右の部分集合へ分割し、すでに計算した部分式を combineFormula で結合する。小さな部分問題の結果を再利用する動的計画法であり、同じ式の値を何度も計算する無駄を減らしている。
すべての数字を使った fullMask の表に判定対象の値があり、さらに演算子を使っていればフリードマン数である。見つけた式を参照引数 expression に返すため、判定結果だけでなく、どのような計算で成立したかも表示できる。
通常のフリードマン数は数字の順序を変えてよい。減算、除算、累乗には交換法則がないため、左右を入れ替えた組み合わせも調べる。
解説：ナイス・フリードマン数を判定する
FriedmanNumber.cpp
303: /**
304: * ナイス・フリードマン数かどうかを判定する．
305: * 数字の並び順を変えず，連続する区間の式だけを結合する．
306: * @param unsigned long n 判定する値
307: * @param string& expression 成立する式
308: * @return bool TRUE:ナイス・フリードマン数 / FALSE:それ以外
309: */
310: bool isNiceFriedmanNumber(unsigned long n, string& expression) {
311: string source = to_string(n);
312: const size_t digitCount = source.size();
313: vector<vector<FormulaMap> > formulas(digitCount,
314: vector<FormulaMap>(digitCount + 1));
315:
316: for (size_t length = 1; length <= digitCount; ++length) {
317: for (size_t begin = 0; begin + length <= digitCount; ++begin) {
318: const size_t end = begin + length;
319: // 並び順どおりに連結した整数を登録する（先頭ゼロは禁止）．
320: if (length == 1 || source[begin] != '0') {
321: mpz_class value = 0;
322: for (size_t i = begin; i < end; ++i) {
323: value *= 10;
324: value += source[i] - '0';
325: }
326: string digits = source.substr(begin, length);
327: addFormula(formulas[begin][end], mpq_class(value), digits, false);
328: if (value != 0) {
329: addFormula(formulas[begin][end], mpq_class(-value),
330: "(-" + digits + ")", true);
331: }
332: }
333:
334: // 左右の区間を結合するため，数字の順序は常に保たれる．
335: for (size_t middle = begin + 1; middle < end; ++middle) {
336: const FormulaMap& leftTable = formulas[begin][middle];
337: const FormulaMap& rightTable = formulas[middle][end];
338: for (FormulaMap::const_iterator left = leftTable.begin();
339: left != leftTable.end(); ++left) {
340: for (FormulaMap::const_iterator right = rightTable.begin();
341: right != rightTable.end(); ++right) {
342: combineFormula(formulas[begin][end], left->first, left->second,
343: right->first, right->second);
344: }
345: }
346: }
347: }
348: }
349:
350: FormulaMap::const_iterator found = formulas[0][digitCount].find(mpq_class(n));
351: if (found != formulas[0][digitCount].end() && found->second.usedOperator) {
352: expression = found->second.expression;
353: return true;
354: }
355: return false;
356: }
たとえば736なら、7、3、6、73、36、736という順序を保った区間だけを連結候補にできる。区間を左右に分けるときも、左側の区間を左辺、右側の区間を右辺として結合する。これにより、数字を入れ替えた式が混ざることはない。
ナイス・フリードマン数だった場合は、この関数が見つけた順序保持式を結果に使い、"【ナイス】" と付記する。
解説：指定した桁数まで探索する
FriedmanNumber.cpp
358: /**
359: * 指定した桁数以内のフリードマン数を出力する．
360: * @param unsigned int num 探索範囲の最大桁数
361: * @return なし
362: */
363: void putFriedmanNumber(unsigned int num, bool en=false) {
364: unsigned long maxInteger = 1;
365: for (unsigned int i = 0; i < num; ++i) maxInteger *= 10;
366: --maxInteger;
367:
368: unsigned int index = 1;
369: for (unsigned long n = 1; n <= maxInteger; ++n) {
370: string expression;
371: if (isFriedmanNumber(n, expression)) {
372: string niceExpression;
373: bool nice = isNiceFriedmanNumber(n, niceExpression);
374: if (nice) expression = niceExpression;
375: cout << index << ": " << n << " = " << expression;
376: if (nice) cout << (en ? " [nice]" : " 【ナイス】");
377: cout << endl;
378: ++index;
379: }
380: }
381: }
フリードマン数が見つかると、続いて isNiceFriedmanNumber で数字順を保てるかを調べる。標準出力には通し番号、元の数、計算式を表示し、ナイス・フリードマン数には識別表示を加える。
解説：コマンドラインオプション
FriedmanNumber.cpp
388: // コマンドライン・オプションの定義
389: options_description options("コマンドライン・オプション");
390: options.add_options()
391: ("number,n", value<unsigned int>(), "最大桁数")
392: ("time,t", "計算時間表\示")
393: ("en,e", "英語表\示")
394: ("help,h", "ヘルプ")
395: ("version,v", "バージョン情報")
396: ;
397: // コマンドライン・オプションの取得
398: variables_map vm;
399: try {
400: store(parse_command_line(argc, argv, options), vm);
401: notify(vm);
最大桁数は vm["number"].as<unsigned int>() で取り出す。time を指定すると計算時間、en を指定するとヘルプや識別表示を英語で出力する。
探索範囲と計算量
このプログラムでは実用上の暴走を防ぐため、累乗の指数を−16～16に制限し、中間値の分子と分母にも ValueLimit で上限を設けている。この枝刈りにより4桁以下の既知72個はすべて検出できるが、5～6桁について数学的に漏れのない完全探索を保証するものではない。
オプションとして6桁まで指定できるものの、1から \(10^6-1\) までを順番に判定するため、完走には長い時間を要する。より大きな範囲を探索するには、同じ数字の組み合わせで計算結果を共有する、合同式などで候補を先に絞る、複数のCPUコアへ分散する、といった改良が必要になる。
参考サイト
- Friedman Numbers：Erich Friedman's Math Magic
- C++ Interface Rationals：GNU MP 6.3.0 Manual
- Boost.Program_options Tutorial：Boost C++ Libraries
- C++ 開発環境の準備 -MSYS2編-：ぱふぅ家のホームページ
参考書籍
|
数学でひもとく宇宙 | ||
| 著者 | 横山 明日希/沼 倫加 | ||
| 出版社 | オーム社 | ||
| サイズ | 単行本 |
|
|
| 発売日 | 2026年06月29日頃 | ||
| 価格 | 2,310円（税込） | ||
| ISBN | 9784274234880 | ||
たとえば 25 は \(5^2\)、126 は \(21 \times 6\) と表せるのでフリードマン数である。
さらに、元の数に現れる数字の順序を変えずに式を作れるものをナイス・フリードマン数（nice Friedman number）と呼ぶ。たとえば 736 は \(7 + 3^6\) と表せるのでナイス・フリードマン数である。