완전수와 초과수 (약수의 합 구하기)

완전수와 초과수

어떤 자연수 N의 자기 자신보다 작은 양의 약수들의 합이 자기 자신과 같다면 그 수를 완전수라하고, 만약 약수의 합이 N보다 크다면 초과수라고 한다.

6은 가장 작은 완전수로, 6의 약수는 1, 2, 3, 6이며, 이중 6 자신을 제외한 세 수의 합은 6으로 원래의 값과 일치한다. 12의 약수는 1, 2, 3, 4, 6, 12이고, 12를 제외한 약수의 합은 16으로 12는 초과수이다.

약수의 합을 구하는 방법은 크게 두 가지가 있다.

무식하게 1부터 N까지의 수로 N을 나눠서, 나눠지는 수가 약수이므로 이들을 모두 합산한다.
N을 소인수분해하여, 각 인수의 누적 거듭제곱의 합들을 구하고, 다시 이들의 누적 곱을 구한다. (수학 시간에 약수의 합을 구하는 공식이라고 배웠다.)

컴퓨터를 이용해서 약수의 합을 구할 때는 2의 방법보다 (소인수분해는 컴퓨터에게는 은근히 어려운 작업이다.) 1의 방법이 훨씬 쉽다. 1의 정의를 그대로 코드로 옮기면 다음과 같이 쓸 수 있다.

def s(n):
    s, k = 0, 1
    while k <= n:
        if n % k is 0:
            s += k
        k += 1
    return s

매우 간단하다. 하지만 이 코드는 N 이 조금만 커져도 느려지기 십상이다. 5,000,000의 약수의 합을 구하려면 5백만번의 루프를 돌아야 하기 때문이다.

%time s(5000000)

# Wall time: 752 ms
# 12402312

어떻게하면 시간을 단축할 수 있을까? 만약 N 이 a로 나눠지고 이 때의 몫을 b 라고 하자.

$$N = a \times b$$

이 때, b 역시 N의 약수가 되며, a 로 나눴다면 b 에 대해서는 검사할 필요가 없고 a <= b 인 범위까지만 검사하면 된다. 그리고 a == b 인 상황은 바로 a 가 N의 제곱근이 되는 시점이다. 이를 다시 코드로 옮기면 다음과 같다.

