完全数・不足数・過剰数についての話です。
きっかけは、AIZU ONNLINE JUDGEのVolume21-2101から、"Perfect Number"の出題でした。
https://onlinejudge.u-aizu.ac.jp/problems/2101
まず完全数とは、Wikipediaによれば...
>自分自身が自分自身を除く正の約数の和に等しくなる自然数のことである。
https://ja.wikipedia.org/wiki/完全数
>完全数に関する最初の成果は紀元前3世紀頃のユークリッドである。
もし単位から始まり順次に1対2の比をなす任意個の数が定められ，それらの総和が素数になるようにされ，そして全体が最後の数にかけられてある数を作るならば，その積は完全数であろう。
— エウクレイデス、『ユークリッド原論』第9巻、命題36
>ユークリッドの生成式以外から得られる偶数の完全数は存在しないのかという問題は18世紀までは未解決であったが、レオンハルト・オイラーは偶数の完全数はこの形に限ることを証明した
>2021年8月現在発見されている完全数はメルセンヌ素数と同じく51個である。
>完全数はどれだけあるのかの探求が2500年以上のちの現在まで続けられている。
>紀元前より考察されている対象であるにもかかわらず、「偶数の完全数は無数に存在するか？」、「奇数の完全数は存在するか？」という問題は未解決である。
そもそも完全数は、「万物は数なり」と考えた、ピタゴラスが名付けた数の一つだったみたいです。
でも、どうして「完全」なのかについては、何も書き残されてなかったらしくて、謎のままです。
中世の『聖書』の研究者によれば、完全数の最初の6 (= 1 + 2 + 3)は、「神が世界を創造した（天地創造）6日間」で、次の28 (= 1 + 2 + 4 + 7 + 14)は、「月の公転周期」と同じです。
そこで、「これら2つの数は地上と天界における神の完全性を象徴している」と考えたらしいのだけれど、聖アウグスティヌス（? - 604年）は「6 はそれ自体完全な数である。神が万物を6日間で創造したから 6 が完全なのでなく、むしろ逆が真である」としたそうです。
だから、まるで占いとかの話みたいだなーと思いました。
ただし、古代ギリシアの数秘学（数秘術）の創始者と言われているのもピタゴラスらしくて、それが後の西洋占星術とかタロット占いに繋がっていくみたいだから、由来と言う一点だけに着目すれば、たしかにありえなくもないし、間違いとも言えなさそうです。
次に、不足数について...
https://ja.wikipedia.org/wiki/不足数
>不足数とは、その約数の総和が元の数の 2 倍より小さい自然数のことである。
>この不足数の定義は「その数自身を除く約数の総和が元の数より小さくなるような数」と同値である。
>全ての素数 p は約数の総和が σ(p) = 1 + p < 2p であるので不足数である。
>また、5 以上の素数 p を 2 倍した偶数 2p の約数の総和は σ(2p) = 1 + 2 + p + 2p < 2p × 2 となるので不足数である。
>素数は無数にあるので偶数の不足数も奇数の不足数も無数に存在する。
>不足数や完全数の約数は全て不足数となる。
で、不足数は、不完全数です。
さらに、σ(n) = 2n − 1 を満たす n は不足数であり、概完全数と呼ばれています。
概完全数の最小の数は 1 で、さらに2の冪 (= 1, 2, 4, 8, …) の形をした数しか見つかってないので、他の形をした概完全数が存在するのかどうかは現在も分かっていないのだそうです。
続いて、過剰数について...
https://ja.wikipedia.org/wiki/過剰数
>過剰数とは、その約数の総和が元の数の 2 倍より大きい自然数のことである。
>この過剰数の定義は「その数自身を除く約数の総和が元の数より大きくなるような自然数」と同値である。
>過剰数もしくは完全数の倍数は全て過剰数であり、したがって偶数の過剰数も奇数の過剰数も無数に存在する。
>また、全ての擬似完全数は完全数もしくは過剰数である。
>ほとんどの過剰数は擬似完全数でもあり、そうでない過剰数は不思議数と呼ばれる。
で、過剰数も不完全数です。
ちなみに、σ(n) = 2n + 1 を満たす n は過剰数で、準完全数と呼ばれてはいるけれど、いまだに見つかっていないそうです。
ってか、謎が多すぎて、調べる前よりもモヤモヤした気持ちになりました。
そして、AIZU ONNLINE JUDGEのVolume21-2101から、"Perfect Number"の出題では...
ある整数 N に対し，その数自身を除く約数の和を S とする．
N = S のとき N は完全数 (perfect number)， N > S のとき N は不足数 (deficient number)， N < S のとき N は過剰数 (abundant number) と呼ばれる．
「与えられた整数が，完全数・不足数・過剰数のどれであるかを 判定するプログラムを作成せよ」
プログラムの実行時間が制限時間を越えないように注意すること．
僕が作成、提出したコードは、以下のとおりです。
Aizu Online Judge in C++ #Volume21-2101 : Perfect Number
/* Aizu Online Judge in C++ #Volume21-2101 : Perfect Number https://onlinejudge.u-aizu.ac.jp/problems/2101 提出コードの解答例 https://neguse-atama.hatenablog.com */ #include<bits/stdc++.h> using namespace std; int main(void){ int n; while(cin>>n,n){ int sum=0; for(int i=1;i*i<=n;i++){ if(n%i==0){ sum+=(i+n/i); } if(i*i==n){ sum-=i; } } if(sum==2*n){ cout<<"perfect number"<<endl; }else if(sum>2*n){ cout<<"abundant number"<<endl; }else{ cout<<"deficient number"<<endl; } } }
それから、完全数の拡張について...
・倍積完全数 (multiperfect number)
>正の約数の和が自分自身の倍数である自然数を倍積完全数という。
>特に、それがk倍に等しいものをk倍完全数という。完全数とは2倍完全数のことである。
・ハイパー完全数 (hyperperfect number)
>n が k -ハイパー完全数であるとは、
n = 1 + k(σ(n) − n − 1)（ただしk は自然数）（σ は約数関数）
を満たすことと定義される。
>完全数は 1-ハイパー完全数である。
・超完全数 (superperfect number)
>n が (m, k)-完全数であるとは、
σm(n) = kn（ただし k は自然数）（σ は約数関数）
を満たすときと定義される。
>完全数は (1, 2)-完全数、倍積完全数は (1, k)-完全数、超完全数は (2, 2)-完全数である。
さらに、完全数でない自然数、すなわち不完全数(imperfect number) について...
・不足数 (deficient number)
>自分自身以外の正の約数の和より大きい自然数
・過剰数 (abundant number)
>自分自身以外の正の約数の和より小さい自然数
・友愛数 (amicable pair)
>自分自身以外の正の約数の和が互いに他方に等しい2つの自然数の組。
・社交数 (sociable numbers)
>友愛数と同様の関係が成立する3個以上の自然数の組。
・準完全数 (quasiperfect number)
>n が準完全数であるとは、正の約数の和が 2n + 1 に等しいことと定義される。過剰数の一種。
・概完全数 (almost perfect number)
>n が概完全数であるとは、正の約数の和が 2n − 1 に等しいことと定義される。不足数の一種。
・乗法的完全数 (multiplicative perfect number)
>正の約数の積が自分自身の自乗（2乗）に等しい数を乗法的完全数という。
ヤバイ...めっちゃ沼だらけだわー。
設問の出典は、プログラミング問題のオンライン採点システム「Aizu Online Judge（AOJ）」です。
http://judge.u-aizu.ac.jp/onlinejudge/
