완전수(Perfect Number), 부족수(Deficient Number), 과잉수(Abundant Number)

완전수(Perfect Number), 부족수(Deficient Number), 과잉수(Abundant Number)

완전수(Perfect Number)

• 그 수 자신을 제외한 모든 약수의 합이 그 수 자신과 같은 수를 완전수(Perfect Number)라고 한다.
• 예) 6의 약수는 {1, 2, 3, 6} 이고, 그 수 자신을 제외한 1 + 2 + 3의 합은 6과 같으므로 6은 완전수이다.

 

부족수(Deficient Number)

• 그 수 자신을 제외한 모든 약수의 합이 그 수 자신보다 작은 수를 부족수(Deficient Number)라고 한다.
• 예) 8의 약수는 {1, 2, 4, 8} 이고, 그 수 자신을 제외한 1 + 2 + 4의 합은 7과 같으므로 8은 부족수이다.

 

과잉수(Abundant Number)

• 그 수 자신을 제외한 모든 약수의 합이 그 수 자신보다 큰 수를 과잉수(Abundant Number)라고 한다.
• 예) 12의 약수는 {1, 2, 3, 4, 6, 12} 이고, 그 수 자신을 제외한 1 + 2 + 3 + 4 + 6의 합은 12보다 크므로 12는 과잉수이다.

 

완전수의 역사

 고대 그리스 사람들은 숫자 6이 자신을 제외한 약수들의 합 (6 = 1 + 2 + 3)으로 표시됨을 알아차리고 이것이야 말로 완전한 수의 형태라고 생각했다. 아우구스투스(BC63 ~ AD14, Augustus)는 "신이 세상을 6일 동안 창조하신 이유는 6이 완전수이기 때문이다." 라고 말하기도 하였다.

 완전수(Perfect Number)라는 명칭은 피타고라스(BC582 ~ BC497, Pythagoras)를 따르는 피타고라스 학파가 처음으로 사용하였고, 홀수인 완전수는 아직 밝혀지지 않았으며, 완전수가 무한히 존재하는지도 아직 밝혀지지 않았다. 홀수인 완전수가 없다는 것은 증명되지는 않았지만, 지금까지 발견된 정수 중에는 홀수인 완전수는 없다는 것은 확인되었다.

 2000년이 넘도록 수학자들은 오직 11개의 완전수만을 찾아내었고, 1977년에 한 개의 완전수를 더 찾아내었다. 20세기 후반에 들어오면서 컴퓨터의 발달로 새로운 완전수를 찾기 시작하였고, 1952년 캘리포니아 대학의 로빈손이 컴퓨터 SWAC를 이용하여 새로운 완전수를 발견한 이래로, 2018년 12월 이전까지 모두 51개의 완전수가 발견되었다.

 

최초 5개의 완전 수는 다음과 같다.

6, 28, 496, 8128, 33550336

 

메르센 소수(Mersenne Prime)

고대 그리스인들은 다음의 4개의 완전수 밖에는 알지 못했다.

6, 28, 496, 8128

 

유클리드(Euclid of Alexandria)는 이들을 `2^{n-1} · (2^{n}-1)` 에 알맞은 수를 대입해 구할 수 있다는 것을 발견했다.

`n = 2`일 때 : `2^{1} · (2^{2} - 1) = 6`
`n = 3`일 때 : `2^{2} · (2^{3} - 1) = 28`
`n = 5`일 때 : `2^{4} · (2^{5} - 1) = 496`
`n = 7`일 때 : `2^{6} · (2^{7} - 1) = 8128`

 

이때 `n`은 언제나 소수이지만, `n`이 소수라고 `2^{n} - 1`도 꼭 소수가 되지 않는다.

(`2^{n}-1`이 소수일 때는 이를 메르센 소수(Mersenne Prime)라고 부른다. 즉, 메르센 소수는 소수 가운데 `2^{n}-1` 로 표현되는 소수를 의미한다.) 마랭 메르센(1588 ~ 1648, Marin Mersenne)은 17세기에 정수론과 완전수를 연구한 수도승이었다. 

 

짝수 완전수와 메르센 소수 사이에는 일대일 대응이 있다는 것이 밝혀졌다.

`2^{n-1} · (2^{n}-1) = \frac{M_{n}(M_{n}+1)}{2}`

 

모든 짝수 완전수가 `2^{n-1} · (2^{n}-1)` 꼴이므로, 모든 짝수 완전수는 연속된 자연수의 합으로 표현할 수 있다. 그러나 메르센 수가 소수가 아닌 경우에는 해당 숫자는 과잉수가 된다. 그와 동시에 반완전수이기도 하다. (이러한 예로 120, 2016, 32640, 130816 등이 있다.)

 

메르센 소수의 수가 유한한지 무한한지는 알려져 있지 않다. 그러므로 짝수 완전수의 수가 무한한지도 알려져 있지 않다.

 

참고

• https://ko.wikipedia.org/wiki/%EC%99%84%EC%A0%84%EC%88%98

완전수 - 위키백과, 우리 모두의 백과사전

• https://en.wikipedia.org/wiki/List_of_Mersenne_primes_and_perfect_numbers

List of Mersenne primes and perfect numbers - Wikipedia

 

예제 

완전수 판별하기 (28)

#include <iostream>
using namespace std;

int main() {
    int num, sum;
    
    num = 28;
    sum = 0;
    for (int i = 1; i <= num - 1; i++) {
        if (num % i == 0) {
            sum += i;
        }
    }
    
    if (sum == num) {
        cout << "Perfect Number" << endl;
    }
    
    return 0;
}

Perfect Number