def f(n):
    s, k = 1+n, 2
    while k * k < n:
        if n % k is 0:
            s += k + (n // k)
        k += 1
    if k * k == n:
        s += k
    return s

역시 같은 계산을 수행해보면 놀랄만큼 빨라진 것을 알 수 있다.

%time f(5000000)

# Wall time: 2 ms
# 12402312

완전수

완전수를 찾기 위해서 f()를 다음과 같이 약간 수정하여, N 자신은 합산하지 않도록 한다.

def f(n):
    s, k = 1, 2
    while k * k < n:
        if n % k is 0:
            s += k + (n // k)
        k += 1
    if k * k == n:
        s += k
    return s
    
def is_perfect_number(n):
	return n == f(n)

알려진 첫 네 개의 완전수는 6, 28, 496, 8128로 그리스의 학자들은 이 네 개의 수 보다 더 큰 그 다음의 완전수를 찾지 못했던 것으로 알려졌다. 왜냐하면 완전수는 일정 규모 이하의 범위에서는 매우 드물게 나타나기 때문이다. (다섯번째 완전수는 33,550,336으로 손으로 계산해서 찾아내기에는 엄청 큰 수다. ) 대신에 유클리드는 짝수인 완전수들은 모두 $2^{n-1} \times (2^n - 1)$의 꼴로 존재한다는 것을 밝혔고, 특히 이 때 $2^n -1 $이 소수가 된다는 것도 알았다.

이 때의 $2^n - 1$인 소수를 메르센소수라 부른다. 이는 오일러에 의해서 메르센소수와 모든 짝수 완전수는 1:1 대응한다는 것이 증명되었다. (메르센소수가 무한한지 여부는 아직 밝혀지지 않았고, 따라서 완전수가 무한한지 그렇지 않은지의 문제 역시 밝혀지지 않았다.)

모든 짝수 완전수는 $2^{n-1} \times ( 2^n - 1)$의 꼴이므로 이들은 모두 연속된 자연수의 합이기도 하다.

보너스 : 홀수 완전수

홀수 완전수가 존재하는지 여부는 아직 밝혀지지 않았다. 다만 최근 출간된 논문에 따르면 이는 최소한 1500자리 이상의 수이며, 105로 나누어 떨어지지 않고, 12로 나눈 나머지는 1이 된다는 조건을 만족해야 한다. (그 외의 조건들도 있는데 이는 위키 백과를 참고하자.)

보너스 2 : 초완전수

어떤 자연수 N의 약수의 합을 f(N)이라 할 때, N = 1 + k * (f(N) - 1 - N)을 만족한다면 이를 k-초완전수라 부른다. 즉 1과 자기자신을 제외한 나머지 약수의 합에 k를 곱하고 여기에 다시 1을 더해서 원래의 수가 되는 경우이다. 어떤 수가 완전수인것은 그 수가 1-초완전수인것과 동치이다. 위키 백과에서는 k 값 별로 해당되는 초완전수들을 구해둔 목록을 안내하고 있다.

코딩도장에 최근에 추가된 문제 중 하나가 이 초완전수와 관련된 것으로 특정한 수 N을 입력받을 때, N 보다 작은 모든 k-초완전수들을 출력하는 것이다.

"""자연수 n이 있다. 
f(n)=(n의 양의 약수의 합)이라고고 하자. 
자연수 n이 어떤 k에 대하여 등식 n = 1 + k(f(n)-n-1)을 만족했을 때,
n을 k-초완전수라고 부른다. 

n이 완전수라는 것은 n이 1-초완전수라는 것이라는 명제와 동치이다. 

예를 들어, 21은 2-초완전수이고 301은 6-초완전수이다. 

자연수 N을 입력받고 N 이하의 k-초완전수와 그때의 k를 순서쌍으로 출력하는 프로그램을 작성하라."""

def t(n):
    s, k, l = 0, 2, n**0.5
    while k < l:
        if n % k is 0:
            s += k + (n // k)
        k += 1
    if k * k == n:
        s += k
    return s

def do(n):
    result = []
    if n >= 6:
        for i in range(6, n+1):
            k, j = 1, t(i)
            if j > 0:
                while i > j * k:
                    if j * k + 1 == i:
                        result.append((i, k))
                        break
                    k += 1
    return result

N = 10000
%time print(", ".join(str(x) for x in do(N)))

초과수

진약수 (자기자신보다 작은 약수)의 합이 원래의 수 N보다 크다면, 이 N은 초과수라고 한다. 초과수와 관련하여 재미있는 문제는 오일러 프로젝트의 23번 문제이다.

자신을 제외한 약수(진약수)를 모두 더하면 자기 자신이 되는 수를 완전수라고 합니다.
옐ㄹ 들어 28은 1+2+4+7+14 = 28이므로 완전수입니다. 또, 진약수의 합이 자신보다 작으면 부족수, 자신보다 클 때는 초과수라고 합니다.
12는 1+2+3+4+6 = 16 > 12 로서 초과수 중에서는 가장 작습니다. 따라서 초과수 두 개의 합으로 나타낼 수 있는 가장 작은 수는 24입니다.
해석학적인 방법을 사용하면 28123을 넘는 모든 정수는 두 초과수의 합으로 표현 가능함을 보일 수가 있습니다. 두 초과수의 합으로 나타낼 수 없는 가장 큰 수는 실제로는 이 한계값보다 작지만, 해석학적인 방법으로는 더 이상 한계값을 낮출 수 없다고 합니다.
그렇다면 초과수 두 개의 합으로 나타낼 수 없는 모든 양의 정수의 합은 얼마입니까?

오일러 프로젝트의 문제들이 다 그렇듯이 간단한 문제는 아니다. 이 문제를 푸는 과정을 생각해보자.

두 초과수의 합으로 나타낼 수 없는 현재 알고 있는 가장 큰 수는 28123이다.
따라서 28123보다 작은 모든 초과수의 집합을 구한다.
다시 1~28123 사이의 모든 자연수 중 임의의 자연수 N에 대해서
28123보다 작은 임의의 초과 수 A를 뺀 값 B가 초과수인지를 확인한다. 이 때 B가 앞 서 구한 초과수의 집합에 있는지를 보는 것이, 약수의 합을 재계산하는 것보다 빠르다.
이렇게 N에 대해서 두 초과수의 합으로 표현될 수 있는지를 검사하고, 그렇지 않은 N들을 합산한다.

아래는 이 문제를 계산하는 코드이다. 파이썬으로도 충분히 1초 이내에 답을 낼 수 있는 문제이며, 다음과 같은 테크닉들이 사용됐다.

N 에서 초과수 A를 뺀 값이 초과수인지를 검사하기 위해서는 초과수 여부 함수를 사용하는 것이 아니라, 미리 만들어둔 초과수 집합에 포함되어 있는지 여부만 검사한다.
이 때, 포함 여부를 판단하는 in 연산자는 리스트보다는 집합(set) 타입에서 더 빠르게 계산된다.
N을 테스트할 때는 N 보다 작은 초과수에 대해서만 검사하면 된다. (좀 더 엄밀하게는 N보다 12가 작은 초과수까지) N - A 가 음수가 되면 당연히 초과수가 될 수 없기 때문이다.

"""오일러 프로젝트 23번"""

def isOvernum(n):
    """주어진 수가 초과수인지 검사한다"""
    k, s, l = 2, 0, n**0.5
    while k < l:
        if n % k == 0:
            s += k + (n // k)
        k += 1
    if k * k == n:
        s += k
    return s > n

# 12~28123 범위의 초과수의 집합을 준비한다. 
overnums = set((x for x in range(12, 28123) if isOvernum(x)))
S = set(overnums)

# 주어진 n 이 두 초과수의 합인지를 판단한다. 
def test(n):
    """범위내의 초과수들에 대해서 n에서 초과수를 뺀 값이 다시 초과수인지 검사"""
    for i in overnums:
        if n < i:
            break
        if (n - i) in S:
            return True
    return False

def main():
    result = list(range(1, 24))  # 1~23범위는 두 초과수의 합으로 나타낼 수 없는 값이며,
    for i in range(24, 28123):
        # 테스트를 통과하지 못하는 수를 모두 추려낸다.
        if not test(i):
            result.append(i)
    print(result[-1])  # 덤으로 두 초과수의 합으로 나타낼 수 없는 가장 큰 수도 출력하자. 
    print(sum(result))
    
%time main()
# 20161
# 4179871
# Wall time: 681 ms

이상으로 약수의 합을 통해서, 완전수와 초과수를 이용하는 문제들을 어떻게 접근할 것인지를 살펴보았다. 다음에는 약수나 소수와 관련한 문제의 꽃인 소수 판별과 소인수 분해를 어떻게 할 수 있는지에 대해서 알아보도록 하자.

53Percent

완전수와 초과수 (약수의 합 구하기)