Search on the blog

2011年6月29日水曜日

完全・婚約・友愛

完全数、婚約数、友愛数についておさらい。

①完全数
ある数字nと、nのproper divisors(自分以外の約数)の和が等しいとき、nを完全数(perfect number)と呼ぶ。「博士が愛した数式」という小説にも出てきました。
例えば、6は完全数。6 = 1+2+3。

②婚約数
ある数pとqは、以下の2つの条件をともに満たすとき婚約数(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;
}

0 件のコメント:

コメントを投稿