完全・婚約・友愛

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

①完全数

ある数字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)で探索できる。

view plainprint?

1. #include <iostream>  
2. #include <vector>  
3. #include <map>  
4.   
5. #define MAX_NUM 100000  
6.   
7. using namespace std;  
8.   
9. vector<int> divisors[MAX_NUM+1];  
10. map<int, vector<int> > calcTable;  
11.   
12. vector<int> getPerfectNumber() {  
13.  vector<int>ret;  
14.   
15.  for (int x = 1; x <= MAX_NUM; x++) {  
16.    int y = 0;  
17.   
18.    for (int i = 0; i < divisors[x].size(); i++)  
19.      y += divisors[x][i];  
20.   
21.    y -= x;  
22.    if (x == y)  
23.      ret.push_back(x);  
24.  }  
25.     
26.  return ret;  
27. }  
28.   
29. vector<pair<int, int> > doit(bool excludeOne) {  
30.  map<int, vector<int> > table;  
31.   
32.  for (int x = 1; x <= MAX_NUM; x++) {  
33.    int y = 0;  
34.   
35.    for (int i = 0; i < divisors[x].size(); i++)  
36.      y += divisors[x][i];  
37.   
38.    y -= (x+excludeOne);  
39.    table[y].push_back(x);  
40.  }  
41.   
42.  vector<pair<int, int> >ret;  
43.  for (int x = 1; x <= MAX_NUM; x++) {  
44.    if (!table.count(x))  
45.      continue;  
46.   
47.    int xs = 0;  
48.    for (int i = 0; i < divisors[x].size(); i++)  
49.      xs += divisors[x][i];  
50.   
51.    xs -= (x+excludeOne);  
52.    for (int i = 0; i < table[x].size(); i++) {  
53.      int y = table[x][i];  
54.       
55.      if (y == xs && x < y)  
56.     ret.push_back(make_pair(x, y));  
57.   
58.    }  
59.  }  
60.   
61.  return ret;  
62. }  
63.   
64. vector<pair<int, int> > getbetrothedNumber() {  
65.  return doit(true);  
66. }  
67.   
68. vector<pair<int, int> > getAmicableNumber() {  
69.  return doit(false);  
70. }  
71.   
72. int main() {  
73.  // store each number's divisors  
74.  for (int i = 1; i <= MAX_NUM; i++) {  
75.    for (int j = 1; j*j<=i; j++) {  
76.      if (i % j == 0) {  
77.     divisors[i].push_back(j);  
78.     if (j*j != i)  
79.       divisors[i].push_back(i/j);  
80.      }  
81.    }  
82.  }  
83.   
84.  vector<int>nums;  
85.  vector<pair<int, int> >pairs;  
86.   
87.  // Perfect Numbers  
88.  nums = getPerfectNumber();  
89.  cout << "Perfect Numbers:" << endl;  
90.  for (int i = 0; i < nums.size(); i++)  
91.    cout << nums[i] << endl;  
92.  cout << endl;  
93.  nums.clear();  
94.   
95.  // Betrothed Numbers  
96.  pairs = getbetrothedNumber();  
97.  cout << "Betrothed Numbers:" << endl;  
98.  for (int i = 0; i < pairs.size(); i++)  
99.    cout << pairs[i].first << ", " << pairs[i].second << endl;  
100.  cout << endl;  
101.  pairs.clear();  
102.   
103.  // Amicable Numbers  
104.  pairs = getAmicableNumber();  
105.  cout << "Amicable Numbers:" << endl;  
106.  for (int i = 0; i < pairs.size(); i++)  
107.    cout << pairs[i].first << ", " << pairs[i].second << endl;  
108.  cout << endl;  
109.  pairs.clear();  
110.   
111.  return 0;  
112. }  

#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;
}