完全・婚約・友愛

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

①完全数

ある数字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;
}