目次
サンプル・プログラムの実行例
サンプル・プログラム
| perfectNumbers.php | サンプル・プログラム本体。 |
| pahooInputData.php | データ入力に関わる関数群。 使い方は「PHPでGET／POSTでフォームから値を受け取る」「数値入力とバリデーション」「文字入力とバリデーション」などを参照。include_path が通ったディレクトリに配置すること。 |
| バージョン | 更新日 | 内容 |
|---|---|---|
| 2.0.0 | 2024/11/03 | 全面改訂；GMP関数を導入 |
| 1.1.0 | 2024/11/03 | 最大値を最大桁数に変更 |
| 1.0.0 | 2024/10/18 | 初版 |
| バージョン | 更新日 | 内容 |
|---|---|---|
| 1.8.0 | 2024/11/12 | validRegexPattern() 追加 |
| 1.7.0 | 2024/10/09 | validURL() validEmail() 追加 |
| 1.6.0 | 2024/10/07 | isButton() -- buttonタグに対応 |
| 1.5.0 | 2024/01/28 | exitIfExceedVersion() 追加 |
| 1.4.2 | 2024/01/28 | exitIfLessVersion() メッセージ修正 |
準備：初期値など
perfectNumbers.php
56: // 初期値(START) =============================================================
57: // 表示幅（ピクセル）
58: define('WIDTH', 600);
59:
60: // デフォルトの計算方式
61: define('DEFAULT_METHOD', 2);
62:
63: // デフォルトの最大桁数
64: define('DEFAULT_MAX', 100);
65:
66: // 最大桁数の最小値
67: define('MIN_MIN', 2);
68:
69: // 最大桁数の最大値
70: define('MIN_MAX', 3000);
71:
72: // 初期値(END) ===============================================================
データ入力に関わる関数群 "pahooInputData.php" はinclude_pathが通ったディレクトリに配置すること。
解説：総当たりで完全数を求める
perfectNumbers.php
148: /**
149: * 完全数かどうかを判定する（通常版）
150: * @param int $n 判定する値
151: * @return bool TRUE:完全数である / FALSE:完全数ではない
152: */
153: function isPerfectNumber($n) {
154: $sum = 0;
155:
156: // 自分自身以外の約数の和を求める
157: for ($i = 1; $i < $n; $i++) {
158: if ($n % $i == 0) { // nがiで割り切れる場合
159: $sum += $i;
160: }
161: }
162:
163: // 和が元の数と等しければ完全数
164: return $sum === $n;
165: }
perfectNumbers.php
196: /**
197: * 完全数を求める（総当たり計算）
198: * @param int $num 探索範囲の最大桁数
199: * @param int $method 0:通常判定, 1:高速判定
200: * @return array 完全数の配列
201: */
202: function getPerfectNumbersForce($num, $method) {
203: $maxInteger = pow(10, $num); // 10^numを計算して、最大値を設定
204: $perfectNumbers = array(); // 完全数を格納する配列
205:
206: for ($i = 2; $i <= $maxInteger; $i++) {
207: if ($method == 0) {
208: if (isPerfectNumber($i)) {
209: $perfectNumbers[] = $i;
210: }
211: } else {
212: if (isPerfectNumberRapid($i)) {
213: $perfectNumbers[] = $i;
214: }
215: }
216: }
217: return $perfectNumbers;
218: }
自分自身以外に約数をもつ 2 からはじめて、指定した範囲まで、1つずつユーザー関数 isPerfectNumber に渡し、完全数の定義に従っているかどうかを判定する。
isPerfectNumber の中では、エラトステネスの篩のような高速化アルゴリズムは使わず、総当たりで約数を求める。
5桁までの探索をやらせると、けっこう時間がかかる。しかも悲しいことに、冒頭の4つの完全数しか見つからない。5番目の完全数は 33550336 であり、これに到達するまでには相当な時間がかかるだろう。2024年（令和6年）10月12日発見された52個目の完全数は4102万4320桁の数字で、51番目のものより1600万桁以上大きくなっている。
解説：完全数の判定を高速化する
\( 1 \) と自分自身 \( n \) を除く約数の1つは、\( \sqrt{n} \) 以下であることは自明である。そして、その数とペアになる約数がある。
perfectNumbers.php
167: /**
168: * 完全数かどうかを判定する（高速化）
169: * @param int $n 判定する値
170: * @return bool TRUE:完全数である / FALSE:完全数ではない
171: */
172: function isPerfectNumberRapid($n) {
173: // 自分以外の約数を持たない場合は棄却
174: if ($n < 2) {
175: return false;
176: }
177:
178: $sumDiv = 1; // 1はどの数の約数にも含まれる
179:
180: // 平方根までの約数を探し、ペアの約数を加える
181: $sqrtNum = sqrt($n);
182: for ($i = 2; $i <= $sqrtNum; $i++) {
183: if ($n % $i == 0) {
184: $sumDiv += $i; // 約数を加算
185: $pairDiv = $n / $i; // ペアの約数
186: if ($pairDiv != $i) { // ペアの約数を加算
187: $sumDiv += $pairDiv;
188: }
189: }
190: }
191:
192: // 和が元の数と等しければ完全数
193: return $sumDiv === $n;
194: }
こうすることで、計算量は多くても \( O(max) \times O(\sqrt{n}) \) に減少する。1～2桁の計算をしているときにはそれほど計算量は変わらないが、6桁（100万）になると、isPerfectNumber の計算量が \( O(1,000,000) \) であるのに比べ、isPerfectNumberRapid は \( O(1,000) \) と、3桁も減少する。つまり、桁数が増えれば増えるほど、計算速度の差が開く。
完全数を表示するユーザー関数 getPerfectNumbersForce の第2引数は省略可能だが、1を代入すると、isPerfectNumberRapid を使って判定する。
解説：ユークリッド・オイラーの定理
じつは、偶数の完全数に限っては、18世紀の数学者レオンハルト・オイラーがユークリッド・オイラーの定理を発見しており、これを使うと計算回数を劇的に少なくすることができる。
ユークリッド・オイラーの定理によると、
\[ P = 2^{p - 1} \times (2^p - 1) \]
\( p \) が素数であり、なおかつ \( 2^p - 1 \) も素数である場合（これをメルセンヌ素数と呼ぶ）、\( P \) は偶数の完全数になる。
そして、2024年（令和6年）10月に発見された52個目まで、たまたま、すべて偶数の完全数だった。奇数の完全数が存在するかどうかは証明されていないのだが、少なくともパソコンのパワーでで52個まで計算するのは不可能だから、ユークリッド・オイラーの定理 を使って高速化させてもらう。
perfectNumbers.php
221: /**
222: * メルセンヌ素数かどうかを判定する．
223: * @param unsigned int p 判定する指数
224: * @return bool TRUE:メルセンヌ素数である / FALSE:メルセンヌ素数ではない
225: */
226: function isMersennePrime($p) {
227: // 2^p - 1を計算
228: $mersenne = gmp_sub(gmp_pow(2, $p), 1);
229:
230: // 確率的素数判定
231: return gmp_prob_prime($mersenne, 25) > 0;
232: }
perfectNumbers.php
234: /**
235: * 完全数を生成する
236: * @param int $p メルセンヌ指数
237: * @return gmp 完全数
238: */
239: function generatePerfectNumber($p) {
240: // 完全数を計算: (2^(p-1)) * (2^p - 1)
241: $part1 = gmp_pow(2, $p - 1);
242: $part2 = gmp_sub(gmp_pow(2, $p), 1);
243: $perfect = gmp_mul($part1, $part2);
244:
245: return $perfect;
246: }
perfectNumbers.php
248: /**
249: * 完全数を求める（ユークリッド・オイラーの定理）
250: * @param int $num 探索範囲の最大桁数
251: * @return array 完全数の配列
252: */
253: function getPerfectNumbers($num) {
254: $maxInteger = gmp_pow(10, $num); // 10^numを計算して、最大値を設定
255: $perfectNumbers = array(); // 完全数を格納する配列
256:
257: $index = 1;
258: $p = 2;
259:
260: while (TRUE) {
261: // メルセンヌ素数をチェック
262: if (isMersennePrime($p)) {
263: // 完全数を生成
264: $perfectNumber = generatePerfectNumber($p);
265:
266: // 最大値を超えたらループ終了
267: if (gmp_cmp($perfectNumber, $maxInteger) > 0) {
268: break;
269: }
270:
271: // 結果を出力
272: $perfectNumbers[] = gmp_strval($perfectNumber);
273: $index++;
274: }
275: $p++;
276: }
277: return $perfectNumbers;
278: }
この方法では、計算量は \( O(log_2 \ max) \) となる。2桁（100）の時でも計算量が6に減少するし、6桁（100万）の時には19に激減する。
したがって、総当たり計算と同じ時間ではるかに大きな桁数の完全数を求めることができるので、完全数の型を unsigned long ではなく、GMPの mpz_class に変更し、事実上、無限大の完全数を求められるようにした。現行のノートPCでも、3000桁程度までであれば、数分で出力するだろう。
解説：計算量は非機能要件として検討する
結果を早く求めることができればユーザー喜ぶから、システムの非機能要件として計算量を減らすことを検討するといい。そして、前提条件を導入するかどうかはユーザーに諮らなければならないことだから、数学的に計算量 \( O \) を求め、どのくらい短縮できるかを数字をもって示すようにしよう。
参考サイト
- 4.4 配列と引数の渡し方：ぱふぅ家のホームページ
- 完全数とその魅力について－「博士の愛した数式」を観て、改めて数字の持つ奥深さに魅せられました－：ニッセイ基礎研究所
- C++ で完全数を求める
古代から 6, 28, 496, 8128 の4つが完全数であることが知られているが、ピタゴラスが名付けたとか、世界を創造した6日間と月の公転周期の28日が含まれているからキリスト教の神を完全性を表しているなどと言われてきた。
完全数を求める方程式は発見されていない。自然数を1つずつ虱潰しにしていかなければならないわけだが、こういうときに黙々と作業をするコンピュータが重宝する。
今回は、PHPで完全数を求めるプログラムを作るとともに、計算量について考える。
（2024年11月3日）全面改訂；GMP関数を導入