①完全数
ある数字nと、nのproper divisors（自分以外の約数）の和が等しいとき、nを完全数（perfect number）と呼ぶ。「博士が愛した数式」という小説にも出てきました。
例えば、6は完全数。6 = 1+2+3。
②婚約数
ある数pとqは、以下の２つの条件をともに満たすとき婚約数（betrothed number）とよばれる。準友愛数ともよばれる。
- pと、qの1以外のproper divisorsの和が等しい
- qと、pの1以外のproper divisorsの和が等しい
一番小さな婚約数は、(48, 75)。
48 = 3 + 5 + 15 + 25
75 = 2 + 3 + 4 + 6 + 8+ 12 + 16 + 24
③友愛数
ある数pとqは、以下の2つの条件をともに満たすとき友愛数(amicable number)とよばれる。
- pと、qのproper divisorsの和が等しい
- qと、pのproper divisorsの和が等しい
一番小さな友愛数は、220、284。
220 = 1 + 2 + 4 + 71 + 142
284 = 1 + 2+ 4 + 5 + 10 + 11 + 20 + 22 + 44 + 55 + 110
完全数、婚約数、友愛数を単純探索で列挙して遊んでみる。
約数はメモっておいて、婚約数、友愛数を場合は、逆引き用のテーブルを作っておけば、O(n log n)で探索できる。
#include <iostream>
#include <vector>
#include <map>
#define MAX_NUM 100000
using namespace std;
vector<int> divisors[MAX_NUM+1];
map<int, vector<int> > calcTable;
vector<int> getPerfectNumber() {
vector<int>ret;
for (int x = 1; x <= MAX_NUM; x++) {
int y = 0;
for (int i = 0; i < divisors[x].size(); i++)
y += divisors[x][i];
y -= x;
if (x == y)
ret.push_back(x);
}
return ret;
}
vector<pair<int, int> > doit(bool excludeOne) {
map<int, vector<int> > table;
for (int x = 1; x <= MAX_NUM; x++) {
int y = 0;
for (int i = 0; i < divisors[x].size(); i++)
y += divisors[x][i];
y -= (x+excludeOne);
table[y].push_back(x);
}
vector<pair<int, int> >ret;
for (int x = 1; x <= MAX_NUM; x++) {
if (!table.count(x))
continue;
int xs = 0;
for (int i = 0; i < divisors[x].size(); i++)
xs += divisors[x][i];
xs -= (x+excludeOne);
for (int i = 0; i < table[x].size(); i++) {
int y = table[x][i];
if (y == xs && x < y)
ret.push_back(make_pair(x, y));
}
}
return ret;
}
vector<pair<int, int> > getbetrothedNumber() {
return doit(true);
}
vector<pair<int, int> > getAmicableNumber() {
return doit(false);
}
int main() {
// store each number's divisors
for (int i = 1; i <= MAX_NUM; i++) {
for (int j = 1; j*j<=i; j++) {
if (i % j == 0) {
divisors[i].push_back(j);
if (j*j != i)
divisors[i].push_back(i/j);
}
}
}
vector<int>nums;
vector<pair<int, int> >pairs;
// Perfect Numbers
nums = getPerfectNumber();
cout << "Perfect Numbers:" << endl;
for (int i = 0; i < nums.size(); i++)
cout << nums[i] << endl;
cout << endl;
nums.clear();
// Betrothed Numbers
pairs = getbetrothedNumber();
cout << "Betrothed Numbers:" << endl;
for (int i = 0; i < pairs.size(); i++)
cout << pairs[i].first << ", " << pairs[i].second << endl;
cout << endl;
pairs.clear();
// Amicable Numbers
pairs = getAmicableNumber();
cout << "Amicable Numbers:" << endl;
for (int i = 0; i < pairs.size(); i++)
cout << pairs[i].first << ", " << pairs[i].second << endl;
cout << endl;
pairs.clear();
return 0;
}
